Accueil › Glossaire › Markov Chain

Markov Chain (Chaîne de Markov)

Une chaîne de Markov est un processus stochastique dans lequel la probabilité de chaque événement futur ne dépend que de l’état actuel, et non de la séquence des événements passés. Cette propriété de « sans mémoire » (propriété de Markov) en fait un outil mathématique fondamental en IA, statistique, physique et informatique.

L’idée est intuitive : pour prédire demain, il suffit de connaître aujourd’hui, pas tout l’historique depuis la nuit des temps. Formellement, pour une séquence d’états X₀, X₁, X₂, … :

P(Xₙ₊₁ = x | Xₙ = xₙ, Xₙ₋₁ = xₙ₋₁, ..., X₀ = x₀) = P(Xₙ₊₁ = x | Xₙ = xₙ)

Les chaînes de Markov sont nommées d’après le mathématicien russe Andrey Markov, qui a introduit le concept en 1906 en analysant les séquences de voyelles et consonnes dans Eugène Onéguine de Pouchkine. Depuis, elles sont devenues la brique de base d’une famille de modèles essentiels en IA : les processus de décision markoviens (MDP) qui fondent le reinforcement learning, les modèles de Markov cachés (HMM) pour le traitement de séquences, les méthodes MCMC (Monte Carlo par chaînes de Markov) pour l’inférence bayésienne, et le PageRank de Google pour le classement de pages web.

Les composants d’une chaîne de Markov

Espace d’états

L’espace d’états S est l’ensemble de toutes les valeurs possibles que le processus peut prendre. Il peut être fini (les trois états d’humeur : joyeux, neutre, triste), dénombrable (les entiers naturels), ou continu (les réels). En machine learning, on travaille le plus souvent avec des espaces d’états finis ou discrets pour les chaînes de Markov classiques, et avec des espaces continus pour les processus de diffusion et le MCMC.

Matrice de transition

Pour une chaîne de Markov à états finis, toute la dynamique est capturée dans une matrice de transition P de taille N×N (où N est le nombre d’états). L’élément Pᵢⱼ donne la probabilité de passer de l’état i à l’état j en un pas :

Pᵢⱼ = P(Xₙ₊₁ = j | Xₙ = i)

Chaque ligne de P somme à 1 (c’est une matrice stochastique) : depuis chaque état, l’ensemble des transitions possibles couvre toutes les possibilités. La matrice de transition encode complètement le comportement de la chaîne.

Pour calculer les probabilités de transition en n pas, il suffit d’élever la matrice P à la puissance n. La probabilité de passer de i à j en exactement n pas est l’élément (i, j) de la matrice Pⁿ. C’est l’équation de Chapman-Kolmogorov en forme matricielle.

Distribution initiale

Le vecteur de distribution initiale π₀ spécifie la probabilité de démarrer dans chaque état. La distribution après n pas est π₀ · Pⁿ. Le choix de π₀ affecte le comportement transitoire de la chaîne mais pas son comportement à long terme (si la chaîne est ergodique).

Propriétés fondamentales

Irréductibilité

Une chaîne de Markov est irréductible si chaque état est accessible depuis chaque autre état en un nombre fini de pas. En d’autres termes, il n’y a pas de « cul-de-sac » ni d’« îles isolées ». Si la chaîne est irréductible, elle possède une distribution stationnaire unique.

Apériodicité

Un état a une période d si la chaîne ne peut y revenir qu’après un multiple de d pas. Un état apériodique a d = 1 : la chaîne peut y revenir à n’importe quel moment. Une chaîne irréductible est apériodique si un seul de ses états est apériodique (c’est une propriété de classe).

Ergodicité

Une chaîne irréductible et apériodique est dite ergodique. C’est la condition idéale : la chaîne ergodique converge vers une distribution stationnaire unique, peu importe l’état initial. C’est la propriété fondamentale qui rend le MCMC possible : on construit une chaîne ergodique dont la distribution stationnaire est la distribution cible, et on attend la convergence.

Distribution stationnaire

La distribution stationnaire π est un vecteur de probabilités qui satisfait :

π = π · P

