Probabilidad de cola de ruina del jugador justo
Estoy viendo la siguiente variante del problema de la ruina del jugador justo: El jugador comienza con 1 dólar. Lanzan repetidamente una moneda justa. Cabezas, +1 dólar; Colas -1 dólar. El juego se detiene cuando el jugador llega a 0 dólares.
Es bien sabido que el juego termina con probabilidad 1 y que el tiempo medio para que termine el juego es infinito.
Estoy interesado en la siguiente pregunta: ¿Cuál es la probabilidad (asintótica) de que el juego aún no haya terminado después de $n$ voltea?
A partir de un argumento heurístico, estoy bastante seguro de que la respuesta es $\theta(1/\sqrt{n})$. De la simulación, parece que la respuesta es sobre$0.8/\sqrt{n}$.
Me gustaría saber la respuesta exacta y me gustaría saber cómo derivarla analíticamente. Al menos, me gustaría saber cómo demostrar que la probabilidad es$\theta(1/\sqrt{n})$. Supongo que la prueba implica una martingala, pero no puedo encontrarla yo mismo.
Respuestas
La probabilidad exacta de que el juego no haya terminado después del $\ n^\text{th}\ $ lanzar es $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$La prueba de la primera expresión resulta ser más sencilla de lo que esperaba inicialmente. La aproximación asintótica se deriva de las bien conocidas expresiones asintóticas para los coeficientes binomiales centrales:\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} por $\ i\ge1\ $ dejar $\ p_{in}\ $ ser la probabilidad de que el jugador tenga $\ i\ $ dólares después del $\ n^\text{th}\ $ lanzar y dejar $\ p_{0n}\ $ ser la probabilidad de que el juego termine en o antes del $\ n^\text{th}\ $sacudida. Luego\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} Para simplificar el cálculo, deje $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ para $\ 0\le j<n\ $. Luego\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} De la última de estas identidades se desprende que $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ Los números $\ T_{nj}\ $son las entradas en el triángulo catalán . Los números$\ T_{nn}\ $a lo largo de la diagonal están los números catalanes ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ de donde obtenemos \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} De la recurrencia de $\ p_{in}\ $ también obtenemos $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ y \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} Se puede verificar por inducción que la solución de esta recurrencia es \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} Ahora $\ p_{0n}\ $ es la probabilidad de que después de la $\ n^\text{th}\ $lanzar el juego ha terminado, por lo que la probabilidad de que el juego no haya terminado después de la$\ n^\text{th}\ $ lanzar es $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ como se indicó anteriormente.