Probabilité stationnaire d'une chaîne de Markov

La probabilité stationnaire ${\displaystyle \pi =(\pi _{i})_{i\in E}}$ d'une chaîne de Markov ${\displaystyle X=(X_{n})_{n\geq 0}}$ s'interprète usuellement comme la fraction du temps passé en chaque état ${\displaystyle i}$ de l'espace d'états ${\displaystyle E}$ de cette chaîne de Markov, asymptotiquement. En effet, une version de la loi forte des grands nombres pour les chaînes de Markov stipule que :

${\displaystyle \pi _{i}\ =\ \lim _{n}\ {\frac {1_{X_{0}=i}+1_{X_{1}=i}+\dots +1_{X_{n-2}=i}+1_{X_{n-1}=i}}{n}}\ =\ \lim _{n}\ {\frac {S_{n}(i)}{n}},}$

presque sûrement, sous certaines hypothèses détaillées plus bas. La variable aléatoire ${\displaystyle S_{n}(i)}$ s'interprète comme le temps passé en ${\displaystyle i}$ lors des ${\displaystyle n}$ premiers pas de la chaîne de Markov ${\displaystyle X.}$ La fraction ${\displaystyle S_{n}(i)/n}$ est donc la fraction de temps passé en l'état ${\displaystyle i}$ pendant les ${\displaystyle n}$ premiers pas de la chaîne de Markov. La convergence de cette fraction lorsque ${\displaystyle n}$ tend vers l'infini n'est pas un résultat anodin. On trouvera une discussion plus poussée sur le temps de séjour sur la page Récurrence et transience d'une chaîne de Markov.

Définition

Existence et unicité : cas irréductible

L'existence d'une probabilité stationnaire ${\displaystyle \pi }$ pour une chaîne de Markov irréductible est liée aux propriétés du temps de retour en ${\displaystyle i,}$ et en particulier aux propriétés de récurrence de l'état ${\displaystyle i.}$

Rappelons que 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 ${\displaystyle \forall i\in E,\quad \mathbb {P} \left(X_{0}=i\right)=\mu _{i},}$ alors les probabilités sont notées ${\displaystyle \mathbb {P} _{\mu }\left(\dots \right),}$ et les espérances sont notées ${\displaystyle \mathbb {E} _{\mu }\left[\dots \right].}$ En particulier, si ${\displaystyle \mathbb {P} \left(X_{0}=j\right)=1,}$ on dit que la chaîne de Markov part de ${\displaystyle j,}$ les probabilités sont notées ${\displaystyle \mathbb {P} _{j}\left(\dots \right),}$ et les espérances sont notées ${\displaystyle \mathbb {E} _{j}\left[\dots \right].}$ Ci-dessus, dans la notation ${\displaystyle \mathbb {E} _{i},}$ l'indice ${\displaystyle i}$ signifie qu'on calcule l'espérance pour la chaîne de Markov partant de ${\displaystyle i,}$ i.e. de loi initiale définie par ${\displaystyle \mathbb {P} (X_{0}=i)=1.}$ Ainsi ${\displaystyle \mathbb {E} _{i}\left[T_{i}\right]}$ s'interprète comme l'intervalle de temps "typique" entre deux passages consécutifs à l'état ${\displaystyle i.}$

La relation entre existence et unicité des probabilités stationnaires, classifications des états de la chaîne de Markov et récurrence positive est traité dans un cadre complètement général à la section Existence et unicité. Cependant les théorèmes ci-dessus, valables uniquement pour les chaînes de Markov irréductibles, sont suffisants dans un grand nombre d'exemples.

Loi forte des grands nombres

Dans le cas d'une chaîne de Markov irréductible et récurrente positive, la loi forte des grands nombres est en vigueur : la moyenne d'une fonction ${\displaystyle f}$ sur les instances de la chaîne de Markov est égale à sa moyenne selon sa probabilité stationnaire. Plus précisément, sous l'hypothèse

${\displaystyle \sum _{i\in E}|f(i)|\,\pi _{i}\ <+\infty ,}$

on a presque sûrement :

${\displaystyle \lim _{n}\;{\frac {1}{n}}\;\sum _{k=0}^{n-1}f(X_{k})\ =\ \sum _{i\in E}f(i)\,\pi _{i}\ =\ \pi f.}$

La moyenne de la valeur des instances est donc, sur le long terme, égale à l'espérance de la probabilité stationnaire. En particulier, cette équivalence sur les moyennes s'applique si ${\displaystyle f}$ est la fonction indicatrice d'un sous-ensemble ${\displaystyle A}$ de l'espace des états :

