Probabilité stationnaire d'une chaîne de Markov

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

La probabilité stationnaire $π = (π_{i})_{i \in E}$ d'une chaîne de Markov $X = (X_{n})_{n \geq 0}$ s'interprète usuellement comme la fraction du temps passé en chaque état $\scriptstyle\ i\$ de l'espace d'états $\scriptstyle\ 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 :

π_{i} = n lim \frac{1 _{X_{0} = i} + 1 _{X_{1} = i} + \dots + 1 _{X_{n - 2} = i} + 1 _{X_{n - 1} = i}}{n} = n lim \frac{S _{n} ( i )}{n},

presque sûrement, sous certaines hypothèses détaillées plus bas. La variable aléatoire $\scriptstyle\ S_n(i)\$ s'interprète comme le temps passé en $\scriptstyle\ i\$ lors des $\scriptstyle\ n\$ premiers pas de la chaîne de Markov $X .$ La fraction $\scriptstyle\ S_n(i)/n\$ est donc la fraction de temps passé en l'état $\scriptstyle\ i\$ pendant les $\scriptstyle\ n\$ premiers pas de la chaîne de Markov. La convergence de cette fraction lorsque $\scriptstyle\ 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

Définition —

Une mesure $μ = (μ_{i})_{i \in E}$ sur l'espace d'états $\scriptstyle\ E\$ d'une chaîne de Markov $X = (X_{n})_{n \geq 0}$ de matrice de transition $P = (p_{i, j})_{(i, j) \in E^{2}}$ est dite stationnaire si

μ = μ P,

ou, de manière équivalente,

\forall j \in E, μ_{j} = i \in E \sum μ_{i} p_{i, j} .

Une mesure stationnaire est une fonction propre de la transposée de la matrice de transition, associée à la valeur propre 1.

Une mesure stationnaire $π$ est appelée probabilité stationnaire ou loi stationnaire si elle remplit les conditions supplémentaires :

\forall i \in E, π_{i} \geq 0,

et i \in E \sum π_{i} = 1.

Remarques :

La chaîne de Markov $X = (X_{n})_{n \geq 0}$ est un processus stationnaire, i.e., pour tout $n \geq 1,$ $(X_{n}, X_{n + 1}, X_{n + 2}, \dots)$ a même loi de probabilité que $(X_{0}, X_{1}, X_{2}, \dots),$ si et seulement si la loi initiale de $X$ (la loi de $X_{0}$ ) est une probabilité stationnaire.
Cela entraîne en particulier que si la loi initiale de la chaîne de Markov $X$ est une probabilité stationnaire, alors la loi de $\scriptstyle\ X_n\$ est cette même probabilité stationnaire, indépendamment de $\scriptstyle\ n.\$
L'ensemble des probabilités stationnaires est convexe.

Existence et unicité : cas irréductible

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

Définition —

Le temps de premier retour en $i,$ noté $T_{i},$ 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..

L'état $i$ 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

E_{i} [T_{i}] < + \infty.

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

Théorème — Si une chaîne de Markov est irréductible, alors il existe au plus une probabilité stationnaire. On a alors équivalence entre les 3 propositions :

il existe une probabilité stationnaire,
il existe un état récurrent positif,
tous les états sont récurrents positifs.

Supposons qu'une des 3 conditions ci-dessus est remplie et notons $π$ l'unique probabilité stationnaire : alors

\forall i \in E, π_{i} = \frac{1}{E _{i} [ T _{i} ]} .

Théorème — Une chaîne de Markov irréductible à espace d'états fini est récurrente positive (i.e. tous ses états sont récurrents positifs).

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

Distribution empirique (rouge) et distribution stationnaire (bleue) pour la marche réfléchie en 0, départ à la moyenne stationnaire -1+1/ρ=2 : p=0.4, q=0.6, ρ=1/3, 2 000 pas

Distribution empirique (rouge) : départ à la moyenne stationnaire -1+1/ρ=12, p=0.48, q=0.52, ρ=1/13, 2 000 pas

Distribution empirique (rouge) : départ à la moyenne stationnaire -1+1/ρ=12, p=0.48, q=0.52, ρ=1/13, 20 000 pas

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 $\scriptstyle\ 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

i \in E \sum ∣ f (i) ∣ π_{i} < + \infty,

on a presque sûrement :

n lim \frac{1}{n} k = 0 \sum n - 1 f (X_{k}) = i \in E \sum f (i) π_{i} = π 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 $\scriptstyle\ f\$ est la fonction indicatrice d'un sous-ensemble $\scriptstyle\ A\$ de l'espace des états :

