next up previous contents
Next: About this document ... Up: Introduction aux processus stochastiques Previous: Chaînes de Markov absorbantes   Contents


Chaînes de Markov ergodiques


\begin{definition}[Cha\^\i ne de Markov ergodique] Une cha\^\i ne de Markov est ... ...ent positifs. Une cha\^\i ne r\'eguli\\lq ere est donc ergodique. \end{definition}

La particularité des chaînes régulières est que l'on peut aller de n'importe quel état vers n'importe quel autre état en un nombre fixé $ k$ de pas, où $ k$ est indépendant de l'état de départ. Pour les chaînes ergodiques, on demande simplement que tout état soit atteignable depuis tout autre, mais le nombre de pas n'est pas nécessairement fixé.

\begin{figure}{\small {\bf Figure 3.8. } La cha\^\i ne de Markov associ\'ee au mod\\lq ele d'Ehrenfest.}\end{figure}


\begin{example}[Mod\\lq ele d'Ehrenfest] Quatre boules sont r\'eparties sur deux ur... ...'ement $(P^n)_{ij}$\ est nul chaque fois que $i+j+n$\ est impair. \end{example}

Nous allons d'abord étudier de plus près les chaînes régulières, dont le comportement asymptotique est plus simple. En particulier, la suite des puissances $ P^n$ de leur matrice de transition converge toujours vers une matrice particulière, dont toutes les lignes sont égales.


\begin{theorem} Soit $P$\ la matrice de transition d'une cha\^\i ne de Markov r\... ...\;, \end{equation}o\\lq u tous les $w_i$\ sont strictement positifs. \end{theorem}

D´EMONSTRATION. Si la chaîne n'a qu'un état, le résultat est immédiat, donc nous pouvons admettre que $ m\geqs 2$. Nous pouvons supposer que tous les éléments de $ P^k$ sont positifs pour $ k=1$, sinon il suffit de considérer la chaîne dont la matrice de transition est $ P^k$ au lieu de $ P$. Soit $ d>0$ le plus petit élément de $ P$. Alors $ d\leqs 1/2$, puisque $ md\leqs 1$. Soit $ y$ un vecteur colonne tel que

$\displaystyle 0 \leqs m_0 \leqs y_i \leqs M_0 \qquad \forall i\in\set{1,\dots,m}\;.$ (3.53)

Soit $ z=Py$. La plus grande valeur possible d'une composante $ z_j$ de $ z$ est obtenue si $ y^T=(m_0,M_0,\dots,M_0)$ et $ p_{k1}=d$. Dans ce cas, la somme des $ m-1$ derniers éléments de la ligne $ j$ de $ P$ vaut $ 1-d$, et par conséquent $ z_j = dm_0 + (1-d) M_0$. On a donc nécessairement

$\displaystyle z_j \leqs dm_0 + (1-d) M_0 \bydef M_1 \qquad \forall j\in\set{1,\dots,m}\;.$ (3.54)

Un raisonnement similaire montre que

$\displaystyle z_j \geqs dM_0 + (1-d) m_0 \bydef m_1 \qquad \forall j\in\set{1,\dots,m}\;.$ (3.55)

Par conséquent, nous avons $ m_1\leqs z_j\leqs M_1$, avec

$\displaystyle M_1 - m_1 = (1-2d) (M_0-m_0)\;.$ (3.56)

De plus, on voit facilement que $ m_1\geqs m_0$ et $ M_1\leqs M_0$. Après $ n$ itérations, les composantes de $ P^n y$ seront comprises entre des nombres $ m_n$ et $ M_n$, satisfaisant

$\displaystyle M_n - m_n = (1-2d)^n (M_0-m_0)$ (3.57)

et

$\displaystyle m_0 \leqs m_n \leqs M_n \leqs M_0\;.$ (3.58)

Les suites $ \set{m_n}_{n\geqs1}$ et $ \set{M_n}_{n\geqs1}$ sont donc adjacentes, et convergent vers une même limite $ u$. On a donc

$\displaystyle \lim_{n\to\infty} P^n y = \begin{pmatrix}u \\ \vdots \\ u \end{pmatrix}\;,$ (3.59)

où $ u$ dépend de $ y$. Appliquons cette relation sur les vecteurs de base $ e_1,\dots,e_m$. Il existe des nombres $ w_i$ tels que

$\displaystyle \lim_{n\to\infty} P^n e_i = \begin{pmatrix}w_i \\ \vdots \\ w_i \end{pmatrix}$ (3.60)

pour chaque $ i$. Or $ P^n e_i$ est la $ i$-ème colonne de $ P^n$, nous avons donc prouvé la relation (3.5.2). Par ailleurs, comme dans le cas $ y=e_i$ on a $ m_0=0$ et $ M_0=1$, la relation (3.5.5) donne $ m_1\geqs d$, donc $ w_j\geqs d$. Par conséquent, tous les $ w_j$ sont strictement positifs. $ \qedsymbol$

L'interprétation des grandeurs $ w_1,\dots,w_m$ est la suivante: On a

$\displaystyle \lim_{n\to\infty} \probin{i}{X_n=j} = \lim_{n\to\infty} (P^n)_{ij} = w_j\;.$ (3.61)

La probabilité que la chaîne de Markov se trouve dans l'état $ j$ tend donc vers $ w_j$ lorsque le temps tend vers l'infini, indépendamment de l'état de départ.

Pour déterminer les $ w_j$, il n'est pas nécessaire de calculer $ P^n$ explicitement. En effet, le résultat suivant montre que $ w$ est un vecteur propre (à gauche) de $ P$. On peut donc le calculer en résolvant un système linéaire.


\begin{theorem} Soit $P$\ la matrice de transition d'une cha\^\i ne de Markov r\... ...in{equation} \lim_{n\to\infty} vP^n = w\;. \end{equation}\end{enum}\end{theorem}

D´EMONSTRATION.
\begin{enum} \item Comme $P^n\to W$\ et $P^{n+1}\to WP$\ pour $n \to\infty$, on ... ...\\ \vdots \\ w \end{pmatrix}= \sum_{i=1}^m v_i w = w\;. \end{equation}\end{enum}
$ \qedsymbol$

L'équation $ wP=w$ a une interprétation importante. Supposons qu'à un instant $ k$, on ait $ \prob{X_k=i}=w_i$ pour tout $ i$. À l'instant $ k+1$ on aura

$\displaystyle \prob{X_{k+1}=j} = \sum_{i=1}^m w_i P_{ij} = (wP)_j = w_j\;,$ (3.62)

ce qui signifie que $ X_{k+1}$ et $ X_k$ ont la même loi.


\begin{definition}[Distribution stationnaire] Le vecteur $w=(w_1,\dots,w_m)$\ te... ...tion aux valeurs propres $wP=w$telle que $\sum_{i=1}^m w_i=1$. \end{definition}


\begin{example} % latex2html id marker 4161Dans l'Exemple~\ref{ex_markov1} du ... ...cha\^\i ne. On v\'erifie que l'on a bien $wP=w$\ et $w_1+w_2=1$. \end{example}

Si la chaîne de Markov est ergodique mais non régulière, la suite des $ P^n$ ne tend en général pas vers une matrice constante. Par exemple, les $ P^n$ peuvent osciller entre plusieurs valeurs. Cependant, certaines propriétés du Théorème 3.5.4 restent vraies pour les chaînes ergodiques générales.


\begin{prop} Soit $P$\ la matrice de transition d'une cha\^\i ne de Markov ergod... ...ite de $P$\ de valeur propre $1$\ est colin\'eaire \\lq a $c$. \end{enum}\end{prop}

D´EMONSTRATION. Considérons la matrice

$\displaystyle Q = \frac12 \bigbrak{I+P}\;.$ (3.63)

On vérifie facilement que c'est une matrice stochastique. Soit $ k$ le nombre maximal de pas nécessaires pour joindre deux états quelconques de la chaîne. Considérons la matrice

$\displaystyle Q^k = I + \binom{k}{1}P + \binom{k}{2}P^2 + \dots + \binom{k}{k-1}P^{k-1} + P^k\;.$ (3.64)

Pour tout $ (i,j)$, il existe au moins une puissance $ \ell$ de $ P$ telle que $ (P^\ell)_{ij}$ soit strictement positif. Comme tous les autres éléments sont positifs ou nuls, la matrice $ Q^k$ n'a que des éléments strictement positifs, et par conséquent $ Q$ est la matrice de transition d'une chaîne régulière. On peut donc appliquer le Théorème 3.5.4, pour obtenir l'existence d'un vecteur $ w$ tel que $ wQ=w$. Mais ceci implique

$\displaystyle \frac12 \bigbrak{w+wP} = w\;,$ (3.65)

donc $ wP=w$. Les autres points se démontrent de la même manière. $ \qedsymbol$

Nous appellerons encore dans le cas général distribution stationnaire l'unique vecteur $ w$ tel que $ wP=w$ et $ \sum_{i=1}^m w_i=1$. Ce vecteur satisfait toujours la relation (3.5.18).


\begin{example} % latex2html id marker 4206Revenons au mod\\lq ele d'Ehrenfest du... ...\lq a des mod\\lq eles d'Ehrenfest avec un nombre arbitraire de boules. \end{example}

On sait déterminer d'autres propriétés d'une chaîne de Markov que son comportement asymptotique. Une quantité importante est la fréquence moyenne de passage dans les différents états de la chaîne.


\begin{definition}[Temps de premier passage et de r\'ecurrence] Soit une cha\^\i... ...est la\/ \defwd{matrice de r\'ecurrence moyenne}\/. \end{itemiz}\end{definition}

Une première méthode de calculer $ m_{ij}$ est la suivante. On modifie la matrice de transition $ P$ en rendant l'état $ j$ absorbant, c'est-à-dire que l'on remplace $ P_{jj}$ par $ 1$, et tous les autres éléments de la ligne $ j$ par 0. La chaîne ainsi modifiée est alors absorbante. Le temps de premier passage moyen $ m_{ij}$ est alors égal au temps d'absorption $ t_i$ du Théorème 3.4.6. Cette méthode est néanmoins assez fastidieuse à mettre en oeuvre, et nous allons introduire une méthode plus efficace pour calculer $ M$.


\begin{theorem} Soit $P$\ la matrice de transition d'une cha\^\i ne ergodique. ... ...a $i$-\\lq eme composante de la distribution stationnaire. \end{enum}\end{theorem}

D´EMONSTRATION.
\begin{enum} \item Pour $i\neq j$, on a $\probin{i}{\tau_{ij}=1}=p_{ij}$, donc ... ...\\lq a la fois la positivit\'e des $w_i$\ et la relation~\eqref{cme16}. \end{enum}
$ \qedsymbol$


\begin{example} Les temps de r\'ecurrence moyens du mod\\lq ele d'Ehrenfest sont do... ...site $0$, contre seulement $8/3$\ entre deux visites au site $2$. \end{example}

L'équation (3.5.31) ne permet pas encore de calculer $ M$, car $ I-P$ n'est pas inversible puisque $ P$ admet la valeur propre $ 1$. Il s'avère cependant que $ I-P+W$ est inversible, et que son inverse permet de calculer les éléments de matrice de $ M$.


\begin{theorem} Soit $P$\ la matrice de transition d'une cha\^\i ne de Markov er... ...ion} m_{ij} = \frac{z_{jj}-z_{ij}}{w_j}\;. \end{equation}\end{enum}\end{theorem}

D´EMONSTRATION.
\begin{enum} \item Soit $x$\ un vecteur colonne tel que $(I-P+W)x=0$. Alors \be... ..._j\;, \end{equation}ce qui prouve~\eqref{cme21} puisque $r_j=1/w_j$. \end{enum}
$ \qedsymbol$


\begin{remark} La relation~\eqref{cme20} a l'interpr\'etation suivante en termes... ...w$, $Z$\ agit trivialement dans le sous-espace engendr\'e par $w$. \end{remark}


\begin{example} % latex2html id marker 4423Dans le cas de la cha\^\i ne \\lq a de... ...r \lq\lq succ\\lq es\rq\rq\ du passage de l'\'etat 1 \\lq a l'\'etat 2. \end{example}

Finalement, on peut également caractériser la fréquence des passages en un état donné. Le nombre de passages en $ j$ parmi $ n$ itérations est donné par la variable aléatoire

$\displaystyle S^j_n = \sum_{k=0}^{n-1} \indexfct{X_k=j}\;.$ (3.66)

La variable $ \frac1n S^j_n$ donne donc la proportion du temps passée dans l'état $ j$.


\begin{theorem} On a \begin{align} \lim_{n\to\infty} \frac1n \expecin{i}{S^j_n}... ...} = \frac1{\sqrt{2\pi}} \int_a^b \e^{-x^2/2}\,\6x\;. \end{equation}\end{theorem}

D´EMONSTRATION. Nous allons nous borner à prouver la relation (3.5.57). Un calcul direct montre que $ PW=W$, et on a donc

$\displaystyle (I+P+P^2+\dots+P^{n-1}) (I-P+W)$ $\displaystyle = I - P^n + W + PW + \dots + P^{n-1}W$    
  $\displaystyle = I - P^n + nW\;.$ (3.67)

En multipliant à droite par $ Z$, il vient

$\displaystyle I+P+P^2+\dots+P^{n-1}$ $\displaystyle = (I - P^n + nW)Z$    
  $\displaystyle = (I - P^n)Z + nW\;.$ (3.68)

Or l'espérance de $ S^j_n$ est donnée par

$\displaystyle \expecin{i}{S^j_n}$ $\displaystyle = \sum_{k=0}^{n-1} \expecin{i}{\indexfct{X_k=j}} = \sum_{k=0}^{n-1} \probin{i}{X_k=j} = \sum_{k=0}^{n-1} (P^k)_{ij}$    
  $\displaystyle = \biggpar{\sum_{k=0}^{n-1} P^k}_{ij} = \bigpar{(I-P^n)Z+nW}_{ij} = z_{ij} - (P^nZ)_{ij} + nw_j\;.$    

On a donc

$\displaystyle \frac1n \expecin{i}{S^j_n} = w_j + \frac1n \bigbrak{z_{ij} - (P^nZ)_{ij}}\;.$ (3.69)

Comme les éléments de $ P^n$ sont compris entre 0 et $ 1$, cette expression converge vers $ w_j$ lorsque $ n$ tend vers l'infini. $ \qedsymbol$

\begin{figure}{\small {\bf Figure 3.9. } La cha\^\i ne de Markov associ\'ee au mod\\lq ele d'Ehrenfest \\lq a deux boules.}\end{figure}


\begin{example} Consid\'erons un mod\\lq ele d'Ehrenfest \\lq a deux boules, dont le g... ...s, ce qui est \'evident lorsqu'on regarde le graphe du processus. \end{example}

Nils Berglund
FRUMAM, CPT-CNRS LUMINY
Case 907, 13288 Marseille Cedex 9, France
et
PHYMAT, UNIVERSITÉ DE TOULON
E-mail address: berglund@cpt.univ-mrs.fr

next up previous contents
Next: About this document ... Up: Introduction aux processus stochastiques Previous: Chaînes de Markov absorbantes   Contents
berglund 2005-11-28