Chaîne de Markov

C'est la propriété caractéristique d'une chaîne de Markov : la prédiction du futur à partir du présent n'est pas rendue plus précise par des éléments d'information supplémentaires concernant le passé, car toute l'information utile pour la prédiction du futur est contenue dans l'état présent du processus. La propriété de Markov faible possède plusieurs formes équivalentes qui reviennent toutes à constater que la loi conditionnelle de ${\displaystyle X_{n+1}}$ sachant le passé, c'est-à-dire sachant ${\displaystyle \left(X_{k}\right)_{0\leq k\leq n},}$ est une fonction de ${\displaystyle X_{n}}$ seul : ${\displaystyle {\begin{aligned}\forall n\geq 0,\forall (i_{0},\ldots ,i_{n-1},i,j)&\in E^{n+2}\ {\text{tel que}}\ \mathbb {P} {\Big (}X_{0}=i_{0},X_{1}=i_{1},\ldots ,X_{n-1}=i_{n-1},X_{n}=i{\Big )}>0,\\\mathbb {P} {\Big (}X_{n+1}=j&\mid \,X_{0}=i_{0},X_{1}=i_{1},\ldots ,X_{n-1}=i_{n-1},X_{n}=i{\Big )}=\mathbb {P} \left(X_{n+1}=j\mid X_{n}=i\right).\end{aligned}}}$

Une variante courante des chaînes de Markov est la chaîne de Markov homogène, pour laquelle la probabilité de transition est indépendante de ${\displaystyle n}$ : ${\displaystyle \forall n\geq 1,\forall (i,j)\in E^{2},\quad \mathbb {P} (X_{n+1}=j\mid X_{n}=i)=\mathbb {P} (X_{n}=j\mid X_{n-1}=i)}$

Dans la suite de l'article on ne considèrera que des chaînes de Markov homogènes. Pour une application intéressante des chaînes de Markov non homogènes à l'optimisation combinatoire, voir l'article Recuit simulé. Il existe une propriété de Markov forte, liée à la notion de temps d'arrêt : cette propriété de Markov forte est cruciale pour la démonstration de résultats importants (divers critères de récurrence, loi forte des grands nombres pour les chaînes de Markov). Elle est énoncée dans l'article « Propriété de Markov ».

La terminologie matrice de transition est la plus utilisée, mais elle n'est appropriée, en toute rigueur, que lorsque, pour un entier ${\displaystyle n\geq 1,}$ ${\displaystyle E=\{1,2,\ldots ,n\}.}$ Lorsque ${\displaystyle E}$ est fini, par exemple de cardinal ${\displaystyle n,}$ on peut toujours numéroter les éléments de ${\displaystyle E}$ arbitrairement de 1 à ${\displaystyle n,}$ ce qui règle le problème, mais imparfaitement, car cette renumérotation est contre-intuitive dans beaucoup d'exemples.

Plutôt que de renuméroter les états à partir de 1, il est donc plus ergonomique dans beaucoup de cas d'accepter des matrices finies ou infinies dont les lignes et colonnes sont « numérotées » à l'aide des éléments de ${\displaystyle E.}$ Le produit de deux telles « matrices », ${\displaystyle A=\left(a_{i,j}\right)_{(i,j)\in E^{2}}}$ et ${\displaystyle B=\left(b_{i,j}\right)_{(i,j)\in E^{2}}}$, est alors défini très naturellement par ${\displaystyle (AB)_{i,j}=\sum _{\ell \in E}a_{i,\ell }b_{\ell ,j},}$ par analogie avec la formule plus classique du produit de deux matrices carrées de taille ${\displaystyle n,}$ ${\displaystyle (AB)_{i,j}=\sum _{k=1}^{n}a_{i,k}b_{k,j}.}$

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

Pour ${\displaystyle k\geq 1,}$ la probabilité de transition en ${\displaystyle k}$ pas, ${\displaystyle \mathbb {P} \left(X_{n+k}=j\mid X_{n}=i\right),}$ ne dépend pas de ${\displaystyle n}$ :

