Combinatorics Counting Puzzle: tira 20 dadi a 8 facce, qual è la probabilità di ottenere almeno 5 dadi dello stesso valore

Question

Assumi un gioco in cui si tira 20, dado a 8 facce, per un numero totale di 8 ^ 20 possibili esiti. Per calcolare la probabilità che si verifichi un particolare evento, dividiamo il numero di modi in cui l'evento può verificarsi per 8 ^ 20.

Si può calcolare il numero di modi per ottenere esattamente 5 dadi del valore 3. (20 scegliere 5) ci dà il numero di ordini di 3. 7 ^ 15 ci dà il numero di modi in cui non possiamo ottenere il valore 3 per 15 rotoli.

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

La risposta può anche essere vista in quanti modi posso riorganizzare la stringa 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0 (20 scelgono 5) volte il numero totale di valori che abbiamo zero (assumendo 7 valori legali) 7 ^ 15 (è corretto).

• Domanda 1: Come posso calcolare il numero di modi per ottenere esattamente 5 dadi dello stesso valore (Cioè, per tutti i valori dei dadi). Nota: se uso solo ingenuamente la mia prima risposta sopra e moltiplico bt 8, ottengo un'enorme quantità di doppio conteggio?

  Capisco che potrei risolvere per ciascuno dei casi (5 1), (5, 2), (5, 3), ... (5, 8) sommarli (più semplicemente 8 * (5 1) ). Quindi sottrarre la somma del numero di sovrapposizioni (5 1) e (5 2), (5 1) e (5 3) ... (5 1) e (5, 2) e ... e (5, 8) ma questo sembra estremamente disordinato. Vorrei generalizzarlo in un modo che si ingrandisca fino a un gran numero di campioni e un gran numero di classi.

• Come posso calcolare il numero di modi per ottenere almeno 5 dadi dello stesso valore?

  Quindi 111110000000000000000 o 11110100000000000002 o 11111100000001110000 o 11011211222222223333, ma non 00001111222233334444 o 000511512252363347744.

Sto cercando risposte che spieghino la matematica o puntino a una libreria che lo supporta (moduli esp python). Punti extra per dettagli ed esempi.

Answer 1

Il doppio conteggio può essere risolto utilizzando il Inclusion / Exclusion Principle

Sospetto che venga fuori:

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

E così via. Questo non risolve il problema direttamente di "più di 5 dello stesso", come se si sommasse semplicemente i risultati di questo applicato a 5,6,7..20; conteresti i casi in cui hai, diciamo, 10 1 e 5 8.

Probabilmente potresti applicare nuovamente l'esclusione per includere quella seconda risposta; quindi, P (di almeno 5) = P (un set di 20) + ... + (P (un set di 15) - 7 * P (set di 5 da 5 dadi)) + ((P (un set di 14) - 7 * P (un set di 5 da 6) - 7 * P (un set di 6 da 6). Trovarsi con il codice sorgente per questo si sta dimostrando più difficile.

Answer 2

Ti suggerisco di dedicare un po 'di tempo a scrivere una simulazione Monte Carlo e lasciarla correre mentre lavori a mano la matematica. Spero che la simulazione Monte Carlo converrà prima che tu abbia finito con la matematica e sarai in grado di verificare la tua soluzione.

Un'opzione leggermente più veloce potrebbe comportare la creazione di un clone SO per domande di matematica.

Answer 3

L'esatta distribuzione di probabilità Fs, i di una somma di dadi i-sided può essere calcolata come la convoluzione ripetuta della distribuzione di probabilità single-die con se stessa.

dove per tutti e 0 altrimenti.

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

Answer 4

Questo problema è davvero difficile se devi generalizzarlo (ottieni la formula esatta).

Ma comunque, lasciami spiegare l'algoritmo. Se vuoi sapere

  

il numero di modi per ottenere esattamente 5   dadi dello stesso valore

devi riformulare il tuo problema precedente, come

  

calcola il numero di modi per ottenere   esattamente 5 dadi del valore 3 E no   l'altro valore può essere ripetuto esattamente 5   volte

Per semplicità, chiamiamo la funzione F (20,8,5) (5 dadi, tutti i valori) la prima risposta, e F (20,8,5,3) (5 dadi, valore 3) la seconda. Abbiamo che F (20,8,5) = F (20,8,5,3) * 8 + (eventi in cui più di un valore viene ripetuto 5 volte)

Quindi se possiamo ottenere F (20,8,5,3) dovrebbe essere piuttosto semplice, vero? Beh ... non così tanto ...

Innanzitutto, definiamo alcune variabili: X1, X2, X3 ..., Xi, dove Xi = numero di volte in cui otteniamo i dadi i

Quindi:

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 (istruzione) è il modo standard per scrivere una probabilità.

continuiamo:

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

ricorsivamente:

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

Bene, allora ... F (5,5,5,4) è il numero di modi per ottenere 5 dadi di valore 4 in 5 tiri, come nessun altra ripetizione di dadi 5 volte. C'è solo 1 via, su un totale di 5 ^ 5. La probabilità è quindi 1/5 ^ 5.

F (5,5,5) è il numero di modi per ottenere 5 dadi di qualsiasi valore (su 5 valori) in 5 tiri. È ovviamente 5. La probabilità è quindi 5/5 ^ 5 = 1/5 ^ 4.

F (10,6,5,2) è il numero di modi per ottenere 5 dadi di valore 2 in 10 tiri, come nessun altro dado ripetuto 5 volte. F (10,6,5,2) = (1-F (5,5,5) / 5 ^ 5) * 6 ^ 10 = (1-1 / 5 ^ 4) * 6 ^ 10

Beh ... penso che potrebbe non essere corretto da qualche parte, ma comunque, hai capito. Spero di poter rendere comprensibile l'algoritmo.

modifica Ho fatto alcuni controlli e mi sono reso conto che devi aggiungere alcuni casi quando ricevi più di un valore ripetuto esattamente 5 volte. Non hai tempo per risolvere quella parte tu ...

Answer 5

Ecco cosa sto pensando ...

Se avessi solo 5 dadi, avresti solo otto modi per ottenere ciò che desideri.

Per ognuna di queste otto modalità, funzionano tutte le possibili combinazioni degli altri 15 dadi.

Quindi - penso che la risposta sia: (8 * 8 15) / 8 20

(La risposta per almeno 5 uguali.)

Answer 6

Credo che tu possa usare la formula di x occorrenze in n eventi come:

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

Quindi il risultato finale sarà la somma dei risultati da 0 a n.

Non vedo davvero alcun modo semplice per combinarlo in un solo passaggio che sarebbe meno disordinato. In questo modo hai anche la formula indicata nel codice. Tuttavia, potresti dover scrivere il tuo metodo fattoriale.

  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

Soluzione ricorsiva:

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