Die erwartete Anzahl von Münzwürfen wird N in Folge erhalten, wenn M in Folge gegeben wird

Interviewstreet hatte im Januar ihren zweiten CodeSprint, der die folgende Frage enthielt. Die programmatische Antwort wird veröffentlicht, enthält jedoch keine statistische Erklärung.

(Sie können das ursprüngliche Problem und die veröffentlichte Lösung anzeigen, indem Sie sich mit Google Creds auf der Interviewstreet-Website anmelden und dann auf dieser Seite zum Coin Tosses-Problem wechseln .)

Münzwurf

Sie haben eine unvoreingenommene Münze, die Sie so lange werfen möchten, bis Sie N aufeinanderfolgende Köpfe erhalten. Sie haben die Münze M-mal geworfen und überraschenderweise haben alle Würfe zu Köpfen geführt.

Was ist die erwartete Anzahl zusätzlicher Würfe, die benötigt werden, bis Sie N aufeinanderfolgende Köpfe erhalten?

Eingabe:
Die erste Zeile enthält die Anzahl der Fälle T. Jede der nächsten T-Zeilen enthält zwei Zahlen N und M.

Ausgang:
Ausgang T Linien die Antwort für den entsprechenden Testfall enthält. Drucken Sie die Antwort auf genau 2 Dezimalstellen gerundet.

Probeneingabe:
4
2 0
2 1
3 3
3 2

Probenausgabe:
6.00
4.00
0.00
8.00

Beispielerklärungen:
Wenn N = 2 und M = 0, müssen Sie die Münze so lange werfen, bis Sie 2 aufeinanderfolgende Köpfe erhalten. Es ist nicht schwer zu zeigen, dass durchschnittlich 6 Münzwürfe erforderlich sind.
Wenn N = 2 und M = 1, benötigen Sie 2 aufeinanderfolgende Köpfe und haben bereits 1. Sie müssen noch einmal werfen, egal was passiert. In diesem ersten Wurf sind Sie fertig, wenn Sie Köpfe bekommen. Andernfalls müssen Sie neu beginnen, wenn der aufeinanderfolgende Zähler zurückgesetzt wird, und Sie müssen die Münze weiter werfen, bis Sie N = 2 aufeinanderfolgende Köpfe erhalten. Die erwartete Anzahl der Münzwürfe beträgt somit 1 + (0,5 * 0 + 0,5 * 6) = 4,0. Wenn N = 3 und M = 3, haben Sie bereits 3 Köpfe, sodass Sie keine weiteren Würfe mehr benötigen.

Alle mathematischen Gleichungen, die ich mir ausgedacht habe, hatten die richtigen Antworten für die oben aufgeführten Beispiel-Eingabedaten, waren jedoch für alle anderen Eingabesätze (die nicht bekannt sind) falsch. Ihre programmatische Lösung scheint das Problem ganz anders zu lösen als meine Methode, eine Gleichung zu entwickeln. Kann jemand bitte erklären, wie man eine Gleichung findet, die dies lösen würde?

probability stochastic-processes markov-process Polshgiant
quelle

Siehe auch hier, wo wir auch das -Ergebnis von Daniel Johnson unten finden.

2^{N + 1} - 2^{M + 1}

$2^{N+1}-2^{M+1}$

Dilip Sarwate

Antworten:

Dies ist eine Rechenübung, denken Sie also rekursiv . Der aktuelle Zustand des Münzwurfs wird durch das geordnete Paar mit . Die erwartete Anzahl von Flips, um aufeinanderfolgende Köpfe zu erreichen, sei : $(N,M)$ $N\ge M\ge 0$ $N$ $e(N,M)$

(1) Es besteht eine 50% ige Chance, dass der nächste Flip Köpfe sind, die Sie in den Zustand bringen , und eine 50% ige Chance, dass der nächste Flip Schwänze sind, die Sie in den Zustand bringen . Dies kostet einen Flip. Daher ist die Erwartung (rekursiv) gegeben durch $(N,M+1)$ $(N,0)$

e (N, M) = \frac{1}{2} e (N, M + 1) + \frac{1}{2} e (N, 0) + 1.

$e(N,M) = \frac{1}{2} e(N,M+1) + \frac{1}{2} e(N,0) + 1.$

