Probabilité de passage à l'origine

On se demande quelle est la probabilité ${\displaystyle q_{n}}$ d'être revenu au moins une fois à l'origine lors d'un parcours de longueur 2n ; il est remarquable que l'évènement contraire ${\displaystyle \{X_{k}\neq 0,1\leqslant k\leqslant 2n\}}$ a aussi pour probabilité ${\displaystyle p_{n}={1 \over {2^{2n}}}{\binom {2n}{n}}}$ et que donc ${\displaystyle q_{n}=1-p_{n}}$ tend vers 1 lorsque n tend vers l'infini : une marche aléatoire isotrope sur la droite repasse presque surement au moins une fois à son point de départ (donc en fait y repasse une infinité de fois), et ceci vaut même pour tout point par lequel elle passe. On verra plus loin que ceci reste vrai en dimension 2, mais devient faux en dimension supérieure.

Démonstration de la formule précédente :

Pour raison de symétrie, le nombre de marches aléatoires de longueur ${\displaystyle 2n}$ ne repassant pas par ${\displaystyle 0}$ est le double du nombre de celles qui restent ${\displaystyle >0}$.

Notre problème est de dénombrer les marches allant de ${\displaystyle 0}$ à ${\displaystyle 2k}$ en ${\displaystyle 2n}$ coups et se situant, à part ${\displaystyle 0}$, strictement à droite de ${\displaystyle 0}$.

Le premier segment d'une telle marche allant forcément de ${\displaystyle 0}$ à ${\displaystyle 1}$, il suffit de compter le nombre de chemins qui vont de ${\displaystyle 1}$ à ${\displaystyle \ 2k}$ en ${\displaystyle 2n-1}$ coups sans passer par ${\displaystyle 0}$.

D'une façon générale, le nombre de chemins qui vont de ${\displaystyle a}$ à ${\displaystyle b}$ en ${\displaystyle m}$ coups vaut ${\displaystyle \left({\begin{array}{c}m\\{\frac {m+b-a}{2}}\end{array}}\right)=}$ ${\displaystyle \left({\begin{array}{c}m\\{\frac {m-b+a}{2}}\end{array}}\right)}$(le chemin est entièrement déterminé par les ${\displaystyle {\frac {m+b-a}{2}}}$ déplacements vers la droite (ou les ${\displaystyle {\frac {m-b+a}{2}}}$ déplacements vers la gauche)), à choisir parmi les ${\displaystyle m}$ déplacements totaux. Donc déjà, le nombre total de marches qui vont de ${\displaystyle 1}$ à ${\displaystyle 2k}$ vaut ${\displaystyle \left({\begin{array}{c}2n-1\\n+k-1\end{array}}\right).}$

La partie délicate est de déterminer le nombre de marches de ${\displaystyle 1}$ à ${\displaystyle 2k}$ en ${\displaystyle 2n-1}$ coups qui passent par 0. On utilise pour cela le principe de réflexion, (voir l'article sur le problème du scrutin).

Pour une telle marche, on peut remplacer bijectivement la partie entre le ${\displaystyle 0}$ de départ et le premier retour en ${\displaystyle 0}$ par son symétrique par rapport à ${\displaystyle 0}$: ce nombre est donc le même que celui des marches allant de ${\displaystyle -1}$ à ${\displaystyle 2k}$ en ${\displaystyle 2n-1}$ coups soit ${\displaystyle \left({\begin{array}{c}2n-1\\n+k\end{array}}\right).}$

.Le nombre de marches allant de ${\displaystyle 0}$ à ${\displaystyle 2k}$ de longueur ${\displaystyle 2n}$ sans passer par l'axe vaut donc ${\displaystyle \left({\begin{array}{c}2n-1\\n+k-1\end{array}}\right)-\left({\begin{array}{c}2n-1\\n+k\end{array}}\right)}$. Notons que ce résultat est équivalent à celui du théorème du scrutin.

On en déduit le nombre de marches évitant ${\displaystyle 0}$ : ${\displaystyle 2^{2n}(1-q_{n})=2{\underset {k=1}{\overset {n}{\sum }}}\left(\left({\begin{array}{c}2n-1\\n+k-1\end{array}}\right)-\left({\begin{array}{c}2n-1\\n+k\end{array}}\right)\right)}$ ; somme télescopique donnant ${\displaystyle 2^{2n}(1-q_{n})=2\left({\begin{array}{c}2n-1\\n\end{array}}\right)=\left({\begin{array}{c}2n\\n\end{array}}\right)}$, ce qu'il fallait démontrer.

Autre interprétation du même résultat : le nombre de mots binaires de longueur ${\displaystyle 2n}$ dont tous les sous-mots commençant par la gauche (resp. par la droite) présentent strictement plus de 1 que de 0 (resp. l'inverse) vaut ${\displaystyle \left({\begin{array}{c}2n\\n\end{array}}\right)}$ (ne pas confondre avec les mots de Dyck).

Un calcul similaire montre que dans le cas impair, la probabilité de retour à l'origine lors d'un parcours de longueur ${\displaystyle 2n+1}$ vaut aussi ${\displaystyle 1-p_{n}}$ (voir la suite A063886 de l'OEIS et la suite A307768 de l'OEIS).

Temps de premier retour à l'origine

En utilisant des résultats précédents, on peut obtenir la probabilité ${\displaystyle r_{2n}}$que la marche revienne à l'origine pour la première fois au temps ${\displaystyle 2n}$ : ${\displaystyle r_{2n}={p_{n} \over {2n-1}}}$. On en déduit que l'espérance du temps de premier retour à l'origine ${\displaystyle {\underset {n=1}{\overset {\infty }{\sum }}}}{2nr_{2n}}$ est infinie puisque ${\displaystyle 2nr_{2n}\sim {1 \over {\sqrt {\pi n}}}}$.

Démonstration de la formule précédente :

Une marche qui revient à l'origine au temps ${\displaystyle 2n}$ passe forcément par 1 ou par -1 au temps précédent et, toujours par symétrie, il y a autant de marches arrivant en 1 qu'en -1 ; le nombre de marches revenant à l'origine pour la première fois au temps ${\displaystyle 2n}$ vaut donc le double du nombre de marches de longueur ${\displaystyle 2n-1}$ aboutissant en 1 et restant >0 ; on peut refaire un raisonnement du type précédent ou appliquer directement la formule du scrutin ${\displaystyle 2^{2n}r_{2n}=2{{p-q} \over {p+q}}\left({\begin{array}{c}p+q\\p\end{array}}\right)}$ avec ${\displaystyle p+q=2n-1,p-q=1}$, d'où ${\displaystyle 2^{2n}r_{2n}=2{{1} \over {2n-1}}\left({\begin{array}{c}2n-1\\n\end{array}}\right)={{1} \over {2n-1}}\left({\begin{array}{c}2n\\n\end{array}}\right)}$, ce que nous voulions.

Notons que ${\displaystyle {{1} \over {2n-1}}\left({\begin{array}{c}2n\\n\end{array}}\right)={{2} \over {n}}\left({\begin{array}{c}2(n-1)\\n-1\end{array}}\right)}$ est le double du nombre de Catalan d'ordre ${\displaystyle n-1}$.