Explorateur de chaînes de Markov stationnaires

Simulateur de matrice de transition avec évolution en k étapes et intuition sur l'état stationnaire.

Exemple résolu — Explorateur de chaînes de Markov stationnaires

1	0.65985
2	0.218714
3	0.121436
Distance à la stationnarité	0.08893

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Explorateur de chaînes de Markov stationnaires

Une distribution est stationnaire lorsqu'un pas de plus ne change rien : πP = π. C'est un point fixe de la matrice de transition — la chaîne continue d'évoluer entre les états, mais les proportions cessent de varier.

Ce que signifie chaque symbole

P: la matrice de transition. L'élément situé à la ligne i, colonne j est la probabilité de passer de l'état i à l'état j, si bien que la somme de chaque ligne doit valoir 1 — ce que la grille ci-dessus vérifie pour vous.
p(0): la distribution initiale : le point de départ de la chaîne. La valeur par défaut (1, 0, 0) signifie qu'elle commence dans l'état 1 avec certitude.
p(k): la distribution après k pas, obtenue en multipliant par P une fois par pas.
π: la distribution stationnaire — celle qui vérifie πP = π.
k: le nombre de pas à effectuer, défini ci-dessus. Le tableau de trajectoire affiche chaque distribution de p(0) à p(k).

D’où vient la formule

Exprimez ce que demande la stationnarité : après un pas, la distribution reste inchangée, d'où πP = π.
En réorganisant, on obtient π(P − I) = 0 — un système d'équations linéaires, à raison d'une par état. À lui seul, ce système possède une infinité de solutions, car tout multiple d'une solution en est aussi une.
Ajoutez la condition qui en fait une distribution de probabilité, Σπ = 1, et la solution devient unique. Pour la matrice par défaut, elle vaut exactement 8/13, 3/13, 2/13 — soit les 0.615385, 0.230769, 0.153846 indiqués ci-dessus.

Comment lire ce que vous voyez

Trois panneaux. p(k) indique où se trouve réellement la chaîne après vos k pas ; π indique sa destination, avec le nombre d'itérations et la mention de convergence ; et la distance à la stationnarité mesure l'écart entre les deux — 0.08893 pour la valeur par défaut k = 8, ce qui explique pourquoi la note indique que la chaîne ne s'est pas encore totalement mélangée. Le tableau de trajectoire ci-dessous montre chaque pas, en partant de (1, 0, 0).

Suppose: Un ensemble fini d'états et des probabilités qui ne varient jamais au cours du temps. Le fait que la somme de chaque ligne soit égale à 1 n'est pas une règle de mise en forme, mais l'affirmation que la chaîne doit aller quelque part à chaque pas.
Ne tient plus quand: Le π ci-dessus est qualifié d'estimation pour une bonne raison : il est obtenu en faisant évoluer la chaîne de manière répétée — 83 itérations pour la matrice par défaut — et le calcul s'arrête lorsque les distributions successives cessent de varier. Il s'agit d'un critère numérique, et non d'une démonstration. La réponse exacte est ici l'ensemble de rationnels 8/13, 3/13, 2/13, et les décimales affichées sont ces valeurs arrondies à six chiffres après la virgule.

PageRank est exactement ce calcul, appliqué au web entier 🖖

La distribution stationnaire n’est pas qu’un exercice de manuel : Google s’est fondé sur une. Voyez chaque page web comme un état et chaque lien comme une transition ; la distribution stationnaire de cette chaîne colossale indique la fréquence à laquelle un lecteur cliquant indéfiniment atterrirait sur chaque page. C’est PageRank. Le fameux facteur d’amortissement de 0,85, qui envoie le surfeur sur une page au hasard 15% du temps, n’est pas non plus un réglage arbitraire : il garantit que chaque état peut atteindre tous les autres, c’est-à-dire précisément la condition qui rend la distribution stationnaire unique et atteignable. Sans lui, les pages sans issue et les boucles fermées piégeraient la marche et fausseraient la réponse.

Vers quoi le long terme se stabilise 🖖

Chaque ligne de la matrice de transition n'est qu'un jeu de probabilités : si vous êtes dans un état, avec quelle probabilité sautez-vous vers chacun des autres à l'étape suivante. Multipliez votre vecteur de probabilité actuel par P une fois par étape et les nombres dérivent vers un mélange fixe, la distribution stationnaire π. Ce mélange indique la fraction du temps que le système passe dans chaque état à long terme — essayez l'exemple météo et observez p(k) se stabiliser.

Une cible unique jamais atteinte 🖖

Réglez la matrice à deux états sur [[0,1],[1,0]] — une pièce qui bascule toujours. Elle possède une distribution stationnaire unique parfaitement valide π = (0.5, 0.5), mais en partant de (1, 0), p(k) oscille indéfiniment 1,0 → 0,1 → 1,0 sans jamais converger. Ce sont précisément ces chaînes périodiques qui expliquent pourquoi l'explorateur peut afficher converged: no ; la convergence garantie exige une chaîne apériodique, pas seulement une π unique.

Exercice

Vérifiez-vous

Prédisez d’abord la réponse, puis utilisez les commandes ci-dessus pour vérifier. N’affichez la solution qu’après vous être engagé sur une hypothèse : c’est ce qui en fait un exercice.

Par défaut, la chaîne démarre avec certitude dans l’état 1, p(0) = (1, 0, 0). Passez à (0, 0, 1) pour qu’elle parte de l’état 3. Prédisez quels affichages bougent et lesquels non.

Afficher la réponse

