Chaînes de Markov

Dans de nombreux modèles réels, on suppose des résultats déterministes : si l'on connaît les données d'entrée, on peut calculer exactement la sortie. Cependant, de nombreux systèmes présentent des variations aléatoires. Un modèle stochastique utilise les probabilités pour décrire et prédire des résultats lorsque le hasard intervient.
Les chaînes de Markov sont une classe particulière de modèles stochastiques permettant de décrire des systèmes qui évoluent au cours du temps, et pour lesquels l'avenir ne dépend que de l'état présent.

Propriété de Markov

Pour modéliser un système au cours du temps, on considère une suite de variables aléatoires $(X_0, X_1, X_2, \dots)$. Chaque variable $X_n$ représente l'état du système à l'étape $n$. La caractéristique essentielle d'une chaîne de Markov est que la probabilité d'évoluer vers un état futur ne dépend que de l'état actuel, et non de l'historique des états précédents.

Définition Espace des états et propriété de Markov

Soit $E$ un ensemble fini $\{e_1, e_2, \dots, e_k\}$ appelé espace des états.
Une suite de variables aléatoires $(X_n)_{n \in \mathbb{N}}$ à valeurs dans $E$ est une chaîne de Markov si, pour tout $n \in \mathbb{N}$, pour tous indices $i,j \in \{1,\dots,k\}$, et pour tous indices $i_0,\dots,i_{n-1} \in \{1,\dots,k\}$ tels que l'événement de conditionnement soit de probabilité non nulle,$$P\!\Bigl(X_{n+1}=e_j \,\Big|\, X_n=e_i,\; X_{n-1}=e_{i_{n-1}},\dots,\; X_0=e_{i_0}\Bigr)=P\!\Bigl(X_{n+1}=e_j \,\Big|\, X_n=e_i\Bigr).$$Dans ce chapitre, on se place dans le cas homogène, c'est-à-dire que la probabilité conditionnelle$$p_{ij}=P\!\bigl(X_{n+1}=e_j \mid X_n=e_i\bigr)$$ne dépend pas de $n$. La valeur $p_{ij} \in [0, 1]$ est la probabilité de transition de l'état $e_i$ vers l'état $e_j$.

Méthode Du langage naturel au modèle de chaîne de Markov

Lorsqu'une situation est décrite en langage courant, on construit un modèle de chaîne de Markov en suivant les étapes suivantes :

Repérer les instants. Choisir ce que représente une étape (un jour, une semaine, une transaction, etc.).
Choisir les états. Lister les situations possibles du système à chaque étape (ensemble fini $E=\{e_1,\dots,e_k\}$).
Indexer les états. Fixer un ordre sur $E$ et associer à chaque état un indice : $$ e_1 \leftrightarrow 1,\quad e_2 \leftrightarrow 2,\quad \dots,\quad e_k \leftrightarrow k. $$ Cette indexation servira à construire des vecteurs et des matrices.
Définir les variables aléatoires. Introduire $(X_n)_{n\in\mathbb{N}}$ où $X_n$ désigne l'état du système à l'instant $n$, avec valeurs dans $E$.
Traduire l'hypothèse « sans mémoire ». Écrire que l'avenir ne dépend que du présent : $$ P(X_{n+1}=e_j \mid X_n=e_i,\dots,X_0=e_{i_0})=P(X_{n+1}=e_j \mid X_n=e_i). $$
Extraire les probabilités de transition. Pour chaque couple $(i,j)$, on définit $$ p_{ij}=P(X_{n+1}=e_j\mid X_n=e_i). $$

Exemple Modèle météo - États (avec indexation)

