Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank

La propriété de Markov, la matrice de transition et l’évolution d’une distribution sur un modèle météo, la distribution stationnaire et le théorème ergodique, l’analyse des voyelles de Markov appliquée au Máj de Mácha, PageRank et la génération de texte.

13 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 38 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

En 1913, le mathématicien russe Andreï Markov était penché sur l’Eugène Onéguine de Pouchkine et faisait une chose qu’un spécialiste de la littérature aurait jugée barbare : il comptait combien de fois une voyelle est suivie d’une autre voyelle. Il voulait montrer que la loi des grands nombres vaut aussi pour des événements qui dépendent les uns des autres — et il inventa au passage un modèle qui classe aujourd’hui les pages dans les moteurs de recherche, prévoit la météo, génère du texte et se trouve à l’origine de toute une famille d’algorithmes d’intelligence artificielle. Cette partie ouvre le module consacré aux modèles probabilistes.

Elle fait suite aux parties Probabilité conditionnelle et théorème de Bayes et Algèbre linéaire pour l’apprentissage automatique.

1. Un processus sans mémoire

Définition — chaîne de Markov

Une suite de variables aléatoires X₀, X₁, X₂, … à valeurs dans un ensemble fini d’états S est une chaîne de Markov si, pour tout t et tous les états, elle vérifie la propriété de Markov

P(X_t+1 = j | X_t = i, X_t−1, …, X₀) = P(X_t+1 = j | X_t = i).

Si cette probabilité ne dépend pas de t, la chaîne est dite homogène.

Ce qu’apporte la propriété de Markov se voit sur la probabilité d’une trajectoire entière. En général, la règle de la chaîne la décompose en un produit de probabilités conditionnelles qui dépendent chacune de tout le passé. La propriété de Markov raye de chaque condition tout sauf le dernier état :

P(X₀ = x₀, …, X_T = x_T) = π₀(x₀) · ∏_t=1^T P(x_t | x_t−1)

P(X₀ = x₀, …)

probabilité que la chaîne passe exactement par cette suite d’états

π₀(x₀)

distribution initiale — la matrice ne dit pas d’où la chaîne part ; cette donnée doit venir de l’extérieur

∏_t=1^T

produit sur les pas — les pas s’enchaînent et chacun doit « réussir », c’est pourquoi on multiplie

P(x_t | x_t−1)

probabilité de transition d’un pas, c’est-à-dire l’élément de la matrice de transition à la ligne x_t−1 et à la colonne x_t — grâce à la propriété de Markov, elle ne dépend que de l’état précédent, pas de toute l’histoire ; sans elle, on aurait ici P(x_t | x₀, …, x_t−1)

2. La matrice de transition

Définition — matrice de transition

Une chaîne homogène à n états est déterminée par sa matrice de transition P = (p_ij), où p_ij = P(X_t+1 = j | X_t = i). La matrice est stochastique : p_ij ≥ 0 et chaque ligne a pour somme 1.

Un modèle météo jouet à trois états : après une journée de soleil, il refait soleil avec une probabilité de 0,6, il y a des nuages avec 0,3 et il pleut avec 0,1 ; après une journée nuageuse, 0,3 / 0,4 / 0,3 ; après une journée de pluie, 0,2 / 0,4 / 0,4. Sous forme de graphe :

La même information sous forme de matrice — la ligne est la météo d’aujourd’hui, la colonne celle de demain :

Exemple — probabilité d’une trajectoire

Aujourd’hui, il fait soleil (π₀ = (1 ; 0 ; 0)). Quelle est la probabilité que les trois jours suivants soient soleil, nuages, pluie ? D’après la formule de la trajectoire

P = 1 · p_{soleil→soleil} · p_{soleil→nuages} · p_{nuages→pluie} = 1 · 0,6 · 0,3 · 0,3 = 0,054.

Soit 5,4 %. La somme sur les 3³ = 27 triplets de jours possibles vaut 1 — précisément parce que chaque ligne de la matrice a pour somme 1.

3. Comment la distribution évolue

Théorème — distribution après n pas