p(k) et la distance bougent ; π et le nombre d’itérations non. Depuis l’état 1, huit pas atteignent 0.659852, 0.218714, 0.121436, une distance de 0.08893. Depuis l’état 3, ils atteignent 0.522304, 0.255274, 0.222421, une distance de 0.18616 — plus loin, car l’état 3 est la destination la plus rare. Dans les deux cas π affiche 0.615385, 0.230769, 0.153846 après les mêmes 83 itérations. Le point de départ décide où en est la chaîne, jamais où elle va : πP = π ne mentionne que la matrice.
Revenez à (1, 0, 0) et augmentez le nombre de pas. Au bout de combien la distance à la stationnarité affiche-t-elle 0 — et la chaîne est-elle alors arrivée ?

Afficher la réponse

k = 80 affiche 0, et non, elle n’y est pas. Dès k = 40 la distance vaut 0.000024 ; les six décimales affichées s’épuisent simplement avant l’écart. Cette chaîne s’approche de π géométriquement et ne l’atteint jamais en un nombre fini de pas : le 0 est l’arrondi de l’affichage, la même raison pour laquelle π lui-même est présenté comme une estimation. Comparez k = 8, où la distance est 0.08893 et la note dit encore que la chaîne n’a pas mélangé.

Problème entièrement résolu

Huit étapes d'une chaîne à trois états démarrée à l'état 1 5 étapes
Une chaîne à trois états initialisée entièrement dans l'état 1, exécutée pendant huit étapes. Déterminez vers quoi elle tend et quelle distance il lui reste à parcourir.
1. Une étape est un produit vecteur-matrice : la probabilité de se trouver dans l'état j à l'étape suivante est la somme sur i d'être en i actuellement et de passer de i → j.
  
  $p_{k + 1} = p_{k} P, p_{0} = (1, 0, 0)$
2. Huit étapes de ce calcul donnent la distribution affichée par le panneau. L'état 1 détient encore deux tiers de la probabilité, ce qui est beaucoup sachant que la chaîne y a démarré avec certitude.
  
  $p_{8} = (0.65985, 0.218714, 0.121436)$
3. La destination est la distribution stationnaire — celle qu'une étape laisse inchangée. Résoudre πP = π avec la somme des probabilités égale à 1 donne des fractions exactes, des huitièmes et des treizièmes, et non des décimaux.
  
  $π P = π, \sum π_{i} = 1 ⟹ π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) = (0.615385, 0.230769, 0.153846)$
4. Comparer les deux donne la distance indiquée par le panneau, et elle n'est pas négligeable : après huit étapes, la chaîne est encore distante d'environ 0,089 au total.
  
  $∥ p_{8} - π ∥_{1} = 0.04447 + 0.01206 + 0.03241 = 0.08893$
5. Cet écart s'amenuise géométriquement, régi par la deuxième plus grande valeur propre de P. Une décroissance géométrique signifie qu'il diminue de moitié en un nombre fixe d'étapes et n'atteint jamais zéro en un nombre fini d'étapes.
  
  $the gap shrinks like ∣ λ_{2} ∣^{k} — geometric, never zero$
Réponse

L'outil affiche 0,65985, 0,218714, 0,121436 après huit étapes, encore éloigné de 0,08893 de la stationnarité. La distribution stationnaire est exactement (8/13, 3/13, 2/13), et le fait à retenir est qu'elle ne dépend pas du point de départ : ces trois mêmes fractions constituent la limite pour toute distribution initiale, ce qui en fait une propriété de la matrice de transition plutôt que de cette exécution particulière. Cette indépendance est ce qui rend les distributions stationnaires utiles : PageRank, l'échantillonnage MCMC et l'occupation des files d'attente reposent tous sur le fait que le résultat à long terme est une propriété des seules règles de transition. Seul le temps nécessaire pour y parvenir dépend du point de départ.

$π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) is where it goes, and p_{0} does not matter$

Références (1)

The stationary distribution put to work on the whole web, damping factor and all: S. Brin & L. Page, “The anatomy of a large-scale hypertextual Web search engine.” Computer Networks and ISDN Systems 30, 107–117, 1998.

Par l’équipe 42Math · Mis à jour 2026-07-26

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Mathématiques →

Exemples de problèmes

chaîne ergodique à 3 états - Après huit étapes, l'affichage indique toujours un écart L1 de 0,08893. La distribution stationnaire atteinte — 0,615385 ; 0,230769 ; 0,153846 — correspond très exactement à 8/13, 3/13 et 2/13. Une matrice écrite en dixièmes possède ainsi un point fixe en treizièmes, car π s'obtient en résolvant πP = π, et non à partir des coefficients que vous avez saisis.
météo, 2 états - 0,666667 et 0,333333 : pour une chaîne à deux états, vous n'avez jamais besoin d'itérer pour les obtenir. π correspond aux deux probabilités hors diagonale, interverties puis normalisées : 0,4 / (0,2 + 0,4) = 2/3. En partant d'une distribution 50/50, dix étapes vous amènent à moins de 0,000035 de ce résultat.
chaîne à 3 états à mélange lent - Ici, trente étapes laissent une distance L1 de 0,081995, soit un éloignement de la stationnarité plus de deux mille fois supérieur à ce qu'atteint la chaîne météo en dix itérations. L'explication se trouve sur la diagonale. Avec 0,97, 0,94 et 0,96, la chaîne ne quitte presque jamais son état courant. Il a fallu 493 itérations de la méthode de la puissance contre 25 pour la chaîne météo, et π vaut 4/11, 4/11, 3/11.