Définition

Une chaîne de Markov est une suite de variables aléatoires $X_0, X_1, \ldots$ prenant des valeurs dans un ensemble fini d’états $\{1, 2, \ldots, n\}$ , avec la propriété de Markov :

$P(X_{n+1} = j \mid X_n = i) = p_{ij} \quad \text{(ne dépend pas du passé)}$

Matrice de transition

La matrice de transition $T = (p_{ij})$ contient les probabilités de passage d’un état à l’autre.

Propriétés :

$p_{ij} \geq 0$
$\displaystyle\sum_j p_{ij} = 1$ pour chaque ligne $i$ (matrice stochastique)

Distribution de probabilité

L’état à l’instant $n$ est représenté par un vecteur ligne de probabilités :

$\vec{\pi}_n = (\pi_n(1), \ldots, \pi_n(k)) \quad \text{avec } \sum_j \pi_n(j) = 1$

Évolution :

$\vec{\pi}_{n+1} = \vec{\pi}_n \cdot T$

$\vec{\pi}_n = \vec{\pi}_0 \cdot T^n$

Exemple

Deux états : Soleil (S) et Pluie (P).

$T = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}$

Si $\vec{\pi}_0 = (1, 0)$ (soleil aujourd’hui) :

$\vec{\pi}_1 = (0{,}7,\; 0{,}3)$ $\vec{\pi}_2 = (0{,}7 \times 0{,}7 + 0{,}3 \times 0{,}4,\; \ldots) = (0{,}61,\; 0{,}39)$

État stationnaire

L’état stationnaire $\vec{\pi}^*$ vérifie :

$\vec{\pi}^* = \vec{\pi}^* \cdot T \quad \text{et} \quad \sum_j \pi^*(j) = 1$

Méthode : Résoudre le système linéaire.

Exemple : $\vec{\pi}^*(S) = 0{,}7\,\pi^*(S) + 0{,}4\,\pi^*(P)$ avec $\pi^*(S) + \pi^*(P) = 1$

$0{,}3\,\pi^*(S) = 0{,}4\,\pi^*(P) \implies \pi^*(S) = \dfrac{4}{7}$ , $\pi^*(P) = \dfrac{3}{7}$

Convergence

Pour une chaîne de Markov irréductible (tous les états communicants) et apériodique, la distribution converge vers l’unique état stationnaire quel que soit l’état initial :

$\vec{\pi}_n \xrightarrow[n\to+\infty]{} \vec{\pi}^*$