Si π_t est le vecteur ligne de la distribution de X_t, alors π_t+1 = π_t P, et donc π_t = π₀ P^t. L’élément (i, j) de la matrice Pⁿ est la probabilité de passer de i à j en n pas.

π_t+1(j) = ∑_i π_t(i) · p_ij

π_t+1(j)

probabilité que demain soit dans l’état j — une composante du nouveau vecteur ligne

∑_i

somme sur tous les états d’aujourd’hui — on peut arriver en j depuis n’importe où et ces chemins s’excluent mutuellement, donc leurs probabilités s’additionnent (formule des probabilités totales)

π_t(i)

à quel point il est probable que nous soyons en i aujourd’hui — le poids du chemin passant par i

p_ij

probabilité de passer de i à j — d’après la propriété de Markov, il suffit de connaître l’état d’aujourd’hui

Exemple — la distribution d’après-demain

Demain (après une journée de soleil aujourd’hui), π₁ = (0,6 ; 0,3 ; 0,1). Pour après-demain, composante par composante — une colonne de la matrice multipliée par le vecteur π₁ :

• soleil : 0,6 · 0,6 + 0,3 · 0,3 + 0,1 · 0,2 = 0,36 + 0,09 + 0,02 = 0,47,
• nuages : 0,6 · 0,3 + 0,3 · 0,4 + 0,1 · 0,4 = 0,18 + 0,12 + 0,04 = 0,34,
• pluie : 0,6 · 0,1 + 0,3 · 0,3 + 0,1 · 0,4 = 0,06 + 0,09 + 0,04 = 0,19.

La somme vaut de nouveau 1. Dans trois jours, la même démarche donne (0,422 ; 0,353 ; 0,225).

Chose intéressante : au bout d’une semaine environ, peu importe qu’il fasse soleil ou qu’il pleuve aujourd’hui. Les deux distributions se rejoignent aux mêmes valeurs et ne changent plus. La chaîne a « oublié » où elle avait commencé.

Théorème — à quelle vitesse la chaîne oublie

Si la matrice P à n états a n valeurs propres distinctes 1 = λ₁, λ₂, …, λ_n et si |λ_k| < 1 pour k ≥ 2, alors toute distribution initiale se décompose sur les vecteurs propres à gauche et

π_t = π + a₂λ₂^tu₂ + … + a_nλ_n^tu_n,

où π est la distribution stationnaire. L’écart à π décroît donc comme |λ₂|^t, où λ₂ est la deuxième plus grande valeur propre en valeur absolue.

π_t ≈ π + a₂u₂ · λ₂^t

π_t

distribution après t jours

π

distribution stationnaire — elle correspond à la valeur propre 1, qui ne change pas quand on l’élève à une puissance ; c’est pourquoi c’est la seule partie qui survit

a₂u₂

écart initial dans la direction du deuxième vecteur propre — c’est seulement ici que se manifeste le point de départ de la chaîne (soleil ou pluie) ; pour la composante soleil, il est positif pour un départ ensoleillé et négatif pour un départ pluvieux

λ₂^t

chaque jour, l’écart est multiplié par λ₂ — c’est la vitesse d’oubli ; les autres termes, aux |λ| plus petits, disparaissent encore plus vite, c’est pourquoi on peut les omettre

Exemple — valeurs propres de la matrice météo

La somme des valeurs propres est la trace de la matrice, 0,6 + 0,4 + 0,4 = 1,4, et leur produit est le déterminant, qui vaut 0,01. Une valeur propre est 1 (les lignes ont pour somme 1), donc les deux autres vérifient λ₂ + λ₃ = 0,4 et λ₂λ₃ = 0,01. Ce sont les racines de λ² − 0,4λ + 0,01 = 0 :

λ_2,3 = 0,2 ± √0,03 = (2 ± √3)/10, soit λ₂ ≈ 0,373 et λ₃ ≈ 0,027.

