Combinatorics Counting Puzzle: Roll 20, 8-seitig-Würfel, Wie groß ist die Wahrscheinlichkeit, mindestens 5 Würfel mit demselben Wert zu erhalten
https://stackoverflow.com/questions/1202343
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Nehmen wir ein Spiel an, bei dem man 20, 8-seitig stirbt, für eine Gesamtzahl von 8^20 möglichen Ergebnissen. Um die Wahrscheinlichkeit eines bestimmten Ereignisses zu berechnen, teilen wir die Anzahl der Möglichkeiten, wie das Ereignis um 8^20 auftreten kann.
Man kann die Anzahl der Möglichkeiten berechnen, um genau 5 Würfel des Wertes 3 zu erhalten. (20 Wählen Sie 5) gibt uns die Anzahl der Bestellungen von 3. 7^15 Liefert uns die Anzahl der Möglichkeiten, den Wert 3 für 15 Rollen nicht zu erhalten können .
number of ways to get exactly 5, 3's = (20 choose 5)*7^15.
Die Antwort kann auch als wie viele Möglichkeiten angesehen werden, wie ich die Zeichenfolge 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 neu anordnen kann , 0,0 (20 Wählen Sie 5).
Frage 1: Wie kann ich die Anzahl der Möglichkeiten berechnen, um genau 5 Würfel mit demselben Wert zu erhalten (dh für alle Würfelwerte). HINWEIS: Wenn ich nur naiv meine erste Antwort oben benutze und BT 8 multipliziere, bekomme ich eine enorme Menge an Doppelzählungen?
Ich verstehe, dass ich für jeden der Fälle (5 1), (5, 2), (5, 3), ... (5, 8) sie summieren kann (einfacher 8*(5 1)). Subtrahieren Sie dann die Summe der Anzahl der Überlappungen (5 1) und (5 2), (5 1) und (5 3) ... (5 1) und (5, 2) und ... und (5, 8) Aber das scheint außerordentlich chaotisch. Ich würde eine Verallgemeinerung davon auf eine Weise, die bis zu einer großen Anzahl von Proben und einer großen Anzahl von Klassen skaliert.
Wie kann ich die Anzahl der Möglichkeiten berechnen, um zu bekommen? wenigstens 5 Würfel des gleichen Wertes?
SO 111110000000000000000 oder 111101000000000002 oder 111111100000110000 OR 1101121222222223333, jedoch nicht 0000001111222222233334444 oder 000511512523333477744.
Ich suche nach Antworten, die entweder die Mathematik erklären oder auf eine Bibliothek hinweisen, die dies unterstützt (insbesondere Python -Module). Zusätzliche Punkte für Details und Beispiele.
Lösung
Die Doppelzählung kann durch Verwendung der gelöst werden Einschluss-/Ausschlussprinzip
Ich vermute, es kommt zu:
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
Usw. Dies löst das Problem nicht direkt von "Mehr als 5 davon", als ob Sie einfach die Ergebnisse davon auf 5,6,7..20 zusammenfassen. Sie würden die Fälle zählen, in denen Sie beispielsweise 10 1 und 5 8 haben.
Sie könnten wahrscheinlich wieder Einschlussausschluss anwenden, um diese zweite Antwort zu finden. Also p (von mindestens 5) = P (ein Satz von 20) + ... + (p (ein Satz von 15) - 7*P (Set von 5 von 5 Würfel)) + ((P (ein Satz) von 14) - 7*P (ein Satz von 5 von 6) - 7*P (ein Satz von 6 von 6)). Der Quellcode dafür ist schwieriger.
Andere Tipps
Ich schlage vor, dass Sie ein wenig Zeit damit verbringen, eine Monte -Carlo -Simulation aufzuschreiben und sie laufen zu lassen, während Sie die Mathematik von Hand ausarbeiten. Hoffentlich wird die Monte -Carlo -Simulation konvergieren, bevor Sie mit der Mathematik fertig sind und Sie Ihre Lösung überprüfen können.
Eine etwas schnellere Option beinhaltet möglicherweise das Erstellen eines SO -Klons für mathematische Fragen.
Die genaue Wahrscheinlichkeitsverteilung fs, i einer Summe von I-Side-Würfeln kann als wiederholte Faltung der Single-Stie-Wahrscheinlichkeitsverteilung mit sich selbst berechnet werden.
wo 
für alle 
und 0 sonst.
Dieses Problem ist wirklich schwierig, wenn Sie es verallgemeinern müssen (die genaue Formel erhalten).
Aber trotzdem lassen Sie mich den Algorithmus erklären. Wenn du wissen willst
Die Anzahl der Möglichkeiten, genau 5 Würfel des gleichen Wertes zu erhalten
Sie müssen Ihr vorheriges Problem umformulieren als
Berechnen Sie die Anzahl der Möglichkeiten, um genau 5 Würfel des Wertes 3 zu erhalten, und kein anderer Wert kann genau das 5 -fache genau wiederholt werden
Um die erste Antwort und F (20,8,5,3) (5 Würfel, Wert 3) die zweite aufzurufen, um die Funktion F (20,8,5) (5 Würfel, alle Werte) aufzurufen. Wir haben das f (20,8,5) = f (20,8,5,3) * 8 + (Ereignisse, wenn mehr als ein Wert 5 -mal wiederholt wird)
Wenn wir also F (20,8,5,3) bekommen können, sollte es ziemlich einfach sein, nicht wahr? Nun ... nicht so sehr ...
Lassen Sie uns zunächst einige Variablen definieren:X1, x2, x3 ..., xi, wobei xi = Anzahl der Würfel erhält
Dann:
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 (Aussage) ist die Standardmethode, um eine Wahrscheinlichkeit zu schreiben.
wir machen weiter:
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
rekursiv:
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
Nun, dann ... f (5,5,5,4) ist die Anzahl der Möglichkeiten, 5 Wert von Wert 4 in 5 Rollen zu erhalten, wie z. B. keine anderen Würfel wiederholt 5 Mal. Es gibt nur einen Weg, von insgesamt 5^5. Die Wahrscheinlichkeit beträgt dann 1/5^5.
F (5,5,5) ist die Anzahl der Möglichkeiten, 5 ZiNEN von Wert (von 5 Werten) in 5 Rollen zu erhalten. Es ist offensichtlich 5. Die Wahrscheinlichkeit ist dann 5/5^5 = 1/5^4.
F (10,6,5,2) ist die Anzahl der Möglichkeiten, 5 Ziehen von Wert 2 von 10 Rollen zu erhalten, wie z. B. keine anderen Würfel wiederholt 5 Mal. F (10,6,5,2) = (1-F (5,5,5)/5^5) * 6^10 = (1-1/5^4) * 6^10
Nun ... ich denke, es mag bei einem Teil falsch sein, aber trotzdem bekommst du die Idee. Ich hoffe, ich könnte den Algorithmus verständlich machen.
bearbeiten:Ich habe einige Überprüfungen durchgeführt, und ich wurde festgestellt, dass Sie einige Fälle hinzufügen müssen, wenn Sie mehr als einen Wert erhalten, der genau das 5 -fache wiederholt wurde. Ich habe keine Zeit, diesen Teil zu lösen, du ...
Hier ist was ich denke ...
Wenn Sie gerade 5 Würfel hätten, hätten Sie nur acht Möglichkeiten, um das zu bekommen, was Sie wollen.
Für jeden dieser acht Arten sind alle möglichen Kombinationen der anderen 15 Würfelarbeit.
Also - ich denke die Antwort lautet: (8 * 815) / 820
(Die Antwort für mindestens 5 gleich.)
Ich glaube, Sie können die Formel von X -Vorkommen in N -Ereignissen verwenden wie:
P = Wahrscheinlichkeit^n * (n!/((N - x)! X!))
Das Endergebnis wird also die Summe der Ergebnisse von 0 bis n sein.
Ich sehe keine einfache Möglichkeit, es zu einem Schritt zu kombinieren, der weniger chaotisch wäre. Mit dieser Weise haben Sie auch die Formel im Code geschrieben. Möglicherweise müssen Sie jedoch Ihre eigene faktorielle Methode schreiben.
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) );
}
}
Rekursive Lösung:
Prob_same_value(n) = Prob_same_value(n-1) * (1 - Prob_noone_rolling_that_value(N-(n-1)))
