Chaînes de Markov

Demain, il fera beau avec une probabilité qui ne dépend que du temps d'aujourd'hui. Un système qui saute au hasard d'un état à l'autre, sans mémoire du passé, est une chaîne de Markov. Graphes, matrices et probabilités s'y rejoignent : l'évolution se calcule avec des puissances de matrices.

  • Associer un graphe pondéré et une matrice de transition à une chaîne de Markov
  • Calculer la distribution après $n$ transitions : $\pi_n = \pi_0P^n$
  • Interpréter les coefficients de $P^n$
  • Déterminer une distribution invariante

Cours

1. Chaîne de Markov et matrice de transition

On considère une suite de variables aléatoires $(X_n)$ à valeurs dans un ensemble d'états $E = \{1, 2\}$ ou $\{1, 2, 3\}$ : $X_n$ est l'état du système à l'instant $n$. C'est une chaîne de Markov (homogène) si la probabilité de passer de l'état $i$ à l'état $j$ ne dépend ni de $n$, ni des états occupés avant l'instant $n$ : $$P_{\{X_n = i\}}(X_{n+1} = j) = p_{ij}\quad\text{pour tout } n.$$

On représente la chaîne par un graphe orienté pondéré : un sommet par état, et un arc de $i$ vers $j$ de poids $p_{ij}$ (s'il est non nul). La somme des poids des arcs qui partent d'un sommet vaut 1.

La matrice de transition est $P = (p_{ij})$ : la ligne $i$ contient les probabilités de partir de l'état $i$. Tous ses coefficients sont positifs et la somme de chaque ligne vaut 1.

S'il fait beau (état 1) un jour, il fait beau le lendemain avec probabilité 0,8 ; s'il pleut (état 2), il pleut le lendemain avec probabilité 0,6. Alors $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6\end{pmatrix}$.

2. Évolution de la distribution

La distribution à l'instant $n$ est la matrice ligne $\pi_n = \big(P(X_n = 1)\ \ P(X_n = 2)\big)$ (ou à trois coefficients). La somme de ses coefficients vaut 1. $\pi_0$ est la distribution initiale.

Pour une chaîne de Markov de matrice de transition $P$ et tout entier $n$ :

  • $\pi_{n+1} = \pi_nP$, et donc $\pi_n = \pi_0P^n$ ;
  • la probabilité de passer de l'état $i$ à l'état $j$ en $n$ transitions est le coefficient $(i, j)$ de $P^n$.

Une transition. Les événements $\{X_n = 1\}$, …, $\{X_n = p\}$ forment une partition de l'univers. D'après la formule des probabilités totales, pour tout état $j$ : $$P(X_{n+1} = j) = \sum_{i=1}^{p}P(X_n = i)\,P_{\{X_n = i\}}(X_{n+1} = j) = \sum_{i=1}^{p}(\pi_n)_i\,p_{ij},$$ qui est le coefficient $j$ de la matrice ligne $\pi_nP$. Donc $\pi_{n+1} = \pi_nP$.

n transitions. Par récurrence : $\pi_0 = \pi_0P^0$, et si $\pi_n = \pi_0P^n$, alors $\pi_{n+1} = \pi_nP = \pi_0P^nP = \pi_0P^{n+1}$.

De i à j. Si le système part de l'état $i$, la distribution initiale est la matrice ligne $\pi_0$ qui a un 1 en position $i$ et des 0 ailleurs. Alors $\pi_0P^n$ est la ligne $i$ de $P^n$, et sa coordonnée $j$, la probabilité d'être en $j$ après $n$ transitions, est le coefficient $(i, j)$ de $P^n$. $\blacksquare$

Il fait beau aujourd'hui : $\pi_0 = (1\ \ 0)$. Alors $\pi_1 = \pi_0P = (0{,}8\ \ 0{,}2)$ et $\pi_2 = \pi_1P = (0{,}8 \times 0{,}8 + 0{,}2 \times 0{,}4\ \ \ 0{,}8 \times 0{,}2 + 0{,}2 \times 0{,}6) = (0{,}72\ \ 0{,}28)$. Il pleut dans deux jours avec probabilité 0,28, coefficient $(1, 2)$ de $P^2$.

3. Distribution invariante

Une distribution $\pi$ (matrice ligne à coefficients positifs de somme 1) est invariante (ou stationnaire) si $\pi P = \pi$ : si le système suit la loi $\pi$ à un instant, il la suit à tous les instants suivants.

Pour $P = \begin{pmatrix} 1 - p & p \\ q & 1 - q\end{pmatrix}$ avec $p + q > 0$, l'unique distribution invariante est $\pi = \left(\dfrac{q}{p + q}\ \ \dfrac{p}{p + q}\right)$.

Si de plus $0 < p + q < 2$, alors $\pi_n$ converge vers $\pi$ quelle que soit la distribution initiale.

Preuve de la propriété.

Écrivons $\pi = (x\ \ 1 - x)$. $\pi P = \pi$ donne $x(1 - p) + (1 - x)q = x$, soit $x(p + q) = q$ et $x = \frac{q}{p + q}$.

Notons $x_n = P(X_n = 1)$. D'après $\pi_{n+1} = \pi_nP$ : $x_{n+1} = (1 - p)x_n + q(1 - x_n) = (1 - p - q)x_n + q$. C'est une suite arithmético-géométrique de point fixe $\frac{q}{p + q}$ : $$x_n = \left(x_0 - \frac{q}{p + q}\right)(1 - p - q)^n + \frac{q}{p + q}.$$ Si $0 < p + q < 2$, alors $|1 - p - q| < 1$, donc $(1 - p - q)^n \to 0$ et $x_n \to \frac{q}{p + q}$. $\blacksquare$

On résout le système $\pi P = \pi$ avec $\pi_1 + \pi_2 + \pi_3 = 1$ (une des trois équations de $\pi P = \pi$ est redondante et est remplacée par la condition de somme).

$p = 0{,}2$, $q = 0{,}4$ : $\pi = \left(\frac{0{,}4}{0{,}6}\ \ \frac{0{,}2}{0{,}6}\right) = \left(\frac23\ \ \frac13\right)$. À long terme, il fait beau deux jours sur trois, quel que soit le temps d'aujourd'hui.

4. Un exemple célèbre : PageRank

Pour classer les pages web, Google imagine un internaute qui clique au hasard sur les liens. C'est une chaîne de Markov dont les états sont les pages ; l'importance d'une page est sa probabilité dans la distribution invariante.

Andreï Markov (1856-1922) introduit ces chaînes en 1906. Pour montrer qu'une loi des grands nombres vaut encore sans indépendance, il analyse la succession des voyelles et des consonnes dans le roman en vers Eugène Onéguine de Pouchkine. Un siècle plus tard, l'algorithme PageRank (1998) de Brin et Page fonde le moteur de recherche Google.

Méthodes à connaître

  1. Numérote les états dans un ordre fixé.
  2. Coefficient ligne $i$, colonne $j$ : probabilité de passer de l'état $i$ à l'état $j$ (lue sur l'arête $i \to j$, 0 s'il n'y en a pas).
  3. Vérifie que la somme de chaque ligne vaut 1.
  1. Écris la distribution initiale $\pi_0$ en vecteur ligne.
  2. Utilise $\pi_{n+1} = \pi_n P$, donc $\pi_n = \pi_0 P^n$ (calculatrice pour $P^n$).
  3. La probabilité d'être dans l'état $j$ après $n$ étapes est la $j$-ième coordonnée de $\pi_n$.
  1. Pose $\pi = (x\ \ y)$ (ou avec plus de coordonnées) et écris $\pi P = \pi$.
  2. Ajoute la condition $x + y = 1$.
  3. Résous le système ; pour une chaîne à deux états sans coefficient nul, $\pi_n$ converge vers cette distribution.

Exemple. $P = \begin{pmatrix}0{,}9 & 0{,}1\\0{,}3 & 0{,}7\end{pmatrix}$ : $0{,}9x + 0{,}3y = x$ donne $0{,}1x = 0{,}3y$, avec $x + y = 1$ : $\pi = (0{,}75\ \ 0{,}25)$.

Mini-jeux

Exercices

Avec la chaîne météo du cours, sachant qu'il pleut aujourd'hui, quelle est la probabilité qu'il fasse beau dans deux jours ?

Coefficient $(2, 1)$ de $P^2$ : $0{,}4 \times 0{,}8 + 0{,}6 \times 0{,}4 = 0{,}32 + 0{,}24 = 0{,}56$.

Un joueur de tennis gagne un point avec probabilité 0,7 s'il a gagné le précédent, et 0,4 s'il l'a perdu. Représenter la situation par un graphe pondéré à deux états (G et P) et donner la matrice de transition. Déterminer la distribution invariante.

Probabilité invariante de G :

$P = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6\end{pmatrix}$ (états G puis P). Ici $p = 0{,}3$, $q = 0{,}4$ : $\pi = \left(\frac{0{,}4}{0{,}7}\ \ \frac{0{,}3}{0{,}7}\right) = \left(\frac47\ \ \frac37\right)$. À long terme, il gagne environ 57 % des points.

Pour la chaîne météo, on note $x_n$ la probabilité qu'il fasse beau le jour $n$, avec $x_0 = 0$. Montrer que $x_{n+1} = 0{,}4x_n + 0{,}4$, puis exprimer $x_n$ en fonction de $n$.

$x_{n+1} = 0{,}8x_n + 0{,}4(1 - x_n) = 0{,}4x_n + 0{,}4$. Point fixe $\ell = \frac{0{,}4}{0{,}6} = \frac23$ ; $x_n - \frac23 = 0{,}4^n\left(0 - \frac23\right)$, donc $x_n = \frac23\left(1 - 0{,}4^n\right)$.

Une souris se déplace chaque minute entre trois pièces. De la pièce 1, elle va en 2 ou en 3 de façon équiprobable ; de la pièce 2, elle va en 1 ou en 3 de façon équiprobable ; de la pièce 3, elle retourne toujours en 1. Donner la matrice de transition puis la distribution invariante.

$P = \begin{pmatrix} 0 & \frac12 & \frac12 \\ \frac12 & 0 & \frac12 \\ 1 & 0 & 0\end{pmatrix}$. $\pi P = \pi$ donne $\pi_1 = \frac12\pi_2 + \pi_3$, $\pi_2 = \frac12\pi_1$, $\pi_3 = \frac12\pi_1 + \frac12\pi_2 = \frac34\pi_1$. Avec la somme égale à 1 : $\pi_1\left(1 + \frac12 + \frac34\right) = 1$, donc $\pi = \left(\frac49\ \ \frac29\ \ \frac39\right)$.

Avec la matrice de la souris et $\pi_0 = (1\ \ 0\ \ 0)$, calculer $\pi_1$, $\pi_2$ et $\pi_3$.

$\pi_1 = \left(0\ \ \frac12\ \ \frac12\right)$, $\pi_2 = \left(\frac12 \times \frac12 + \frac12 \times 1\ \ \ 0\ \ \ \frac12 \times \frac12\right) = \left(\frac34\ \ 0\ \ \frac14\right)$, $\pi_3 = \left(\frac14\ \ \frac38\ \ \frac38\right)$.

Deux boules sont réparties entre deux urnes A et B. À chaque instant, on choisit une boule au hasard et on la change d'urne. $X_n$ est le nombre de boules dans A (états 0, 1, 2). (a) Donner la matrice de transition. (b) Vérifier que $\pi = \left(\frac14\ \ \frac12\ \ \frac14\right)$ est invariante. (c) En partant de $X_0 = 0$, calculer $\pi_n$ : converge-t-elle ?

(a) $P = \begin{pmatrix} 0 & 1 & 0 \\ \frac12 & 0 & \frac12 \\ 0 & 1 & 0\end{pmatrix}$. (b) $\pi P = \left(\frac14\ \ \frac14 + \frac14\ \ \frac14\right) = \pi$. (c) $\pi_0 = (1\ \ 0\ \ 0)$, $\pi_1 = (0\ \ 1\ \ 0)$, $\pi_2 = \left(\frac12\ \ 0\ \ \frac12\right)$, $\pi_3 = (0\ \ 1\ \ 0)$… La suite alterne : elle ne converge pas (chaîne périodique), bien qu'il existe une distribution invariante. Ce modèle de diffusion (1907) illustre la thermodynamique.

Un joueur possède 1 € et joue à pile ou face : il gagne ou perd 1 € à chaque partie, et s'arrête quand il a 0 € ou 2 €. États 0, 1, 2. (a) Écrire la matrice de transition (les états 0 et 2 sont absorbants : on y reste). (b) Calculer $\pi_n$ avec $\pi_0 = (0\ \ 1\ \ 0)$. (c) Quelle est la probabilité de finir ruiné ?

(a) $P = \begin{pmatrix} 1 & 0 & 0 \\ \frac12 & 0 & \frac12 \\ 0 & 0 & 1\end{pmatrix}$. (b) $\pi_1 = \left(\frac12\ \ 0\ \ \frac12\right)$ puis $\pi_n = \pi_1$ pour tout $n \geqslant 1$. (c) $\frac12$. Ici toute distribution $(a\ \ 0\ \ 1 - a)$ est invariante : l'unicité n'est pas garantie en général.