(2) Grundbedingungen: Das haben Sie bereits festgelegt

e (N, 0) = 2^{N + 1} - 2

$e(N,0) = 2^{N+1}-2$

und natürlich

e (N, N) = 0

$e(N,N) = 0$

(Es sind keine Flips mehr erforderlich).

Hier ist das entsprechende Mathematica- Programm (einschließlich des Zwischenspeicherns von Zwischenergebnissen, um die Rekursion zu beschleunigen, was es effektiv zu einer dynamischen Programmierlösung macht):

e[n_, m_] /; n > m > 0 := e[n, m] = 1 + (e[n, m + 1] + e[n, 0])/2 // Simplify
e[n_, 0] := 2^(n + 1) - 2
e[n_, n_] := 0

Das Programm würde in anderen Programmiersprachen, die die Rekursion unterstützen, ähnlich aussehen. Mathematisch können wir überprüfen, dass , indem wir einfach die Rekursion überprüfen, da dies offensichtlich für die Basisfälle gilt: $e(N,M) = 2^{N+1} - 2^{M+1}$

2^{N + 1} - 2^{M + 1} = 1 + (2^{N + 1} - 2^{M + 2} + 2^{N + 1} - 2) / 2,

$2^{N+1} - 2^{M+1} = 1 + (2^{N+1} - 2^{M+2} + 2^{N+1} - 2)/2,$

Dies gilt für jedes und , QED. $M$ $N$

Allgemeiner wird der gleiche Ansatz feststellen, dass wenn die Münze die Wahrscheinlichkeit von Köpfen hat. Der schwierige Teil besteht darin, die Grundbedingung . Dies geschieht durch Verfolgen der Rekursion aus Schritten, bis schließlich als sich selbst ausgedrückt wird und gelöst wird: $e(N,M) = \frac{p^{-N} - p^{-M}}{1-p}$ $p$ $e(N,0)$ $N$ $e(N,0)$

\begin{aligned} e (N, 0) & = 1 + p e (N, 1) + (1 - p) e (n, 0) \\ = 1 + p (1 + p e (N, 2) + (1 - p) e (N, 0)) + (1 - p) e (N, 0) \\ \dots \\ = 1 + p + p^{2} + \dots + p^{N - 1} + (1 - p) [1 + p + \dots + p^{N - 1}] e (N, 0); \\ e (N, 0) & = \frac{1 - p^{N}}{1 - p} + (1 - p^{N}) e (N, 0); \\ e (N, 0) & = \frac{p^{- N} - 1}{1 - p} . \end{aligned}

$\eqalign{ e(N,0) &= 1 + p e(N,1) + (1-p) e(n,0) \\ &= 1 + p\left(1 + p e(N,2) + (1-p) e(N,0)\right) + (1-p) e(N,0) \\ \cdots \\ &= 1 + p + p^2 + \cdots + p^{N-1} + (1-p)[1 + p + \cdots + p^{N-1}]e(N,0);\\ e(N,0) &= \frac{1-p^N}{1-p} + (1-p^N)e(N,0); \\ e(N,0) &= \frac{p^{-N}-1}{1-p}. }$

whuber
quelle

Vielleicht ist es besser , iterativ als rekursiv zu arbeiten? Sie haben , was ergibt und so und so weiter ergibtOder die Differenzgleichung könnte "theoretisch" anstatt durch Iteration gelöst werden.

e (N, M) = \frac{1}{2} e (N, M + 1) + \frac{1}{2} e (N, 0) + 1

$e(N,M)=\frac{1}{2}e(N,M+1)+\frac{1}{2}e(N,0)+1$

e (N, M + 1) = 2 e (N, M) - 2^{N + 1}

$e(N,M+1)=2e(N,M)-2^{N+1}$

\begin{aligned} e (N, 1) & = 2 e (N, 0) - 2^{N + 1} = 2 (2^{N + 1} - 2) - 2^{N + 1} = 2^{N + 1} - 4 \\ e (N, 2) & = 2 e (N, 1) - 2^{N + 1} = 2 (2^{N + 1} - 4) - 2^{N + 1} = 2^{N + 1} - 8 \end{aligned}

