chaîne de Markov

Imaginez une machine qui peut être active ou en veille. À chaque étape, elle peut conserver son état ou en changer, avec des probabilités fixées. Pour prévoir l'étape suivante, son état actuel suffit : le chemin suivi auparavant n'ajoute aucune information utile.

Une chaîne de Markov décrit cette succession d'états aléatoires. Elle ne dit pas que le passé n'a jamais compté : ses effets sont résumés dans le présent.

Une chaîne de Markov est un processus stochastique, c'est-à-dire une famille de variables aléatoires qui décrit un état évoluant au hasard. Dans le cadre à temps discret, X_n désigne l'état observé à l'étape n. La propriété de Markov exige que, une fois X_n connu, les états antérieurs n'apportent aucune information supplémentaire sur X_n+1.

Pour des états i₀, …, i_n−1, i et j dont l'événement conditionnant a une probabilité non nulle, cette propriété s'écrit :Les probabilités de passer de l'état i à l'état j sont les probabilités de transition. Si elles ne dépendent pas de n, la chaîne est dite homogène ; pour un espace d'états fini ou dénombrable, elles peuvent alors être rangées dans une matrice de transition.

L'espace des états peut être discret ou continu. Le temps peut aussi être discret ou continu ; dans ce dernier cas, on indexe habituellement l'état par un réel t et l'on adapte la propriété de Markov à tous les instants. Une marche aléatoire sur un graphe fournit un exemple classique à espace discret.

Considérons une machine fictive à deux états : A pour « active » et V pour « en veille ». Si elle est active, elle reste active avec la probabilité 0,8 et passe en veille avec la probabilité 0,2. Si elle est en veille, elle devient active avec la probabilité 0,3 et reste en veille avec la probabilité 0,7. Au départ, elle est active avec certitude.

1. Après une étape, les probabilités sont 0,8 pour A et 0,2 pour V.
2. Pour être active après deux étapes, deux chemins sont possibles : A → A → A ou A → V → A.
3. Le premier chemin a pour probabilité 0,8 × 0,8 = 0,64 ; le second, 0,2 × 0,3 = 0,06.
4. Ces chemins étant incompatibles, leurs probabilités s'additionnent : 0,64 + 0,06 = 0,70.

La machine est donc active après deux étapes avec la probabilité 0,70, soit 70 %. Le contrôle consiste à calculer l'état complémentaire : 0,8 × 0,2 + 0,2 × 0,7 = 0,30, et 0,70 + 0,30 = 1. Le graphe de transition rassemble les quatre probabilités utilisées dans ce calcul.

Le même résultat s'obtient avec la matrice de transition. En plaçant les états de départ en lignes dans l'ordre (A, V), on écrit :Le vecteur ligne de départ est (1 ; 0), puisque la machine est active avec certitude. Il donne successivement :La première composante retrouve donc la probabilité 0,70 calculée par les chemins, et la seconde fournit directement le contrôle 0,30.

Sur un graphe, une marche aléatoire choisit le prochain sommet selon des probabilités attachées aux déplacements possibles. Une chaîne de Markov convient lorsque le sommet actuel suffit à fixer ce choix ; si tout l'itinéraire modifie la règle, il faut enrichir l'état ou employer un modèle avec mémoire.

En informatique ou en sciences de la décision, on peut représenter une succession de situations par des états et estimer les probabilités de passage. Le geste essentiel consiste à choisir un état assez informatif pour que le passé devienne superflu une fois cet état connu.

En physique statistique et en probabilités, on suit de même une évolution aléatoire étape par étape. Une simulation directe est utile pour observer des trajectoires ; le calcul matriciel est préférable lorsque l'on veut obtenir exactement la distribution après un nombre fixé d'étapes dans un modèle fini homogène.

Variables indépendantes. Dans une suite indépendante, connaître l'état présent ne change pas la loi du suivant. Dans une chaîne de Markov, le suivant peut dépendre fortement du présent : pour la machine, la probabilité d'être active à l'étape suivante vaut 0,8 depuis A, mais 0,3 depuis V.

Suite déterministe. Une règle déterministe impose un unique état suivant, tandis qu'une chaîne de Markov autorise plusieurs issues assorties de probabilités. Elle peut toutefois devenir déterministe si chaque état n'a qu'une transition de probabilité 1.

Graphe et matrice de transition. Le graphe montre quels passages sont possibles ; la matrice associe une probabilité à chaque paire d'états selon une convention d'ordre. Deux graphes identiques peuvent donc porter des chaînes différentes si leurs probabilités diffèrent.

État trop pauvre. Si la prochaine transition dépend de l'avant-dernier état même après connaissance du présent, la variable choisie ne forme pas une chaîne de Markov. Il faut souvent agrandir l'état, par exemple en mémorisant les deux derniers états.

Homogénéité supposée à tort. La propriété de Markov n'oblige pas les probabilités de transition à rester constantes au fil du temps. Si la règle change avec l'étape n, il faut conserver cet indice au lieu d'utiliser une seule matrice.

Transitions impossibles. Une probabilité nulle interdit un passage direct, mais pas forcément tout passage ultérieur. Dans la machine, remplacer 0,3 par 0 rendrait impossible le retour direct de V vers A ; il faudrait alors vérifier s'il existe un autre chemin dans un modèle comportant davantage d'états.

Convention de matrice. Certaines présentations placent les états de départ en lignes, d'autres en colonnes. Avant de multiplier des vecteurs et des matrices, il faut vérifier où les probabilités sortantes totalisent 1 et conserver la même convention.

La matrice de transition organise les probabilités de passage et permet de calculer une distribution après plusieurs étapes.

La fiche Conditionnelle (probabilité) précise le langage probabiliste qui exprime l'indépendance du futur et du passé sachant le présent.

L'article Markov : les chaînes de l'espoir replace ces modèles dans un récit mathématique plus large.