Probabilità di coda di rovina del giocatore giusto
Sto esaminando la seguente variante del problema della rovina del giocatore leale: il giocatore inizia con 1 dollaro. Lanciano ripetutamente una moneta equa. Teste, +1 dollaro; Code -1 dollaro. Il gioco si ferma quando il giocatore raggiunge 0 dollari.
È noto che il gioco finisce con probabilità 1 e che il tempo medio per la fine del gioco è infinito.
Mi interessa la seguente domanda: qual è la probabilità (asintotica) che il gioco non sia ancora finito dopo $n$ capovolge?
Da un argomento euristico, sono abbastanza certo che la risposta sia $\theta(1/\sqrt{n})$. Dalla simulazione, sembra che la risposta riguardi$0.8/\sqrt{n}$.
Mi piacerebbe conoscere la risposta esatta e vorrei sapere come ricavarla analiticamente. Almeno, mi piacerebbe sapere come dimostrare che la probabilità è$\theta(1/\sqrt{n})$. Immagino che la prova implichi una martingala, ma non riesco a trovarla da solo.
Risposte
La probabilità esatta che il gioco non sia terminato dopo il $\ n^\text{th}\ $ il lancio è $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$La dimostrazione della prima espressione risulta essere più semplice di quanto mi aspettassi inizialmente. L'approssimazione asintotica deriva dalle ben note espressioni asintotiche per i coefficienti binomiali centrali:\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} Per $\ i\ge1\ $ permettere $\ p_{in}\ $ essere la probabilità che il giocatore ha $\ i\ $ dollari dopo il $\ n^\text{th}\ $ lanciare e lasciare $\ p_{0n}\ $ essere la probabilità che la partita finisca prima o prima del $\ n^\text{th}\ $lanciare. Poi\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} Per semplificare il calcolo, lascia $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ per $\ 0\le j<n\ $. Poi\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} Dall'ultima di queste identità segue che $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ I numeri $\ T_{nj}\ $sono le voci nel triangolo catalano . I numeri$\ T_{nn}\ $lungo la diagonale sono i numeri catalani ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ da cui otteniamo \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} Dalla ricorrenza per $\ p_{in}\ $ otteniamo anche $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ e \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} Si può verificare per induzione che la soluzione di questa ricorrenza è \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} Adesso $\ p_{0n}\ $ è la probabilità che dopo il $\ n^\text{th}\ $lancia il gioco è terminato, quindi la probabilità che il gioco non sia terminato dopo il$\ n^\text{th}\ $ il lancio è $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ come detto sopra.