$\begin{align*}e(N,1)&=2e(N,0)-2^{N+1}=2(2^{N+1}-2)-2^{N+1}=2^{N+1}-4\\e(N,2)&=2e(N,1)-2^{N+1}=2(2^{N+1}-4)-2^{N+1}=2^{N+1}-8\end{align*}$

e (N, M) = 2^{N + 1} - 2^{M + 1} .

$e(N,M)=2^{N+1}-2^{M+1}.$

Dilip Sarwate

@Dilip Die Schlussfolgerungen, die Sie sowohl bei "was gibt" als auch bei "und so weiter" ziehen, sind rekursiv. Welche Lösungsmethode haben Sie mit "theoretisch gelöst" im Sinn?

whuber

Meiner Meinung nach ist der Unterschied zwischen rekursiv und iterativ die Arbeitsweise. Für die Beziehung berechnet die Rekursion als während die Iteration sagt "Theoretisch" bedeutete das Lösen einer Differenzgleichung, indem das charakteristische Polynom gefunden, seine Wurzeln bestimmt und dann die allgemeine Lösung an die Anfangsbedingungen angepasst wurde, anstatt wie oben einfach zu berechnen.

x (n) = 2 x (n - 1), x (0) = 1,

$x(n)=2x(n-1),~~ x(0)=1,$

x (n)

$x(n)$

x (n) = 2 x (n - 1) = 2 (2 x (n - 2)) = 2 (2 (2 x (n - 3))) = \dots = 2 (2 (\dots 2 x (0) \dots) = 2^{n}

$x(n)=2x(n-1)=2(2x(n-2))=2(2(2x(n-3)))=\cdots=2(2(\cdots 2x(0)\cdots)=2^n$

x (0) = 1 \Rightarrow x (1) = 2 x (0) = 2 \Rightarrow x (2) = 2 x (1) = 2^{2} \Rightarrow \dots x (n) = 2 x (n - 1) = 2 \cdot 2^{n - 1} = 2^{n} .

$x(0)=1\Rightarrow x(1)=2x(0)=2\Rightarrow x(2)=2x(1)=2^2\Rightarrow \cdots x(n)=2x(n-1)=2\cdot 2^{n-1}=2^n.$

Dilip Sarwate

Aus programmtechnischer Sicht ist ein Programm find_x(n)rekursiv, wenn es so etwas wie sagt, if n=0 return 1 else return 2*find_x(n-1)in dem es find_xsich mal aufruft , während ein iteratives Programm so etwas wie

n

$n$ y = 1; while n > 0 do begin y=2*y; n=n-1 end; return y

Dilip Sarwate

Wenn Sie sich ansehen, wie diese Programme tatsächlich auf dem Computer @Dilip implementiert sind, unterscheiden sie sich in vielen Umgebungen (z. B. R) kaum. (In einem Fall erstellen Sie einen Vektor 1:nund verarbeiten ihn dann. In dem anderen Fall werden Sie feststellen, dass n:1er auf dem Stapel platziert und umgekehrt verarbeitet wurde.) Ein Teil meines Punktes war jedoch konzeptionell : Ihr erster Kommentar sprach von "iterativ arbeiten". Das bezog sich auf die Analyse und nicht auf ein Computerprogramm. Dies sind jedoch triviale, tangentiale Punkte, deren Diskussion keine Erweiterung dieses Kommentarthreads rechtfertigt.

whuber

Um dieses Problem zu lösen, werde ich stochastische Prozesse, Stoppzeiten und dynamische Programmierung verwenden.

Zunächst einige Definitionen:

X_{n} ≐ # (of consecutive heads after the nth flip)

$X_n \doteq \#\text{(of consecutive heads after the nth flip)}$ Wir erlauben auch, dass ein Wert für die Anzahl von aufeinanderfolgenden Köpfen bedeutet, bevor wir beginnen. Für und die Folge der Flips HHTHHHTHTTHH sind die entsprechenden Werte von 120123010012. Wenn wir , wären die Werte von X (M + 1) (M + 2) 0123010012.

X_{0}

$X_0$

X_{0} = 0

$X_0 = 0$

X

$X$

X_{0} = M

$X_0 = M$

Definieren Sie dann die folgenden Stoppzeiten:

τ_{N} ≐ min {k : X_{k} = N} and τ_{0} ≐ min {k > 1 : X_{k} = 0}

$\tau_N \doteq \min\{k: X_k = N\} \text{ and } \tau_0 \doteq \min\{k > 1: X_k = 0\}$

Der Wert ist der erwartete Wert von , die Anzahl der Flips, die , um N aufeinanderfolgende Flips zu beobachten , , wir haben bereits M aufeinanderfolgende Flips beobachtet . Angenommen, da die Antwort ansonsten trivial 0 ist. Wir berechnen: $\tau_N$ $(X_{\tau_N} = N)$ $(X_0 = M)$ $M \leq N$

E [τ_{N} | X_{0} = M] = E [τ_{N} 1_{{τ_{N} < τ_{0}}} + τ_{N} 1_{{τ_{N} > τ_{0}}} | X_{0} = M]

$E[\tau_N|X_0 =M] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =M]$

= (N - M) (\frac{1}{2})^{N - M} + E [τ_{0} | τ_{N} > τ_{0}, X_{0} = M] + (1 - (\frac{1}{2})^{N - M}) E [τ_{N} | X_{0} = 0]

$= (N-M)(\frac{1}{2})^{N-M} + E[\tau_0|\tau_N > \tau_0,X_0 =M] + (1 - (\frac{1}{2})^{N-M})E[\tau_N|X_0 = 0]$ Damit können wir die letzten beiden bedingten Erwartungen berechnen.

Die erste entspricht der erwarteten Anzahl von Flips vor dem Erhalten eines Schwanzes unter der Annahme, dass ein Schwanz umgedreht wird, bevor N aufeinanderfolgende Köpfe beobachtet werden, vorausgesetzt, wir beginnen mit M aufeinanderfolgenden Köpfen. Das ist nicht allzu schwer zu sehen

E [τ_{0} | τ_{N} > τ_{0}, X_{0} = M] = \sum_{j = 1}^{N - M} (j) (\frac{1}{2})^{j} = 2 - (N - M + 2) (\frac{1}{2})^{N - M}

$E[\tau_0|\tau_N > \tau_0,X_0 =M] = \sum^{N-M}_{j=1}(j)(\frac{1}{2})^j = 2 - (N-M+2)(\frac{1}{2})^{N-M}$

Jetzt müssen wir nur noch die zweite bedingte Erwartung berechnen, die der erwarteten Anzahl von Flips entspricht, die erforderlich sind, um N aufeinanderfolgende Köpfe ab 0 zu beobachten. Mit ähnlichen Berechnungen sehen wir das

E [τ_{N} | X_{0} = 0] = E [τ_{N} 1_{{τ_{N} < τ_{0}}} + τ_{N} 1_{{τ_{N} > τ_{0}}} | X_{0} = 0]

$E[\tau_N|X_0 = 0] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =0]$

