Chaîne de Markov
Une chaîne de Markov est un modèle mathématique décrivant une séquence d’événements possibles, appelés états, dans laquelle la probabilité de passer à l’état suivant ne dépend que de l’état actuel et non des états précédents. C’est un type spécifique de processus stochastique, caractérisé par sa propriété d’absence de mémoire, connue sous le nom de propriété de Markov.
Les concepts fondamentaux des chaînes de Markov incluent l’espace d’états, qui est l’ensemble de tous les états possibles que le système peut occuper. Cet espace peut être fini ou infini dénombrable. Les transitions entre les états sont régies par des probabilités de transition. La probabilité de passer de l’état i à l’état j en une étape est notée P(i, j) ou P_ij. Ces probabilités sont souvent organisées dans une matrice appelée matrice de transition (P), où chaque ligne représente l’état actuel et chaque colonne l’état suivant, et la somme des probabilités sur chaque ligne doit être égale à 1. La propriété de Markov est le principe essentiel : la connaissance de l’état présent rend toute information sur les états passés inutile pour prédire l’état futur. On distingue les chaînes de Markov à temps discret, où les transitions se produisent à des instants spécifiques (t=0, 1, 2,…), et les chaînes de Markov à temps continu, où les transitions peuvent se produire à n’importe quel moment. La distribution initiale décrit la probabilité que le processus commence dans chacun des états possibles au temps t=0.
L’importance des chaînes de Markov réside dans leur capacité à modéliser une vaste gamme de phénomènes aléatoires évoluant dans le temps ou l’espace dans divers domaines scientifiques et techniques. Elles fournissent un cadre conceptuel et computationnel puissant pour analyser le comportement à court et long terme de systèmes dynamiques soumis à l’incertitude. Elles constituent la base de modèles plus complexes et sont un outil fondamental en théorie des probabilités, en statistique, en apprentissage automatique, en recherche opérationnelle et en physique statistique. Leur pertinence vient de l’équilibre entre simplicité (grâce à la propriété de Markov) et puissance de modélisation.
Les applications pratiques des chaînes de Markov sont nombreuses et variées. En traitement du langage naturel, les modèles n-grammes, qui prédisent le mot suivant en fonction des n-1 mots précédents, sont une application directe (pour n=2, c’est une chaîne de Markov de premier ordre). Elles sont utilisées pour la génération de texte simple, la reconnaissance vocale et la correction orthographique. En bioinformatique, elles modélisent l’évolution des séquences d’ADN ou de protéines et aident à identifier des gènes. En finance, elles peuvent modéliser les changements de notation de crédit, les mouvements de prix d’actifs (bien que souvent simplificateurs) ou les régimes de marché. En météorologie, des modèles simples de prévision du temps (pluvieux/ensoleillé) peuvent être basés sur des chaînes de Markov. L’algorithme PageRank de Google, dans sa conception originale, utilisait une chaîne de Markov pour modéliser la navigation d’un utilisateur sur le web et ainsi classer les pages par importance. En théorie des files d’attente, elles modélisent l’arrivée et le service des clients. Les méthodes de Monte Carlo par chaînes de Markov (MCMC) sont une classe d’algorithmes cruciaux en statistique bayésienne et en physique pour échantillonner des distributions de probabilité complexes.
Il existe plusieurs nuances et variations du concept de base. La distinction principale est entre les chaînes de Markov à temps discret (CMTD) et à temps continu (CMTC). Les chaînes de Markov d’ordre supérieur généralisent la propriété de Markov en faisant dépendre l’état suivant des k états précédents (k > 1). Les chaînes de Markov cachées (Hidden Markov Models – HMM) sont une extension importante où les états eux-mêmes ne sont pas directement observables, mais influencent des observations visibles ; elles sont largement utilisées en reconnaissance de formes (parole, écriture) et en bioinformatique. Les processus de décision markoviens (Markov Decision Processes – MDP) ajoutent des actions et des récompenses au modèle, formant la base de l’apprentissage par renforcement. On peut aussi étudier des propriétés spécifiques comme la réversibilité d’une chaîne, qui simplifie certaines analyses. La classification des états (récurrent, transitoire, absorbant, périodique, apériodique) et les concepts d’irréductibilité et d’ergodicité sont essentiels pour comprendre le comportement à long terme, notamment l’existence et l’unicité d’une distribution stationnaire (ou limite), qui décrit les probabilités d’être dans chaque état après un long moment, indépendamment de l’état initial.
Plusieurs concepts sont étroitement liés aux chaînes de Markov. Le terme « processus stochastique » est plus général et englobe tout processus évoluant aléatoirement. La « propriété de Markov » est la caractéristique définissant ces chaînes. La « matrice stochastique » est une matrice dont les éléments sont non négatifs et dont la somme des éléments de chaque ligne vaut 1, représentant souvent la matrice de transition. La « distribution stationnaire » est une distribution de probabilité sur les états qui reste inchangée après une transition. Comme mentionné, les HMM, MCMC et MDP sont des extensions ou applications importantes. Le « processus de Poisson » est un exemple fondamental de processus de comptage lié aux chaînes de Markov à temps continu. Bien qu’il n’y ait pas de synonymes parfaits, « processus de Markov » peut parfois être utilisé, bien que ce terme puisse aussi désigner des processus plus généraux (temps continu, espace d’états continu). Le concept opposé serait un « processus non-markovien » ou un « processus avec mémoire », où l’avenir dépend du passé au-delà de l’état présent. Un système « déterministe » est l’opposé d’un système stochastique.
L’origine des chaînes de Markov remonte au mathématicien russe Andreï Andreïevitch Markov, qui les a introduites en 1906. Son travail initial visait à étudier les séquences de lettres dans des textes littéraires, notamment le poème « Eugène Onéguine » d’Alexandre Pouchkine. Il cherchait à démontrer que la dépendance pouvait exister dans des séquences aléatoires tout en obéissant à certaines lois probabilistes comme la loi des grands nombres, contredisant ainsi l’idée, défendue par son ancien professeur Pafnouti Tchebychev, que l’indépendance était une condition nécessaire. Les travaux de Markov ont jeté les bases d’une nouvelle branche de la théorie des probabilités, qui a été considérablement développée au cours du 20e siècle par des mathématiciens comme Andreï Kolmogorov, William Feller et Joseph Doob.
Les avantages des chaînes de Markov incluent leur simplicité conceptuelle et leur facilité d’analyse mathématique pour de nombreux problèmes. Elles fournissent un cadre bien compris pour modéliser la dynamique stochastique et calculer des quantités importantes comme les probabilités d’atteinte, les temps moyens de premier passage et les distributions limites. Elles servent de bloc de construction essentiel pour des modèles plus sophistiqués qui capturent des structures plus complexes. Cependant, elles présentent aussi des inconvénients et limitations. L’hypothèse de Markov (absence de mémoire) est souvent une simplification forte et peut ne pas être réaliste pour de nombreux systèmes réels où l’histoire passée influence significativement l’évolution future. Elles ne capturent pas intrinsèquement les dépendances à long terme ou les changements de régime dans la dynamique du système. La taille de l’espace d’états peut devenir prohibitivement grande pour des problèmes complexes, rendant les calculs (comme la manipulation de la matrice de transition) infaisables. Enfin, l’estimation précise des probabilités de transition à partir de données observées peut être difficile, surtout si les données sont rares ou bruitées. Malgré ces limitations, les chaînes de Markov restent un outil fondamental et largement utilisé en modélisation stochastique.