La marche aléatoire à l'échelle $\sqrt{n}$

La stratégie. L'additivité de la variance fixe l'échelle de la marche ; la loi binomiale donne la probabilité exacte d'un retour ; la linéarité, appliquée à des indicatrices, compte les retours. Entre les deux derniers, un encadrement par télescopage, sans aucun équivalent asymptotique.

a) L'échelle de la marche. Chaque pas vérifie $E(X_i)=0$ et $E(X_i^2)=1$, donc $V(X_i)=1$. Par linéarité, $E(S_n)=0$ ; par indépendance, la variance est additive : $V(S_n)=n$. L'inégalité de Bienaymé-Tchebychev, avec $\epsilon =10\sqrt{n}$, donne $$P(|S_n|\ge 10\sqrt{n})\le \frac{V(S_n)}{100n}=\frac{1}{100}.$$ Avec probabilité au moins $0,99$, le marcheur est dans $]-10\sqrt{n},10\sqrt{n}[$ : il s'éloigne comme $\sqrt{n}$, pas comme $n$.

b) La loi exacte d'un retour. Posons $Y_i=\frac{X_i+1}{2}$, qui vaut $1$ si le $i$-ième pas va vers la droite et $0$ sinon. Fonctions respectives des $X_i$ indépendantes, les $Y_i$ sont indépendantes, de loi $\mathcal{B}\left(\frac{1}{2}\right)$, et leur somme $\frac{S_n+n}{2}$, qui compte les pas vers la droite, suit la loi $\mathcal{B}(n,\frac{1}{2})$. Pour $n=2p$, l'événement $(S_{2p}=0)$ signifie « exactement $p$ pas vers la droite », d'où $$P(S_{2p}=0)=\left(\genfrac{}{}{0ex}{}{2p}{p}\right)(\frac{1}{2}{)}^{2p}=\frac{\left(\genfrac{}{}{0ex}{}{2p}{p}\right)}{4^p},$$ le coefficient binomial se lisant « $p$ parmi $2p$ ». Un retour n'est possible qu'aux instants pairs.

c) L'encadrement par télescopage. Le produit. Dans $(2p)!={\prod }_{k=1}^p(2k-1)(2k)$, les facteurs pairs donnent ${\prod }_{k=1}^{p}2k=2^{p}p!$. Donc $$\frac{\left(\genfrac{}{}{0ex}{}{2p}{p}\right)}{4^p}=\frac{(2p)!}{p{!}^2{4}^p}=\frac{2^{p}p!{\prod }_{k=1}^p(2k-1)}{p{!}^2{2}^p{2}^p}=\frac{{\prod }_{k=1}^p(2k-1)}{2^{p}p!}=\prod _{k=1}^p\frac{2k-1}{2k}.$$ Notons $u_p$ ce produit.

Majoration. Pour tout $k\ge 1$, $(2k{)}^2=4k^2\ge 4k^2-1=(2k-1)(2k+1)$, donc $(\frac{2k-1}{2k}{)}^2\le \frac{(2k-1{)}^2}{(2k-1)(2k+1)}=\frac{2k-1}{2k+1}$. En multipliant ces inégalités entre réels positifs pour $k=1,\dots ,p$, le produit télescope : $$u_p^2\le \frac{1}{3}\cdot \frac{3}{5}\cdots \frac{2p-1}{2p+1}=\frac{1}{2p+1},\text{donc}{u}_p\le \frac{1}{\sqrt{2p+1}}.$$

Minoration. Pour $k\ge 2$, $(2k-1{)}^2=4k^2-4k+1\ge 4k^2-4k=(2k-2)\cdot 2k$, donc $(\frac{2k-1}{2k}{)}^2\ge \frac{(2k-2)\cdot 2k}{(2k{)}^2}=\frac{k-1}{k}$ ; le facteur d'indice $1$ vaut $\frac{1}{2}$, de carré $\frac{1}{4}$. En multipliant, le produit télescope encore : $$u_p^2\ge \frac{1}{4}\cdot \frac{1}{2}\cdot \frac{2}{3}\cdots \frac{p-1}{p}=\frac{1}{4p},\text{donc}{u}_p\ge \frac{1}{2\sqrt{p}}.$$

d) Le nombre moyen de retours. Écrivons $R_n={\sum }_{p=1}^n{1}_{(S_{2p}=0)}$ ; par linéarité, $E(R_n)={\sum }_{p=1}^n{u}_p$. Il reste à comparer chaque $u_p$ à une différence qui télescope.

Minoration. On a $\sqrt{p+1}-\sqrt{p}=\frac{1}{\sqrt{p+1}+\sqrt{p}}\le \frac{1}{2\sqrt{p}}\le u_p$, donc $$E(R_n)\ge \sum _{p=1}^n(\sqrt{p+1}-\sqrt{p})=\sqrt{n+1}-1.$$

Majoration. On a $\sqrt{2p+1}-\sqrt{2p-1}=\frac{2}{\sqrt{2p+1}+\sqrt{2p-1}}\ge \frac{2}{2\sqrt{2p+1}}=\frac{1}{\sqrt{2p+1}}\ge u_p$, donc $$E(R_n)\le \sum _{p=1}^n(\sqrt{2p+1}-\sqrt{2p-1})=\sqrt{2n+1}-1.$$

Commentaire. Le nombre moyen de retours tend vers $+\infty$, mais seulement comme $\sqrt{n}$ : le marcheur ne repasse par son point de départ qu'une fraction de l'ordre de $\frac{1}{\sqrt{n}}$ du temps. Pour $n=10000$, la somme vaut $E(R_{10000})\approx 111,8$, dans l'encadrement $[99,0;140,4]$.

Contrôle. Pour $p=1,\dots ,5$, l'énumération des $4^p$ marches donne $P(S_{2p}=0)=\frac{1}{2},\frac{3}{8},\frac{5}{16},\frac{35}{128},\frac{63}{256}$, qui sont bien les produits $\prod \frac{2k-1}{2k}$, chacun dans l'encadrement du c) : pour $p=2$, $0,354\le \frac{3}{8}\le 0,447$.

Le point délicat. L'additivité de la variance exige des pas indépendants — ou au moins décorrélés ; et l'encadrement du c) ne demande aucun équivalent : deux comparaisons de carrés et deux produits télescopiques suffisent, là où l'on attendrait la formule de Stirling.

Ce que l'exercice installe. Une marche aléatoire vit à l'échelle $\sqrt{n}$ : écart type $\sqrt{n}$, probabilité de retour à l'instant $2p$ de l'ordre de $\frac{1}{\sqrt{p}}$, nombre moyen de retours de l'ordre de $\sqrt{n}$. C'est la loi de la diffusion : la distance typique parcourue par une particule qui diffuse croît comme la racine du temps.