Langage naturel.
Considérons la météo d'une ville. Chaque jour, le temps est soit ensoleillé, soit pluvieux. On suppose que :
- s'il fait soleil aujourd'hui, alors la probabilité qu'il pleuve demain est $0{,}2$ ;
- s'il pleut aujourd'hui, alors la probabilité qu'il fasse soleil demain est $0{,}4$.
Dans les deux cas, on suppose que ces probabilités ne dépendent pas du temps qu'il faisait les jours précédents.
Formalisme mathématique.
On choisit comme pas de temps un jour. On retient deux états :$$e_1=S \quad (\text{Soleil}), \qquad e_2=R \quad (\text{Pluie}),$$donc l'espace des états est $E=\{e_1,e_2\}=\{S,R\}$, avec l'indexation$$S \leftrightarrow 1,\qquad R \leftrightarrow 2.$$On définit une suite de variables aléatoires $(X_n)_{n\in\mathbb{N}}$ en posant : $X_n$ est l'état de la météo au jour $n$, avec valeurs dans $E$. L'expression « ne dépendent pas du temps qu'il faisait les jours précédents » se traduit par la propriété de Markov. Les probabilités de transition sont alors :$$p_{12}=P(X_{n+1}=e_2\mid X_n=e_1)=P(X_{n+1}=R\mid X_n=S)=0{,}2,$$$$p_{21}=P(X_{n+1}=e_1\mid X_n=e_2)=P(X_{n+1}=S\mid X_n=R)=0{,}4.$$Comme la somme des probabilités sortantes d'un état vaut $1$, on en déduit aussi :$$p_{11}=1-p_{12}=0{,}8, \qquad p_{22}=1-p_{21}=0{,}6.$$Ainsi, l'ensemble des probabilités de transition est :$$p_{11}=0{,}8,\quad p_{12}=0{,}2,\quad p_{21}=0{,}4,\quad p_{22}=0{,}6.$$

Définition Graphe probabiliste

On peut visualiser une chaîne de Markov à l'aide d'un graphe probabiliste :

Chaque sommet représente un état de $E$.
Chaque arête orientée (flèche) de $i$ vers $j$ représente la transition $i \to j$.
Le poids de l'arête est la probabilité $p_{ij}$.
Règle : La somme des probabilités des flèches sortant d'un sommet doit être égale à $1$.

Exemple Graphe de la météo

Ce graphe indique que si l'on est dans l'état $R$ (pluie) aujourd'hui, alors il y a $40\pourcent$ de chances d'être dans l'état $S$ (soleil) le lendemain, et $60\pourcent$ de chances de rester dans l'état $R$.

Formalisme matriciel

Pour effectuer des calculs, on associe à chaque état un indice (en général $1,2,\dots,k$). On peut alors organiser les probabilités de transition sous forme de vecteurs et de matrices, et utiliser le calcul matriciel pour étudier l'évolution du système.

Définition Vecteur probabilité

La distribution de probabilité à l'étape $n$ est représentée par un vecteur ligne $\pi_n$ :$$\pi_n = \begin{pmatrix} P(X_n = e_1) & P(X_n = e_2) & \dots & P(X_n = e_k) \end{pmatrix}.$$Chaque composante appartient à $[0,1]$, et la somme des composantes est toujours égale à $1$. Le vecteur $\pi_0$ s'appelle la distribution initiale.

Définition Matrice de transition

La matrice de transition $M$ est une matrice carrée dont le coefficient $m_{ij}$ de la $i$-ème ligne et de la $j$-ème colonne est :$$m_{ij} = P(X_{n+1} = e_j \mid X_n = e_i)=p_{ij}.$$Matrice stochastique : Dans ce cadre, la somme des coefficients de chaque ligne de $M$ est égale à $1$.

Dans une matrice de transition $M = (m_{ij})$ :

Les lignes représentent l'état actuel (Départ).
Les colonnes représentent l'état suivant (Arrivée).
Le coefficient $m_{ij}$ est la probabilité de passer à l'état $j$ sachant qu'on est à l'état $i$.
La somme des coefficients de chaque ligne est égale à 1.

Exemple Matrice de transition de la météo

Soit l'état 1 = Soleil ($S$) et l'état 2 = Pluie ($R$).
Si aujourd'hui il fait beau avec certitude, $\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$. La matrice est :

Évolution du système

Une fois la matrice de transition définie, on peut calculer la distribution du système à tout instant $n$ grâce au calcul matriciel.

Proposition Règle d'évolution

Pour une chaîne de Markov de matrice de transition $M$ et de vecteur probabilité $\pi_n$ :$$\pi_{n+1} = \pi_n M\quad \text{et, par récurrence,} \quad\pi_n = \pi_0 M^n.$$

Preuve

Démontrons cette propriété en deux étapes.

