Wie oft musst du voraussichtlich würfeln, bis jede Seite dreimal aufgetaucht ist?
Diese Frage wurde in der neuseeländischen Grundschule gestellt und mithilfe von Simulationen gelöst. Was ist die analytische Lösung für dieses Problem?
Wie oft musst du voraussichtlich würfeln, bis jede Seite dreimal aufgetaucht ist?
Diese Frage wurde in der neuseeländischen Grundschule gestellt und mithilfe von Simulationen gelöst. Was ist die analytische Lösung für dieses Problem?
Antworten:
Angenommen, alle Seiten haben gleiche Chancen. Lassen Sie uns verallgemeinern und finden die erwartete Anzahl von Rollen benötigt , bis Seite erschienen ist mal, Seite erschienen mal, ... und Seite erschienen mal. Da die Identität der Seiten keine Rolle spielt (sie haben alle die gleichen Chancen), kann die Beschreibung dieses Ziels zusammengefasst werden: Nehmen wir an, dass Seiten überhaupt nicht erscheinen müssen, Seiten müssen nur einmal erscheinen , ... und der Seiten müssen mal vorkommen. Lassen1 n 1 2 n 2 d n d i 0 i 1 i n n = max ( n 1 , n 2 , … , n d ) i = ( i 0 , i 1 , … , i n )d=6 1 n1 2 n2 d nd i0 i1 in n = max ( n1, n2, … , Nd)
Eine einfache Wiederholung ist verfügbar. An der nächsten Rolle, die Seite , die entspricht einer der erscheint : das heißt, entweder brauchten wir nicht , es zu sehen, oder wir brauchten es einmal zu sehen, ... oder was wir brauchten, um zu sehen mehrmals . ist die Häufigkeit, mit der wir es gesehen haben. n jichj n j
Wenn , mussten wir es nicht sehen und nichts ändert sich. Dies geschieht mit der Wahrscheinlichkeit .i 0 / dj = 0 ich0/ d
Bei wir diese Seite sehen. Jetzt gibt es eine Seite weniger, die mal gesehen werden muss, und eine weitere Seite, die mal gesehen werden muss. Somit wird zu und wird . Lassen Sie diese Operation für die Komponenten von als , so dassj j - 1 i j i j - 1 i j - 1 i j + 1 i i ⋅ jj > 0 j j - 1 ichj ichj- 1 ichj - 1 ichj+ 1 ich ich ⋅j
Dies geschieht mit der Wahrscheinlichkeit .ichj/ d
Wir müssen nur diesen Würfelwurf zählen und rekursiv angeben, wie viele weitere Würfel zu erwarten sind. Durch die Gesetze der Erwartung und der Gesamtwahrscheinlichkeit,
(Lassen Sie uns verstehen, dass der entsprechende Term in der Summe Null ist , wenn ist.)ichj= 0
Wenn , sind wir fertig und . Andernfalls können wir nach auflösen und die gewünschte rekursive Formel angebene ( i ) = 0 e ( i )ich0= d e ( i ) = 0 e ( i )
Beachten Sie, dass ist die Gesamtzahl der Ereignisse, die wir sehen möchten. Die Operation reduziert diese Menge für jedes um eins, vorausgesetzt, , was immer der Fall ist. Daher endet diese Rekursion in einer Tiefe von genau(gleich in der Frage). Darüber hinaus ist (wie nicht schwer zu überprüfen ist) die Anzahl der Möglichkeiten bei jeder Rekursionstiefe in dieser Frage gering (niemals größer als ). Folglich ist dies eine effiziente Methode, zumindest wenn die kombinatorischen Möglichkeiten nicht zu zahlreich sind und wir die Zwischenergebnisse auswendig lernen (so dass kein Wert von vorliegt)⋅ j j > 0 i j > 0 | ich | 3 ( 6 ) = 18 8 e
Ich berechne, dass
Das kam mir schrecklich klein vor, also habe ich eine Simulation (mit32,669 0,027
R
) durchgeführt. Nach über drei Millionen Würfeln war dieses Spiel mehr als 100.000 Mal zu Ende gespielt worden, mit einer durchschnittlichen Länge von . Der Standardfehler dieser Schätzung beträgt : Die Differenz zwischen diesem Mittelwert und dem theoretischen Wert ist unbedeutend, was die Genauigkeit des theoretischen Werts bestätigt.0,027Die Längenverteilung kann von Interesse sein. (Offensichtlich muss es bei beginnen , die minimale Anzahl von Rollen, die benötigt wird, um alle sechs Seiten dreimal zu sammeln.)18
Implementierung
Die rekursive Berechnung von ist zwar einfach, birgt jedoch in einigen Computerumgebungen einige Herausforderungen. Das Wichtigste unter diesen ist das Speichern der Werte von während sie berechnet werden. Dies ist wichtig, da ansonsten jeder Wert (redundant) sehr oft berechnet wird. Der Speicherplatz, der möglicherweise für ein von indiziertes Array benötigt wird, kann jedoch enorm sein. Im Idealfall sollten nur Werte von gespeichert werden, die während der Berechnung tatsächlich auftreten. Dies erfordert eine Art assoziatives Array.e e ( i ) ich ich
Zur Veranschaulichung hier istich ich ⋅j
R
Arbeitscode. Die Kommentare beschreiben die Erstellung einer einfachen "AA" -Klasse (Assoziatives Array) zum Speichern von Zwischenergebnissen. Vektoren werden in Zeichenfolgen konvertiert und diese werden zum Indizieren in eine Liste verwendet , die alle Werte enthält. Die Operation wird implementiert als .E
%.%
Durch diese Vorkehrungen kann die rekursive Funktion ziemlich einfach in einer Weise definiert werden, die der mathematischen Notation entspricht. Insbesondere die Leitunge
ist direkt vergleichbar mit der obigen Formel . Beachten Sie, dass alle Indizes um erhöht wurden, da die Indizierung der Arrays bei und nicht bei beginnt .( 1 ) 1 1 0
R
Das Timing zeigt, dass die Berechnung Sekunden dauert . sein Wert ist0,01
e(c(0,0,0,6))
Kumulierte Gleitkomma- Rundungsfehler hat , die letzten beiden Ziffern zerstört (was sein sollte ,
68
statt06
).Schließlich ist hier die ursprüngliche Mathematica- Implementierung, die die genaue Antwort ergab. Das Auswendiglernen erfolgt über den
e[i_] := e[i] = ...
Ausdruck " idiomatisch" , wodurch fast alleR
vorbereitenden Schritte entfallen . Intern tun die beiden Programme jedoch dasselbe.quelle
Die ursprüngliche Version dieser Frage begann mit der Frage:
Natürlich ist das eine Frage, auf die @JuhoKokkala keine Antwort hat: Die Antwort ist eine Zufallsvariable mit einer Verteilung, die gefunden werden muss. Die Frage wurde dann geändert, um zu fragen: "Was ist die erwartete Anzahl von Rollen." Die folgende Antwort versucht, die ursprüngliche Frage zu beantworten: Wie kann man die Verteilung der Anzahl der Rollen ermitteln , ohne Simulation und nur mit konzeptionell einfachen Techniken, die jeder neuseeländische Student mit einem Computer implementieren könnte ? Warum nicht? Das Problem reduziert sich auf einen 1-Liner.→
Verteilung der Anzahl der benötigten Rollen ... so, dass jede Seite dreimal erscheint
Wir würfeln Mal. Es sei die mit der die Seite des Würfels erscheint, wobei . Dann wird die gemeinsame PMF von ist das heißt :n Xich ich i ∈ { 1 , … , 6 } ( X1, X2, … , X6) Multinomial ( n , 16)
Es sei:Dann ist der cdf von :N= min { n :Xich≥ 3∀ich} . N P( N≤ n )=P( X∀ich≥ 3∣∣n )
dh um das cdf , berechnen Sie einfach für jeden Wert von :P( N≤ n ) n = { 18 , 19 , 20 , … }
Hier ist zum Beispiel Mathematica- Code, der dies tut, da von 18 auf 60 ansteigt. Es ist im Grunde genommen ein Einzeiler:n
... was die exakte cdf ergibt, wenn zunimmt:n
Hier ist eine Darstellung des cdf als Funktion von :P( N≤ n ) n
Um die pmf abzuleiten , differenzieren Sie zunächst die cdf:P( N=n )
Natürlich hat die Verteilung keine Obergrenze, aber wir können hier so viele Werte auflösen, wie praktisch erforderlich. Die Vorgehensweise ist allgemein und sollte für jede gewünschte Kombination von Seiten geeignet sein.
quelle