${\displaystyle \lim _{n}\;{\frac {1}{n}}\;\sum _{k=0}^{n-1}1_{A}(X_{k})\ =\ \sum _{i\in A}\ \pi _{i}\ =\ \pi (A).}$

Cela permet d'approcher la probabilité stationnaire par un histogramme (la distribution empirique) construit à partir d'une séquence particulière.

Ergodicité

En particulier, si le processus est construit en prenant la probabilité stationnaire comme loi initiale, le shift ${\displaystyle \theta }$ défini par

${\displaystyle x=(x_{0},x_{1},x_{2},\dots )\in E^{\mathbb {N} }\quad \rightarrow \quad \theta \,x=(x_{1},x_{2},x_{3},\dots )}$

préserve la mesure, ce qui fait de la chaîne de Markov un système dynamique. La loi forte des grands nombres entraine alors que la chaîne de Markov est un système dynamique ergodique. L'ergodicité est à la fois plus forte que la loi forte des grands nombres car on peut en déduire, par exemple, que ${\displaystyle {\frac {1}{n}}\;\sum _{k=0}^{n-1}f(X_{k},X_{k+1}),}$ a pour limite presque sûre ${\displaystyle \sum _{i,j\in E}f(i,j)\,\pi _{i}p_{i,j},}$ mais elle est aussi plus faible car elle réclame en principe la stationnarité de la chaîne de Markov, ce qui n'est pas le cas de la loi forte des grands nombres.

Convergence vers la loi stationnaire

Convergence de la loi marginale

Si la chaîne de Markov est irréductible, récurrente positive et apériodique, alors ${\displaystyle P^{k}}$ converge vers une matrice dont chaque ligne est l'unique distribution stationnaire ${\displaystyle \pi .}$ En particulier, la loi ${\displaystyle \mu _{n}}$ de ${\displaystyle X_{n}}$ converge vers ${\displaystyle \pi }$ indépendamment de la loi initiale ${\displaystyle \mu _{0}.}$ Dans le cas d'un espace d'état fini, cela se prouve par le théorème de Perron-Frobenius.

Typiquement, par exemple dans le cas d'une chaîne de Markov à espace d'états fini irréductible et apériodique, la convergence est exponentiellement rapide, i.e. pour une norme quelconque, on peut trouver ${\displaystyle K>0}$ et ${\displaystyle \alpha \in ]0,1[}$ tels que

${\displaystyle \Vert \mu _{n}-\pi \Vert \leq K\ \alpha ^{n}.}$

On trouve plus loin dans l'article une démonstration de cette décroissance exponentielle dans le cas particulier des chaînes réversibles.

Convergence de la mesure empirique

Si la chaîne de Markov est irréductible et récurrente positive alors, par suite de la loi forte des grands nombres, la mesure empirique de la chaîne de Markov,

${\displaystyle {\tfrac {1}{n}}\quad \sum _{k=0}^{n-1}\,\delta _{X_{k}}\quad =\quad {\tfrac {1}{n}}\quad \sum _{i\in E}\ S_{n}(i)\,\delta _{i},}$

converge vers l'unique distribution stationnaire. Typiquement, par exemple dans le cas d'une chaîne de Markov à espace d'états fini irréductible et récurrente positive, la convergence est, en un certain sens, en ${\displaystyle {\mathcal {O}}(1/{\sqrt {n}}).}$ Cela permet d'approcher la probabilité stationnaire par un histogramme construit à partir d'une séquence particulière. Nota: alors que la loi de ${\displaystyle X_{n},}$ notée ${\displaystyle \mu _{n}}$ ci-dessus, est une mesure de probabilité fixée, la loi empirique est, elle, une mesure de probabilité aléatoire, ou bien, si l'on veut, une variable aléatoire à valeurs dans les mesures de probabilité.

Chaînes réversibles

Critères

La matrice ${\displaystyle (q_{i,j})_{i,j\in E}}$ est l'adjointe de la matrice ${\displaystyle (p_{i,j})_{i,j\in E}}$ pour le produit scalaire défini par

${\displaystyle \langle x,y\rangle \ =\ \sum _{i\in E}\pi _{i}x_{i}y_{i}.}$

Interprétation

Si une variable aléatoire ${\displaystyle X=(X_{t})_{t\in \mathbb {Z} }}$ à valeur dans ${\displaystyle E^{\mathbb {Z} }}$ satisfait, pour tout ${\displaystyle (t,n)\in \mathbb {Z} \times \mathbb {N} ,}$ et toute suite ${\displaystyle (i_{0},i_{1},\dots ,i_{n})\in E^{n+1},}$

