Probabilité stationnaire d'une chaîne de Markov

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.

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.

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é.

Théorème — 1. Si ${\displaystyle \mu =(\mu _{i})_{i\in E}}$ est une mesure de masse ${\displaystyle \Vert \mu \Vert }$ finie ${\displaystyle (\Vert \mu \Vert =\sum _{i\in E}\mu _{i}<+\infty )}$ satisfaisant

${\displaystyle \forall i,j\in E,\qquad \mu _{i}p_{i,j}=\mu _{j}p_{j,i},}$

alors ${\displaystyle \pi =\mu /\Vert \mu \Vert }$ est une probabilité stationnaire.

2. Plus généralement, si pour une mesure de masse finie ${\displaystyle \mu =(\mu _{i})_{i\in E}}$ il existe une matrice de transition ${\displaystyle (q_{i,j})_{i,j\in E}}$ satisfaisant

${\displaystyle \forall i,j\in E,\qquad \mu _{i}p_{i,j}=\mu _{j}q_{j,i},}$

alors ${\displaystyle \pi =\mu /\Vert \mu \Vert }$ est une probabilité stationnaire.

3. Si ${\displaystyle \pi }$ est une probabilité stationnaire, associée à la matrice de transition ${\displaystyle (p_{i,j})_{i,j\in E},}$ telle que ${\displaystyle \forall i\in E,\ \pi _{i}>0,}$ alors ${\displaystyle (q_{i,j})_{i,j\in E},}$ définie par

${\displaystyle q_{i,j}={\frac {\pi _{j}p_{j,i}}{\pi _{i}}},}$

est une matrice de transition.

Démonstration

1. et 2. ${\displaystyle {\begin{aligned}(\mu \,P)_{j}&=\sum _{i\in E}\mu _{i}p_{i,j}\\&=\sum _{i\in E}\mu _{j}q_{j,i}\\&=\mu _{j}\sum _{i\in E}q_{j,i}\\&=\mu _{j},\end{aligned}}}$

la dernière égalité découlant de ce qu'une matrice de transition (par exemple ${\displaystyle (q_{i,j})_{i,j\in E}}$) est une matrice stochastique. Donc μ et π sont des vecteurs propres à gauche de P, associés à la valeur propre 1, CQFD. (Nota : 1. est un cas particulier de 2.) 3. Vérifions que ${\displaystyle (q_{i,j})_{i,j\in E}}$) est une matrice stochastique : pour tout i dans E,

${\displaystyle {\begin{aligned}\sum _{j\in E}q_{i,j}&=\sum _{j\in E}{\frac {\pi _{j}p_{j,i}}{\pi _{i}}}\\&={\frac {1}{\pi _{i}}}\ \sum _{j\in E}\pi _{j}p_{j,i}\\&=1.\end{aligned}}}$

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}.}$

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

Démonstration

${\displaystyle \pi _{i_{n}}p_{i_{n},i_{n-1}}\dots p_{i_{1},i_{0}}=\pi _{i_{0}}q_{i_{0},i_{1}}\dots q_{i_{n-1},i_{n}},}$

or

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

Graphe de la marche du cavalier sur l'échiquier (quart Sud-Ouest), et degré des sommets

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.

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.

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.

On suppose

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

Alors[6]

Théorème — La matrice de transition P est diagonalisable à gauche dans une base orthonormée pour la distance du χ² , i.e. dans une base orthonormée pour la forme bilinéaire

${\displaystyle \langle x,y\rangle \ =\ \sum _{i=1}^{N}\,{\frac {x_{i}\,y_{i}}{\pi _{i}}}.}$

Ses valeurs propres à gauche sont réelles et de valeurs absolues inférieures à 1.

Démonstration

Notons D la matrice diagonale de terme diagonal général ${\displaystyle {\sqrt {\pi _{i}}}.}$ Alors S = D.P.D^-1 est une matrice symétrique, semblable à P. En effet

${\displaystyle S_{i,j}\ =\ {\frac {{\sqrt {\pi _{i}}}\,p_{i,j}}{\sqrt {\pi _{j}}}}\ =\ {\frac {{\sqrt {\pi _{j}}}\,p_{j,i}}{\sqrt {\pi _{i}}}}\ =\ S_{j,i}.}$

En vertu du théorème spectral, on conclut donc que S est diagonalisable en base orthonormée, et n'a que des valeurs propres réelles. Si u et v sont deux vecteurs propres à gauches de S, orthogonaux (i.e. u.^tv = 0 ), alors les vecteurs propres correspondants de P sont x = u.D et y = v.D. On a donc

${\displaystyle 0\ =\ u.^{t}v\ =\ x.D^{-2}.^{t}y\ =\ \sum _{i=1}^{N}\,{\frac {x_{i}\,y_{i}}{\pi _{i}}}.}$

L'encadrement des valeurs propres découle des deux relations :

${\displaystyle u\left({\text{Id}}-DPD^{-1}\right)\,^{t}u\ =\ {\tfrac {1}{2}}\ \sum _{1\leq i,j\leq N}\,\pi _{i}p_{i,j}\,\left({\tfrac {u_{i}}{\pi _{i}}}-{\tfrac {u_{j}}{\pi _{j}}}\right)^{2},}$

