Probabilidade de cauda de ruína do jogador justo
Estou olhando para a seguinte variante do problema da ruína do jogador justo: O jogador começa com 1 dólar. Eles repetidamente lançam uma moeda justa. Cabeças, +1 dólar; Caudas -1 dólar. O jogo para quando o jogador chega a 0 dólares.
É sabido que o jogo termina com probabilidade 1, e que o tempo médio para o término do jogo é infinito.
Estou interessado na seguinte questão: Qual é a probabilidade (assintótica) de que o jogo ainda não acabou depois $n$ vira?
A partir de um argumento heurístico, tenho quase certeza de que a resposta é $\theta(1/\sqrt{n})$. Pela simulação, parece que a resposta é sobre$0.8/\sqrt{n}$.
Gostaria de saber a resposta exata e gostaria de saber como derivá-la analiticamente. Pelo menos, gostaria de saber como provar que a probabilidade é$\theta(1/\sqrt{n})$. Suponho que a prova envolve um martingale, mas não consigo encontrar sozinho.
Respostas
A probabilidade exata de o jogo não ter terminado após o $\ n^\text{th}\ $ jogar é $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$A prova da primeira expressão acaba sendo mais direta do que eu esperava inicialmente. A aproximação assintótica segue das expressões assintóticas bem conhecidas para os coeficientes binomiais centrais:\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} Para $\ i\ge1\ $ deixei $\ p_{in}\ $ seja a probabilidade de que o jogador tenha $\ i\ $ dólares após o $\ n^\text{th}\ $ jogue e deixe $\ p_{0n}\ $ ser a probabilidade de o jogo terminar no dia ou antes do $\ n^\text{th}\ $sorteio. Então\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 o cálculo, deixe $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ para $\ 0\le j<n\ $. Então\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} Decorre da última dessas identidades que $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ Os números $\ T_{nj}\ $são as entradas do triângulo catalão . Os números$\ T_{nn}\ $ao longo da diagonal estão os números catalães ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ de onde obtemos \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} Da recorrência para $\ p_{in}\ $ nós também temos $\ 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} Pode-se verificar por indução que a solução desta recorrência é \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} Agora $\ p_{0n}\ $ é a probabilidade de que após o $\ n^\text{th}\ $lançar o jogo terminou, então a probabilidade de que o jogo não tenha terminado após o$\ n^\text{th}\ $ jogar é $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ conforme indicado acima.