Wirf einen 6-seitigen Würfel, bis die Summe

11

Hier ist die Frage:

Sie würfeln iterativ einen fairen 6-seitigen Würfel, bis die Summe der Würfelwürfe größer oder gleich M ist. Was ist der Mittelwert und die Standardabweichung der Summe minus M, wenn M = 300?

Sollte ich einen Code schreiben, um diese Art von Fragen zu beantworten?

Bitte geben Sie mir einige Hinweise dazu. Vielen Dank!

eli
quelle
1
Bitte füge das [self-study]Tag hinzu und lies das Wiki . Dann sagen Sie uns, was Sie bisher verstanden haben, was Sie versucht haben und wo Sie stecken bleiben. Wir geben Ihnen Tipps, wie Sie sich lösen können.
Gung - Reinstate Monica
2
Ich vermute, dass M=300 als "sehr großes M " gelesen werden könnte, da ich glaube, dass M=301 oder M=999 fast genau das gleiche Ergebnis liefern würden. Was ich tun würde, ist die Verteilung der Summe minus M .
Henry

Antworten:

13

Sie können sicherlich Code verwenden, aber ich würde nicht simulieren.

Ich werde den "Minus M" Teil ignorieren (das kannst du am Ende leicht genug machen).

Sie können die Wahrscheinlichkeiten sehr einfach rekursiv berechnen, aber die tatsächliche Antwort (mit einem sehr hohen Grad an Genauigkeit) kann aus einfachen Überlegungen berechnet werden.

Lassen Sie die Rollen X1,X2,.... Sei St=i=1tXi .

Sei τ der kleinste Index, wobei SτM .

P(Sτ=M)=P(got to M6 at τ1 and rolled a 6)+P(got to M5 at τ1 and rolled a 5)++P(got to M1 at τ1 and rolled a 1)=16j=16P(Sτ1=Mj)

Geben Sie hier die Bildbeschreibung ein

ähnlich

P(Sτ=M+1)=16j=15P(Sτ1=Mj)

P(Sτ=M+2)=16j=14P(Sτ1=Mj)

P(Sτ=M+3)=16j=13P(Sτ1=Mj)

P(Sτ=M+4)=16j=12P(Sτ1=Mj)

P(Sτ=M+5)=16P(Sτ1=M1)

Gleichungen, die der ersten oben ähnlich sind, könnten dann (zumindest im Prinzip) zurückgeführt werden, bis Sie eine der Anfangsbedingungen treffen, um eine algebraische Beziehung zwischen den Anfangsbedingungen und den von uns gewünschten Wahrscheinlichkeiten zu erhalten (was mühsam und nicht besonders aufschlussreich wäre). , oder Sie können die entsprechenden Vorwärtsgleichungen konstruieren und sie unter den Anfangsbedingungen vorwärts ausführen, was numerisch einfach zu bewerkstelligen ist (und auf diese Weise habe ich meine Antwort überprüft). All das können wir jedoch vermeiden.

Die Wahrscheinlichkeiten der Punkte sind gewichtete Durchschnittswerte früherer Wahrscheinlichkeiten. Diese glätten (geometrisch schnell) jede Abweichung der Wahrscheinlichkeit von der anfänglichen Verteilung (alle Wahrscheinlichkeit am Punkt Null im Fall unseres Problems). Das

In einer Näherung (eine sehr genaue) können wir sagen, dass bis M - 1 zum Zeitpunkt τ - 1 (sehr nahe daran) fast gleich wahrscheinlich sein sollten , und so können wir aus dem Obigen aufschreiben, dass die Wahrscheinlichkeiten werden sehr nahe daran sein, in einfachen Verhältnissen zu sein, und da sie normalisiert werden müssen, können wir einfach Wahrscheinlichkeiten aufschreiben.M6M1τ1

Das heißt, wir können sehen, dass, wenn die Wahrscheinlichkeiten für den Start von bis M - 1 genau gleich wären , es 6 gleich wahrscheinliche Wege gibt, um zu M zu gelangen , 5 um zu M + 1 zu gelangen und so weiter bis hinunter 1 Weg zu M + 5 .M6M1MM+1M+5

Das heißt, die Wahrscheinlichkeiten liegen im Verhältnis 6: 5: 4: 3: 2: 1 und summieren sich zu 1, sodass sie trivial aufzuschreiben sind.

Die genaue Berechnung (bis zu akkumulierten numerischen Rundungsfehlern) durch Vorwärtslaufen der Wahrscheinlichkeitsrekursionen von Null (ich habe es in R getan) ergibt Unterschiede in der Größenordnung von .Machine$double.eps( auf meiner Maschine) gegenüber der obigen Näherung (dh einfach) Wenn Sie in die oben genannten Richtungen argumentieren, erhalten Sie effektiv genaue Antworten, da sie den aus der Rekursion berechneten Antworten so nahe kommen, wie wir es von den genauen Antworten erwarten würden.2.22e-16

