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

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.

Sommaire

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.
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.\
  • Portail des probabilités et des statistiques Portail des probabilités et des statistiques

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Récurrence et transience d'une chaîne de Markov de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Probabilité stationnaire d'une chaîne de Markov — La probabilité stationnaire d une chaîne de Markov s interprète usuellement comme la fraction du temps passé en chaque état de l espace d états de cette chaîne de Markov, asymptotiquement. En effet, une version de la loi forte des grands nombres… …   Wikipédia en Français

  • Chaine De Markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaine de Markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaine de markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaîne De Markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

  • Chaîne de Markov à espace d'états discret — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaîne de markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

  • Chaîne de Markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

  • Chaînes de Markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Loi de Bernoulli — Pour les articles homonymes, voir Théorème de Bernoulli. Bernoulli Paramètres (nombre réel) Support …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”