Sommaire

Chaîne de Markov

Cet article ne cite pas suffisamment ses sources (mars 2021).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Enmathématiques, une chaîne de Markov est un processus de Markov à temps discret, ou à temps continu et à espace d'états discret. Un processus de Markov est un processus stochastique possédant la propriété de Markov : l'information utile pour la prédiction du futur est entièrement contenue dans l'état présent du processus et n'est pas dépendante des états antérieurs (le système n'a pas de « mémoire »). Les processus de Markov portent le nom de leur inventeur, Andreï Markov.

Un processus de Markov à temps discret est une séquence ${\displaystyle X_{0},}$ ${\displaystyle X_{1},}$ ${\displaystyle X_{2},}$ ${\displaystyle X_{3},\ \dots }$devariables aléatoires à valeurs dans l’espace des états, qu'on notera ${\displaystyle E}$ dans la suite. La valeur ${\displaystyle X_{n}}$ est l'état du processus à l'instant ${\displaystyle n.}$ Les applications où l'espace d'états ${\displaystyle E}$ est fini ou dénombrable sont innombrables : on parle alors de chaîne de Markov ou de chaînes de Markov à espace d'états discret. Les propriétés essentielles des processus de Markov généraux, par exemple les propriétés de récurrence et d'ergodicité, s'énoncent ou se démontrent plus simplement dans le cas des chaînes de Markov à espace d'états discret. Cet article concerne précisément les chaînes de Markov à espace d'états discret.

Andreï Markov a publié les premiers résultats sur les chaînes de Markov à espace d'états fini en 1906. Une généralisation à un espace d'états infini dénombrable a été publiée par Kolmogoroven1936. Les processus de Markov sont liés au mouvement brownien et à l'hypothèse ergodique, deux sujets de physique statistique qui ont été très importants au début du XX^e siècle.

Propriété de Markov faible[modifier | modifier le code]

Définitions[modifier | modifier le code]

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

Critère[modifier | modifier le code]

Le critère est fondamental en cela que toute chaîne de Markov homogène peut être simulée via une récurrence de la forme ${\displaystyle X_{n+1}=f\left(X_{n},Y_{n+1}\right),}$ pour une fonction ${\displaystyle f}$ bien choisie. On peut même choisir ${\displaystyle F=[0,1],}$ et choisir des variables ${\displaystyle Y_{j}}$ indépendantes et uniformes sur l'intervalle [0,1], ce qui est commode pour l'étude de chaînes de Markov via des méthodes de Monte-Carlo.

Probabilités de transition[modifier | modifier le code]

Définition[modifier | modifier le code]

La famille de nombres ${\displaystyle P=\left(p_{i,j}\right)_{(i,j)\in E^{2}}}$ est appelée matrice de transition, noyau de transition, ou opérateur de transition de la chaîne 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.

Alors ${\displaystyle E}$ possède ${\displaystyle 2^{N}}$ éléments, mais les numéroter de 1 à ${\displaystyle 2^{N}}$ serait malcommode pour suivre l'évolution du système, qui consiste à choisir une des ${\displaystyle N}$ coordonnées de ${\displaystyle x}$ au hasard et à changer sa valeur. Si l'on veut comprendre le système moins en détail (car on n'est pas capable de reconnaître une puce d'une autre), on peut se contenter d'étudier le nombre de puces sur le chien n°1, ce qui revient à choisir ${\displaystyle E=\{0,1,2,\dots ,N\}.}$ Là encore, pour la compréhension, il serait dommage de renuméroter les états de 1 à ${\displaystyle N+1.}$ Notons que pour cette nouvelle modélisation, ${\displaystyle p_{k,k+1}={\tfrac {N-k}{N}}{\text{ et }}p_{k,k-1}={\tfrac {k}{N}},}$ puisque, par exemple, le nombre de puces sur le dos du chien n°1 passe de k à k-1 si c'est une de ces k puces qui est choisie pour sauter, parmi les N puces présentes dans le « système ». Ce modèle porte plus souvent le nom de « modèle des urnes d'Ehrenfest ». Il a été introduit en 1907 par TatianaetPaul Ehrenfest pour illustrer certains des « paradoxes » apparus dans les fondements de la mécanique statistique naissante, et pour modéliser le bruit rose. Le modèle des urnes d'Ehrenfest était considéré par le mathématicien Mark Kac comme « probablement l'un des modèles les plus instructifs de toute la physique ».

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

Propriétés[modifier | modifier le code]

Au rang ${\displaystyle n,}$ en posant ${\displaystyle P_{k}=\mathbb {P} \left(X_{0}=i_{0},X_{1}=i_{1},\ldots ,X_{k-1}=i_{k-1},X_{k}=i_{k}\right),}$ ${\displaystyle {\frac {P_{n}}{P_{n-1}}}=\mathbb {P} {\Big (}X_{n}=i_{n}\mid \,X_{0}=i_{0},X_{1}=i_{1},\ldots ,X_{n-1}=i_{n-1}{\Big )}=p_{i_{n-1},i_{n}},}$ en vertu de la propriété de Markov faible, donc si ${\displaystyle P_{n-1}}$ a l'expression attendue, alors ${\displaystyle P_{n}}$ aussi.

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

Puissances de la matrice de transition[modifier | modifier le code]

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

Au rang ${\displaystyle k,}$ ${\displaystyle {\begin{aligned}\mathbb {P} \left(X_{n}=i{\text{ et }}X_{n+k}=j\right)&=\sum _{\ell \in E}\mathbb {P} \left(X_{n}=i,\,X_{n+k-1}=\ell {\text{ et }}X_{n+k}=j\right)\\&=\sum _{\ell \in E}\mathbb {P} \left(X_{n}=i,\,X_{n+k-1}=\ell \right)\ \mathbb {P} \left(X_{n+k}=j\mid X_{n}=i,\,X_{n+k-1}=\ell \right)\\&=\sum _{\ell \in E}\mathbb {P} \left(X_{n}=i,\,X_{n+k-1}=\ell \right)\ p_{\ell ,j}\\&=\mathbb {P} \left(X_{n}=i\right)\ \sum _{\ell \in E}p_{i,\ell }^{(k-1)}\ p_{\ell ,j}\\&=\mathbb {P} \left(X_{n}=i\right)\ p_{i,j}^{($k)},\end{aligned}}} où

• la1^re égalité est le troisième axiome des probabilités,
• la2^e égalité est la définition d'une probabilité conditionnelle,
• la3^e égalité est due à une forme de propriété de Markov faible,
• la4^e égalité est la propriété de récurrence au pas ${\displaystyle k-1,}$
• la5^e égalité est la formule du produit de deux « matrices », appliquée au produit de ${\displaystyle P^{k-1}}$ avec ${\displaystyle P.}$

Pour conclure, on divise les deux termes extrêmes de cette suite d'égalités par ${\displaystyle \mathbb {P} \left(X_{n}=i\right),}$ sauf si ce dernier terme est nul, auquel cas on peut définir ${\displaystyle \mathbb {P} \left(X_{n+k}=j\mid X_{n}=i\right)}$ arbitrairement, donc, par exemple, égal à ${\displaystyle p_{i,j}^{($k)}.}

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

En particulier, ${\displaystyle \mathbb {P} \left(X_{n}=j\right)=\sum _{i\in E}\mathbb {P} \left(X_{0}=i\right)p_{i,j}^{($n)}.}

En écriture matricielle, si la loi de ${\displaystyle X_{n}}$ est considérée comme un vecteur-ligne ${\displaystyle \mu _{n}=(\mu _{n,i})_{i\in E},}$ avec ${\displaystyle \mu _{n,i}=\mathbb {P} \left(X_{n}=i\right),}$ cela se reformule en : ${\displaystyle \mu _{n+k}=\mu _{n}P^{k}\quad {\text{ et }}\quad \mu _{n}=\mu _{0}P^{n}.}$

Classification des états[modifier | modifier le code]

Pour ${\displaystyle (i,j)\in E^{2}}$, on dit que ${\displaystyle j}$ est accessible à partir de ${\displaystyle i}$ si et seulement s'il existe ${\displaystyle n\geq 0}$ tel que ${\displaystyle \mathbb {P} (X_{n}=j\mid X_{0}=i)>0.}$ On note : ${\displaystyle \{j\leftarrow i\}\quad \Leftrightarrow \quad \left\{\exists n\geq 0{\text{ tel que }}p_{i,j}^{($n)}>0\right\}.}

On dit que ${\displaystyle i}$et${\displaystyle j}$ communiquent si et seulement s'il existe ${\displaystyle (n,m)\in \mathbb {N} ^{2}}$ tels que ${\displaystyle \mathbb {P} (X_{n}=j\mid X_{0}=i)>0}$et${\displaystyle \mathbb {P} (X_{m}=i\mid X_{0}=j)>0.}$ On note : ${\displaystyle \{j\leftrightarrow i\}\quad \Leftrightarrow \quad \left\{j\leftarrow i{\text{ et }}i\leftarrow j\right\}.}$

La relation communiquer, notée ${\displaystyle \leftrightarrow ,}$ est une relation d'équivalence. Quand on parle de classe en parlant des états d'une chaîne de Markov, c'est en général aux classes d'équivalence pour la relation ${\displaystyle \leftrightarrow }$ qu'on fait référence. Si tous les états communiquent, la chaîne de Markov est dite irréductible.

La relation être accessible, notée ${\displaystyle \leftarrow ,}$ s'étend aux classes d'équivalence : pour deux classes ${\displaystyle C}$et${\displaystyle C^{\prime }}$, on a ${\displaystyle \{C\leftarrow C^{\prime }\}\quad \Leftrightarrow \quad \left\{\exists (i,j)\in C\times C^{\prime },\qquad i\leftarrow j\right\}\quad \Leftrightarrow \quad \left\{\forall (i,j)\in C\times C^{\prime },\qquad i\leftarrow j\right\}.}$