Wahrscheinlichkeit, dass ein fairer Spieler den Schwanz ruiniert
Ich betrachte die folgende Variante des Ruinproblems des fairen Spielers: Der Spieler beginnt mit 1 Dollar. Sie werfen wiederholt eine faire Münze. Köpfe, +1 Dollar; Schwänze -1 Dollar. Das Spiel stoppt, wenn der Spieler 0 Dollar erreicht.
Es ist bekannt, dass das Spiel mit der Wahrscheinlichkeit 1 endet und dass die mittlere Zeit bis zum Ende des Spiels unendlich ist.
Ich interessiere mich für folgende Frage: Wie hoch ist die (asymptotische) Wahrscheinlichkeit, dass das Spiel danach noch nicht beendet ist? $n$ flippt?
Aufgrund eines heuristischen Arguments bin ich mir ziemlich sicher, dass die Antwort lautet $\theta(1/\sqrt{n})$. Aus der Simulation geht hervor, dass die Antwort ungefähr ist$0.8/\sqrt{n}$.
Ich möchte die genaue Antwort wissen und möchte wissen, wie man sie analytisch ableitet. Zumindest möchte ich wissen, wie man die Wahrscheinlichkeit beweist$\theta(1/\sqrt{n})$. Ich vermute, der Beweis beinhaltet ein Martingal, aber ich kann es selbst nicht finden.
Antworten
Die genaue Wahrscheinlichkeit, dass das Spiel nach dem nicht beendet wurde $\ n^\text{th}\ $ werfen ist $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$Der Beweis des ersten Ausdrucks erweist sich als einfacher als ich ursprünglich erwartet hatte. Die asymptotische Näherung folgt aus den bekannten asymptotischen Ausdrücken für die zentralen Binomialkoeffizienten:\begin{align} {2n\choose n}&\sim\frac{4^n}{\sqrt{\pi n}}=2^{2n}\sqrt{\frac{2}{2n\pi}}\\ {2n+1\choose n}&={2n+1\choose n+1}\sim\frac{2^{2n+1}}{\sqrt{\pi(n+1)}}\\ &=2^{2n+1}\sqrt{\frac{2}{\pi(2n+1)}}\sqrt{1-\frac{1}{2n+2}}\ . \end{align} Zum $\ i\ge1\ $ Lassen $\ p_{in}\ $ sei die Wahrscheinlichkeit, die der Spieler hat $\ i\ $ Dollar nach dem $\ n^\text{th}\ $ werfen und lassen $\ p_{0n}\ $ sei die Wahrscheinlichkeit, dass das Spiel am oder vor dem endet $\ n^\text{th}\ $werfen. Dann\begin{align} p_{n+1\,n}&=\frac{1}{2^n}\ ,\\ p_{n\,n}&=0\ ,\\ p_{0\,n}&= p_{0\,n-1}+\frac{p_{1\,n-1}}{2}\ ,\\ p_{1\,n}&= \frac{p_{2\,n-1}}{2}\ , \text{ and}\\ p_{i\,n}&= \frac{p_{i+1\,n-1}+p_{i-1\,n-1}}{2}\ \text{ for }\ i\ge2\ . \end{align} Um die Berechnung zu vereinfachen, lassen Sie $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ zum $\ 0\le j<n\ $. Dann\begin{align} T_{n0}&=1\ ,\\ T_{11}&=1\ ,\text{ and}\\ T_{nj}&=T_{n\,j-1}+T_{n-1\,j}\ \text{ for }\ 1\le j\le n\ . \end{align} Aus der letzten dieser Identitäten folgt, dass $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ Die Zahlen $\ T_{nj}\ $sind die Einträge im katalanischen Dreieck . Die Zahlen$\ T_{nn}\ $entlang der Diagonale sind die katalanischen Zahlen ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ von denen wir erhalten \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} Aus der Wiederholung für $\ p_{in}\ $ wir bekommen auch $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ und \begin{align} p_{0\,2n}&=p_{0\,2n-1}\\ &=p_{0\,2n-2}+\frac{p_{1\,2n-2}}{2}\\ &= p_{0\,2n-2}+\frac{2n-2\choose n-1}{n2^{2n-1}} \end{align} Durch Induktion kann überprüft werden, dass die Lösung dieses Wiederauftretens ist \begin{align} p_{0\,2n}&=1-\frac{2n\choose n}{2^{2n}}\\ &=1-\frac{2n-1\choose n-1}{2^{2n-1}}\\ &=p_{0\,2n-1}\ . \end{align} Jetzt $\ p_{0n}\ $ ist die Wahrscheinlichkeit, dass nach dem $\ n^\text{th}\ $Werfen Sie das Spiel ist beendet, so dass die Wahrscheinlichkeit, dass das Spiel nicht nach dem beendet wurde$\ n^\text{th}\ $ werfen ist $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ wie oben erwähnt.