Problème : le théorème de Pólya en dimension 1

La stratégie d'ensemble. La question 1 montre que le nombre moyen de retours est infini. Cela ne suffit pas : les événements $(S_{2n}=0)$ ne sont pas indépendants, et le second lemme de Borel–Cantelli de l'exercice 1 ne s'applique pas. On décompose donc selon le premier retour (question 2), ce qui donne une convolution ; les génératrices la changent en produit (question 3), qu'on résout (question 4) ; le comportement de $F$ en $1$ dit tout (question 5).

1) Le retour en $0$ à l'instant $2n$.

La parité. Si $b$ des $n$ premiers pas valent $-1$ et les $n-b$ autres $+1$, alors $S_n=n-2b$ a la parité de $n$ : $S_n=0$ impose $n$ pair.

La probabilité exacte. Soit $A$ le nombre de pas égaux à $+1$ parmi les $2n$ premiers ; alors $S_{2n}=2A-2n$, et $(S_{2n}=0)=(A=n)$. La variable $A$ compte les succès de $2n$ épreuves indépendantes de probabilité $\frac{1}{2}$ : $A\sim \mathcal{B}(2n,\frac{1}{2})$, d'où $$u_n=P(A=n)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)(\frac{1}{2}{)}^{2n}=(\genfrac{}{}{0ex}{}{2n}{n})4^{-n},$$ où $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ se lit « n parmi 2n ». (Lecture en chemins : les $4^n$ suites de $2n$ pas sont équiprobables, et revenir en $0$, c'est choisir les $n$ pas montants parmi les $2n$.)

L'équivalent. Par la formule de Stirling, $(2n)!\sim \sqrt{4\pi n}(\frac{2n}{e}{)}^{2n}$ et $(n!{)}^2\sim 2\pi n(\frac{n}{e}{)}^{2n}$. Par quotient d'équivalents, et puisque $(2n{)}^{2n}=4^n{n}^{2n}$, $$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\frac{(2n)!}{(n!{)}^2}\sim \frac{2\sqrt{\pi n}{4}^n}{2\pi n}=\frac{4^n}{\sqrt{\pi n}}.$$ D'où $u_n\sim \frac{1}{\sqrt{\pi n}}$ — l'équivalent que le TD 6 obtient aussi par les intégrales de Wallis. Contrôle : $u_{10}\approx 0,17620$ contre $\frac{1}{\sqrt{10\pi }}\approx 0,17841$, et $u_{1000}\approx 0,0178390$ contre $0,0178412$.

La divergence. Les suites positives $(u_n)$ et $\left(\frac{1}{\sqrt{\pi n}}\right)$ sont équivalentes, donc leurs séries sont de même nature, et $\sum \frac{1}{\sqrt{n}}$ diverge (Riemann, exposant $\frac{1}{2}\le 1$) : $\sum u_n=+\infty$. Par linéarité, le nombre moyen de retours en $0$ avant l'instant $2N$, ${\sum }_{n=1}^N{u}_n$, tend vers l'infini.

2) L'équation de renouvellement.

$(T=2k)$ ne dépend que des $2k$ premiers pas. Par définition, $(T=2k)=(S_1\ne 0)\cap \cdots \cap (S_{2k-1}\ne 0)\cap (S_{2k}=0)$, et chaque $S_j$, pour $j\le 2k$, est une fonction de $(X_1,\dots ,X_{2k})$ : l'indicatrice de $(T=2k)$ aussi.

