Récurrence et transience d'une chaîne de Markov

Un état $\scriptstyle\ i\quad$ d'une chaîne de Markov $\scriptstyle\ X=(X_n)_{n\ge 0}\quad$ est dit récurrent si une trajectoire « typique » de la chaîne de Markov passe par $\scriptstyle\ i\quad$ une infinité de fois, sinon l'état $\scriptstyle\ i\quad$ est dit transient. Ces propriétés de transience ou de récurrence sont souvent partagées par tous les états de la chaîne $\scriptstyle\ X,\quad$ par exemple quand la chaîne $\scriptstyle\ X\quad$ est irréductible : en ce cas c'est la chaîne de Markov qui est dite transiente ou récurrente.

Temps de séjour et temps de premier retour

Pour chaque état i d'une chaîne de Markov, on a les définitions suivantes :

Définition — 

• Le temps de séjour (ou nombre de passages) en $\scriptstyle\ i\$ est une variable aléatoire $\scriptstyle\ S(i)\$ à valeurs dans $\scriptstyle\ \overline{\mathbb{N}}=\mathbb{N}\cup\{+\infty\},\$ définie par

$S(i)\ =\ \sum_{k\ge 0}1_{X_k=i}.$

La quantité

$S_n(i)\ =\ \sum_{0\le k\le n-1}1_{X_k=i},$

mesure le temps passé dans l'état $\scriptstyle\ i\$ lors des $\scriptstyle\ n\$ premiers pas de la chaîne de Markov. Les relations suivantes seront utiles :

$S_n(i)\le n,\quad\sum_{i\in E}S_n(i)= n,\mathrm{~et~}\lim_nS_n(i)=S(i).$

• Le temps de premier retour en $\scriptstyle\ i,\quad$ noté $\scriptstyle\ T_i,\quad$ est une variable aléatoire à valeurs dans $\scriptstyle\ \overline{\mathbb{N}}=\mathbb{N}\cup\{+\infty\},\$ définie par

