Chaînes de Markov

Ce que tu sais déjà. Tu sais utiliser les probabilités conditionnelles et la formule des probabilités totales (Première — Probabilités conditionnelles), et calculer avec des matrices (Matrices) et des graphes (Graphes). Une chaîne de Markov décrit un système qui passe au hasard d’un état à un autre, avec une règle simple : l’avenir ne dépend que du présent, pas du passé.

1. Graphe probabiliste

Situation. Un système peut se trouver dans un nombre fini d’états (ici $2$ ou $3$). À chaque étape (jour, année, coup…), il change d’état (ou reste dans le même) au hasard. On note $X_n$ l’état à l’étape $n$. On parle de chaîne de Markov lorsque la probabilité de passer de l’état $i$ à l’état $j$ ne dépend que de $i$ et $j$ (ni de $n$, ni des états antérieurs) : $$P_{(X_n = i)}(X_{n+1} = j) = p_{ij}.$$

Graphe probabiliste. On représente la chaîne par un graphe orienté pondéré : les sommets sont les états, l’arc de $i$ vers $j$ porte la probabilité de transition $p_{ij}$. La somme des poids des arcs qui partent d’un sommet vaut $1$.

Exemple (météo). Dans une ville, s’il fait beau ($B$) un jour, il fait beau le lendemain avec la probabilité $0{,}8$ ; s’il pleut ($P$), il pleut le lendemain avec la probabilité $0{,}6$.

→ S’entraîner : Exercice 1

2. Matrice de transition et distributions

Définition. La matrice de transition est la matrice carrée $P = (p_{ij})$, où $p_{ij}$ est la probabilité de passer de l’état $i$ à l’état $j$. Chaque coefficient est entre $0$ et $1$, et la somme de chaque ligne vaut $1$.

Pour la météo (ordre $B$, $P$) : $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}$.

Distribution. La distribution à l’étape $n$ est la matrice ligne $\pi_n = \begin{pmatrix} P(X_n = 1) & P(X_n = 2) & \dots \end{pmatrix}$ ; ses coefficients sont positifs et de somme $1$. $\pi_0$ est la distribution initiale.

Théorème. Pour tout entier $n$ : $\pi_{n+1} = \pi_nP$, et donc $\pi_n = \pi_0P^n$.

Exemple. Il fait beau aujourd’hui : $\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$. Demain : $\pi_1 = \pi_0P = \begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}$ ; après-demain : $\pi_2 = \pi_1P = \begin{pmatrix} 0{,}8 \times 0{,}8 + 0{,}2 \times 0{,}4 & 0{,}8 \times 0{,}2 + 0{,}2 \times 0{,}6 \end{pmatrix} = \begin{pmatrix} 0{,}72 & 0{,}28 \end{pmatrix}$.

→ S’entraîner : Exercice 2 · Exercice 3

3. Transitions en n étapes

Théorème. Le coefficient $(i, j)$ de $P^n$ est la probabilité de passer de l’état $i$ à l’état $j$ en $n$ transitions : $$\left(P^n\right)_{ij} = P_{(X_0 = i)}(X_n = j).$$

Exemple. $P^2 = \begin{pmatrix} 0{,}72 & 0{,}28 \\ 0{,}56 & 0{,}44 \end{pmatrix}$ : s’il pleut aujourd’hui, la probabilité qu’il fasse beau dans deux jours est $0{,}56$.

Lien avec les graphes. C’est la version « pondérée » du comptage de chemins : la probabilité de passer de $i$ à $j$ en $n$ étapes est la somme des produits des poids le long de tous les chemins de longueur $n$ de $i$ à $j$.

→ S’entraîner : Exercice 4

4. Distribution invariante et comportement à long terme

Définition. Une distribution $\pi$ est invariante (ou stationnaire) si $\pi P = \pi$ : si le système suit cette distribution à une étape, il la suit encore à l’étape suivante.

Propriété (admise). Pour une chaîne à deux états dont la matrice de transition n’a aucun coefficient nul (ou, plus généralement, dont une puissance $P^k$ n’a que des coefficients strictement positifs), il existe une unique distribution invariante $\pi$, et quelle que soit la distribution initiale, $\pi_n$ converge vers $\pi$.

Interprétation. À long terme, il fait beau environ $2$ jours sur $3$ dans cette ville, quel que soit le temps du premier jour.

Pour deux états, un calcul explicite. Avec $p_n = P(X_n = B)$ : $p_{n+1} = 0{,}8p_n + 0{,}4(1 - p_n) = 0{,}4p_n + 0{,}4$. C’est une suite arithmético-géométrique : $p_n - \dfrac23 = 0{,}4^n\left(p_0 - \dfrac23\right)$, qui tend vers $0$.

import numpy as np
P = np.array([[0.8, 0.2], [0.4, 0.6]])
pi = np.array([0, 1])          # il pleut le jour 0
for n in range(10):
    pi = pi @ P
print(pi)                       # [0.66659... 0.33340...]

→ S’entraîner : Exercice 5 · Exercice 6 · Exercice 7

À retenir.

• Chaîne de Markov : la probabilité de la transition $i \to j$ ne dépend que de $i$ et $j$ ; graphe pondéré, poids sortants de somme $1$.
• Matrice de transition $P$ : lignes de somme $1$. Distribution = matrice ligne.
• $\pi_{n+1} = \pi_nP$, $\pi_n = \pi_0P^n$ ; $(P^n)_{ij}$ = probabilité de passer de $i$ à $j$ en $n$ étapes.
• Distribution invariante : $\pi P = \pi$ et somme des coefficients $= 1$ ; limite de $\pi_n$ sous les hypothèses du cours.