$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Chaîne de Markov

Si on lance un grand nombre de fois une pièce de monnaie, on obtient la plupart du temps autant de piles que de faces. Cela se traduit en mathématiques par le théorème appelé loi des grands nombres. Cette loi exprime que, lorsque les lancers sont indépendants les uns des autres, la fréquence empirique de réalisation d'un événement va tendre vers la probabilité théorique de réalisation de cet événement.

Sous cette forme, la loi des grands nombres est loin de couvrir tous les phénomènes que l'on peut modéliser par une expérience aléatoire. Prenons l'exemple du temps qu'il fait. Bien sûr, la météo du jour dépend de celle de la veille. Mais on peut dire qu'elle ne dépend pas de celle d'il y a un an! La question de savoir si on peut étendre la loi des grands nombres à une suite d'expériences aléatoires qui dépendent les unes des autres, mais pas trop, a été résolue par le mathématicien Markov en 1902, en introduisant ce qu'on appelle maintenant les chaînes de Markov.

Définition : On appelle chaîne de Markov une suite de variables aléatoires $(X_n)$ à valeurs dans un espace probabilisé $(E,P)$ avec $E$ fini telle que, pour chaque $n\in\mathbb N$, $$P(X_{n+1}=i_{n+1}|X_1=i_1,\dots,X_n=i_n)=P(X_{n+1}=i_{n+1}|X_n=i_n).$$

L'ensemble $E$ où la suite $(X_n)$ prend ses valeurs s'appelle l'espace des états de la suite de Markov, chaque élément de $E$ étant un état possible de la chaîne.

Exemple typique : Tirage avec remise différée. Dans une urne, on a placé 2 boules rouges et 2 boules noires. On effectue des tirages successifs, avec remise différée d'un tour:

  • au 1er tirage : on enlève une boule choisie au hasard dans l'urne
  • au $i$-ème tirage : on enlève une boule choisie au hasard parmi les boules de l'urne et on remet la boule tirée au $(i-1)$-ème tirage.

On désigne ensuite par $X_n$ la couleur de la boule prise au $n$-ème tirage.

Si on connait la couleur de la boule tirée à la $n$-ième étape, alors on connait la constitution de l'urne lorsqu'on effectuera le $n+1$-ième tirage et donc on a tout ce qui faut pour prédire de la facon la plus précise possible ce qui se passera la $n+1$-ième tirage :

  • sachant que la $n$-ème boule tire est rouge, la probabilite de tirer une boule rouge au $n+1$ ème tirage est de 1/3;
  • sachant que la $n$-ème boule tire est noire, la probabilite de tirer une boule rouge au $n+1$ ème tirage est de 2/3.

Le fait de connaitre, en plus de la couleur de la n-ième boule tirée, le résultat des informations sur les n-1 premiers tirages ne permet pas de modifier les prédictions précédentes.

Dans ce cas, la loi des grands nombres énoncée par Markov affirme qu'après un grand nombre de tirages, on aura tiré à peu près autant de boules rouges que de boules noires.

Autre exemple typique : les marches aléatoires. Une puce se déplace sur un carré dont les sommets sont nommés $A,B,C,D$. A chaque instant, elle passe d'un sommet à un sommet adjacent de façon équiprobable. On suppose qu'au temps $0$ elle est en $A$ et on désigne par $X_n$ le sommet sur lequel elle est au temps $n$. Alors, pour connaitre la probabilité que la puce soit en $A$ à l'instant $n+1$, il suffit de savoir où elle était au temps $n$, le fait de savoir où elle était avant n'apporte pas d'informations supplémentaires.

C'est Markov lui-même qui a le premier appliqué ses chaînes à un domaine autre que les mathématiques. Il s'en est servi pour analyser les successions de lettres dans l'alphabet russe. Le même type d'applications se retrouve aujourd'hui dans les téléphones portables : les chaînes de Markov sont mises à contribution par les logiciels d'écriture de SMS, qui essaient de deviner ce que vous allez écrire. Plus sérieusement, les chaînes de Markov sont devenues un outil très employé, pour l'anlyse de l'ADN, la prédiction de l'évolution des épidémies, ou pour classer l'importance des pages internet....

Cette entrée s'inspire en partie d'un article de Benoit Rittaud, publié dans La Recherche n° 578 (septembre 2004).
Consulter aussi
Recherche alphabétique
Recherche thématique