Hier ist mein Code dafür (das meiste davon initialisiert nur die Variablen, die Arbeit ist alles in einer Zeile). Der Code beginnt nach dem ersten Wurf (um mir das Einfügen einer Zelle 0 zu ersparen, was ein kleines Ärgernis in R ist); Bei jedem Schritt nimmt es die niedrigste Zelle, die besetzt sein könnte, und bewegt sich durch einen Würfelwurf vorwärts (verteilt die Wahrscheinlichkeit dieser Zelle auf die nächsten 6 Zellen):

 p = array(data = 0, dim = 305)
 d6 = rep(1/6,6)
 i6 = 1:6
 p[i6] = d6
 for (i in 1:299) p[i+i6] = p[i+i6] + p[i]*d6

(Wir könnten rollapply(von zoo) verwenden, um dies effizienter zu machen - oder eine Reihe anderer solcher Funktionen -, aber es wird einfacher zu übersetzen sein, wenn ich es explizit halte.)

Beachten Sie, dass dies d6eine diskrete Wahrscheinlichkeitsfunktion über 1 bis 6 ist, sodass der Code in der Schleife in der letzten Zeile laufende gewichtete Durchschnittswerte früherer Werte erstellt. Es ist diese Beziehung, die die Wahrscheinlichkeiten glättet (bis zu den letzten Werten, an denen wir interessiert sind).

Hier sind also die ersten 50 ungeraden Werte (die ersten 25 mit Kreisen markierten Werte). Bei jedem repräsentiert der Wert auf der y-Achse die Wahrscheinlichkeit, die sich in der hintersten Zelle angesammelt hat, bevor wir sie in die nächsten 6 Zellen vorwärts gerollt haben.t

Geben Sie hier die Bildbeschreibung ein

Wie Sie sehen, glättet es sich ziemlich schnell (auf , der Kehrwert des Mittelwerts der Anzahl der Schritte, die jeder Würfelwurf benötigt) und bleibt konstant.1/μ

Und sobald wir treffen , fallen diese Wahrscheinlichkeiten weg (weil wir die Wahrscheinlichkeit für Werte bei M und darüber hinaus nicht der Reihe nach vorwärts setzen).MM

Geben Sie hier die Bildbeschreibung ein

Die Idee, dass die Werte bei bis M - 6 gleich wahrscheinlich sein sollten, da die Schwankungen von den Anfangsbedingungen geglättet werden, ist eindeutig der Fall.M1M6

Da die Argumentation von nichts anderem abhängt, als dass groß genug ist, dass die Anfangsbedingungen auswaschen, so dass M - 1 bis M - 6 zum Zeitpunkt τ - 1 nahezu gleich wahrscheinlich sind , ist die Verteilung für jedes große im Wesentlichen gleich M , wie Henry in den Kommentaren vorgeschlagen hat.MM1M6τ1M

Rückblickend würde Henrys Hinweis (der auch in Ihrer Frage steht), mit der Summe minus M zu arbeiten, ein wenig Mühe sparen, aber das Argument würde sehr ähnlichen Linien folgen. Sie können fortfahren, indem Sie und ähnliche Gleichungen schreiben, die R 0 mit den vorhergehenden Werten in Beziehung setzen, und so weiter.Rt=StMR0

Aus der Wahrscheinlichkeitsverteilung sind dann der Mittelwert und die Varianz der Wahrscheinlichkeiten einfach.

Edit: Ich nehme an, ich sollte den asymptotischen Mittelwert und die Standardabweichung der Endposition minus angeben :M

Der asymptotische mittlere Überschuss beträgt und die Standardabweichung ist253 . BeiM=300 istdies viel genauer, als Sie wahrscheinlich interessieren.253M=300