La factorisation. Sur $(T=2k)$, $S_{2k}=0$, donc $S_{2n}=S_{2n}-S_{2k}=X_{2k+1}+\cdots +X_{2n}$. Ainsi $$(T=2k)\cap (S_{2n}=0)=(T=2k)\cap (X_{2k+1}+\cdots +X_{2n}=0).$$ Le premier événement dépend de $(X_1,\dots ,X_{2k})$, le second de $(X_{2k+1},\dots ,X_{2n})$ : deux coalitions disjointes de variables indépendantes, donc deux événements indépendants par le lemme des coalitions. De plus, $(X_{2k+1},\dots ,X_{2n})$ a la même loi que $(X_1,\dots ,X_{2n-2k})$ — la loi conjointe de variables indépendantes est le produit des marginales, ici toutes égales —, donc $X_{2k+1}+\cdots +X_{2n}$ a la même loi que $S_{2(n-k)}$. D'où $$P(T=2k,S_{2n}=0)=P(T=2k)P(S_{2(n-k)}=0)=f_k{u}_{n-k},$$ y compris pour $k=n$, où le second facteur vaut $u_0=1$ (la somme est vide).

Le point délicat. On n'a pas « recommencé la marche à l'instant aléatoire $T$ » — ce serait la propriété de Markov forte, hors programme. On a travaillé à l'instant fixe $2k$, sur l'événement $(T=2k)$, qui ne dépend que des $2k$ premiers pas : c'est ce qui rend le lemme des coalitions applicable.

La décomposition. Si $S_{2n}=0$, alors $T\le 2n$, et $T$, lorsqu'il est fini, est pair d'après la question 1. L'événement $(S_{2n}=0)$ est donc la réunion disjointe des $(T=2k)\cap (S_{2n}=0)$, $1\le k\le n$, et par additivité $$u_n=\sum _{k=1}^{n}P(T=2k,S_{2n}=0)=\sum _{k=1}^n{f}_k{u}_{n-k}.$$

3) L'équation sur les génératrices.

La convergence. Pour $s\in ]-1,1[$, $|u_n{s}^n|\le |s{|}^n$ et $|f_n{s}^n|\le |s{|}^n$, car $u_n$ et $f_n$ sont des probabilités : les deux séries convergent absolument, par comparaison à une série géométrique.

Le produit de Cauchy. Posons $f_0=0$. Le produit de Cauchy de deux séries absolument convergentes converge, et sa somme est le produit des sommes : $$F(s)U(s)=\sum _{n=0}^{+\infty }\left(\sum _{k=0}^n{f}_k{u}_{n-k}\right)s^n.$$ Pour $n=0$, le coefficient vaut $f_0{u}_0=0$ ; pour $n\ge 1$, il vaut $u_n$ par l'équation de renouvellement. Donc $F(s)U(s)={\sum }_{n\ge 1}{u}_n{s}^n=U(s)-u_0$, soit $$U(s)=1+F(s)U(s).$$ Lecture : une convolution — « premier retour à l'instant $2k$, puis retour en $0$ en $2(n-k)$ pas » — devient un produit. C'est le mécanisme des nombres de Catalan du TD 8 ; ici, la conclusion sera probabiliste.

4) Les deux génératrices, explicitement. Pour $x\in ]-1,1[$ et $\alpha$ réel, $(1+x{)}^{\alpha }={\sum }_{n\ge 0}\frac{\alpha (\alpha -1)\cdots (\alpha -n+1)}{n!}{x}^n$ (chapitre des séries entières). Prenons $\alpha =-\frac{1}{2}$ et $x=-s$, avec $s\in ]-1,1[$. Le coefficient de $s^n$ vaut $$(-1{)}^n\frac{(-\frac{1}{2})(-\frac{3}{2})\cdots (-\frac{2n-1}{2})}{n!}=\frac{1\cdot 3\cdots (2n-1)}{2^{n}n!},$$ puisque les $n$ signes moins se compensent avec $(-1{)}^n$. Or $1\cdot 3\cdots (2n-1)=\frac{(2n)!}{2\cdot 4\cdots (2n)}=\frac{(2n)!}{2^{n}n!}$, donc ce coefficient vaut $\frac{(2n)!}{4^n(n!{)}^2}=u_n$. Les deux séries entières sont identiques, donc $$U(s)=(1-s{)}^{-1/2}=\frac{1}{\sqrt{1-s}}.$$ Comme $U(s)>0$, la question 3 donne $F(s)=1-\frac{1}{U(s)}$, c'est-à-dire $$F(s)=1-\sqrt{1-s}.$$

5) Retour presque sûr, et temps moyen infini.