${\displaystyle \mathbb {P} \left((X_{t},X_{t+1},\dots ,X_{t+n})=(i_{0},i_{1},\dots ,i_{n})\right)=\pi _{i_{0}}p_{i_{0},i_{1}}\dots p_{i_{n-1},i_{n}}}$

on dit que X est une chaîne de Markov stationnaire, de matrice de transition ${\displaystyle (p_{i,j})_{i,j\in E},\qquad }$ et de loi stationnaire ${\displaystyle (\pi _{i})_{i\in E}.}$ En effet :

• cela définit une et une seule mesure de probabilité sur ${\displaystyle E^{\mathbb {Z} }}$ ;
• X possède la propriété de Markov faible ;
• stationnarité : la suite ${\displaystyle X^{(s)}=(X_{t}^{(s)})_{t\in \mathbb {Z} }}$ (définie par ${\displaystyle X_{t}^{(s)}=X_{s+t}}$) a même loi que la suite X, pour tout entier relatif s.

Renversons le cours du temps, i.e. considérons la suite ${\displaystyle Y=(Y_{t})_{t\in \mathbb {Z} }}$ définie par

${\displaystyle Y_{t}=X_{-t}.}$

On a alors

Exemples

Marche aléatoire sur un graphe

Soit G un graphe connexe, fini, simple et sans boucles. Par définition,

${\displaystyle \forall i,j\in E=V(G),{\text{ tels que }}i\sim j,\qquad p_{i,j}={\frac {1}{d_{i}}},}$

i.e. à partir de ${\displaystyle i,}$ on saute vers un de ses ${\displaystyle d_{i}}$ voisins choisis au hasard (avec équiprobabilité), ${\displaystyle d_{i}}$ désignant le degré de ${\displaystyle i}$ dans le graphe ${\displaystyle G.}$ La connexité de ${\displaystyle G}$ entraîne l'irréductibilité de la marche aléatoire et l'unicité de la probabilité stationnaire. On remarque que ${\displaystyle \mu _{i}=d_{i}\qquad }$ satisfait le critère 2, or ${\displaystyle \Vert \mu \Vert =2\vert E(G)\vert ,\qquad }$ i.e. ${\displaystyle \Vert \mu \Vert \qquad }$ est deux fois le nombre d'arêtes de ${\displaystyle G.\qquad }$ Ainsi ${\displaystyle \pi _{i}=d_{i}/(2\vert E(G)\vert )\qquad }$ est l'unique probabilité stationnaire : on passe d'autant plus de temps en un sommet que son degré est élevé, et ce temps de séjour asymptotique est proportionnel au degré du sommet, avec coefficient de proportionnalité ${\displaystyle 1/(2\vert E(G)\vert ).\qquad }$ Un exemple amusant est la marche aléatoire d'un cavalier sur un échiquier.

Marche du cavalier sur l'échiquier

C'est un cas particulier de l'exemple ci-dessus, où ${\displaystyle 2\leq d_{i}\leq 8,\ \vert V(G)\vert =|E|=64,}$ et ${\displaystyle \Vert \mu \Vert =2\vert E(G)\vert =336.}$ Ainsi

${\displaystyle \pi _{\text{coin SO}}={\frac {2}{336}}\quad {\text{et}}\quad \mathbb {E} _{\text{coin SO}}\left[T_{\text{coin SO}}\right]=168,}$

c'est-à-dire qu'il faut en moyenne 168 sauts à un cavalier partant du coin Sud-Ouest pour y retourner. On peut étudier de la même manière les autres pièces du jeu d'échecs.

Modèle des urnes d'Ehrenfest

Deux chiens (disons A et B) se partagent N puces de la manière suivante : à chaque instant t entier, une des N puces est tirée au hasard et change alors de chien. Notons X_t le nombre de puces infestant A au temps t : X=(X_t )_t≥0 est une chaîne de Markov en vertu du critère fondamental. Supposons que dans l'état initial, le chien A n'a aucune puce.

Cette chaîne de Markov est clairement irréductible. Si on la suppose réversible, on doit avoir

${\displaystyle {\frac {\pi _{k+1}}{\pi _{k}}}\ =\ {\frac {p_{k,k+1}}{p_{k+1,k}}}\ =\ {\frac {N-k}{k+1}}\ =\ {\frac {N \choose k+1}{N \choose k}},}$

ce qui suggère une probabilité stationnaire, π = (π_k )_0≤k≤N , proportionnelle aux coefficients binomiaux. La seule loi de probabilité proportionnelle aux coefficients binomiaux est la loi binomiale de paramètre 1/2 (et N). La chaîne est donc bien réversible, et le temps écoulé entre deux passages par l'état initial est

