Comment passer d'un graphe pondéré à la matrice de transition, et inversement ?

On numérote les états. Le coefficient $p_{ij}$ de la matrice de transition $P$ est le poids de l'arc allant de l'état $i$ vers l'état $j$ (probabilité de passer de $i$ à $j$ en une transition) ; une boucle sur $i$ donne le coefficient diagonal $p_{ii}$. Absence d'arc = coefficient $0$. Chaque ligne de $P$ a pour somme $1$ : c'est un bon moyen de vérifier qu'aucune probabilité n'a été oubliée.

Comment déterminer la distribution invariante d'une chaîne de Markov ?

On cherche une matrice ligne $\pi = (a \ b)$ (ou $(a \ b \ c)$ pour trois états) telle que $\pi P = \pi$, avec $a + b = 1$ (ou $a + b + c = 1$). Le produit $\pi P = \pi$ donne un système linéaire dont une équation est redondante ; on la remplace par la condition de somme $1$, puis on résout. Si tous les coefficients de $P$ sont strictement positifs, cette distribution est unique et $\pi_n$ converge vers elle quelle que soit la distribution initiale.

Quelle différence entre $\pi_n$ et $P^n$ ?

$\pi_n = \pi_0P^n$ est la distribution après $n$ transitions : c'est une matrice ligne dont le coefficient $j$ est la probabilité d'être dans l'état $j$ à l'étape $n$, en partant de la distribution initiale $\pi_0$. Le coefficient $(i, j)$ de $P^n$ est la probabilité conditionnelle de se trouver en $j$ à l'étape $n$ sachant qu'on était en $i$ à l'étape $0$ : la ligne $i$ de $P^n$ est donc $\pi_n$ pour le départ certain en $i$.

Chaînes de Markov

Définitions

Définition 1 — chaîne de Markov et propriété de Markov. Soit $E = \{1, 2\}$ ou $E = \{1, 2, 3\}$ un ensemble d’états. Une chaîne de Markov sur $E$ est une suite de variables aléatoires $(X_n)_{n \in \mathbb N}$ à valeurs dans $E$ telle que, pour tous états $i, j$ et tout entier $n$ , la probabilité $p_{ij} = P(X_{n+1} = j \mid X_n = i)$ ne dépend ni de $n$ , ni des états occupés avant l’étape $n$ (propriété de Markov : « le futur ne dépend du passé qu’à travers le présent »). $X_n$ est l’état du système à l’étape $n$ ; $p_{ij}$ est la probabilité de transition de $i$ vers $j$ .

Définition 2 — matrice de transition et graphe pondéré. La matrice de transition est la matrice carrée $P = (p_{ij})$ : la ligne $i$ contient les probabilités des transitions au départ de $i$ , la colonne $j$ celles à l’arrivée en $j$ . Le graphe orienté pondéré associé a pour sommets les états, avec un arc de $i$ vers $j$ pondéré par $p_{ij}$ lorsque $p_{ij} \neq 0$ (une boucle si $i = j$ ). Convention du programme : les distributions sont des matrices lignes et se multiplient à droite par $P$ .

Définition 3 — distribution à l’étape $n$ . La distribution (ou loi) de $X_n$ est la matrice ligne $\pi_n = \big(P(X_n = 1) \ \ P(X_n = 2)\big)$ (ou avec trois coefficients pour trois états), à coefficients positifs de somme $1$ . $\pi_0$ est la distribution initiale.

Définition 4 — distribution invariante et état absorbant. Une distribution $\pi$ est invariante (ou stationnaire) si $\pi P = \pi$ : si $\pi_0 = \pi$ , alors $\pi_n = \pi$ pour tout $n$ , la loi du système ne change plus. Un état $i$ est absorbant si $p_{ii} = 1$ : une fois atteint, on y reste, et la distribution concentrée sur $i$ est invariante.

Exemple fil rouge (météo) : chaque jour est ensoleillé ( $S$ ) ou pluvieux ( $R$ ) ; après un jour de soleil, soleil le lendemain avec probabilité $0{,}7$ ; après un jour de pluie, soleil avec probabilité $0{,}4$ . Le temps du lendemain ne dépend que du temps du jour : c’est une chaîne de Markov à deux états, de matrice $P = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}$ (ordre $S, R$ ). Les cercles du graphe figurent les boucles (rester dans le même état).

Théorèmes et propriétés