Par une simple application de la formule des probabilités totales, on en déduit les lois marginales de la chaîne de Markov.

Il peut exister une ou plusieurs mesures ${\displaystyle \pi =(\pi _{i})_{i\in E},}$ sur l'espace d'états ${\displaystyle E,}$ telles que : ${\displaystyle \pi =\pi \,P,}$ ou bien encore ${\displaystyle \forall j\in E,\qquad \pi _{j}=\sum _{i\in E}\pi _{i}\,p_{i,j}.}$

Une telle mesure ${\displaystyle \pi }$ est appelée une mesure stationnaire. Une mesure stationnaire est une fonction propre de la transposée de la matrice de transition, associée à la valeur propre 1. Elle est appelée probabilité stationnaire ou loi stationnaire si elle remplit les conditions supplémentaires :

• ${\displaystyle \forall i\in E,\qquad \pi _{i}\ \geq \ 0,}$
• ${\displaystyle \sum _{i\in E}\pi _{i}\ =\ 1.}$

Le terme « stationnaire » est justifié par la proposition suivante :

Plus généralement, la chaîne de Markov est un processus stationnaire si et seulement si sa loi initiale est une probabilité stationnaire.

Dans le cas des chaînes de Markov à espace d'états discret, certaines propriétés du processus déterminent s'il existe ou non une probabilité stationnaire, et si elle est unique ou non :

• une chaîne de Markov est irréductible si tout état est accessible à partir de n'importe quel autre état ;
• un état est récurrent positif si l'espérance du temps de premier retour en cet état, partant de cet état, est finie.

Si une chaîne de Markov possède au moins un état récurrent positif, alors il existe une probabilité stationnaire. S'il existe une probabilité stationnaire ${\displaystyle \pi }$ telle que ${\displaystyle \pi _{i}>0}$, alors l'état ${\displaystyle i}$ est récurrent positif, et réciproquement.

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

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 suivant 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}\chi _{A}(X_{k})\ =\ \sum _{i\in A}\ \pi _{i}\ =\ \pi (A).}$

Cela permet d'approcher la probabilité stationnaire par la distribution empirique (qui est un histogramme construit à partir d'une séquence particulière), comme dans le cas de la marche aléatoire avec barrière.

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 mesuré. 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. Notons qu'il est naturel que la suite ${\displaystyle \mu _{n},}$ définie par récurrence par la relation ${\displaystyle \mu _{n+1}=\mu _{n}P,}$ ait, éventuellement, pour limite un point fixe de cette transformation, i.e. une solution de l'équation ${\displaystyle \pi =\pi P.}$

Si une chaîne de Markov est irréductible et si son espace d'états est fini, tous ses états sont récurrents positifs. La loi forte des grands nombres est alors en vigueur.

Plus généralement, tous les éléments d'une classe finale finie sont récurrents positifs, que l'espace d'états soit fini ou bien infini dénombrable.

Les diagrammes peuvent montrer toutes les flèches, chacune représentant une probabilité de transition. Cependant, c'est plus lisible si :