Autrement dit, si le processus est distribué selon π à un instant donné, il reste distribué selon π à l’instant suivant (et à tous les instants futurs). C’est un point fixe de la dynamique.

Mathématiquement, π est un vecteur propre à gauche de P avec une valeur propre de 1. Pour une chaîne ergodique, cette distribution est unique et la proportion de temps passé dans chaque état converge vers π : π(x) = 1 / E[temps de retour à x].

import numpy as np
from scipy import linalg

# Matrice de transition (3 états : Soleil, Nuage, Pluie)
P = np.array([
    [0.7, 0.2, 0.1],  # Soleil → Soleil/Nuage/Pluie
    [0.3, 0.4, 0.3],  # Nuage  → Soleil/Nuage/Pluie
    [0.2, 0.3, 0.5],  # Pluie  → Soleil/Nuage/Pluie
])

# Méthode 1 : puissance de matrice (P^100 converge)
P_stationary = np.linalg.matrix_power(P, 100)
print("Via P^100 :", P_stationary[0])  # Toutes les lignes sont identiques

# Méthode 2 : vecteur propre à gauche
eigenvalues, left_eigvecs = linalg.eig(P, left=True, right=False)
# Trouver le vecteur propre avec valeur propre ≈ 1
idx = np.argmin(np.abs(eigenvalues - 1.0))
pi = left_eigvecs[:, idx].real
pi = pi / pi.sum()  # Normaliser
print("Via eigendecomposition :", pi)

# Méthode 3 : simulation Monte Carlo
state = 0
counts = np.zeros(3)
for _ in range(100_000):
    state = np.random.choice(3, p=P[state])
    counts[state] += 1
print("Via simulation :", counts / counts.sum())

Applications en IA et machine learning

MCMC : l’inférence bayésienne

Les méthodes Monte Carlo par chaînes de Markov (MCMC) sont la raison principale pour laquelle les chaînes de Markov sont omniprésentes en ML moderne. L’idée : construire une chaîne de Markov dont la distribution stationnaire est la distribution postérieure bayésienne que l’on veut approximer. En faisant tourner la chaîne assez longtemps, les échantillons produits sont des tirages (approximatifs) de la postérieure.

Les algorithmes de Metropolis-Hastings, Gibbs sampling et Hamiltonian Monte Carlo sont tous des méthodes pour construire de telles chaînes. La condition de balance détaillée (detailed balance) garantit que la chaîne converge vers la bonne distribution.

MDP et reinforcement learning

Les processus de décision markoviens (MDP) étendent les chaînes de Markov en ajoutant des actions et des récompenses. L’agent choisit une action, l’environnement transite vers un nouvel état selon une distribution markovienne, et l’agent reçoit une récompense. Toute la théorie du reinforcement learning repose sur cette formalisation : Q-learning, policy gradient, PPO et tous les algorithmes de RL sont des méthodes pour résoudre des MDP.

La propriété de Markov est cruciale ici : elle signifie que l’état actuel contient toute l’information nécessaire pour prendre la décision optimale. Si ce n’est pas le cas (l’environnement n’est pas complètement observable), on utilise des extensions comme les POMDP (Partially Observable MDP).

Hidden Markov Models (HMM)

Les modèles de Markov cachés sont des chaînes de Markov où les états ne sont pas directement observés. On observe une émission (un signal) qui dépend probabilistiquement de l’état caché. Les HMM ont été historiquement essentiels en reconnaissance vocale, en bio-informatique (alignement de séquences, prédiction de gènes), et en NLP (étiquetage morphosyntaxique).

Trois problèmes classiques des HMM : l’évaluation (probabilité d’une séquence observée, résolu par l’algorithme forward), le décodage (séquence d’états cachés la plus probable, résolu par Viterbi), et l’apprentissage (estimation des paramètres, résolu par Baum-Welch/EM).

PageRank

L’algorithme PageRank de Google modélise la navigation sur le web comme une chaîne de Markov. Chaque page web est un état, et les liens hypertextes définissent les probabilités de transition. La distribution stationnaire de cette chaîne donne le « score d’importance » de chaque page : les pages vers lesquelles convergent beaucoup de liens de pages importantes ont un PageRank élevé. C’est l’algorithme qui a fondé le succès initial de Google.

