Problème — Marche aléatoire sur un triangle

Graphes et Matrices · niveau 1 (application)

Énoncé

Problème — Marche aléatoire sur un triangle.

Un pion se déplace sur les sommets $1, 2, 3$ d'un triangle. À chaque étape, il quitte son sommet et rejoint l'un des deux autres, choisi au hasard (probabilité $\frac{1}{2}$ chacun).

Écrire la matrice de transition $P$ de cette chaîne de Markov à trois états.
Le pion part du sommet 1 : $π_{0} = (1, 0, 0)$ . Calculer $π_{1}$ et $π_{2}$ .
Vérifier que la distribution uniforme $π = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ est invariante.

Corrigé

De chaque sommet, le pion va vers chacun des deux autres avec probabilité $\frac{1}{2}$ (et jamais ne reste) :

$P = 0 \frac{1}{2} \frac{1}{2} \frac{1}{2} 0 \frac{1}{2} \frac{1}{2} \frac{1}{2} 0$

$π_{1} = π_{0} P = (0, \frac{1}{2}, \frac{1}{2})$ , puis :

$π_{2} = π_{1} P = (\frac{1}{2} \times \frac{1}{2} + \frac{1}{2} \times \frac{1}{2}, \frac{1}{2} \times \frac{1}{2}, \frac{1}{2} \times \frac{1}{2}) ... d e ˊ taillons :$

composante 1 : $0 \times 0 + \frac{1}{2} \times \frac{1}{2} + \frac{1}{2} \times \frac{1}{2} = \frac{1}{2}$ ; composante 2 : $0 \times \frac{1}{2} + \frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ ; composante 3 : $\frac{1}{4}$ par symétrie.

$π_{2} = (\frac{1}{2}, \frac{1}{4}, \frac{1}{4})$

Chaque composante de $π P$ vaut $\frac{1}{3} \times \frac{1}{2} + \frac{1}{3} \times \frac{1}{2} = \frac{1}{3}$ : on a bien $π P = π$ . À long terme, le pion est équiréparti sur les trois sommets.