• on ne dessine pas les flèches de probabilité zéro (transition impossible) ;
• on ne dessine pas les boucles (flèche d'un état vers lui-même). Cependant elles existent ; leur probabilité est sous-entendue car on sait que la somme des probabilités des flèches partant de chaque état doit être égale à 1.

• 
  Exemple avec boucles implicites
• 
  Exemple avec boucles dessinées

La matrice de transition de ce système est la suivante (les lignes et les colonnes correspondent dans l'ordre aux états représentés sur le graphe par copeaux, mangeoire, roue) : ${\displaystyle P={\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}}$

Prenons l'hypothèse que Doudou dort lors de la première minute de l'étude. ${\displaystyle \mathbf {x} ^{(0)}={\begin{bmatrix}1&0&0\end{bmatrix}}}$

Au bout d'une minute, on peut prédire : ${\displaystyle \mathbf {x} ^{(1)}=\mathbf {x} ^{(0)}P={\begin{bmatrix}1&0&0\end{bmatrix}}{\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}={\begin{bmatrix}0,9&0,05&0,05\end{bmatrix}}}$

Ainsi, après une minute, on a 90 % de chances que Doudou dorme encore, 5 % qu'il mange et 5 % qu'il coure.

${\displaystyle \mathbf {x} ^{(2)}=\mathbf {x} ^{(1)}P=\mathbf {x} ^{(0)}P^{2}={\begin{bmatrix}1&0&0\end{bmatrix}}{\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}^{2}={\begin{bmatrix}0,885&0,045&0,07\end{bmatrix}}}$

Après 2 minutes, il y a 4,5 % de chances que le hamster mange.

De manière générale, pour ${\displaystyle n}$ minutes : ${\displaystyle \mathbf {x} ^{(n)}=\mathbf {x} ^{(n-1)}P}$ et ${\displaystyle \mathbf {x} ^{(n)}=\mathbf {x} ^{(0)}P^{n}}$

La théorie montre qu'au bout d'un certain temps, la loi de probabilité est indépendante de la loi initiale. Notons-la ${\displaystyle q}$ : ${\displaystyle \mathbf {q} =\lim _{n\to \infty }\mathbf {x} ^{(n)}}$

On obtient la convergence si et seulement si la chaîne est apériodique et irréductible. C'est le cas dans notre exemple, on peut donc écrire : ${\displaystyle {\begin{aligned}P&={\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}\\\mathbf {q} P&=\mathbf {q} \qquad {\mbox{(}}\mathbf {q} {\mbox{ est la loi invariante par rapport à }}P{\mbox{.)}}\\&=\mathbf {q} I\\\mathbf {q} (I-P)&=\mathbf {0} \\&=\mathbf {q} \left({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\\end{bmatrix}}-{\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}\right)\\&=\mathbf {q} {\begin{bmatrix}0,1&-0,05&-0,05\\-0,7&1&-0,3\\-0,8&0&0,8\\\end{bmatrix}}\\&={\begin{bmatrix}q_{1}&q_{2}&q_{3}\end{bmatrix}}{\begin{bmatrix}0,1&-0,05&-0,05\\-0,7&1&-0,3\\-0,8&0&0,8\\\end{bmatrix}}\\&={\begin{bmatrix}0&0&0\end{bmatrix}}\end{aligned}}}$

Sachant que ${\displaystyle q_{1}+q_{2}+q_{3}=1}$, on obtient : ${\displaystyle {\begin{bmatrix}q_{1}&q_{2}&q_{3}\end{bmatrix}}={\begin{bmatrix}0,884&0,0442&0,0718\end{bmatrix}}}$

Doudou passe donc 88,4 % de son temps à dormir, 4,42 % à manger et 7,18 % à courir.

• Méthode de Monte-Carlo par chaînes de Markov
• Matrice d'adjacence
• Problème de décision de Markov (MDP)
• Problème de décision de Markov partiellement observable (POMDP)
• Marche aléatoire
• Mouvement brownien
• Modèle des urnes d'Ehrenfest
• Modèle de Markov caché
• Processus de Markov à temps continu
• Processus de Markov
• Propriété de Markov
• Couverture de Markov
• Martingale
• Équation maîtresse

• Bruno Sericola : Chaînes de Markov - Théorie, algorithmes et applications. Hermes/Lavoisier, 2013.
• Sylvie Méléard : Modèles aléatoires en écologie et évolution. Springer, 2016.
• Paolo Baldi, Laurent Mazliak, Pierre Priouret, Martingales et chaînes de Markov. Théorie élémentaire et exercices corrigés, (ISBN 2-7056-6425-4), Hermann (éditions), 2001

• Philippe Gay, « Markov et la Belle au bois dormant », sur Images des Maths, 5 septembre 2014
• (en) [PDF] Charles M. Grinstead et J. Laurie Snell, chap. « Markov Chains », dans Introduction to probability, AMS
• (en) Markov Marvellous Chain
• Exercices corrigés (wims de l'université de Nice Sophia Antipolis)