n lim \frac{1}{n} k = 0 \sum n - 1 1_{A} (X_{k}) = i \in A \sum π_{i} = π (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 $\scriptstyle\ \theta\$ défini par

x = (x_{0}, x_{1}, x_{2}, \dots) \in E^{N} \to θ 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 $\scriptstyle\ \frac{1}{n} \; \sum_{k=0}^{n-1} f(X_k,X_{k+1}),\$ a pour limite presque sûre $\scriptstyle\ \sum_{i,j\in E} f(i,j)\,\pi_ip_{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 $\scriptstyle\ P^k\$ converge vers une matrice dont chaque ligne est l'unique distribution stationnaire $\scriptstyle\ \pi.\$ En particulier, la loi $\scriptstyle\ \mu_n\$ de $\scriptstyle\ X_n\$ converge vers $\scriptstyle\ \pi\$ indépendamment de la loi initiale $\scriptstyle\ \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, récurrente positive et apériodique, la convergence est exponentiellement rapide, i.e. pour une norme quelconque, on peut trouver $\scriptstyle\ K>0\$ et $\scriptstyle\ \alpha\in]0,1[\$ tels que

∥ μ_{n} - π ∥ \leq K α^{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,

\frac{1}{n} k = 0 \sum n - 1 δ_{X_{k}} = \frac{1}{n} i \in E \sum S_{n} (i) δ_{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 $O (1/ 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 $X_{n},$ notée $μ_{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é.

Marche aléatoire réfléchie :

C'est la chaîne de Markov d'espace d'états $E = N,$ de matrice de transition définie par $p_{k, k + 1} = p,$ pour tout $k,$ et $p_{k, k - 1} = 1 - p = q,$ pour $k \geq 1,$ $p_{0, 0} = q .$ Ce modèle est étroitement lié à l'étude des files d'attente M/M/1. La marche aléatoire réfléchie est

irréductible pour $0 < p < 1,$
récurrente positive pour $0 < p < 0.5,$ de loi stationnaire $π_{k} = (1 - ρ)^{k} ρ, ρ = (q - p) / q,$
récurrente nulle pour $p = 0.5,$
transiente pour $p > 0.5.$

On a dessiné ci-contre des exemples de distributions empiriques et de distributions stationnaires pour la marche réfléchie en 0, pour $ρ > 0$ : il semble que la convergence de l'une vers l'autre soit de plus en plus lente lorsque $ρ$ tend vers 0, i.e. quand on se rapproche des cas récurrents nuls et transients.

Chaînes réversibles

Critères

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

\forall i, j \in E, μ_{i} p_{i, j} = μ_{j} p_{j, i},

alors $π = μ /∥ μ ∥$ est une probabilité stationnaire.

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

\forall i, j \in E, μ_{i} p_{i, j} = μ_{j} q_{j, i},

alors $π = μ /∥ μ ∥$ est une probabilité stationnaire.

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

q_{i, j} = \frac{π _{j} p _{j, i}}{π _{i}},

est une matrice de transition.

Interprétation

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

P ((X_{t}, X_{t + 1}, \dots, X_{t + n}) = (i_{0}, i_{1}, \dots, i_{n})) = π_{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 $(p_{i, j})_{i, j \in E},$ et de loi stationnaire $(π_{i})_{i \in E} .$ En effet :

cela définit une et une seule mesure de probabilité sur $E^{Z}$ ;
X possède la propriété de Markov faible ;
stationnarité : la suite $\scriptstyle\ X^{(s)} =(X^{(s)}t){t\in \mathbb{Z}}\$ (définie par $\scriptstyle\ X^{(s)}t =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 $\scriptstyle\ Y =(Y_t)_{t\in \mathbb{Z}}\$ définie par

Y_t = X _{− t}.

On a alors

Proposition —

Y est une chaîne de Markov stationnaire, de matrice de transition $(q_{i, j})_{i, j \in E},$ (définie au point 3 ci-dessus) et de loi stationnaire $(π_{i})_{i \in E} .$
Si $\scriptstyle\ (q_{i,j}){i,j\in E}=(p{i,j})_{i,j\in E},\$ ou, de manière équivalente, si

alors X et Y ont même loi. On dit que ces deux chaînes de Markov sont réversibles.

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

Exemples

Marche aléatoire sur un graphe

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

\forall i, j \in E = V (G), tels que i \sim j, p_{i, j} = \frac{1}{d _{i}},

i.e. à partir de $i,$ on saute vers un de ses $d_{i}$ voisins choisis au hasard (avec équiprobabilité), $d_{i}$ désignant le degré de $i$ dans le graphe $G .$ La connexité de $G$ entraîne l'irréductibilité de la marche aléatoire et l'unicité de la probabilité stationnaire. On remarque que $μ_{i} = d_{i}$ satisfait le critère 2, or $∥ μ ∥ = 2∣ E (G) ∣,$ i.e. $∥ μ ∥$ est deux fois le nombre d'arètes de $G .$ Ainsi $π_{i} = d_{i} / (2∣ E (G) ∣)$ 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é $1/ (2∣ E (G) ∣) .$ 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ù $2 \leq d_{i} \leq 8, ∣ V (G) ∣ = ∣ E ∣ = 64,$ et $\scriptstyle\ \Vert\mu\Vert=2\vert E(G)\vert=336.\$ Ainsi

π_{coin SO} = \frac{2}{336} et E coin SO [T coin SO] = 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

\frac{π _{k + 1}}{π _{k}} = \frac{p _{k, k + 1}}{p _{k + 1, k}} = \frac{N - k}{k + 1} = \frac{( k + 1 N )}{( k N )},

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

E 0 [T 0] = \frac{1}{π _{0}} = 2^{N} .

Cet exemple illustre la réponse de Boltzmann à Zermelo : Zermelo observait une contradiction entre le théorème de récurrence de Poincaré, 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 consiste à estimer le temps de récurrence moyen : pour un gaz macroscopique contenant $N ≫ 1$ molécules, Boltzmann estime celui-ci d'ordre $1 0^{N}$ , une durée qui est largement supérieure à l'age de l'univers lorsque $N \sim N_{A} = 6.02 1 0^{+ 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

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

⟨ x, y ⟩ = i = 1 \sum N \frac{x _{i} y _{i}}{π _{i}} .

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

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 que

⟨ μ_{n} - π, μ_{n} - π ⟩ \leq C α^{2 n} .

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

ε_{i} = \frac{μ _{n, i} - π _{i}}{π _{i}},

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

⟨ μ_{n} - π, μ_{n} - π ⟩ = i = 1 \sum N π_{i} ε_{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 :

∥ μ_{n} - π ∥^{2} = i = 1 \sum N (μ_{n, i} - π_{i})^{2} = i = 1 \sum N π_{i}^{2} ε_{i}^{2} .

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

Théorème — La matrice de transition P possède N+1 valeurs propres distinctes :

1 = λ_{0} \geq λ_{1} \geq \dots \geq λ_{k} = \frac{N - 2 k}{N} \geq \dots \geq λ_{N} = - 1.

Le vecteur e_k défini par

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

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

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

i = 0 \sum N (- 1)^{i} μ_{i} = 0.

En ce cas

∥ μ . P^{k} - π ∥ \leq C (1 - \frac{2}{N})^{k} .

Existence et unicité

Graphe d'une chaîne de Markov non irréductible à espace d'états fini, possédant 3 classes : et

Discuter l'existence et l'unicité d'une probabilité stationnaire $\scriptstyle\ \pi\$ telle que $\scriptstyle\ \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 $\scriptstyle\ i,\$ et souvent notée $T_{i} .$

Théorème — On a équivalence entre les 2 propositions suivantes

L'état $i$ est récurrent positif,
il existe une probabilité stationnaire $\scriptstyle\ \pi\$ telle que $\scriptstyle\ \pi_i>0.\$

Si l'une des deux conditions précédentes est remplie, alors

la classe $C$ de l'état $i$ est une classe finale,
le support de $π$ contient $C,$
tous les éléments de $C$ sont récurrent positifs,
$π_{i} E_{i} [T_{i}] \leq 1.$

De plus, il y a équivalence entre

le support de $π$ est exactement $C,$ i.e.
${π_{j} > 0} \Leftrightarrow {j \in C},$
$π_{i} E_{i} [T_{i}] = 1,$
$π$ est un point extrémal de l'ensemble (convexe) des probabilités stationnaires.

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

Exemple :

Pour la chaîne dont le graphe est représenté ci-dessus, l'ensemble des probabilités stationnaires est le segment dont les extrémités, correspondant aux deux classes finales $\scriptstyle\ C=\{1,3\}\$ et $\scriptstyle\ C^{\prime}=\{4,5\},\$ sont $π_{C} = (\frac{1}{2}, 0, \frac{1}{2}, 0, 0)$ et $π_{C^{'}} = (0, 0, 0, \frac{1}{2}, \frac{1}{2}) .$ Une probabilité stationnaire est nécessairement de la forme $π = (α, 0, α, β, β), α + β = 0.5.$

Corollaire — Si une chaîne de Markov possède une seule classe finale $\scriptstyle\ C,\$ alors il existe au plus une probabilité stationnaire. On a alors équivalence entre les 3 propositions :

il existe une probabilité stationnaire,
il existe un état récurrent positif,
tous les états de la classe finale sont récurrents positifs.

Supposons qu'une des 3 conditions ci-dessus soit remplie et notons $π$ l'unique probabilité stationnaire : alors

\forall i \in E, π_{i} = \frac{1}{E _{i} [ T _{i} ]},

et on a la série d'équivalences

{π_{i} > 0} \Leftrightarrow {i \in C} \Leftrightarrow {i est recurrent positif} .

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 $C = E .$