Rompecabezas de conteo combinatorio: tira 20 dados de 8 lados, ¿cuál es la probabilidad de obtener al menos 5 dados del mismo valor?

Question

Supongamos un juego en el que uno tira 20, dados de 8 lados, para un total de 8 ^ 20 resultados posibles. Para calcular la probabilidad de que ocurra un evento en particular, dividimos el número de formas en que ese evento puede ocurrir por 8 ^ 20.

Uno puede calcular el número de formas de obtener exactamente 5 dados del valor 3. (20 elige 5) nos da el número de órdenes de 3. 7 ^ 15 nos da el número de formas en que no podemos obtener el valor 3 por 15 rollos.

number of ways to get exactly 5, 3's = (20 choose 5)*7^15.

La respuesta también se puede ver de cuántas maneras puedo reorganizar la cadena 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0. 0,0,0,0 (20 elija 5) multiplicado por el número total de valores que el cero (asumiendo 7 valores legales) 7 ^ 15 (es correcto).

• Pregunta 1: ¿Cómo puedo calcular la cantidad de maneras de obtener exactamente 5 dados del mismo valor (es decir, para todos los valores de los dados)? Nota: si solo uso ingenuamente mi primera respuesta de arriba y multiplico bt 8, ¿obtengo una cantidad enorme de conteo doble?

  Entiendo que podría resolver para cada uno de los casos (5 1's), (5, 2's), (5, 3's), ... (5's, 8) sumarlos (más simplemente 8 * (5 1's) ). Luego reste la suma del número de superposiciones (5 1's) y (5 2's), (5 1's) y (5 3's) ... (5 1's) y (5, 2's) y ... y (5, 8's) pero esto parece extremadamente desordenado. Me gustaría una generalización de esto de una manera que se amplía a un gran número de muestras y un gran número de clases.

• ¿Cómo puedo calcular la cantidad de formas de obtener al menos 5 dados del mismo valor?

  Por lo tanto, 111110000000000000000 o 11110100000000000002 o 11111100000001110000 o 11011211222222223333, pero no 00001111222233334444 o 000511512252363347744.

Estoy buscando respuestas que expliquen las matemáticas o que apunten a una biblioteca que admita esto (especialmente los módulos de Python). Puntos extra para detalles y ejemplos.

Answer 1

El doble conteo se puede resolver mediante el uso del Principio de inclusión / exclusión

Sospecho que se trata de:

Choose(8,1)*P(one set of 5 Xs) 
- Choose(8,2)*P(a set of 5 Xs and a set of 5 Ys) 
+ Choose(8,3)*P(5 Xs, 5 Ys, 5 Zs) 
- Choose(8,4)*P(5 Xs, 5 Ys, 5 Zs, 5 As)

P(set of 5 Xs) = 20 Choose 5 * 7^15 / 8^20
P(5 Xs, 5 Ys) = 20 Choose 5,5 * 6^10 / 8^20

Y así sucesivamente. Esto no resuelve el problema directamente de 'más de 5 de lo mismo', como si simplemente sumara los resultados de esto aplicado a 5,6,7..20; contaría en exceso los casos en los que tiene, por ejemplo, 10 1 y 5 8.

Probablemente podría aplicar la exclusión de inclusión nuevamente para obtener la segunda respuesta; entonces, P (de al menos 5) = P (un conjunto de 20) + ... + (P (un conjunto de 15) - 7 * P (conjunto de 5 a 5 dados)) + ((P (un conjunto de 14) - 7 * P (un conjunto de 5 de 6) - 7 * P (un conjunto de 6 de 6)). Encontrar el código fuente es más difícil.

Answer 2

Te sugiero que pases un poco de tiempo escribiendo una simulación de Monte Carlo y la dejes correr mientras trabajas las matemáticas a mano. Esperamos que la simulación de Monte Carlo converja antes de que termines con los cálculos y puedas comprobar tu solución.

Una opción un poco más rápida podría implicar la creación de un clon SO para las preguntas de matemáticas.

Answer 3

La distribución de probabilidad exacta Fs, i de una suma de i dados de lado s se puede calcular como la convolución repetida de la distribución de probabilidad de un solo dado consigo misma.

donde ??para todos y 0 en caso contrario.

http://en.wikipedia.org/wiki/Dice

Answer 4

Este problema es realmente difícil si tiene que generalizarlo (obtenga la fórmula exacta).

Pero de todos modos, déjame explicarte el algoritmo. Si quieres saber

  

la cantidad de formas de obtener exactamente 5   dados del mismo valor

debe reformular su problema anterior, como

  

calcular la cantidad de formas de obtener   exactamente 5 dados del valor 3 Y no   otro valor se puede repetir exactamente 5   tiempos

Para simplificar, llamemos a la función F (20,8,5) (5 dados, todos los valores) la primera respuesta, y F (20,8,5,3) (5 dados, valor 3) la segunda. Tenemos que F (20,8,5) = F (20,8,5,3) * 8 + (eventos cuando más de un valor se repite 5 veces)

Entonces, si podemos obtener F (20,8,5,3) debería ser bastante simple, ¿no? Bueno ... no tanto ...

Primero, definamos algunas variables: X1, X2, X3 ..., Xi, donde Xi = número de veces que obtenemos los dados i

Entonces:

F(20,8,5)/20^8 = P(X1=5 or X2=5 or ... or X8=5, with R=20(rolls) and N=8(dice number))

, P (declaración) es la forma estándar de escribir una probabilidad.

continuamos:

F(20,8,5,3)/20^8 = P(X3=5 and X1<>5 and ... and X8<>5, R=20, N=8) 
F(20,8,5,3)/20^8 = 1 - P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7)  
F(20,8,5,3)/20^8 = 1 - F(15,7,5)/7^15

recursivamente:

F(15,8,5) = F(15,7,5,1) * 7  
P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7) = P(X1=5 and X2<>5 and X4<>5 and .. and X8<>5. R=15, N=7) * 7