Pour un départ ensoleillé, l’écart de la probabilité du soleil à sa valeur stationnaire 0,393 vaut après 3, 4 et 5 jours 0,0286 ; 0,0107 ; 0,0040 — environ 0,373 fois plus petit chaque jour. Au bout d’une semaine, il vaut 0,0006, et −0,0005 pour un départ pluvieux : les deux débuts ne diffèrent qu’à la quatrième décimale. L’écart est divisé par cent en ln 0,01 / ln 0,373 ≈ 4,7 jours.

4. La distribution stationnaire

Définition — distribution stationnaire

Une distribution π est stationnaire si π P = π — autrement dit, π est un vecteur propre à gauche de la matrice P pour la valeur propre 1.

Définition — chaîne irréductible et apériodique

Notons p_ij⁽ⁿ⁾ l’élément (i, j) de la matrice Pⁿ, c’est-à-dire la probabilité de passer de i à j en n pas.

• La chaîne est irréductible si, pour tous états i, j, il existe n ≥ 1 tel que p_ij⁽ⁿ⁾ > 0.
• La période de l’état i est d(i) = pgcd{n ≥ 1 : p_ii⁽ⁿ⁾ > 0} — le plus grand commun diviseur des longueurs de tous les chemins qui reviennent en i. Si d(i) = 1, l’état est apériodique ; dans une chaîne irréductible, tous les états ont la même période.

La météo est les deux d’emblée : tous les éléments de P sont positifs (n = 1 suffit) et p_ii > 0, donc le retour est possible en 1 pas et la période vaut 1. En revanche, une chaîne à deux états qui les alterne régulièrement (p₁₂ = p₂₁ = 1) est irréductible, mais de période 2 : pour le départ (1 ; 0), π₀P^t saute indéfiniment entre (1 ; 0) et (0 ; 1), bien que la distribution stationnaire (½ ; ½) existe.

Théorème — théorème ergodique pour les chaînes finies

Si une chaîne finie est irréductible (on peut aller de chaque état à chaque état) et apériodique, elle a une unique distribution stationnaire π et, pour toute distribution initiale, π₀ P^t → π. De plus, la proportion du temps que la chaîne passe dans l’état j tend avec probabilité 1 vers π_j, et le temps moyen de retour en j vaut 1/π_j.

Pour notre modèle, la distribution stationnaire vaut exactement (24/61 ; 22/61 ; 15/61) ≈ (0,393 ; 0,361 ; 0,246) : à long terme, il fait soleil 39 % des jours, il y a des nuages 36 % des jours et il pleut 25 % des jours. Après une journée de pluie, on attend la pluie suivante en moyenne 1/0,246 ≈ 4,07 jours.

Exemple — la distribution stationnaire de la météo à la main

On cherche π = (a ; b ; c) tel que πP = π. Colonne par colonne de la matrice :

• a = 0,6a + 0,3b + 0,2c, donc 4a = 3b + 2c,
• b = 0,3a + 0,4b + 0,4c,
• c = 0,1a + 0,3b + 0,4c, donc 6c = a + 3b.

Les équations sont dépendantes (en additionnant les trois, on obtient a + b + c = a + b + c), on laisse donc de côté celle du milieu. De la troisième, a = 6c − 3b ; en substituant dans la première, 24c − 12b = 3b + 2c, donc b = 22c/15 et a = 6c − 66c/15 = 24c/15. Le rapport est a : b : c = 24 : 22 : 15, et la condition a + b + c = 1 donne

π = (24/61 ; 22/61 ; 15/61) ≈ (0,393 ; 0,361 ; 0,246).

Le temps moyen de retour à la pluie vaut 1/π_pluie = 61/15 ≈ 4,07 jours.

Et la simulation d’une trajectoire aléatoire montre le théorème ergodique en action :

La simulation tire chaque jour séparément selon la ligne de l’état du jour : un nombre aléatoire u dans [0, 1) est comparé aux sommes cumulées de la ligne. Après une journée de soleil, u < 0,6 mène au soleil, 0,6 ≤ u < 0,9 aux nuages et le reste à la pluie :

