Probabilité de ruine du joueur juste
Je regarde la variante suivante du problème de ruine du joueur équitable: Le joueur commence avec 1 dollar. Ils lancent à plusieurs reprises une pièce équitable. Chefs, +1 dollar; Tails -1 dollar. Le jeu s'arrête lorsque le joueur atteint 0 dollars.
Il est bien connu que le jeu se termine avec la probabilité 1 et que le temps moyen de fin du jeu est infini.
Je suis intéressé par la question suivante: quelle est la probabilité (asymptotique) que le jeu ne soit pas encore terminé après $n$ flips?
D'un argument heuristique, je suis à peu près certain que la réponse est $\theta(1/\sqrt{n})$. D'après la simulation, il semble que la réponse concerne$0.8/\sqrt{n}$.
J'aimerais connaître la réponse exacte, et j'aimerais savoir comment la dériver analytiquement. Au moins, j'aimerais savoir comment prouver que la probabilité est$\theta(1/\sqrt{n})$. J'imagine que la preuve implique une martingale, mais je ne peux pas la trouver moi-même.
Réponses
La probabilité exacte que le jeu ne soit pas terminé après le $\ n^\text{th}\ $ lancer est $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$La preuve de la première expression s'avère plus simple que ce à quoi je m'attendais au départ. L'approximation asymptotique découle des expressions asymptotiques bien connues des coefficients binomiaux centraux:\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} Pour $\ i\ge1\ $ laisser $\ p_{in}\ $ être la probabilité que le joueur ait $\ i\ $ dollars après le $\ n^\text{th}\ $ lancer et laisser $\ p_{0n}\ $ être la probabilité que le jeu se termine le ou avant le $\ n^\text{th}\ $lancer. ensuite\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} Pour simplifier le calcul, laissez $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ pour $\ 0\le j<n\ $. ensuite\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} Il découle de la dernière de ces identités que $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ Les nombres $\ T_{nj}\ $sont les entrées du triangle catalan . Les nombres$\ T_{nn}\ $le long de la diagonale se trouvent les nombres catalans ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ d'où nous obtenons \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} De la récurrence pour $\ p_{in}\ $ nous obtenons aussi $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ et \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} On peut vérifier par induction que la solution de cette récurrence est \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} Maintenant $\ p_{0n}\ $ est la probabilité qu'après le $\ n^\text{th}\ $lancer le jeu est terminé, donc la probabilité que le jeu ne soit pas terminé après le$\ n^\text{th}\ $ lancer est $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ Comme indiqué ci-dessus.