La continuité de $F$ sur $[0,1]$. Les événements $(T=2n)$, $n\ge 1$, sont deux à deux disjoints, de réunion $(T<+\infty )$ ; par $\sigma$-additivité, ${\sum }_{n\ge 1}{f}_n=P(T<+\infty )\le 1$. Pour $s\in [0,1]$, $|f_n{s}^n|\le f_n$, terme général d'une série convergente : la série $\sum f_n{s}^n$ converge normalement sur $[0,1]$, et sa somme $F$ y est continue, comme somme d'une série normalement convergente de fonctions continues.

Le retour. D'une part, $F(1)={\sum }_{n\ge 1}{f}_n=P(T<+\infty )$. D'autre part, par continuité de $F$ en $1$ et par la question 4, $$F(1)=\underset{s\to 1^{-}}{\lim }(1-\sqrt{1-s})=1.$$ Donc $P(T<+\infty )=1$ : la marche revient presque sûrement en $0$.

Un système complet ? La famille $((T=2k){)}_{k\ge 1}$ est formée d'événements deux à deux disjoints, dont la réunion $(T<+\infty )$ est de probabilité $1$ : c'est un système quasi-complet d'événements. Il n'est pas complet : dans l'univers des suites de pas, la suite constante égale à $+1$ ne revient jamais ; elle réalise l'événement $(T=+\infty )$, qui n'est donc pas vide. Presque sûr n'est pas certain — exactement comme la suite « que des faces » du cours.