stav = soleil
for den in 1 … N:
    u = nombre aléatoire dans [0, 1)
    j = 0
    while u ≥ P[stav][j]:          # soustrais les probabilités jusqu’à ce que u « tombe » dans une case
        u = u − P[stav][j]
        j = j + 1
    stav = j
    počet[stav] += 1
podíly = počet / N                 # d’après le théorème ergodique → π

La distribution stationnaire elle-même se calcule sans tirage, par multiplications répétées par la matrice :

import numpy as np

P = np.array([[0.6, 0.3, 0.1],
              [0.3, 0.4, 0.3],
              [0.2, 0.4, 0.4]])

pi = np.ones(3) / 3
for _ in range(100):          # méthode de la puissance itérée : π ← π P
    pi = pi @ P
print(pi.round(3))            # [0.393 0.361 0.246]

5. Markov, Onéguine et Máj

Markov a parcouru les 20 000 premières lettres d’Eugène Onéguine et a marqué chacune comme voyelle ou consonne. Les voyelles représentaient 43,2 %. Si les lettres se suivaient indépendamment, une voyelle suivrait une voyelle aussi dans 43,2 % des cas. Markov n’en a pourtant compté que 12,8 %, contre 66,3 % après une consonne. Les lettres dépendent les unes des autres — et pourtant, la proportion de voyelles dans un long texte converge de façon fiable. C’était sa preuve que la loi des grands nombres n’a pas besoin de l’indépendance.

Refaisons-le sur la première strophe de Máj (« Mai »), le poème de Karel Hynek Mácha (« Byl pozdní večer – první máj… », « C’était le soir, le premier mai… »). Elle compte 311 lettres, dont 37,6 % de voyelles. Estimation de la matrice de transition à partir des effectifs des paires :

La strophe ne contient que 6 paires de voyelles consécutives — le tchèque aime les alterner avec des consonnes encore plus que le russe. Et la distribution stationnaire de cette chaîne donne 37,7 % de voyelles : la chaîne estimée à partir du texte se « stabilise » pratiquement sur la proportion réellement présente dans le texte (seules la première et la dernière lettre font la différence).

p̂_ij = n_ij / ∑_k n_ik

p̂_ij

estimation de la probabilité de transition — le chapeau indique qu’il s’agit d’un nombre calculé à partir des données, et non de la vraie valeur

n_ij

nombre de fois où, dans le texte, j a suivi directement i — on compte les paires de lettres voisines, car une chaîne de Markov ne regarde qu’un pas en arrière

∑_k n_ik

nombre de fois où i a été suivi de n’importe quoi — la division fait que la ligne a pour somme 1, comme l’exige une matrice stochastique

Exemple — effectifs des paires dans la première strophe

311 lettres donnent 310 paires voisines. Voyelle–voyelle 6, voyelle–consonne 111, consonne–voyelle 111, consonne–consonne 82. D’où

p̂_voy→voy = 6/117 = 0,051, p̂_voy→con = 111/117 = 0,949, p̂_con→voy = 111/193 = 0,575, p̂_con→con = 82/193 = 0,425.

Une chaîne à deux états a une distribution stationnaire donnée par une formule simple :

π_voy = p_con→voy / (p_voy→con + p_con→voy)

π_voy

proportion de voyelles à long terme

p_con→voy

flux vers les voyelles — plus on passe souvent d’une consonne à une voyelle, plus il y a de voyelles

p_voy→con

flux sortant des voyelles — plus on quitte vite une voyelle, moins il y en a

Exemple — Máj et Onéguine d’après la formule

Máj : π_voy = 0,575 / (0,949 + 0,575) = 0,377. Plus précisément : il y a autant de transitions voyelle→consonne que consonne→voyelle (111), donc π_voy = (111/193) / (111/117 + 111/193) = 117/310. La proportion réelle de voyelles est 117/311 — elle ne diffère que par le dénominateur, car la dernière lettre de la strophe (« r ») ne commence aucune paire.

Onéguine : à partir des nombres de Markov (voyelle après voyelle 12,8 %, donc voyelle→consonne 87,2 % ; voyelle après consonne 66,3 %), on obtient π_voy = 0,663 / (0,872 + 0,663) = 0,432 — exactement les 43,2 % de voyelles que Markov avait comptés directement.

