Algèbre linéaire · Chaîne de Markov

Chaîne de Markov

Une chaîne de Markov change d’état au hasard. Les chances du prochain état dépendent uniquement de l’état actuel. Avec la matrice de transition P, la distribution de demain est celle d’aujourd’hui multipliée par P. En répétant, on approche souvent une distribution stationnaire π telle que πP = π, vecteur propre à gauche de valeur propre 1.

Chaîne de Markov dans cette visualisation

Dans une chaîne de Markov, les chances du prochain état dépendent uniquement de l’état actuel. Ici, les états sont soleil, nuages et pluie. La ligne ii de la matrice de transition PP donne les probabilités de demain si l’état du jour est ii. Chaque ligne est donc un vecteur de probabilités. Si la distribution du jour est le vecteur ligne pp, celle du lendemain est pPpP et celle après nn jours est pn=p0Pnp_n = p_0 P^n. Avec trois états, chaque distribution est un point du triangle : chaque sommet représente un état certain et les trois probabilités sont les poids des sommets. Les points foncés sont les lignes de PP, le bleu est le départ et le trajet rouge relie p0,p1,p2,…p_0, p_1, p_2, \dots.

L’effet d’un pas

Un pas envoie chaque sommet sur sa ligne : après une journée certainement ensoleillée vient la distribution de la première ligne. Toute distribution pp est une moyenne pondérée des sommets, donc pPpP est la même moyenne des lignes. Tout le triangle entre dans celui formé par les lignes, puis, au deuxième pas, dans celui des lignes de P2P^2. Si une puissance de PP a toutes ses entrées strictement positives, ces triangles emboîtés se resserrent sur un point : la distribution stationnaire π\pi.

Pourquoi π est un vecteur propre et à quelle vitesse pₙ s’en approche

Le point fixe vérifie πP=π\pi P = \pi : π\pi est un vecteur propre à gauche de valeur propre 1 (en colonnes, PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). Les composantes de l’écart p0−πp_0 - \pi ont une somme nulle. Sur ce sous-espace, PP a les deux autres valeurs propres λ2,λ3\lambda_2, \lambda_3. Chaque pas multiplie un vecteur d’une direction propre par la valeur propre associée. Si leurs modules sont inférieurs à 1, pnp_n tend vers π\pi, au rythme fixé par le plus grand module ∣λ2∣|\lambda_2|. Pour la météo, ∣λ2∣≈0.462|\lambda_2| \approx 0.462 : pour nn grand, il reste un peu moins de la moitié de la distance par pas si le départ a une composante dans la direction de λ2\lambda_2. Si les valeurs propres sont complexes, le trajet tourne en se contractant.

Quand la distribution ne converge pas

Dans le cycle, soleil, nuages et pluie se succèdent sans fin. Les deux autres valeurs propres ont pour module 1 et pnp_n continue de tourner sauf si le départ est π\pi. Avec deux états absorbants, soleil et pluie persistent chacun indéfiniment. La valeur propre 1 est double, tout mélange des deux reste fixe, et pnp_n converge vers une limite qui dépend du départ. Dans une chaîne finie, pnp_n tend vers le même π\pi depuis tout départ exactement lorsqu’il existe une seule classe fermée d’états communicants et qu’elle est apériodique. Ses états peuvent tous se rejoindre sans qu’on puisse en sortir. Il suffit par exemple qu’une puissance PmP^m ait toutes ses entrées strictement positives.

À remarquer

  • Quelle que soit la météo initiale, la distribution stationnaire donne les probabilités pour un jour lointain. Le temps, lui, continue de changer de jour en jour.
  • Au-delà de trois états, les distributions remplissent un simplexe, analogue du triangle en dimension supérieure. Le raisonnement reste le même.

Commandes

  • Faites glisser un point foncé pour changer une ligne de la matrice ou le point bleu pour changer le départ. Les flèches déplacent le point sélectionné d’un centième.

Notions liées