Exercices — Graphes et chaînes de Markov

1. On place un sommet par élève ($A$, $B$, $C$, $D$, $E$) et une arête par binôme : $A\text{–}B$, $A\text{–}C$, $B\text{–}C$, $C\text{–}D$, $D\text{–}E$. Le graphe est non orienté (un binôme n’a pas de sens de parcours) et compte $5$ arêtes.

2. L’ordre est le nombre de sommets : $5$. Les degrés se lisent en comptant les arêtes en chaque sommet :

$\deg(A) = 2 \qquad \deg(B) = 2 \qquad \deg(C) = 3 \qquad \deg(D) = 2 \qquad \deg(E) = 1$

Petit contrôle de cohérence : la somme des degrés vaut $2 + 2 + 3 + 2 + 1 = 10$, soit deux fois le nombre d’arêtes — normal, chaque arête est comptée à ses deux extrémités.

3. Connexe : oui. On peut relier deux sommets quelconques par une chaîne, par exemple $E\text{–}D\text{–}C\text{–}A$ relie Emma à Ana. Complet : non. Il manque des arêtes, par exemple $A\text{–}D$ : le graphe complet d’ordre $5$ aurait $\dfrac{5 \times 4}{2} = 10$ arêtes, il n’y en a que $5$.

Réflexe à retenir : à la lecture d’un énoncé, identifie d’abord qui sont les sommets et ce qui fait une arête — puis contrôle ton dessin avec la somme des degrés, qui doit valoir deux fois le nombre d’arêtes.

1. Le coefficient ligne $i$, colonne $j$ vaut $1$ si l’arc $i \to j$ existe, $0$ sinon :

$M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$

(La matrice n’est pas symétrique : le graphe est orienté.)

2. Produit ligne par colonne :

$M^2 = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}$

Le coefficient ligne $1$ ($A$), colonne $3$ ($C$) vaut $1$ : il y a exactement un chemin de longueur $2$ de $A$ vers $C$, à savoir $A \to B \to C$. (Le coefficient ligne $1$, colonne $1$ vaut $1$ aussi : c’est le chemin $A \to C \to A$.)

3. $M^3 = M^2 \times M = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}$. Le coefficient ligne $1$, colonne $1$ vaut bien $1$ : il existe un unique chemin de longueur $3$ de $A$ vers $A$, qui est $A \to B \to C \to A$.

Réflexe à retenir : le coefficient $(i\,;\,j)$ de $M^n$ compte les chemins de longueur $n$ de $i$ vers $j$ — calcule la puissance, lis le coefficient, et sers-toi du graphe pour expliciter les chemins si l’énoncé le demande. Énumérer à la main sans matrice, c’est le risque d’en oublier.

1. Quatre flèches : $A \to A$ avec $0{,}8$, $A \to B$ avec $0{,}2$, $B \to B$ avec $0{,}7$, $B \to A$ avec $0{,}3$. D’où :

$P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7 \end{pmatrix}$

Chaque ligne somme à $1$ ✓ (ligne = état de départ).

2. $\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}$ : après un an, $55\ \%$ des clients sont en $A$. Puis :

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

(Les deux coefficients somment bien à $1$ ✓.)

3. Le coefficient ligne $2$, colonne $1$ de $P^2$ est la probabilité de passer de l’état $B$ à l’état $A$ en deux transitions : la probabilité qu’un client aujourd’hui en $B$ soit en $A$ dans deux ans (en passant par $A$ ou par $B$ l’année intermédiaire).

Réflexe à retenir : construis toujours le graphe pondéré d’abord, la matrice ensuite, et contrôle que chaque ligne somme à $1$. Ensuite les calculs s’enchaînent mécaniquement : $\pi_{n+1} = \pi_n P$, et une distribution doit toujours sommer à $1$ — vérification gratuite à chaque étape.

1. Une distribution invariante vérifie $\pi P = \pi$, avec $a + b = 1$ (c’est une distribution). L’égalité $\pi P = \pi$ donne coordonnée par coordonnée :

$\begin{cases} 0{,}8a + 0{,}3b = a \\ 0{,}2a + 0{,}7b = b \end{cases}$