---

F(15,7,5,1)/7^15 = 1 - F(10,6,5)/6^10 F(10,6,5) = F(10,6,5,2) * 6

---

F(10,6,5,2)/6^10 = 1 - F(5,5,5)/5^5
F(5,5,5) = F(5,5,5,4) * 5

Bueno, entonces ... F (5,5,5,4) es el número de formas de obtener 5 dados de valor 4 en 5 tiradas, como ningún otro dado que se repita 5 veces. Solo hay 1 manera, de un total de 5 ^ 5. La probabilidad es entonces 1/5 ^ 5.

F (5,5,5) es el número de formas de obtener 5 dados de cualquier valor (de 5 valores) en 5 rollos. Obviamente es 5. La probabilidad es entonces 5/5 ^ 5 = 1/5 ^ 4.

F (10,6,5,2) es el número de formas de obtener 5 dados de valor 2 en 10 tiradas, como por ejemplo, ningún otro dado se repite 5 veces. F (10,6,5,2) = (1-F (5,5,5) / 5 ^ 5) * 6 ^ 10 = (1-1 / 5 ^ 4) * 6 ^ 10

Bueno ... creo que puede ser incorrecto en alguna parte, pero de todos modos, entiendes la idea. Espero poder hacer que el algoritmo sea comprensible.

editar: Hice algunas verificaciones y me di cuenta de que debe agregar algunos casos cuando obtiene más de un valor repetido exactamente 5 veces. No tienes tiempo para resolver esa parte tú ...

Answer 5

Esto es lo que estoy pensando ...

Si solo tuvieras 5 dados, solo tendrías ocho formas de obtener lo que quieres.

Para cada una de esas ocho formas, todas las combinaciones posibles de los otros 15 dados funcionan.

Entonces, creo que la respuesta es: (8 * 8 15) / 8 20

(La respuesta para al menos 5 lo mismo.)

Answer 6

Creo que puede usar la fórmula de x ocurrencias en n eventos como:

P = probabilidad ^ n * (n! / ((n - x)! x!))

Entonces, el resultado final será la suma de los resultados de 0 a n.

Realmente no veo ninguna manera fácil de combinarlo en un solo paso que sería menos complicado. De esta manera, también tiene la fórmula enunciada en el código. Sin embargo, es posible que deba escribir su propio método factorial.

  float calculateProbability(int tosses, int atLeastNumber) {
    float atLeastProbability = 0;
    float eventProbability = Math.pow( 1.0/8.0, tosses);
    int nFactorial = factorial(tosses);

    for ( i = 1; i <= atLeastNumber; i++) {
      atLeastProbability += eventProbability * (nFactorial / (factorial(tosses - i) * factorial(i) );
    }
  }

Answer 7

Solución recursiva:

Prob_same_value(n) = Prob_same_value(n-1) * (1 - Prob_noone_rolling_that_value(N-(n-1)))