$$\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
Dictionnaire de mathématiques > Dénombrements et probabilités > Probabilités > Processus >

Chaine 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 chaines de Markov.

Définition : On appelle chaine de Markov une suite de variables aléatoires (Xn) à valeurs dans un espace probabilisé (E,B,P) telle que, pour chaque n, connaissant la valeur de Xn, Xn+1 soit indépendante de Xk, pour k inférieur ou égal à n-1.
Autrement dit, pour tout n et pour toutes valeurs possibles i0, ..., in,in+1, la probabilité que Xn+1 prenne la valeur in+1 sachant que X0=i0,X1=i1,... ,Xn-1=in-1 et Xn=in ne dépend que de in+1 et de in, c'est-à-dire :

L'ensemble E où la suite (Xn) 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 chaine.

Exemple typique : Tirage avec remise différée. Dans une urne, on a placé 2 boules rouges (notées R) et 2 boules noires (notées N). On effectue des tirages successifs, avec remise différée d'un tour:
  • au 1er tirage : on enleve une boule choisie au hasard dans l'urne
  • au i-eme tirage : on enleve une boule choisie au hasard parmi les boules de l'urne et on remet la boule tirée au (i-1) ème tirage.
La suite de variables aléatoires considérées est 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és par Markov affirme qu'après un grand nombre de tirages, on aura tiré à peu près autant de R que de N.

C'est Markov lui-même qui a le premier appliqué ses chaines à 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 chaines 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 chaines 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...