2. Les deux équations se ramènent à la même : $0{,}8a + 0{,}3b = a \iff 0{,}3b = 0{,}2a$. C’est la condition $a + b = 1$ qui permet de conclure : en remplaçant $b = 1 - a$ dans $0{,}3(1 - a) = 0{,}2a$, on obtient $0{,}3 = 0{,}5a$, donc $a = 0{,}6$ et $b = 0{,}4$ :

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

Vérification : $0{,}6 \times 0{,}8 + 0{,}4 \times 0{,}3 = 0{,}48 + 0{,}12 = 0{,}6$ ✓ et $0{,}6 \times 0{,}2 + 0{,}4 \times 0{,}7 = 0{,}12 + 0{,}28 = 0{,}4$ ✓.

3. Les distributions successives $\begin{pmatrix} 0{,}5 & 0{,}5 \end{pmatrix}$, $\begin{pmatrix} 0{,}55 & 0{,}45 \end{pmatrix}$, $\begin{pmatrix} 0{,}575 & 0{,}425 \end{pmatrix}$ se rapprochent de $\pi = \begin{pmatrix} 0{,}6 & 0{,}4 \end{pmatrix}$ : la répartition des clients se stabilise au long terme vers $60\ \%$ en $A$ et $40\ \%$ en $B$, la distribution d’équilibre de la chaîne.

Réflexe à retenir : pour une invariante, le système $\pi P = \pi$ donne toujours des équations redondantes — c’est normal, et c’est la condition « somme égale à $1$ » qui débloque la résolution. Ne l’oublie jamais, et vérifie $\pi P = \pi$ à la fin.

1. Depuis chaque sommet partent deux flèches de probabilité $\dfrac{1}{2}$ vers les deux autres sommets (et aucune boucle : le pion quitte toujours son sommet). D’où :

$P = \begin{pmatrix} 0 & \dfrac{1}{2} & \dfrac{1}{2} \\ \dfrac{1}{2} & 0 & \dfrac{1}{2} \\ \dfrac{1}{2} & \dfrac{1}{2} & 0 \end{pmatrix}$

Chaque ligne somme à $1$ ✓.

2. $\pi_1 = \pi_0 P$ : comme $\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}$, c’est la première ligne de $P$ :

$\pi_1 = \begin{pmatrix} 0 & \dfrac{1}{2} & \dfrac{1}{2} \end{pmatrix}$

Puis $\pi_2 = \pi_1 P$ : première coordonnée $0 \times 0 + \dfrac{1}{2} \times \dfrac{1}{2} + \dfrac{1}{2} \times \dfrac{1}{2} = \dfrac{1}{2}$ ; deuxième $\dfrac{1}{2} \times 0 + \dfrac{1}{2} \times \dfrac{1}{2} = \dfrac{1}{4}$ ; troisième $\dfrac{1}{4}$ de même :

$\pi_2 = \begin{pmatrix} \dfrac{1}{2} & \dfrac{1}{4} & \dfrac{1}{4} \end{pmatrix}$

La probabilité que le pion soit revenu en $A$ au bout de deux étapes vaut $\dfrac{1}{2}$ — logique : où qu’il soit après une étape ($B$ ou $C$), il revient en $A$ avec probabilité $\dfrac{1}{2}$.

3. Les coefficients de $\pi$ sont positifs et somment à $1$ : c’est bien une distribution. Calculons $\pi P$ : chaque coordonnée vaut

$\frac{1}{3} \times 0 + \frac{1}{3} \times \frac{1}{2} + \frac{1}{3} \times \frac{1}{2} = \frac{1}{3}$

(les colonnes de $P$ contiennent toutes un $0$ et deux $\dfrac{1}{2}$). Donc $\pi P = \pi$ : la distribution uniforme est invariante — au long terme, le pion passe autant de temps sur chaque sommet, ce que la symétrie du triangle laissait deviner.

Réflexe à retenir : à trois états, la mécanique est la même qu’à deux — graphe pondéré, lignes de $P$ qui somment à $1$, $\pi_{n+1} = \pi_n P$. Et pour montrer qu’une distribution donnée est invariante, inutile de résoudre un système : calcule $\pi P$ et constate que tu retrouves $\pi$.