Théorème 1 (matrice stochastique). (démonstration exigible) Tous les coefficients de $P$ sont dans $[0\,;1]$ et la somme de chaque ligne vaut $1$ : $\displaystyle\sum_{j} p_{ij} = 1$ pour tout $i$ . On dit que $P$ est une matrice stochastique.

Démonstration : la ligne $i$ est la loi de $X_{n+1}$ sachant $X_n = i$ , et les probabilités d’une loi ont pour somme $1$ . $\square$ Dans le graphe pondéré, la somme des poids des arcs partant de chaque sommet vaut $1$ .

Théorème 2 (évolution de la distribution). (démonstration exigible) Pour tout entier naturel $n$ :

$\pi_{n+1} = \pi_n P \qquad \text{et} \qquad \pi_n = \pi_0 P^n$

Démonstration : les événements $\{X_n = i\}$ , $i \in E$ , 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 \in E} P(X_n = i)\, P(X_{n+1} = j \mid X_n = i) = \sum_{i \in E} \pi_n(i)\, p_{ij}$ , qui est le coefficient $j$ du produit $\pi_nP$ . Puis par récurrence : $\pi_0 = \pi_0P^0$ et si $\pi_n = \pi_0P^n$ , alors $\pi_{n+1} = \pi_nP = \pi_0P^{n+1}$ . $\square$

Théorème 3 (interprétation de $P^n$ ). Le coefficient $(i, j)$ de $P^n$ est la probabilité de passer de l’état $i$ à l’état $j$ en $n$ transitions :

$(P^n)_{ij} = P(X_n = j \mid X_0 = i)$

Preuve : si l’on part avec certitude de l’état $i$ , $\pi_0$ est la ligne ayant un $1$ en position $i$ et des $0$ ailleurs ; alors $\pi_n = \pi_0P^n$ est la ligne $i$ de $P^n$ (Théorème 2). $\square$ On peut aussi le démontrer par récurrence, comme pour le nombre de chemins dans un graphe : $(P^{n+1})_{ij} = \sum_k (P^n)_{ik}\,p_{kj}$ traduit « aller de $i$ à $k$ en $n$ étapes puis de $k$ à $j$ en une étape », les nombres d’arêtes étant remplacés par des probabilités.

Théorème 4 (convergence vers la distribution invariante). (admis) Si tous les coefficients de $P$ sont strictement positifs (ou plus généralement si une puissance $P^k$ a tous ses coefficients strictement positifs), la chaîne admet une unique distribution invariante $\pi$ , et pour toute distribution initiale $\pi_0$ , la suite $(\pi_n)$ converge vers $\pi$ . De plus, $P^n$ converge vers la matrice dont toutes les lignes sont égales à $\pi$ .

Contre-exemple : $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ (on change d’état à chaque étape) : $(0{,}5 \ \ 0{,}5)$ est invariante, mais partant de $\pi_0 = (1 \ \ 0)$ la suite $(\pi_n)$ alterne entre $(1 \ \ 0)$ et $(0 \ \ 1)$ et ne converge pas ; aucune puissance de $P$ n’a tous ses coefficients strictement positifs ( $P^n$ vaut $I$ ou $P$ ).

Méthodes

Méthode 1 — passer du graphe pondéré à la matrice de transition (et inversement).

Numéroter les états dans l’ordre de l’énoncé.
Remplir la ligne $i$ avec les poids des arcs qui partent de $i$ (boucle = coefficient diagonal, absence d’arc = $0$ ).
Contrôler que chaque ligne somme à $1$ (Théorème 1) : aucune probabilité n’a été oubliée.

Exemple : états $S$ , $R$ avec boucle $0{,}8$ sur $S$ , arc $S \to R$ de poids $0{,}2$ , arc $R \to S$ de poids $0{,}5$ et boucle $0{,}5$ sur $R$ : $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}5 & 0{,}5 \end{pmatrix}$ .

Méthode 2 — calculer la distribution après $n$ transitions.

Écrire la distribution initiale $\pi_0$ en matrice ligne.
Calculer $\pi_1 = \pi_0P$ , $\pi_2 = \pi_1P$ … ou directement $\pi_n = \pi_0P^n$ à la calculatrice (Théorème 2).
Contrôler que la somme des coefficients vaut $1$ ; lire la probabilité demandée.

Exemple (météo, départ soleil) : $\pi_0 = (1 \ \ 0)$ , $\pi_1 = (0{,}7 \ \ 0{,}3)$ , $\pi_2 = (0{,}61 \ \ 0{,}39)$ : la probabilité de pluie dans deux jours est $0{,}39$ ; à la calculatrice, $\pi_{10} = (1 \ \ 0)P^{10} \approx (0{,}571 \ \ 0{,}429)$ .

