Chaînes de Markov

Cours complet · mathématiques appliquées (ECG 2e année), chapitre 10 · prépa ECG, 2e année

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

Un client d'un opérateur téléphonique reste chez lui ou part chez le concurrent ; une page web renvoie vers d'autres pages ; un assuré passe d'un bonus à un malus. Dans tous les cas, un système occupe l'un de plusieurs états et change d'état au fil du temps, avec des probabilités qui ne dépendent que de l'état présent — jamais du chemin parcouru pour y arriver.

C'est une chaîne de Markov. Ce chapitre montre que son évolution s'écrit comme un produit matriciel, et que son comportement à long terme se lit sur un vecteur propre — celui de la valeur propre $1$ . Tout le chapitre 3 y sert.

AttentionTout est admis

Le programme est explicite : « tous les résultats de cette section seront admis ». Ce chapitre est un chapitre de modélisation et de calcul, pas de démonstration.

10.1 Graphe probabiliste et matrice de transition

Définition 10.1Graphe probabiliste, matrice de transition

Un graphe probabiliste à $r$ états est un graphe orienté dont les sommets sont numérotés de $1$ à $r$ et dont chaque arête porte une probabilité, la somme des probabilités sortant de chaque sommet valant $1$ .

La matrice de transition $M = (m_{i, j})$ est la matrice de $M_{r} (R)$ où

$m_{i, j} = P (passer de l’ e ˊ tat i a ˋ l’ e ˊ tat j) .$

Ses coefficients sont positifs et chaque ligne somme à $1$ .

AttentionLe sens des indices, et celui du vecteur

$m_{i, j}$ va de $i$ vers $j$ : c'est la ligne qui décrit le départ. En conséquence, l'état de la chaîne se note en vecteur ligne et la récurrence s'écrit $V_{n} = V_{n - 1} M$ , avec la matrice à droite. C'est l'inverse de ce à quoi le chapitre 3 a habitué, et l'erreur la plus fréquente.

Définition 10.2Chaîne de Markov, état de la chaîne

La chaîne de Markov associée est la suite $(X_{n})$ de variables aléatoires à valeurs dans ${1, \dots, r}$ , où $X_{n}$ est l'état occupé à l'instant $n$ . Le $n$ -ième état de la chaîne est le vecteur ligne

$V_{n} = (P ([X_{n} = 1]), \dots, P ([X_{n} = r])) .$

◆Théorème 10.3La récurrence

Pour tout $n ⩾ 1$ et tout $j$ ,

$P ([X_{n} = j]) = i = 1 \sum r m_{i, j} P ([X_{n - 1} = i]), c’est- a ˋ -dire V_{n} = V_{n - 1} M .$

Par récurrence immédiate, $V_{n} = V_{0} M^{n}$ .

Exemple 10.4Une évolution, pas à pas

Avec $M = (0, 8 0, 3 0, 2 0, 7)$ et $V_{0} = (1; 0)$ — on part certainement de l'état $1$ :

$V_{1} = (0, 8; 0, 2), V_{2} = (0, 7; 0, 3), V_{3} = (0, 65; 0, 35), V_{4} = (0, 625; 0, 375) .$

Le premier calcul : $V_{1} = (1 \times 0, 8 + 0 \times 0, 3, 1 \times 0, 2 + 0 \times 0, 7) = (0, 8; 0, 2)$ . Les suivants se poursuivent de même, et les valeurs semblent converger.

10.2 État stable

Définition 10.5État stable

Un vecteur ligne $V$ à coefficients positifs de somme $1$ est un état stable lorsque

$V M = V .$

◆Théorème 10.6Le lien avec les valeurs propres

$V M = V$ équivaut à $^{t} M^{t} V =^{t} V$ : la colonne $^{t} V$ est un vecteur propre de $^{t} M$ associé à la valeur propre $1$ .

ImportantLa méthode, en trois gestes

Écrire le système $V M = V$ , c'est-à-dire $V (M - I_{r}) = 0$ .
Le résoudre — il est toujours de rang au plus $r - 1$ , puisque $1$ est valeur propre de $^{t} M$ : la somme des lignes de $M - I_{r}$ est nulle.
Normaliser : imposer que la somme des coefficients vaille $1$ . C'est cette dernière équation qui rend la solution unique.

Exemple 10.7Calculer l'état stable

Cherchons $V = (p; q)$ avec $V M = V$ pour $M = (0, 8 0, 3 0, 2 0, 7)$ . La première composante donne

$0, 8 p + 0, 3 q = p ⟹ 0, 3 q = 0, 2 p ⟹ q = \frac{2}{3} p .$

(La seconde composante donne la même équation — c'est toujours le cas.) La normalisation $p + q = 1$ donne $p + \frac{2}{3} p = 1$ , donc $p = 0, 6$ et $q = 0, 4$ .

Vérification : $(0, 6; 0, 4) M = (0, 48 + 0, 12; 0, 12 + 0, 28) = (0, 6; 0, 4)$ .

AttentionLa convergence n'est pas garantie

Prenons $M = (0110)$ : on change d'état à chaque pas, de façon certaine. Partant de $V_{0} = (1; 0)$ , on obtient $(0; 1)$ , $(1; 0)$ , $(0; 1)$ … La suite ne converge pas. Pourtant $(0, 5; 0, 5)$ est bien un état stable : il existe, mais n'attire pas.

Exemple 10.8Un graphe à trois états

Soit

$M = 0, 5 0, 1 0, 2 0, 3 0, 6 0, 2 0, 2 0, 3 0, 6 .$

Chaque ligne somme à $1$ . La résolution de $V M = V$ avec normalisation donne

$V \approx (0, 2326; 0, 3721; 0, 3953) .$

Et en itérant depuis $V_{0} = (1; 0; 0)$ , on obtient exactement ces valeurs au bout d'une vingtaine d'étapes.

Python : Itérer, et vérifier l'état stable


import numpy as np

M = np.array([[0.8, 0.2], [0.3, 0.7]])
V = np.array([1.0, 0.0])

for n in range(5):
    print(n, V.round(6))
    V = V @ M                     # ATTENTION : V a GAUCHE, M a DROITE
# 0 [1. 0.]      1 [0.8 0.2]    2 [0.7 0.3]
# 3 [0.65 0.35]  4 [0.625 0.375]

S = np.array([0.6, 0.4])
print(np.allclose(S @ M, S))      # True   <- c'est bien l'etat stable

Écrire M @ V au lieu de V @ M donne un résultat qui a l'air plausible — un vecteur de bonne taille, à coefficients positifs — et qui est faux. C'est l'erreur à surveiller.

Continuer sur Adloun : animation, QCM, fiches, exercices