Les chaînes de Markov et leurs applications
Des systèmes qui oublient leur passé : la météo, le jeu de l’oie, le classement des pages web, la langue écrite — et le mélange d’un jeu de cartes.
L’idée en une phrase. Une chaîne de Markov est un système qui passe au hasard d’un état à un autre, de telle sorte que l’avenir ne dépend du passé que par le présent : pour prévoir demain, il suffit de savoir où l’on est aujourd’hui, pas comment on y est arrivé.
On la décrit par une matrice de transition P : le nombre P(i, j) est la probabilité d’aller de l’état i à l’état j en un pas. Chaque ligne a pour somme 1. Si μₙ désigne la loi de l’état au temps n (une ligne de probabilités), alors μₙ₊₁ = μₙ·P, donc μₙ = μ₀·Pⁿ : toute la dynamique tient dans les puissances d’une matrice.
| Notion | Ce qu’elle dit | Planche |
|---|---|---|
| Matrice de transition | Les probabilités de passage d’un état à l’autre ; Pⁿ donne les passages en n pas. | 1 |
| Loi stationnaire π | La loi qui ne change plus : π·P = π. Une chaîne irréductible et apériodique y converge, quel que soit son départ. | 2 |
| Théorème ergodique | La fraction du temps passé dans l’état i tend vers π(i), et le temps moyen de retour vaut 1/π(i). | 2 |
| État absorbant | Un état qu’on ne quitte plus. La matrice fondamentale (I − Q)⁻¹ donne le temps moyen avant d’y arriver. | 3 |
| Temps de mélange | Le nombre de pas pour être proche de l’équilibre ; il peut chuter brutalement (phénomène de seuil). | 5 |
Le graphe et la matrice : la météo de Markov
Un modèle de météo à trois états : soleil, nuages, pluie. Chaque flèche du graphe porte la probabilité du passage d’un jour au suivant. Lâchons 600 jetons, qui sautent chaque jour selon ces probabilités : la proportion de jetons dans chaque état suit exactement la loi μₙ = μ₀·Pⁿ, que la page calcule en parallèle.
L’équilibre : la loi stationnaire et la vitesse d’oubli
Quel que soit le point de départ, la loi μₙ se rapproche d’une même loi π, qui vérifie π·P = π : la loi stationnaire. La vitesse de rapprochement est réglée par la deuxième plus grande valeur propre de P, en module |λ₂| : la distance à l’équilibre est divisée par environ 1/|λ₂| à chaque pas. Et sur une seule trajectoire très longue, la fraction du temps passé dans chaque état tend aussi vers π : c’est le théorème ergodique.
Les états absorbants : combien de coups dure le jeu de l’oie ?
Un plateau de 36 cases avec des échelles (qui font monter) et des serpents (qui font descendre). On lance un dé et l’on avance ; la partie s’arrête quand on atteint la case 36. La position est une chaîne de Markov dont la case 36 est un état absorbant. Si Q est la matrice des transitions entre les cases non finales, la matrice fondamentale N = (I − Q)⁻¹ donne le nombre moyen de passages par chaque case, et la somme de sa première ligne le nombre moyen de lancers.
Applications : le web, la langue, la simulation
Comment classer des pages web ? Brin et Page (1998) imaginent un internaute qui clique au hasard sur les liens de la page où il se trouve, et qui, avec une probabilité 1 − d, se « téléporte » sur une page quelconque. Sa position est une chaîne de Markov ; l’importance d’une page, son PageRank, est la probabilité stationnaire d’y être. Une page compte si des pages qui comptent pointent vers elle.
En 1913, Andreï Markov compte à la main les 20 000 premières lettres d’Eugène Onéguine de Pouchkine et note si chaque voyelle ou consonne est suivie d’une voyelle ou d’une consonne. Il trouve 43,2 % de voyelles, une voyelle suivie d’une voyelle dans 12,8 % des cas, une consonne suivie d’une voyelle dans 66,3 % des cas : les lettres ne sont pas indépendantes, mais forment une chaîne à deux états. Refaisons l’expérience sur le texte de cette page.
Claude Shannon (1948) pousse l’idée plus loin : on fabrique du texte en tirant chaque lettre selon les k lettres précédentes, avec les fréquences observées. Plus la mémoire k est longue, plus le texte ressemble à du français — sans jamais avoir de sens.
Comment tirer au hasard selon une loi compliquée qu’on ne sait pas tirer directement ? Metropolis et ses collègues (1953) inventent une chaîne de Markov dont la loi stationnaire est précisément la loi voulue : on propose un pas au hasard, et on l’accepte avec la probabilité min(1, π(nouveau)/π(actuel)). Il suffit de connaître π à une constante près. Ici, une loi à deux bosses sur les entiers de 0 à 60.
Signature — combien de fois faut-il battre les cartes ?
Battre un jeu de cartes « à l’américaine » (on coupe en deux paquets, puis on les entrelace) est un pas d’une chaîne de Markov sur les 52! ordres possibles du jeu, soit environ 8·10⁶⁷ états. La loi stationnaire est l’uniforme : un jeu parfaitement mélangé. En 1992, Dave Bayer et Persi Diaconis ont calculé exactement, pour le modèle de Gilbert, Shannon et Reeds, la distance à l’équilibre après k battages : elle ne dépend que du nombre de « suites montantes » du jeu. Résultat : il faut sept battages, et la distance ne décroît pas doucement — elle s’effondre d’un coup.
Repères historiques
- 1906Andreï Markov étudie des suites de variables dépendantes et montre que la loi des grands nombres s’y applique encore : ce sont les premières chaînes de Markov.
- 1907Paul et Tatiana Ehrenfest proposent leur modèle d’urnes pour expliquer le retour à l’équilibre d’un gaz.
- 1913Markov analyse les successions de voyelles et de consonnes d’Eugène Onéguine.
- 1931Andreï Kolmogorov fonde la théorie des processus de Markov en temps continu.
- 1948Claude Shannon engendre du texte anglais par des chaînes de Markov sur les lettres et les mots, dans sa théorie de l’information.
- 1953Nicholas Metropolis, Arianna et Marshall Rosenbluth, Augusta et Edward Teller publient l’algorithme de Metropolis ; W. Keith Hastings le généralise en 1970.
- 1992Dave Bayer et Persi Diaconis démontrent que sept battages suffisent pour 52 cartes.
- 1998Sergey Brin et Larry Page présentent PageRank, le classement fondateur de Google.
Ce qu’il faut retenir
Une matrice suffit
Une chaîne de Markov est entièrement décrite par sa matrice de transition : la loi après n pas est μ₀·Pⁿ, et la matrice fondamentale donne les temps d’absorption.L’équilibre
Une chaîne irréductible et apériodique oublie son départ et converge vers sa loi stationnaire, à une vitesse réglée par |λ₂| ; les moyennes dans le temps convergent aussi vers π.Des usages partout
Classement du web, modèles de langue, simulation de lois complexes, files d’attente, génétique des populations, finance, physique statistique, mélange des cartes.Pour aller plus loin
Pourquoi la convergence ? Si P est irréductible (on peut aller de tout état à tout autre) et apériodique, le théorème de Perron-Frobenius assure que 1 est une valeur propre simple et que toutes les autres sont de module strictement inférieur à 1. En décomposant μ₀ sur les vecteurs propres, la composante sur π reste et les autres s’éteignent comme |λ₂|ⁿ.
Réversibilité. L’algorithme de Metropolis vérifie l’équilibre détaillé π(i)P(i, j) = π(j)P(j, i), ce qui suffit pour que π soit stationnaire. C’est la base des méthodes de Monte-Carlo par chaînes de Markov (MCMC), utilisées en statistique bayésienne, en physique et en apprentissage automatique.
La formule de Bayer et Diaconis. Après k battages de Gilbert-Shannon-Reeds, une permutation ayant r suites montantes a la probabilité C(2ᵏ + n − r, n)/2^(kn). Le nombre de permutations à r suites montantes est un nombre eulérien ; la distance à l’équilibre en découle par une simple somme, que la page calcule en entiers exacts.