Méthode 3 — déterminer la distribution invariante.

Poser $\pi = (a \ \ b)$ (ou $(a \ \ b \ \ c)$ ) et écrire $\pi P = \pi$ .
Les équations obtenues sont redondantes (les lignes de $P$ somment à $1$ ) : en garder une (deux pour trois états) et la compléter par $a + b = 1$ (ou $a + b + c = 1$ ).
Résoudre le système ; vérifier en recalculant $\pi P$ . Si tous les coefficients de $P$ (ou d’une puissance de $P$ ) sont strictement positifs, conclure à la convergence de $(\pi_n)$ vers $\pi$ (Théorème 4).

Exemple (météo) : $0{,}7a + 0{,}4b = a$ donne $0{,}3a = 0{,}4b$ ; avec $a + b = 1$ : $a = \frac47 \approx 0{,}571$ et $b = \frac37$ . À long terme, il fait soleil environ $4$ jours sur $7$ , cohérent avec $\pi_{10}$ .

Méthode 4 — étudier une marche aléatoire sur un graphe.

Un pion se déplace sur les sommets en choisissant au hasard, de façon équiprobable, l’un des sommets adjacents : diviser chaque ligne de la matrice d’adjacence par le degré du sommet pour obtenir $P$ .
Vérifier que chaque ligne somme à $1$ (Théorème 1).
La distribution invariante est proportionnelle aux degrés : $\pi(i) = \dfrac{d(i)}{2 \times (\text{nombre d'arêtes})}$ .

Exemple : sur le triangle $A - B - C - A$ , chaque sommet a deux voisins : $P = \begin{pmatrix} 0 & \frac12 & \frac12 \\ \frac12 & 0 & \frac12 \\ \frac12 & \frac12 & 0 \end{pmatrix}$ et $\pi = \left(\frac13 \ \ \frac13 \ \ \frac13\right)$ . C’est le point de départ de l’algorithme PageRank, qui classe les pages web selon la fréquence de visite d’un « surfeur aléatoire ».

Méthode 5 — simuler une chaîne de Markov.

Pour calculer $\pi_n$ : itérer le produit ligne-matrice (fonction etape).
Pour simuler une trajectoire : tirer l’état suivant selon la ligne P[etat], en découpant $[0\,;1[$ en intervalles de longueurs $p_{i1}, p_{i2}, \ldots$ et en regardant où tombe un nombre aléatoire.
Comparer la fréquence simulée à la distribution invariante (Méthode 3).

import random

P = [[0.7, 0.3],
     [0.4, 0.6]]          # matrice de transition (états 0 = soleil, 1 = pluie)

def etape(P, pi):
    """Calcule pi P pour une matrice ligne pi."""
    k = len(P)
    return [sum(pi[i] * P[i][j] for i in range(k)) for j in range(k)]

pi = [1, 0]
for _ in range(10):
    pi = etape(P, pi)
print(pi)                  # environ [0.571, 0.429]

def simuler(P, etat, n):
    """Simule n transitions à partir de l'état donné et renvoie l'état final."""
    for _ in range(n):
        r = random.random()
        cumul, j = 0, 0
        while cumul + P[etat][j] < r:
            cumul += P[etat][j]
            j += 1
        etat = j
    return etat

# fréquence de soleil au 10e jour sur 10 000 simulations : proche de 4/7
freq = sum(simuler(P, 0, 10) == 0 for _ in range(10000)) / 10000
print(freq)

Exemple : la fréquence obtenue par simulation (environ $0{,}57$ ) confirme la distribution invariante $\left(\frac47 \ \ \frac37\right)$ calculée par la Méthode 3.

Exemple complet à trois états (opérateurs $A$ , $B$ , $C$ , graphe ci-dessus) : $P = \begin{pmatrix} 0{,}5 & 0{,}5 & 0 \\ 0{,}2 & 0{,}6 & 0{,}2 \\ 0 & 0{,}5 & 0{,}5 \end{pmatrix}$ . La Méthode 3 donne $\pi = \left(\dfrac29 \ \ \dfrac59 \ \ \dfrac29\right)$ et, comme $P^2$ a tous ses coefficients strictement positifs, les parts de marché convergent vers $22{,}2\,\%$ , $55{,}6\,\%$ et $22{,}2\,\%$ quelle que soit la répartition initiale (Théorème 4).

Définitions

Théorèmes et propriétés

Méthodes

Reste informé