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

Un état $i$ d'une chaîne de Markov $X=(X_n{)}_{n\ge 0}$ est dit récurrent (ou persistant) si une trajectoire « typique » de la chaîne de Markov passe par $i$ une infinité de fois, sinon l'état $i$ est dit transitoire (ou transient par calque de l'anglais). Ces propriétés de transience ou de récurrence sont souvent partagées par tous les états de la chaîne $X,$ par exemple quand la chaîne $X$ est irréductible : en ce cas, si tous ses états sont récurrents, la chaîne de Markov est dite 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 : Modèle:Théorème

Récurrence et transience (définition informelle)

Informellement, pour une chaîne de Markov irréductible, un état $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 $i$ vaut 1, et l'état $i$ est dit récurrent,
• soit cette probabilité vaut 0, auquel cas $i$ est dit transient.
• les états récurrents (ceux pour lesquels $\underset{n}{\lim }{S}_n(i)=+\mathrm{\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 $S_n(i)\le n,$ mais $S_n(i)$ ne doit pas être trop petit devant $n$:

$\underset{n}{\lim }\frac{S_n(i)}{n}={\pi }_i>0;$

en notation de Landau, $S_n(i)\in \mathrm{\Theta }(n).$ Cela entraîne que les instants de passage en $i$ sont, en un certain sens, régulièrement espacés, à une distance $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 :

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

i.e. $S_n(i)\to +\mathrm{\infty },$ mais $S_n(i)\in o(n).$ Le système passe infiniment souvent par l'état $i,$ mais les instants de passage en $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 $({\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. Modèle:Article détaillé

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 $\mathrm{\forall }i\in E,\mathbb{P}(X_0=i)={\mu }_i,$ alors les probabilités sont notées ${\mathbb{P}}_{\mu }(\dots ),$ et les espérances sont notées ${𝔼}_{\mu }[\dots ];$
• en particulier, si $\mathbb{P}(X_0=j)=1,$ on dit que la chaîne de Markov part de $j,$ les probabilités sont notées ${\mathbb{P}}_j(\dots ),$ et les espérances sont notées ${𝔼}_j[\dots ].$

Exemples

Marche aléatoire sur un groupe fini

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

Modèle:Exemple Modèle:Exemple Plus généralement, tous les états d'une marche aléatoire sur un groupe fini $G$ sont récurrents positifs, car la loi uniforme discrète sur $G$ est une probabilité stationnaire, indépendamment du pas de la marche : en effet, la matrice de transition $P$ d'une marche aléatoire sur un groupe discret est bistochastique (i.e. non seulement la somme des termes d'une ligne vaut 1, quelle que soit la ligne, mais la somme des termes d'une colonne de $P$ vaut 1, quelle que soit la colonne). Si tous les coefficients du vecteur ligne $x$ valent 1, on vérifie alors sans peine que $xP=x.$ Ainsi la mesure uniforme, qui est proportionnelle à $x,$ est stationnaire.

Marche aléatoire simple sur les entiers relatifs

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

$\mathrm{\forall }k\ge 0,p_{0,0}^{(2k)}=(\genfrac{}{}{0ex}{}{2k}{k})p^k(1-p{)}^k\sim \frac{(4p(1-p){)}^k}{\sqrt{k\pi }},$

alors que $p_{0,0}^{(2k+1)}=0.$

Marche aléatoire biaisée

• Si on observe la forme de la fraction ci-dessus, comme $\{4p(1-p)<1\}\iff \{p\ne 0.5\},$ la marche est transiente si et seulement si $p\ne 0.5,$ en vertu du quatrième critère de transience exprimé dans la partie « Critères de récurrence et de transience ».
• On peut aussi voir que $p\ne 0.5$ entraîne la transience de la chaîne de Markov $X=(X_n{)}_{n\ge 0}$ en construisant cette chaîne à l'aide d'une suite de variables aléatoires i.i.d. $Y=(Y_n{)}_{n\ge 1},$ de la manière suivante : posons

$\begin{array}{cc}{S}_0=0,S_n& =S_{n-1}+Y_{n}n\ge 1\\ & =Y_1+Y_2+\dots +Y_n.\end{array}$

Alors $S=(S_n{)}_{n\ge 0}$ a même loi que $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 $\omega \in \mathrm{\Omega },$

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

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

• Dans le cas où $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 $(n^{-1}{S}_n(\omega ){)}_{n\ge 0}$ vers 0, ce qui n'entraîne pas nécessairement que la suite $(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 $p=0.5$ que dans le cas $p\ne 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(T_i<+\mathrm{\infty })=1\text{ou}{\mathbb{P}}_i(T_i=+\mathrm{\infty })>0.$

En effet

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

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

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

Ainsi

$\begin{array}{cc}\mathbb{P}(T<+\mathrm{\infty })& =\sum _{k\ge 2}\mathbb{P}(T=k)\\ & =G_T(1)\\ & =1-\sqrt{1-4p(1-p)}\\ & =1-|2p-1|\end{array}$

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

Marche aléatoire symétrique

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

$\mathrm{\forall }k\in \mathbb{Z},2{\pi }_k={\pi }_{k-1}+{\pi }_{k+1},$

i.e. si et seulement si les ${\pi }_k$ forment une progression arithmétique :

$\mathrm{\forall }k\in \mathbb{Z},{\pi }_k=ak+b.$

La contrainte de positivité sur les ${\pi }_k$ impose $a=0,b\ge 0,$ i.e. ${\pi }_k$ est une suite constante. Ainsi $\sum _k{\pi }_k$ est infinie ou nulle, suivant la valeur de $b,$ strictement positive ou bien nulle, donc une mesure invariante ne peut en aucun cas être une mesure de probabilité, ce qui fait qu'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, $𝔼[T]=+\mathrm{\infty }.$