Graphes et chaînes de Markov — Terminale

Pour compter des chemins dans un réseau ou modéliser une évolution aléatoire entre plusieurs états (météo, abonnements).

Matrice d'adjacence $A$ : $a_{ij} = 1$ si arête de $i$ vers $j$. Le coefficient $(i, j)$ de $A^k$ = nombre de chemins de longueur $k$ de $i$ à $j$. Chaîne de Markov : matrice de transition $P$ (lignes de somme 1), état $\pi_{n+1} = \pi_n P$, $\pi_n = \pi_0 P^n$. État stable : $\pi = \pi P$ avec somme des coefficients 1.

1. Numérote les sommets, construis $A$ ou $P$.
2. Chemins : calcule $A^k$.
3. Markov : $\pi_{n+1} = \pi_n P$ (vecteur ligne à gauche).
4. État stable : résous $\pi P = \pi$, $x + y = 1$.

Météo : $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}$ (beau, pluie). État stable $(x ; y)$ : $0{,}2x = 0{,}4y$, $x + y = 1$ ⇒ $\left(\frac23 ; \frac13\right)$.

Chaque ligne de $P$ somme à 1 ; l'état est un vecteur ligne multiplié à gauche : $\pi P$, pas $P\pi$.