Résumé — Graphes et chaînes de Markov

Un plan de métro, un réseau social, les pages web et leurs liens : dès que des objets sont reliés entre eux, un graphe les modélise. Et quand on saupoudre les liens de probabilités — quel temps demain sachant le temps d’aujourd’hui ? — on obtient une chaîne de Markov. Le fil rouge du chapitre : les matrices du chapitre précédent font tous les calculs, des chemins dans un graphe jusqu’aux prévisions à long terme.

Le vocabulaire des graphes

Un graphe est un ensemble de sommets, reliés par des arêtes. L’ordre du graphe est son nombre de sommets. Deux sommets reliés par une arête sont adjacents, et le degré d’un sommet est le nombre d’arêtes qui en partent.

• Un graphe est orienté quand ses arêtes ont un sens (des flèches — on parle alors de chemins), non orienté sinon.
• Une chaîne est une suite d’arêtes mises bout à bout ; sa longueur est son nombre d’arêtes. Un graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne — « tout se tient en un seul morceau ».
• Le graphe complet d’ordre $n$ relie chaque paire de sommets : chaque sommet y est de degré $n - 1$, et il compte $\dfrac{n(n-1)}{2}$ arêtes (pour $n = 4$ : $6$ arêtes).

La matrice d’adjacence

On numérote les sommets de $1$ à $n$. La matrice d’adjacence $M$ du graphe est la matrice carrée d’ordre $n$ dont le coefficient ligne $i$, colonne $j$ vaut le nombre d’arêtes allant de $i$ vers $j$ ($1$ ou $0$ dans les cas usuels). Pour un graphe non orienté, chaque arête compte dans les deux sens : $M$ est symétrique.

Autrement dit : au lieu d’énumérer les itinéraires un par un (et d’en oublier), on élève la matrice à la puissance $n$ et on lit le résultat. C’est l’exemple parfait de l’efficacité du calcul matriciel.

Les chaînes de Markov à deux ou trois états

Un système passe d’un état à un autre au fil des étapes (beau temps / pluie ; abonné A / abonné B…), et la probabilité de l’état suivant ne dépend que de l’état présent — pas du passé. C’est une chaîne de Markov, à deux ou trois états au programme. On la représente par un graphe orienté pondéré : les sommets sont les états, chaque flèche de $i$ vers $j$ porte la probabilité de transition correspondante.

• La matrice de transition $P$ range ces probabilités : le coefficient ligne $i$, colonne $j$ est la probabilité de passer de l’état $i$ à l’état $j$ en une étape. Chaque ligne a pour somme $1$ (depuis l’état $i$, on va bien quelque part !).
• La distribution à l’étape $n$ est la matrice ligne $\pi_n$ qui donne les probabilités d’être dans chaque état. $\pi_0$ est la distribution initiale.

Exemple à deux états $A$ et $B$ : $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7 \end{pmatrix}$ (depuis $A$ : rester en $A$ avec $0{,}8$, passer en $B$ avec $0{,}2$ — la ligne somme bien à $1$). Avec $\pi_0 = \begin{pmatrix} 0{,}5 & 0{,}5 \end{pmatrix}$ :

$\pi_1 = \pi_0 P = \begin{pmatrix} 0{,}5 \times 0{,}8 + 0{,}5 \times 0{,}3 & \; 0{,}5 \times 0{,}2 + 0{,}5 \times 0{,}7 \end{pmatrix} = \begin{pmatrix} 0{,}55 & 0{,}45 \end{pmatrix}$

Les distributions invariantes

Une distribution $\pi$ est invariante lorsque $\pi P = \pi$ (avec des coefficients positifs de somme $1$) : si la chaîne suit cette distribution à une étape, elle la suit encore à la suivante — c’est un équilibre. Pour la trouver, on résout le système $\pi P = \pi$ complété par la condition « somme des coefficients égale à $1$ ».

Sur l’exemple ci-dessus, en posant $\pi = \begin{pmatrix} a & 1 - a \end{pmatrix}$ : la première coordonnée de $\pi P = \pi$ donne $0{,}8a + 0{,}3(1 - a) = a$, soit $0{,}3 = 0{,}5a$, donc $a = 0{,}6$ :

$\pi = \begin{pmatrix} 0{,}6 & 0{,}4 \end{pmatrix}$

et on vérifie : $0{,}6 \times 0{,}8 + 0{,}4 \times 0{,}3 = 0{,}6$ ✓. Sur les exemples du programme, les distributions $\pi_n$ se rapprochent de cette distribution d’équilibre quand $n$ grandit — c’est elle qui décrit le « long terme » de la chaîne.

Les pièges classiques