Glen_b - Monica neu starten
quelle
+1 Ich habe diese Antwort nicht vollständig verstanden, bis ich meine eigene entwickelt habe, die jetzt überflüssig erscheint. Vielleicht sehen einige Leser Wert in den Illustrations- und Simulationsergebnissen, deshalb werde ich meine Antwort offen halten.
whuber
1
@whuber Meine Antwort ist viel weniger konkret, als ich es mir gewünscht hätte, da ich davon ausgegangen bin, dass dies Hausaufgaben sind (also habe ich es vermieden, zu viel von der Ableitung zu tun oder Code zu geben - es war eher als Gliederung gedacht). Es fiel mir schwer, eine klare Antwort auf dieses Problem zu schreiben (hier hilft Konkretheit mehr als sonst). Da Sie eine Antwort gegeben haben, die die tatsächlichen Zahlen und den Code enthält (welche Antwort sollte meiner Meinung nach definitiv bleiben), habe ich das Gefühl, dass ich einige Dinge tun kann, die meine Antwort hoffentlich verständlicher machen (expliziter sein, meinen eigenen Code angeben). .
Glen_b -State Monica
Ich habe vor ein paar Jahren irgendwo eine viel bessere Erklärung für diese Art von Problem geschrieben. Wenn ich mich erinnern / herausfinden kann, wie das gelaufen ist, werde ich versuchen, einige davon hier aufzunehmen.
Glen_b -State Monica
@Glen_b verstand die Gleichungen ein wenig. Ich bin ein Neuling. Wie fange ich an, so zu denken? Gibt es Bücher, die Sie für diesen Zweck empfehlen könnten? Ihre Antwort wäre sehr hilfreich.
Üblicher Verdächtiger
Üblicher Verdächtiger - Ich schrieb die Gleichungen, indem ich mir ein Spielbrett wie eine lange Strecke vorstellte und sagte: "Wie kann ich auf eine Weise in diesen Raum gelangen, die den Bedingungen des Problems entspricht und mit welchen Chancen?"; Ich habe es für ein Feld mit der Bezeichnung "M" gemacht, dann für das Feld danach und so weiter. Ich schrieb die ähnliche Berechnung für den Code, indem ich mir vorstellte, in der Nähe der Startzelle zu sein und sagte: "Wenn ich hier wäre, wäre ich der nächste, mit welchen Chancen?". Die Gleichungen sind nur die Antworten auf diese Fragen.
Glen_b -Rate State Monica
8

Ω0nEnn

En={ωΩ|nω}.

XM(ω)ωMXMMXM

XM(ω)M{0,1,2,3,4,5}. By partitioning the event XMM=k according to the immediately preceding value in ω, and letting p(i)=1/6 be the probability of observing face i on one roll of the die (i=1,2,3,4,5,6), it follows that

Pr(XMM=k)=j=k6Pr(EM+kj)p(j)=16j=k6Pr(EM+kj).

At this point we could argue heuristically that, to a very good approximation for all but the smallest M,

Pr(Ei)2/7.
This is because the expected value of a roll is (1+2+3+4+5+6)/6=7/2 and its reciprocal should be the limiting, stable long-run frequency of any particular value in ω.

A rigorous way to demonstrate this considers how Ei could occur. Either Ei1 occurs and the subsequent roll was a 1; or Ei2 occurs and the subsequent roll was a 2; or ... or Ei6 occurs and the subsequent roll was a 6. This is an exhaustive partition of the possibilities, whence

Pr(Ei)=j=16Pr(Eij)p(j)=16j=16Pr(Eij).

The initial values of this sequence are

Pr(E0)=1;Pr(Ei)=0,i=1,2,3,.

Figure: plot of E_i

This plot of Pr(Ei) against i shows how rapidly the chances settle down to a constant 2/7, shown by the horizontal dotted line.

There is a standard theory of such recursive sequences. It can be developed by means of generating functions, Markov chains, or even algebraic manipulation. The general result is that a closed-form formula for Pr(Ei) exists. It will be a linear combination of a constant and the ith powers of roots of the polynomial

x6p(1)x5p(2)x4p(3)x3p(6)=x6(x5+x4+x3+x2+x+1)/6.

The largest magnitude of these roots is approximately exp(0.314368). In a double precision floating point representation, exp(36.05) is essentially zero. Therefore, for i36.05/0.314368=115, we may completely ignore all but the constant. This constant is 2/7.

Consequently, for M=300115, for all practical purposes we may take EM+kj=2/7, whence

Pr(XMM=(0,1,2,3,4,5))=(27)(16)(6,5,4,3,2,1).

Computing the mean and variance of this distribution is straightforward and easy.


Here is an R simulation to confirm these conclusions. It generates almost 100,000 sequences through M+5=305, tabulates the values of X300300, and applies a χ2 test to assess whether the results are consistent with the foregoing. The p-value (in this case) of 0.1367 is large enough to indicate they are consistent.

M <- 300
n.iter <- 1e5
set.seed(17)
n <- ceiling((2/7) * (M + 3*sqrt(M)))
dice <- matrix(ceiling(6*runif(n*n.iter)), n, n.iter)
omega <- apply(dice, 2, cumsum)
omega <- omega[, apply(omega, 2, max) >= M+5]
omega[omega < M] <- NA
x <- apply(omega, 2, min, na.rm=TRUE)
count <- tabulate(x)[0:5+M]
(cbind(count, expected=round((2/7) * (6:1)/6 * length(x), 1)))
chisq.test(count, p=(2/7) * (6:1)/6)
whuber
quelle