${\displaystyle \mathbb {E} _{0}\left[T_{0}\right]\ =\ {\frac {1}{\pi _{0}}}\ =\ 2^{N}.}$

Cet exemple illustre la réponse de Boltzmann à Zermelo : Zermelo observait^[1] une contradiction entre le théorème de récurrence de Poincaré^[2],[3], selon lequel un système dynamique repasse infiniment souvent par un état donné, et le Théorème H de Boltzmann. La réponse de Boltzmann^[4] consiste à estimer le temps de récurrence moyen : pour un gaz macroscopique contenant ${\displaystyle N\gg 1}$ molécules, Boltzmann estime celui-ci d'ordre ${\displaystyle 10^{N}}$, une durée qui est largement supérieure à l'âge de l'univers^[5] lorsque ${\displaystyle N\sim {\mathcal {N}}_{A}=6.02\ 10^{+23}}$ ; les récurrences sont donc invisibles à notre échelle.

Théorie spectrale (cas fini)

On suppose

• l'espace d'états E fini, à N éléments,
• la chaîne réversible,
• chaque π_i strictement positif.

Alors^[6]

Convergence pour la distance du χ²

Si la chaîne est irréductible et apériodique, 1 est valeur propre de P de multiplicité 1, et les autres valeurs propres sont en valeur absolue strictement inférieures à 1. Si on note α le maximum de ces valeurs absolues et si on note μ_n la loi de la chaîne au temps n, on en déduit^[6] que

${\displaystyle \langle \mu _{n}-\pi ,\mu _{n}-\pi \rangle \ \leq \ C\,\alpha ^{2n}.}$

Si l'erreur relative, au site i, est définie par

${\displaystyle \varepsilon _{i}={\frac {\mu _{n,i}-\pi _{i}}{\pi _{i}}},}$

alors la distance du χ² entre μ_n et π s'écrit

${\displaystyle \langle \mu _{n}-\pi ,\mu _{n}-\pi \rangle \ =\ \sum _{i=1}^{N}\,\pi _{i}\,\varepsilon _{i}^{2}.}$

Ainsi les erreurs relatives sont moins pénalisantes si elles affectent les états les moins probables mais sont, toutefois, plus pénalisantes que si on utilise la distance euclidienne classique :

${\displaystyle \Vert \mu _{n}-\pi \Vert ^{2}\ =\ \sum _{i=1}^{N}\,(\mu _{n,i}-\pi _{i})^{2}\ =\ \sum _{i=1}^{N}\,\pi _{i}^{2}\,\varepsilon _{i}^{2}.}$

Théorie spectrale (cas du modèle des urnes d'Ehrenfest)

Ainsi, il y a convergence vers la loi stationnaire uniquement si la loi initiale μ est orthogonale à e_N , i.e. si

${\displaystyle \sum _{i=0}^{N}\,(-1)^{i}\,\mu _{i}=0.}$

En ce cas, il existe une constante C_N telle que, pour tout entier naturel k, on ait :

${\displaystyle \Vert \mu .P^{k}-\pi \Vert \leq C_{N}\,\left(1-{\tfrac {2}{N}}\right)^{k}.}$

Existence et unicité

Discuter l'existence et l'unicité d'une probabilité stationnaire ${\displaystyle \pi }$ telle que ${\displaystyle \pi _{i}>0}$ amène à discuter les propriétés du graphe de la chaîne de Markov et la classification de ses états, amène aussi à étudier les propriétés de la variable aléatoire appelée "temps de retour" en ${\displaystyle i,}$ et souvent notée ${\displaystyle T_{i}.}$

En particulier, si une chaîne de Markov possède au moins un état récurrent positif, alors il existe une probabilité stationnaire.

Ce théorème vaut en particulier pour les chaînes de Markov irréductibles, puisque ces dernières possèdent une seule classe (qui est donc nécessairement une classe finale) ; les chaînes de Markov irréductibles vérifient en particulier ${\displaystyle C=E.}$

À voir

Notes

Bibliographie

• Laurent Saloff-Coste, Lectures on finite Markov chains, Lectures on Probability Theory and Statistics, 301-413. Lecture Notes in Math. n° 1665. Springer (1997).
• Jim Norris, Markov chains.
• Samuel Karlin et Howard E. Taylor, A Second Course in Stochastic Processes.

Pages liées

• Chaîne de Markov
• Modèle des urnes d'Ehrenfest
• Théorème H
• Distribution quasi-stationnaire

• Portail des probabilités et de la statistique