et

${\displaystyle u\left({\text{Id}}+DPD^{-1}\right)\,^{t}u\ =\ {\tfrac {1}{2}}\ \sum _{1\leq i,j\leq N}\,\pi _{i}p_{i,j}\,\left({\tfrac {u_{i}}{\pi _{i}}}+{\tfrac {u_{j}}{\pi _{j}}}\right)^{2}.}$

En effet, les termes de droites de ces égalités sont positifs ou nuls. Si λ est une valeur propre quelconque de P, v un vecteur propre à gauche associé, et si on choisit u = vD^-1 , alors les termes de gauche sont ${\displaystyle (1-\lambda )\Vert u\Vert ^{2}}$ et ${\displaystyle (1+\lambda )\Vert u\Vert ^{2},}$ respectivement. D'où l'encadrement annoncé.

Cas d'égalité. Si u est une probabilité stationnaire de la chaîne, alors, dans la première relation ci-dessus, la somme de droite est nulle, donc tous ses termes (qui sont positifs ou nuls) sont nuls. Cela entraine que la fraction u_j /π_j reste constante le long de n'importe quel chemin du graphe de la chaîne. Si la chaîne est irréductible, il suit que u est proportionnelle à π, donc égale à π. Ainsi il existe une seule probabilité stationnaire.

Une discussion analogue concernant la deuxième égalité permet de conclure à l'existence d'un vecteur propre pour la valeur propre -1 si et seulement si la chaîne est de période 2.

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éorème — La matrice de transition P possède N+1 valeurs propres distinctes :

${\displaystyle 1=\lambda _{0}\geq \lambda _{1}\geq \dots \geq \lambda _{k}={\tfrac {N-2k}{N}}\geq \dots \geq \lambda _{N}=-1.}$

Le vecteur e_k défini par

${\displaystyle (1-X)^{k}(1+X)^{N-k}\,=\,\sum _{j=0}^{N}\ e_{k,j}X^{j}}$

est un vecteur propre à gauche de P associé à la valeur propre λ_k .

Démonstration

On considère l'opérateur T défini sur les suites de nombres réels par

${\displaystyle (Tu)_{k}\,=\,{\tfrac {N-k+1}{N}}\,u_{k-1}+{\tfrac {k+1}{N}}\,u_{k+1},\quad k\geq 0,}$

avec la convention u_-1 =0. Supposons que λ soit une valeur propre de T et notons u un vecteur propre associé. Posons

${\displaystyle F(X)\,=\,\sum _{k\geq 0}\,u_{k}X^{k}.}$

Alors on devrait avoir

${\displaystyle {\begin{aligned}\lambda F(X)&=\sum _{k\geq 0}\,\left({\tfrac {N-k+1}{N}}\,u_{k-1}+{\tfrac {k+1}{N}}\,u_{k+1}\right)X^{k}\\&=X\sum _{k\geq 0}\,\,u_{k-1}X^{k-1}-{\tfrac {X^{2}}{N}}\sum _{k\geq 0}\,(k-1)\,u_{k-1}X^{k-2}+\,{\tfrac {1}{N}}\,\sum _{k\geq 0}\,(k+1)\,u_{k+1}X^{k}\\&=XF(X)-{\tfrac {X^{2}}{N}}\,F^{\prime }(X)+\,{\tfrac {1}{N}}\,F^{\prime }(X)\\&=XF(X)+{\tfrac {1-X^{2}}{N}}\,F^{\prime }(X).\end{aligned}}}$

Il faudrait donc (formellement) que

${\displaystyle {\begin{aligned}{\tfrac {2}{N}}\,{\frac {F^{\prime }(X)}{F(X)}}&=2\ {\frac {\lambda -X}{1-X^{2}}}\\&={\frac {\lambda -1}{1-X}}+{\frac {\lambda +1}{1+X}}.\end{aligned}}}$

ou encore que

${\displaystyle F(X)\ =\ C\,(1-X)^{(1-\lambda )N/2}\ (1+X)^{(\lambda +1)N/2}.}$

Par ailleurs, si v=(v₀ ,v₁ , ... ,v_N ) est un vecteur ligne et si u désigne la suite obtenue en complétant v par une suite infinie de 0's, alors

${\displaystyle vP\ =\ Tu,}$

et la série génératrice F associée à u est un polynôme de degré inférieur à N. Ainsi les valeurs de λ pour lesquelles l'expression de F donnée ci-dessus est un polynome (nécessairement de degré N car N est la somme des exposants) sont non seulement des valeurs propres de T, mais aussi des valeurs propres de P. Or si 1-λ est de la forme 2k/N (où k désigne un entier naturel) alors l'exposant de (1-X) est un entier naturel et l'exposant de (1+X) est un entier relatif. Si, de plus, k≤N, alors le deuxième exposant est un entier naturel. Cela fait à P autant de valeurs propres distinctes qu'il y a d'entiers entre 0 et N, soit N+1 valeurs propres, au moins. Mais la matrice P, de dimension N+1, ne peut avoir plus de N+1 valeurs propres. On a donc trouvé toutes les valeurs propres, et leurs vecteurs propres à gauche associés. Ce calcul est tiré d'un article de Mark Kac[7].

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}.}$

• 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.

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