NLP et génération de texte

Les modèles de langage les plus simples sont des chaînes de Markov sur les mots. Un modèle bigramme prédit le mot suivant conditionnellement au mot actuel uniquement (Markov d’ordre 1). Un modèle trigramme utilise les deux mots précédents (Markov d’ordre 2). Bien que les transformers aient largement supplanté ces modèles pour la génération de texte, les chaînes de Markov restent utilisées pour la prédiction de texte simple, la complétion automatique sur mobile, et comme baseline en NLP.

Les autocomplétion de clavier sur smartphone utilisent souvent des chaînes de Markov (ou des variantes) pour suggérer le mot suivant en fonction du mot actuel, car elles sont rapides et légères en mémoire.

Modèles de diffusion

Les modèles de diffusion (Stable Diffusion, DALL-E) peuvent être interprétés comme des chaînes de Markov continues. Le processus de diffusion directe (ajout progressif de bruit) et le processus inverse (débruitage) sont tous deux des processus markoviens. La théorie des chaînes de Markov fournit les garanties de convergence pour ces modèles génératifs.

Biologie et génétique

Les chaînes de Markov modélisent les mutations génétiques (chaque nucléotide mute selon des probabilités qui ne dépendent que du nucléotide actuel), l’évolution des populations, les dynamiques épidémiologiques (modèles SIR stochastiques), et les structures de protéines. Le logiciel STRUCTURE pour l’analyse de populations génomiques repose sur des MCMC appliquées à des modèles de Markov latents. En bio-informatique, les profils HMM (Profile HMM) modélisent les familles de protéines pour l’alignement de séquences et la recherche d’homologues dans les bases de données génomiques.

Finance et économie

Les chaînes de Markov modélisent les transitions de rating de crédit (une entreprise notée BBB peut passer à A ou BB avec des probabilités estimées sur des données historiques), les cycles économiques (expansion/récession), les dynamiques de prix d’actifs via les modèles à régimes changeants (regime-switching models). Les matrices de transition de crédit publiées par les agences de notation (Moody’s, S&P) sont littéralement des matrices de transition markoviennes. En assurance, les modèles de Markov estiment les probabilités de passage entre états de santé pour le pricing des polices.

Types de chaînes de Markov

Limites de l’hypothèse de Markov

Mémoire limitée : beaucoup de systèmes réels dépendent d’un historique plus long que le seul état courant. Un client dont le comportement dépend de ses 10 derniers achats ne suit pas une chaîne de Markov d’ordre 1. On peut contourner cela en augmentant l’espace d’états (inclure les k derniers états dans l’état courant), mais la taille de l’espace explose exponentiellement.

Stationnarité : les chaînes de Markov homogènes supposent que les probabilités de transition ne changent pas dans le temps. Si l’environnement évolue (changement de saison, évolution du marché), le modèle doit être adapté via des chaînes non stationnaires ou des modèles à régimes changeants.

Dimensionnalité : pour les espaces d’états de grande dimension, la matrice de transition devient impraticable (N² éléments). Les méthodes MCMC contournent ce problème en n’ayant jamais besoin de la matrice complète, seulement des transitions locales.

Observabilité partielle : dans de nombreux systèmes réels, l’état complet n’est pas directement observable. Un robot mobile ne perçoit que ses capteurs, pas sa position exacte. Les POMDP (Partially Observable MDP) et les HMM répondent à ce problème, mais au prix d’une complexité computationnelle considérablement accrue. L’estimation de l’état caché nécessite de maintenir une distribution de croyance (belief state) sur tous les états possibles, ce qui est exponentiellement coûteux dans le pire cas.

Hypothèse de stationnarité des transitions : en pratique, les environnements changent. Les préférences des utilisateurs évoluent, les marchés se transforment, les systèmes physiques se dégradent. Des extensions comme les chaînes de Markov non homogènes, les modèles à régimes changeants et les processus ponctuels marqués tentent de capturer ces dynamiques, mais elles ajoutent des couches de complexité à l’estimation et à l’inférence.