L'espérance infinie. $T$ est à valeurs dans ${\mathbb{N}}^{\ast }\cup \{+\infty \}$, avec $P(T=+\infty )=0$ ; avec la convention du cours, $E(T)={\sum }_{n\ge 1}2n{f}_n\in [0,+\infty ]$. Supposons par l'absurde cette somme finie, égale à $M$. Pour $s\in [0,1[$, comme $\frac{1-s^n}{1-s}=1+s+\cdots +s^{n-1}\le n$, $$\frac{F(1)-F(s)}{1-s}=\sum _{n=1}^{+\infty }{f}_n\frac{1-s^n}{1-s}\le \sum _{n=1}^{+\infty }n{f}_n=\frac{M}{2}.$$ Or, par la question 4, ce taux d'accroissement vaut $\frac{\sqrt{1-s}}{1-s}=\frac{1}{\sqrt{1-s}}$, qui tend vers $+\infty$ quand $s$ tend vers $1$ : contradiction. $T$ n'est pas d'espérance finie : la marche revient presque sûrement, mais le temps moyen de retour est infini.

6) Contrôle, et le théorème.

Le développement. Avec $\alpha =\frac{1}{2}$ et $x=-s$, les coefficients de $(1+x{)}^{1/2}$ donnent $\sqrt{1-s}=1-\frac{s}{2}-\frac{s^2}{8}-\frac{s^3}{16}-\frac{5s^4}{128}+o(s^4)$, donc $$F(s)=\frac{s}{2}+\frac{s^2}{8}+\frac{s^3}{16}+\frac{5s^4}{128}+o(s^4).$$ Par unicité du développement en série entière — $F(s)=1-\sqrt{1-s}$ sur $]-1,1[$ —, $f_1=\frac{1}{2}$, $f_2=\frac{1}{8}$, $f_3=\frac{1}{16}$ et $f_4=\frac{5}{128}$.

Le dénombrement. $f_1=P(T=2)$ : les chemins de deux pas qui reviennent en $0$ sont $(+1,-1)$ et $(-1,+1)$, soit $2$ chemins sur $4$, et $f_1=\frac{1}{2}$. $f_2=P(T=4)$ : il faut $S_4=0$ sans passer par $0$ à l'instant $2$, donc deux premiers pas de même signe et deux derniers de signe opposé, $(+1,+1,-1,-1)$ ou $(-1,-1,+1,+1)$ : $2$ chemins sur $16$, et $f_2=\frac{1}{8}$.

La formule générale. Sur $]-1,1[$, la question 4 donne $1-F(s)=\sqrt{1-s}=(1-s)U(s)$. Les coefficients de $(1-s)U(s)$ sont $u_0=1$ puis $u_n-u_{n-1}$ ; ceux de $1-F(s)$ sont $1$ puis $-f_n$. Par unicité des coefficients, pour tout $n\ge 1$, $$f_n=u_{n-1}-u_n.$$ Or $\frac{u_n}{u_{n-1}}=\frac{(2n)(2n-1)}{4n^2}=\frac{2n-1}{2n}$, donc $u_{n-1}-u_n=u_{n-1}(1-\frac{2n-1}{2n})$, c'est-à-dire $$f_n=\frac{u_{n-1}}{2n}.$$ Contrôle : $\frac{u_0}{2}=\frac{1}{2}$, $\frac{u_1}{4}=\frac{1}{8}$, $\frac{u_2}{6}=\frac{3/8}{6}=\frac{1}{16}$, $\frac{u_3}{8}=\frac{5/16}{8}=\frac{5}{128}$. Et $f_n\sim \frac{1}{2\sqrt{\pi }{n}^{3/2}}$ : la loi du premier retour a une queue si lourde que la série $\sum n{f}_n$ diverge.

Deux relectures. Par télescopage, $P(T\le 2N)={\sum }_{n=1}^N{f}_n=u_0-u_N$ : la probabilité de ne pas être encore revenu à l'instant $2N$ est égale à la probabilité d'être en $0$ à cet instant, $P(T>2N)=u_N\sim \frac{1}{\sqrt{\pi N}}$. Elle tend vers $0$ — le retour presque sûr —, mais lentement : après cent pas, environ 8 pour cent des marches ne sont pas encore revenues ($u_{50}\approx 0,0796$). Et la formule sommatoire du cours, appliquée à $\frac{T}{2}$, à valeurs dans ${\mathbb{N}}^{\ast }\cup \{+\infty \}$, redonne l'espérance infinie : comme $T$ est pair ou infini, $(\frac{T}{2}\ge N)=(T>2N-2)$, et $$E\left(\frac{T}{2}\right)=\sum _{N=1}^{+\infty }P(T>2N-2)=\sum _{N=1}^{+\infty }{u}_{N-1}=+\infty ,$$ par la question 1. La divergence de $\sum u_n$, qui ne suffisait pas à prouver le retour, prouve le temps moyen infini.

Le théorème obtenu — théorème de Pólya (1921), en dimension 1. La marche aléatoire simple symétrique sur $\mathbb{Z}$, partie de $0$, revient en $0$ presque sûrement ; mais l'instant $T$ de son premier retour n'est pas d'espérance finie. Plus précisément, $P(T>2N)=\left(\genfrac{}{}{0ex}{}{2N}{N}\right)4^{-N}\sim \frac{1}{\sqrt{\pi N}}$, et pour tout $s\in [0,1]$, ${\sum }_{n\ge 1}P(T=2n)s^n=1-\sqrt{1-s}$.

Ce que le problème installe. Trois idées. Quand les événements ne sont pas indépendants, la divergence de la série de leurs probabilités ne suffit pas, et Borel–Cantelli se tait : on décompose selon le premier passage, à des instants fixes, pour obtenir une équation de renouvellement. Une convolution devient un produit de fonctions génératrices, et $U=1+FU$ se résout d'un trait. Le comportement de la génératrice en $1$ dit tout : sa valeur donne la probabilité que $T$ soit fini, son taux d'accroissement l'espérance. En physique, la marche au hasard est le modèle microscopique de la diffusion : une particule qui diffuse sur une droite repasse presque sûrement par son point de départ, mais en un temps moyen infini. En dimension $3$, la série correspondante converge et la marche peut s'échapper : Pólya a montré que la probabilité de retour y vaut environ $0,34$ — « un homme ivre finit toujours par rentrer chez lui, un oiseau ivre peut se perdre à jamais », selon le mot de Kakutani.