= N (\frac{1}{2})^{N} + E [τ_{0} | τ_{N} > τ_{0}, X_{0} = 0] + (1 - (\frac{1}{2})^{N}) E [τ_{N} | X_{0} = 0]

$= N(\frac{1}{2})^{N} + E[\tau_0|\tau_N > \tau_0,X_0 =0] + (1 - (\frac{1}{2})^N)E[\tau_N|X_0 = 0]$

= 2^{N} {N (\frac{1}{2})^{N} + (2 - (N + 2) (\frac{1}{2})^{N})}

$= 2^N\lbrace N(\frac{1}{2})^{N} + (2 - (N+2)(\frac{1}{2})^{N})\rbrace$

= 2^{N + 1} - 2

$= 2^{N+1} - 2$

Dies gibt eine endgültige Antwort von:

E [τ_{N} | X_{0} = M] = (N - M) (\frac{1}{2})^{N - M} + 2 - (N - M + 2) (\frac{1}{2})^{N - M} + (1 - (\frac{1}{2})^{N - M}) (2^{N + 1} - 2)

$E[\tau_N|X_0 =M] = (N-M)(\frac{1}{2})^{N-M} + 2 - (N-M+2)(\frac{1}{2})^{N-M} + (1 - (\frac{1}{2})^{N-M})(2^{N+1} - 2)$

= 2^{N + 1} - 2^{M + 1}

$= 2^{N+1}-2^{M+1}$