6. PageRank : le surfeur aléatoire

En 1998, Sergey Brin et Larry Page, les fondateurs de Google, ont proposé une façon de classer les pages web par importance. Ils ont imaginé un surfeur qui clique au hasard sur les liens et se sont demandé : sur quelles pages passera-t-il le plus de temps ?

Définition — PageRank

Soit une page i avec k_i liens sortants. Avec une probabilité d (en général 0,85), le surfeur aléatoire clique sur l’un des liens choisi uniformément au hasard ; sinon, il saute sur l’une quelconque des N pages :

p_ij = (1 − d)/N + d/k_i si i a un lien vers j, sinon (1 − d)/N.

Le PageRank est la distribution stationnaire de cette chaîne. Les sauts garantissent que la chaîne est irréductible et apériodique.

En tête se trouve C (0,374), vers laquelle pointe presque chaque page. A est plus intéressante : elle n’a qu’un seul lien entrant et pourtant elle est deuxième (0,342) — parce que ce lien vient de C et que C ne pointe nulle part ailleurs. B, vers laquelle seule A pointe, reçoit la moitié du poids de A (0,171). Les pages D, E et F, qui se lient surtout entre elles, restent autour de 0,04. Le vrai PageRank calculait la même chose pour des milliards de pages, par la méthode de la puissance itérée.

L’équation π = πP écrite pour une seule page donne la forme connue du PageRank :

PR(j) = (1 − d)/N + d ∑_i→j PR(i) / k_i

PR(j)

PageRank de la page j — la proportion du temps que le surfeur y passe ; la somme sur toutes les pages vaut 1

(1 − d)/N

contribution des sauts aléatoires — chaque page la reçoit à parts égales, même celle vers laquelle rien ne pointe ; grâce à elle, la chaîne est irréductible et apériodique

d

probabilité que le surfeur clique sur un lien au lieu de sauter ailleurs — 0,85 dans l’article original de Brin et Page

∑_i→j

somme uniquement sur les pages qui pointent vers j — un lien est un « vote » pour la page cible

PR(i) / k_i

le vote de la page i pèse autant que i elle-même est importante, et il se partage entre ses k_i liens — une page avec des milliers de liens n’en donne que peu à chacun

Exemple — vérification de A, B et C

Pour N = 6 et d = 0,85, on a (1 − d)/N = 0,025. Vers A ne mène que le lien depuis C, qui n’a qu’un seul lien (k_C = 1) ; vers B, seulement celui depuis A, qui en a deux :

• PR(A) = 0,025 + 0,85 · 0,37351 / 1 = 0,34248,
• PR(B) = 0,025 + 0,85 · 0,34248 / 2 ≈ 0,1706,
• PR(C) = 0,025 + 0,85 · (PR(A)/2 + PR(B)/1 + PR(D)/2 + PR(E)/3 + PR(F)/1) = 0,025 + 0,85 · 0,41001 = 0,37351.

Les valeurs de la méthode de la puissance itérée vérifient l’équation — c’est ainsi qu’on reconnaît que l’itération a convergé.

PR = [1/N] * N                              # commence uniformément
repeat:
    nové = [(1 − d)/N] * N                  # sauts aléatoires
    for i in stránky:
        if i n’a pas de liens:              # impasse : saute n’importe où
            nové[j] += d · PR[i]/N  pour tout j
        else:
            for j in odkazy[i]:
                nové[j] += d · PR[i]/k_i
    PR = nové
until PR ne change presque plus

7. Chaînes, texte et modèles de langage

Une chaîne dont les états sont des lettres peut servir à générer. À partir des paires de lettres de la première strophe de Máj, on estime ce qui suit chaque lettre, puis on tire au sort. Voici à quoi ressemblent 90 caractères :

lal kou lasvavzvný dnkyl plásnětičaskol dnou ta javu snáscezepráro pl h jin trů bo kylalav