Démonstration de $\pi_{n+1} = \pi_n M$ : D'après la loi des probabilités totales, pour tout état $j$ : $$ P(X_{n+1} = j) = \sum_{i=1}^{k} P(X_n = i) \times P(X_{n+1} = j \mid X_n = i) $$ En utilisant nos notations ($(\pi_n)_i$ pour le vecteur et $m_{ij}$ pour la matrice) : $$ (\pi_{n+1})_j = \sum_{i=1}^{k} (\pi_n)_i \times m_{ij} $$ Cette somme correspond à la définition du produit d'un vecteur ligne par une matrice. On a donc : $$ \pi_{n+1} = \pi_n \times M $$
Démonstration de $\pi_n = \pi_0 M^n$ par récurrence :
- Initialisation : Pour $n=0$, $\pi_0 M^0 = \pi_0 I = \pi_0$.
- Hérédité : Si $\pi_n = \pi_0 M^n$, alors $\pi_{n+1} = \pi_n M = (\pi_0 M^n) M = \pi_0 M^{n+1}$.
- Conclusion : Par récurrence, la propriété est vraie pour tout $n \in \mathbb{N}$.

Proposition Coefficient $(i\virgule j)$ de $M^n$

Soit $M$ la matrice de transition d'une chaîne de Markov $(X_n)$.Le coefficient situé à la $i$-ème ligne et la $j$-ème colonne de la matrice $M^n$, noté $(M^n)_{ij}$, est la probabilité d'être dans l'état $j$ après $n$ étapes, sachant que le système était initialement dans l'état $i$ :$$ (M^n)_{ij} = P(X_n = j \mid X_0 = i) $$

Exemple Prédiction météo

Aujourd'hui il fait beau. Trouver la probabilité qu'il fasse beau après-demain.

Correction

Méthode 1 (évolution pas à pas).
On utilise la matrice météo$$M=\begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}$$et la distribution initiale (aujourd'hui il fait soleil avec certitude)$$\pi_0=\begin{pmatrix} 1 & 0 \end{pmatrix}.$$On calcule alors :$$\pi_1=\pi_0 M=\begin{pmatrix} 1 & 0 \end{pmatrix}\begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}=\begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}.$$Puis, après deux jours ($n=2$) :$$\pi_2=\pi_1 M=\begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}\begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}=\begin{pmatrix} 0{,}72 & 0{,}28 \end{pmatrix}.$$Ainsi, la probabilité qu'il fasse soleil après-demain est $0{,}72$, soit $72\pourcent$.
Méthode 2 (puissance de matrice).
On calcule directement$$M^2=\begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}\begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}=\begin{pmatrix}0{,}72 & 0{,}28 \\ 0{,}56 & 0{,}44\end{pmatrix}.$$Comme le système démarre dans l'état $S$ (indice $1$), la probabilité cherchée est le coefficient $(1,1)$ :$$(M^2)_{11}=P(X_2=S\mid X_0=S)=0{,}72.$$

État stable et convergence

Sur une longue période, de nombreuses chaînes de Markov se rapprochent d'un équilibre : la distribution de probabilité ne change alors plus d'une étape à l'autre. Une telle distribution est appelée état stable ou distribution stationnaire.

Définition État stable

Un vecteur probabilité $\pi$ est un état stable (ou une distribution stationnaire) si :$$\pi M = \pi.$$

Méthode Calculer l'état stable

Pour déterminer un état stable $\pi=\begin{pmatrix} x & y \end{pmatrix}$ dans le cas de deux états :

On résout l'équation matricielle $\begin{pmatrix} x & y \end{pmatrix} M = \begin{pmatrix} x & y \end{pmatrix}$.
On obtient un système d'équations dont l'une est redondante.
On ajoute la condition de normalisation $x+y=1$.

Exemple État stable de la météo

Pour $M=\begin{pmatrix}0{,}8 & 0{,}2\\ 0{,}4 & 0{,}6\end{pmatrix},$ la résolution de $\begin{cases}\pi M = \pi\\x + y = 1\end{cases}\quad\text{avec}\quad\pi=\begin{pmatrix} x & y \end{pmatrix}$ donne :$$\begin{cases}\begin{pmatrix} x & y \end{pmatrix} \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix} = \begin{pmatrix} x & y \end{pmatrix}\\ x + y = 1\end{cases}\Leftrightarrow\begin{cases}0{,}8x + 0{,}4y = x \\ 0{,}2x + 0{,}6y = y \\ x + y = 1\end{cases}\Leftrightarrow\begin{cases}-0{,}2x+0{,}4y=0 \\ x + y = 1\end{cases}\Leftrightarrow\begin{cases}x = 2y \\ 3y = 1\end{cases}$$Ainsi, l’état stable est$$\pi=\begin{pmatrix}\dfrac{2}{3} & \dfrac{1}{3}\end{pmatrix}.$$Interprétation : à long terme, la probabilité d’être dans l’état $S$ (soleil) est $\dfrac{2}{3}$.