Combinatorics Counting Puzzle: Lancez 20 dés à 8 faces, quelle est la probabilité d'obtenir au moins 5 dés de même valeur

Question

Supposons un jeu dans lequel on lance 20 dés à 8 faces, pour un nombre total de 8 ^ 20 résultats possibles. Pour calculer la probabilité qu'un événement particulier se produise, nous divisons le nombre de façons dont cet événement peut survenir par 8 ^ 20.

On peut calculer le nombre de façons d'obtenir exactement 5 dés de la valeur 3. (20 choisissez 5) nous donne le nombre de commandes de 3. 7 ^ 15 nous donne le nombre de façons dont nous ne pouvons pas obtenir la valeur 3 pour 15 rouleaux.

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

La réponse peut également être vue comme combien de façons puis-je réorganiser la chaîne 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0 (20 choisissez 5) fois le nombre total de valeurs égales à zéro (en supposant 7 valeurs légales) 7 ^ 15 (est-ce exact).

• Question 1: Comment puis-je calculer le nombre de façons d'obtenir exactement 5 dés de même valeur (c'est-à-dire pour toutes les valeurs de dés). Remarque: si je me sers naïvement de ma première réponse ci-dessus et que je multiplie par 8, je reçois une énorme quantité de doubles comptes?

  Je comprends que je pourrais résoudre pour chacun des cas (5 1), (5, 2), (5, 3), ... (5, 8) les additionner (plus simplement 8 * (5 1) ). Ensuite, soustrayez la somme du nombre de chevauchements (5 1) et (5 2), (5 1) et (5 3) ... (5 1) et (5 2) et ... et (5, 8) mais cela semble extrêmement compliqué. Je voudrais une généralisation de ceci d’une manière qui permette de passer à un grand nombre d’échantillons et à un grand nombre de classes.

• Comment puis-je calculer le nombre de façons d'obtenir au moins 5 dés de même valeur?

  Donc 111110000000000000000 ou 11110100000000000002 ou 11111100000001110000 ou 11011211222222223333, mais pas 00001111222233334444 ou 000511512252363347744.

Je cherche des réponses qui expliquent le calcul ou pointent vers une bibliothèque qui le supporte (modules python en particulier). Points supplémentaires pour les détails et les exemples.

Answer 1

Le double comptage peut être résolu en utilisant le Principe d'inclusion / exclusion

Je pense que cela vient à:

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

Et ainsi de suite. Cela ne résout pas directement le problème de «plus de 5% de la même chose», comme si vous résumiez simplement les résultats obtenus avec 5,6,7..20; vous compteriez plus les cas où vous avez, par exemple, 10 1 et 5 8.

Vous pourriez probablement appliquer à nouveau l'exclusion de l'inclusion pour trouver cette deuxième réponse. Donc, P (d'au moins 5) = P (un ensemble de 20) + ... + (P (un ensemble de 15) - 7 * P (ensemble de 5 à partir de 5 dés)) + ((P (un ensemble de 14) - 7 * P (un jeu de 5 à 6) - 7 * P (un jeu de 6 à 6)). Trouver le code source qui s’avère plus difficile

Answer 2

Je vous suggère de passer un peu de temps à rédiger une simulation de Monte Carlo et à la laisser s'exécuter pendant que vous calculez les calculs à la main. Espérons que la simulation de Monte Carlo convergera avant la fin du calcul et que vous pourrez vérifier votre solution.

Une option légèrement plus rapide pourrait impliquer la création d'un clone SO pour les questions mathématiques.

Answer 3

La distribution de probabilité exacte Fs, i d’une somme de dés de type s peut être calculée comme la convolution répétée de la distribution de probabilité à un seul sort avec elle-même.

où pour tous et 0 sinon.

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

Answer 4

Ce problème est vraiment difficile si vous devez le généraliser (obtenir la formule exacte).

Mais enfin, laissez-moi vous expliquer l’algorithme. Si vous voulez savoir

  

le nombre de façons d'obtenir exactement 5   dés de même valeur

vous devez reformuler votre problème précédent, comme

  

calculer le nombre de façons d'obtenir   exactement 5 dés de la valeur 3 ET non   autre valeur peut être répétée exactement 5   fois

Par souci de simplicité, appelons la fonction F (20,8,5) (5 dés, toutes les valeurs) la première réponse et F (20,8,5,3) (5 dés, valeur 3) le second. Nous avons que F (20,8,5) = F (20,8,5,3) * 8 + (événements lorsque plusieurs valeurs sont répétées 5 fois)

Donc, si nous pouvons obtenir F (20,8,5,3), cela devrait être assez simple, n'est-ce pas? Eh bien ... pas tellement ...

Premièrement, définissons quelques variables: X1, X2, X3 ..., Xi, où Xi = nombre de fois où nous obtenons le dé i

Ensuite:

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 (instruction) étant le moyen standard pour écrire une probabilité.

nous continuons:

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

récursivement:

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

Eh bien, alors ... F (5,5,5,4) est le nombre de façons d’obtenir 5 dés de valeur 4 en 5, comme aucun autre dés ne se répète 5 fois. Il n'y a qu'un moyen, sur un total de 5 ^ 5. La probabilité est alors de 1/5 ^ 5.

F (5,5,5) est le nombre de façons d’obtenir 5 dés de n'importe quelle valeur (sur 5 valeurs) sur 5 lancers. C'est évidemment 5. La probabilité est alors 5/5 ^ 5 = 1/5 ^ 4.

F (10,6,5,2) est le nombre de façons d’obtenir 5 dés de valeur 2 rouleaux sur 10, par exemple aucun autre dés ne se répète 5 fois. F (10,6,5,2) = (1-F (5,5,5) / 5 ^ 5) * 6 ^ 10 = (1-1 / 5 ^ 4) * 6 ^ 10

Eh bien ... Je pense que cela peut être incorrect à un moment donné, mais de toute façon, vous voyez l'idée. J'espère pouvoir rendre l'algorithme compréhensible.

modifier: J'ai fait quelques vérifications et je me suis rendu compte que vous deviez ajouter des cas où vous obtenez plus d'une valeur répétée exactement 5 fois. Ne pas avoir le temps de résoudre cette partie tu ...

Answer 5

Voici ce que je pense ...

Si vous ne disposiez que de 5 dés, vous n’auriez que huit façons d’obtenir ce que vous voulez.

Pour chacune de ces huit manières, toutes les combinaisons possibles des 15 autres dés fonctionnent.

Donc, je pense que la réponse est: (8 * 8 15) / 8 20

(La réponse pour au moins 5 identiques.)

Answer 6

Je pense que vous pouvez utiliser la formule de x occurrences dans n événements comme:

P = probabilité ^ n * (n! / ((n - x)! x!))

Le résultat final sera donc la somme des résultats de 0 à n.

Je ne vois pas vraiment de moyen facile de le combiner en une seule étape qui serait moins compliquée. De cette façon, vous avez également la formule énoncée dans le code. Cependant, vous devrez peut-être écrire votre propre méthode factorielle.

  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

Solution récursive:

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