Du charabia — mais un charabia qui « sonne tchèque » : il alterne voyelles et consonnes, a des mots courts et des syllabes comme « lás » ou « kol ». Claude Shannon a fait la même expérience en 1948 avec l’anglais et a montré qu’avec un contexte plus long (triplets de lettres, paires de mots), le texte paraît de plus en plus naturel.

Exemple — la ligne « l » du modèle de bigrammes

On met le texte de la strophe en minuscules et on remplace la ponctuation par un espace. La lettre « l » y est suivie 31 fois d’un autre caractère : 13 fois d’un espace, 7 fois de « a », 6 fois de « á », 2 fois de « o » et une fois chacun de « i », « h », « u ». D’après la formule d’estimation, on a donc

P(espace | l) = 13/31 ≈ 0,42, P(a | l) = 7/31 ≈ 0,23, P(á | l) = 6/31 ≈ 0,19, P(o | l) = 2/31 ≈ 0,06 et les autres 1/31 ≈ 0,03.

La génération fait ensuite la même chose que la simulation de la météo : elle tire le caractère suivant selon la ligne du caractère courant. Après « l », le mot touche le plus souvent à sa fin — « byl », « lhal », « kol », « bol ».

Définition — modèle n-gramme

Un modèle n-gramme prédit le symbole suivant d’après les n − 1 précédents : P(w_t | w_t−n+1, …, w_t−1). C’est une chaîne de Markov dont l’état est formé des n − 1 derniers symboles.

Exemple — combien d’états a un modèle n-gramme

Avec un vocabulaire de V symboles, un modèle n-gramme a |V|ⁿ⁻¹ états et |V| probabilités dans chaque ligne. La strophe de Máj utilise 32 caractères différents (lettres et espace) :

• bigrammes (n = 2) : 32 états, une matrice 32 × 32 = 1 024 nombres — plus que la strophe n’a de caractères, si bien que la plupart d’entre eux valent zéro ;
• trigrammes : 32² = 1 024 états et plus de 32 mille nombres — la strophe ne contient pas du tout la plupart des paires de lettres et leurs lignes restent vides ;
• un modèle de langage avec un vocabulaire de 50 000 tokens et une fenêtre de 1 000 tokens : 50 000^1 000 ≈ 10^4 699 états.

C’est pourquoi un contexte plus long exige soit des données gigantesques, soit un modèle qui ne lit pas les probabilités dans un tableau, mais les estime par une fonction — un réseau de neurones.

8. Où mènent les chaînes de Markov

• Modèles de Markov cachés — et si l’on ne voyait pas l’état, mais seulement ses manifestations ? C’est le sujet de la prochaine partie.
• Processus de décision markoviens : ils ajoutent des actions et des récompenses ; l’apprentissage par renforcement repose sur eux.
• Méthodes de Monte-Carlo par chaînes de Markov (MCMC) : elles construisent une chaîne dont la distribution stationnaire est celle dont on veut tirer des échantillons — typiquement la distribution a posteriori en statistique bayésienne. Le critère de Metropolis de la partie sur le recuit simulé est précisément une telle chaîne.

9. Résumé

• Une chaîne de Markov n’a pas de mémoire : l’état suivant ne dépend que de l’état actuel. Elle est décrite par une matrice de transition stochastique P.
• La distribution évolue par multiplication par la matrice, π_t = π₀ P^t.
• Une chaîne irréductible et apériodique se stabilise sur une unique distribution stationnaire π = π P, indépendamment du début ; pour la météo, (0,393 ; 0,361 ; 0,246).
• Markov a mis en évidence la dépendance des lettres sur Onéguine ; dans Máj, une voyelle ne suit une voyelle que dans 5 % des cas.
• Le PageRank est la distribution stationnaire du surfeur aléatoire ; les modèles n-grammes comme les modèles de langage actuels sont des chaînes de Markov à grand état.

Envie de mettre la main à la pâte ? Demandez à un agent IA de construire un modèle de bigrammes de mots à partir de tout Máj ou de vos propres e-mails et d’en générer des phrases — puis essayez les trigrammes.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.