Dies stimmt mit den vier von Ihnen aufgelisteten Testfällen überein. Mit einer so einfachen Antwort kann es eine einfachere Möglichkeit geben, dies zu berechnen.

Daniel Johnson
quelle

Dies ist ein schwierigerer Weg als die oben aufgeführte rekursive Idee, aber es ist äußerst nützlich, beide Ansätze zusammen zu sehen. Die meisten Menschen wissen nicht zu schätzen, wie Stoppzeitmethoden auch für kleine, praktische Probleme eingesetzt werden können.

Ely

Warnung: Das Folgende kann möglicherweise nicht als richtige Antwort angesehen werden, da es keine geschlossene Lösung für die Frage bietet, insb. im Vergleich zu den vorherigen Antworten . Ich fand den Ansatz jedoch ausreichend interessant, um die bedingte Verteilung zu ermitteln.

Betrachten Sie die vorläufige Frage, eine Folge von Köpfen aus Würfen mit der Wahrscheinlichkeit . Dies ist gegeben durch die Wiederholungsformel In der Tat ist meine Argumentation, dass keine aufeinanderfolgenden Köpfe aus Zügen gemäß dem ersten Auftreten eines Schwanzes aus dem ersten zerlegt werden können wirft. Die Bedingung, ob dieser erste Schwanz bei der ersten, zweiten, ..., ten Ziehung auftritt, führt zu dieser Wiederholungsbeziehung. $N$ $k$ $1-p(N,k)$

p (N, k) = {\begin{cases} 1 & if k < N \\ \sum_{m = 1}^{N} \frac{1}{2^{m}} p (N, k - m) & else \end{cases}

$p(N,k) = \begin{cases} 1 &\text{if } k<N\\ \sum_{m=1}^{N} \frac{1}{2^m}p(N,k-m) &\text{else}\\ \end{cases}$

N

$N$

k

$k$

N

$N$

N

$N$

Als nächstes beträgt die Wahrscheinlichkeit, die ersten aufeinanderfolgenden N Köpfe in Würfen zu erhalten, $$ q (N, m) = \ begin {Fälle} \ dfrac {1} {2 ^ N} & \ text {if} m = N \ $m\ge N$

     p(N,m-N-1) \dfrac{1}{2^{N+1}} &\text{if } N<m<2N+1
     \end{cases}

$$ Der erste Fall ist selbsterklärend. Der zweite Fall entspricht einem Schwanz, der bei der -Ziehung auftritt, gefolgt von Köpfen, und der letzte Fall verbietet aufeinanderfolgende Köpfe vor der -Ziehung. (Die beiden letzten Fälle könnten zu einem zusammengefasst werden, zugegeben!) $m-N-1$ $N$ $N$ $m-N-1$

Nun ist die Wahrscheinlichkeit, Köpfe zuerst und die ersten aufeinanderfolgenden Köpfe in genau Würfen (und nicht weniger) zu bekommen, $$ r (M, N, m) = \ begin {Fälle} 1/2 ^ N & \ text {if} m = N \ $M$ $N$ $m\ge N$

     0 &\text{if } N<m\le N+M\\

      \dfrac{1}{2^{M}}\sum_{r=M+1}^{N}\dfrac{1}{2^{r-M}}q(N,m-r)&\text{if } N+M<m

\ end {Fälle} s (M, N, m) = \ begin {Fälle} 1 / {2 ^ {NM}} & \ text {if} m = N \ 0 & \ text {if} N \ sum_ {r = M + 1} ^ {N} \ dfrac {q (N, mr)} {2 ^ {rM }} & \ text {if} N + M.

H e n c e t h e c o n d i t i o n a l p r o b a b i l i t y o f w a i t i n g $ m $ s t e p s t o g e t $ N $ c o n s e c u t i v e h e a d s g i v e n t h e f i r s t $ M $ c o n s e c u t i v e h e a d s i s

$Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is$

\ end {case} \ mathfrak {E} (M, N) = \ sum_ {m = N} ^ \ infty m \, s (M, N, m) $$ oder für die Anzahl der zusätzlichen Schritte ...

T h e e x p e c t e d n u m b e r o f d r a w s c a n t h e n b e d e r i v e d b y

$The expected number of draws can then be derived by$

E (M, N) - M

$\mathfrak{E}(M,N)-M$

Xi'an
quelle