$T_i=\left\{\begin{array}{ll}\inf\{k\ge 1\,|\,X_k=i\}&\text{ si }\{k\ge 1\,|\,X_k=i\}\neq\emptyset,\\+\infty&\text{ sinon.}\end{array}\right..$

Récurrence et transience (définition informelle)

Informellement, pour une chaîne de Markov irréductible, un état $\scriptstyle\ i\$ du système modélisé par la chaîne de Markov est dit récurrent si une trajectoire typique du système passe infiniment souvent par cet état. Il y a en fait dichotomie :

• soit la probabilité que la trajectoire du système passe infiniment souvent par $\scriptstyle\ i\$ vaut 1, et l'état $\scriptstyle\ i\$ est dit récurrent,
• soit cette probabilité vaut 0, auquel cas $\scriptstyle\ i\$ est dit transient.
• les états récurrents (ceux pour lesquels $\scriptstyle\ \lim_n S_n(i)=+\infty\$) se subdivisent en états récurrents positifs et récurrents nuls :

• un état est dit récurrent positif si le système y passe une fraction non négligeable de son temps : bien sûr $\scriptstyle\ S_n(i)\le n,\$ mais $\scriptstyle\ S_n(i)\$ ne doit pas être trop petit devant $\scriptstyle\ n\$:

$\lim_n \frac{S_n(i)}n=\pi_i>0\ ;$

en notation de Landau, $\scriptstyle\ S_n(i)\in \Theta(n).\$ Cela entraîne que les instants de passage en $\scriptstyle\ i\$ sont, en un certain sens, régulièrement espacés, à une distance $\scriptstyle\ 1/\pi_i\$ les uns des autres en moyenne,

• un état est dit récurrent nul si le système y passe une fraction négligeable de son temps :

$\lim_n \frac{S_n(i)}n=0\ ;$

i.e. $\scriptstyle\ S_n(i)\rightarrow +\infty,\$ mais $\scriptstyle\ S_n(i)\in o(n).\$ Le système passe infiniment souvent par l'état $\scriptstyle\ i,\$ mais les instants de passage en $\scriptstyle\ i\$ sont alors de plus en plus espacés au cours du temps.

Toujours dans le cas d'une chaîne de Markov irréductible, si un état est récurrent positif, tous les états le sont et la suite $\scriptstyle\ (\pi_i)_{i\in E}\$ est appelée probabilité stationnaire de la chaîne de Markov. La probabilité stationnaire joue un rôle très important dans l'étude de la chaîne de Markov.

Article détaillé : Probabilité stationnaire d'une chaîne de Markov.

Marche aléatoire sur $\scriptstyle\ \mathbb{Z}\$ et $\scriptstyle\ \mathbb{Z}_{m}\$  :

Par exemple, si $\scriptstyle\ p_{i,i+1}=p=1-p_{i,i-1},\$ on parle de marche aléatoire sur $\scriptstyle\ \mathbb{Z}\$ ou sur $\scriptstyle\ \mathbb{Z}_{m}.\$

• Si on est sur $\scriptstyle\ \mathbb{Z}_{m},\$ alors, indépendamment de la valeur de $\scriptstyle\ p,\$ chaque état est récurrent positif et chaque $\scriptstyle\ \pi_i\$ vaut $\scriptstyle\ \frac1m;\$
• Si on est sur $\scriptstyle\ \mathbb{Z},\$ et si $\scriptstyle\ p\neq 0.5,\$ chaque état $\scriptstyle\ i\$ est transient : au bout d'un certain temps, aléatoire, une trajectoire typique ne passe plus jamais par $\scriptstyle\ i;$
• Si on est sur $\scriptstyle\ \mathbb{Z},\$ et si $\scriptstyle\ p=0.5,\$ chaque état $\scriptstyle\ i\$ est récurrent nul : $\scriptstyle\ S_n(i)\sim\sqrt{n},\$ et le $\scriptstyle\ n$-ème passage a lieu, grosso-modo, au bout de $\scriptstyle\ n^2\$ unités de temps.

Récurrence et théorie ergodique  :

Il faut mentionner une notion très voisine : le théorème de récurrence de Poincaré (1890) dit que, pour presque toutes les « conditions initiales », un système dynamique conservatif dont l'espace des phases est de « volume » fini va repasser au cours du temps aussi près que l'on veut de sa condition initiale, et ce de façon répétée.

Critères de récurrence et de transience

Notations. Lorsqu'on étudie une chaîne de Markov particulière, sa matrice de transition est en général bien définie et fixée tout au long de l'étude, mais la loi initiale peut changer lors de l'étude et les notations doivent refléter la loi initiale considérée sur le moment :

• si à un moment de l'étude on considère une chaîne de Markov de loi initiale définie par $\scriptstyle\ \forall i\in E,\quad \mathbb{P}\left(X_{0}=i\right)=\mu_i,\quad$ alors les probabilités sont notées $\scriptstyle\ \mathbb{P}_{\mu}\left(\dots\right),\quad$ et les espérances sont notées $\scriptstyle\ \mathbb{E}_{\mu}\left[\dots\right]\ ;\quad$
• en particulier, si $\scriptstyle\ \mathbb{P}\left(X_{0}=j\right)=1,\quad$ on dit que la chaîne de Markov part de $\scriptstyle\ j,\quad$ les probabilités sont notées $\scriptstyle\ \mathbb{P}_{j}\left(\dots\right),\quad$ et les espérances sont notées $\scriptstyle\ \mathbb{E}_{j}\left[\dots\right].\quad$

Définition — 

• Un état $\scriptstyle\ i\$ est dit récurrent si et seulement si l'une des conditions équivalentes ci-dessous est remplie :

• $\ \mathbb{P}_{i}\left(S(i)=+\infty\right)>0,$
• $\ \mathbb{P}_{i}\left(S(i)=+\infty\right)=1,$
• $\ \mathbb{E}_{i}\left[S(i)\right]=+\infty,$
• $\ \sum_{k\ge 0}p^{(k)}_{i,i}=+\infty,$
• $\ \mathbb{P}_{i}\left(T_i<+\infty\right)=1.$

• Un état $\scriptstyle\ i\$ est dit transient dans le cas contraire, i.e. si et seulement si l'une des conditions équivalentes ci-dessous est remplie :

• $\ \mathbb{P}_{i}\left(S(i)=+\infty\right)<1,$
• $\ \mathbb{P}_{i}\left(S(i)=+\infty\right)=0,$
• $\ \mathbb{E}_{i}\left[S(i)\right]<+\infty,$
• $\ \sum_{k\ge 0}p^{(k)}_{i,i}<+\infty,$
• $\ \mathbb{P}_{i}\left(T_i=+\infty\right)>0.$

• L'état $\scriptstyle\ i\quad$ est récurrent positif si

• l'espérance du temps de premier retour en cet état, partant de cet état, est finie, i.e. si

$\mathbb{E}_i\left[T_i\right]\ <\ +\infty.$

ou bien, équivalemment, si

• il existe une probabilité stationnaire $\scriptstyle\ \pi=(\pi_i)_{i\in E}\quad$ telle que $\scriptstyle\ \pi_i>0,\$ i.e. une probabilité $\scriptstyle\ \pi\quad$ telle que $\scriptstyle\ \pi_i>0$ et telle que $\scriptstyle\ \pi P=\pi,\$ cette dernière relation s'écrivant aussi, coordonnées par coordonnées,

$\forall j \in E,\qquad\sum_{i\in E}\pi_ip_{i,j}=\pi_j.$

• L'état $\scriptstyle\ i\quad$ est récurrent nul s'il est récurrent et si, pourtant, l'espérance du temps de premier retour en cet état, partant de cet état, est infinie, i.e. si

• $\mathbb{P}_{i}\left(T_i<+\infty\right)=1\quad\text{et}\quad\mathbb{E}_i\left[T_i\right]\ =\ +\infty.$

Exemples

Marche aléatoire sur un groupe fini

Graphe de 2 marches aléatoires élémentaires, respectivement sur le groupe cyclique $\scriptstyle\ \mathbb{Z}_{8}\$ et sur le groupe diédral $\scriptstyle\ D_4.\$

Marche aléatoire sur $\scriptstyle\ \mathbb{Z}_{m}\$  :

Dans cet exemple, $\scriptstyle\ p_{i,i-1}=p=1-p_{i,i+1}.\$ La matrice de transition $\scriptstyle\ P\$ s'écrit

$\ P=pA+(1-p)B,\$

où $\scriptstyle\ A\$ (resp. $\scriptstyle\ B\$) est la matrice de la permutation circulaire $\scriptstyle\ (1,2,3,\dots,m)\$ (resp. $\scriptstyle\ (m,m-1,m-2,\dots,1)$). Par conséquent $\scriptstyle\ \pi=(1/m,1/m,\dots,1/m)$ est une probabilité stationnaire, donc chaque état est récurrent positif, en vertu du 2ème critère. Dans la figure ci-contre, $\scriptstyle\ m=8\$ et $\scriptstyle\ q=1-p.\$

Plus généralement, tous les états d'une marche aléatoire sur un groupe fini $\scriptstyle\ G\$ sont récurrents positifs, car la loi uniforme sur $\scriptstyle\ G\$ est une probabilité stationnaire, indépendamment du pas de la marche : en effet, la matrice de transition d'une marche aléatoire sur un groupe discret étant bistochastique, la mesure uniforme est toujours stationnaire.

Marche aléatoire sur $\scriptstyle\ D_{4}\$  :

Dans cet exemple, $\scriptstyle\ p_{g,g\tau}=p\$ et $\scriptstyle\ p_{g,g\rho}=q,\$ où $\scriptstyle\ \tau=(b,d)\$ est la symétrie du carré par rapport à la diagonale (a,c), et où $\scriptstyle\ \rho=(a,b)(c,d)\$ est la symétrie du carré par rapport à son axe horizontal ; $\scriptstyle\ \sigma=\rho\circ\tau=(a,b,c,d)\$ est la rotation d'angle $\scriptstyle\ \pi/2.\$ La probabilité $\scriptstyle\ \pi=(1/8,1/8,\dots,1/8)$ est une probabilité stationnaire, donc chaque état est récurrent positif, en vertu du 2ème critère.

Marche aléatoire simple sur les entiers relatifs

Dans cet exemple, $\scriptstyle\ E=\mathbb{Z}\$ et $\scriptstyle\ p_{i,i+1}=p=1-p_{i,i-1}.\$ Si $\scriptstyle\ 0<p<1,\$ la chaîne $\scriptstyle\ X=(X_n)_{n\ge 0}\quad$ est irréductible, donc tous les états ont même nature. Par exemple on a

$\forall k\ge 0,\qquad p^{(2k)}_{0,0}={2k\choose k}p^k(1-p)^k\sim\frac{(4p(1-p))^k}{\sqrt{k\pi}},\$

alors que $\scriptstyle\ p^{(2k+1)}_{0,0}=0.\$

Marche aléatoire biaisée

• Comme $\scriptstyle\ \{4p(1-p)<1\}\Leftrightarrow\{p\neq 0.5\}, \$ la marche est transiente si et seulement si $\scriptstyle\ p\neq 0.5, \$ en vertu du 4ème critère.

• On peut aussi voir que $\scriptstyle\ p\neq 0.5 \$ entraîne la transience de la chaîne de Markov $\scriptstyle\ X=(X_n)_{n\ge 0} \$ en construisant cette chaîne à l'aide d'une suite de variables aléatoires i.i.d. $\scriptstyle\ Y=(Y_n)_{n\ge 1}, \$ de la manière suivante : posons

$\begin{align}S_0=0,\qquad S_n&=S_{n-1}+Y_n\qquad n\ge 1 \\&=Y_1+Y_2+\dots+Y_n.\end{align}$

Alors $\scriptstyle\ S=(S_n)_{n\ge 0} \$ a même loi que $\scriptstyle\ X=(X_n)_{n\ge 0}, \$ mais la loi forte des grands nombres pour les suites de v.a. i.i.d. entraîne que, presque sûrement en $\scriptstyle\ \omega\in\Omega, \$

$\lim \frac{S_n(\omega)}n=\mathbb{E}[Y_n]=(1-p)\times(-1)+p\times 1=2p-1\neq 0.$

donc, avec probabilité 1, la suite de nombres réels $\scriptstyle\ (S_n(\omega))_{n\ge 0} \$ converge vers $\scriptstyle\ sgn(2p-1)\times+\infty, \$ et visite la valeur 0, au plus, un nombre fini de fois : 0 est donc transient, et tous les entiers de sa classe ($\scriptstyle\ \mathbb Z, \$ en l'occurrence) avec lui.

• Dans le cas où $\scriptstyle\ p=0.5, \$ la méthode précédente ne permet pas de démontrer la récurrence de 0, puisque la loi forte des grands nombres stipule alors la convergence de la suite $\scriptstyle\ (n^{-1}\,S_n(\omega))_{n\ge 0} \$ vers 0, ce qui n'entraîne pas nécessairement que la suite $\scriptstyle\ (S_n(\omega))_{n\ge 0} \$ prenne la valeur 0 une infinité de fois : pour aboutir à la conclusion d'une infinité de visites en 0, il faut invoquer un résultat plus précis que la loi forte des grands nombres, à savoir la loi du logarithme itéré.

• Pour décider de la récurrence ou de la transience aussi bien dans le cas $\scriptstyle\ p=0.5 \$ que dans le cas $\scriptstyle\ p\neq 0.5, \$ on peut aussi calculer explicitement la loi du premier temps T de retour en 0, partant de 0, pour la marche aléatoire simple, et trancher ainsi l'alternative :

$\mathbb{P}_{i}\left(T_i<+\infty\right)=1\quad\text{ou}\quad\mathbb{P}_{i}\left(T_i=+\infty\right)>0.$

En effet

$\forall k\ge 1,\qquad \mathbb{P}(T=2k)=2C_{k-1}\left(p(1-p)\right)^k,\$

où $\scriptstyle\ C_n\$ désigne le n-ème nombre de Catalan. On trouve alors que la série génératrice de T, $\scriptstyle\ G_T(s)=\mathbb{E}[s^T],\$ satisfait

$G_T(s) =1-\sqrt{1-4p(1-p)s^2}.$

Ainsi

$\begin{align} \mathbb{P}(T<+\infty)&=\sum_{k\ge2}\mathbb{P}(T=k) \\ &=G_T(1) \\ &=1-\sqrt{1-4p(1-p)} \\ &=2\min(p,1-p), \end{align}$

est strictement inférieur à 1 si et seulement si $\scriptstyle\ p\neq 0.5. \$

Marche aléatoire symétrique

• Par ailleurs, pour $\scriptstyle\ p=0.5,\$ la mesure de probabilité $\scriptstyle\ \pi\$ est solution du système $\scriptstyle\ \pi P=\pi\$ si et seulement si

$\forall k\in \mathbb{Z},\qquad 2\pi_k=\pi_{k-1}+\pi_{k+1},\$

i.e. si et seulement si les $\scriptstyle\ \pi_k\$ forment une progression arithmétique :

$\forall k\in \mathbb{Z},\qquad \pi_k=ak+b.\$

La contrainte de positivité sur les $\scriptstyle\ \pi_k\$ impose $\scriptstyle\ a=0,\ b\ge 0,\$ i.e. $\scriptstyle\ \pi_k\$ est une suite constante, donc il n'existe pas de probabilité stationnaire : tous les états sont récurrents nuls.

• Puisque, asymptotiquement, les nombres de Catalan se comportent comme

$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}},$

on peut aussi voir directement, grace la formule explicite de la loi du temps T de retour en 0, donnée à la section précédente, que

$2k \mathbb{P}(T=2k)\sim \frac{1}{2\sqrt{\pi k}}$

n'est pas le terme général d'une série convergente, et que, par conséquent, $\scriptstyle\ \mathbb{E}[T]=+\infty.\$