Aventure mathématique : Les Chaînes de Markov.

Aujourd'hui dans cette rubrique de l'agitation de nos neurones, les chaînes de Markov.

Les chaînes de Markov sont utiles dans l'analyse des événements aléatoires dépendants, plus précisément des événements qui dépendent d'un passé récent.

Si on lance un très grand nombre de fois une pièce de monnaie équilibrée, on obtient, avec une quasi-certitude, autant de faces que de piles. La loi des grands nombres théorise ce fait expérimental. Une pièce de monnaie n'ayant pas de mémoire, les lancers sont indépendants les uns des autres. La loi des grands nombres exprime que, pour des expériences aléatoires répétées de manière indépendante, la fréquence empirique de survenue d'un événement tend vers la probabilité théorique de réalisation de cet événement.

La loi des grands nombres, hélas, n'est pas une panacée. Elle nécessite la propriété d'indépendance. Maints processus aléatoires lui échappent. Il en est ainsi des conditions météorologiques. Le temps du jour dépend du temps de la veille, mais n'est pas influencé par le temps d'il y a un an, où même d'il y a un mois. Dans ce type de  situations, les expériences aléatoires sont en partie dépendantes et dans leur déroulement chronologique, l'avenir est commandé par le passé récent.

Peut-on alors étendre la loi des grands nombres à ce type de processus? Sans précautions, ni restrictions, la réponse est non. Mais, comme l'a montré Andreï Markov, en 1906, il existe une façon d'affaiblir les hypothèses d'indépendance qui permet d'obtenir une réponse positive. Cette théorie est connue sous le nom de "chaînes de Markov".

En jargon probabiliste, une chaîne de Markov en temps discret se présente comme une suite de variables aléatoires (Xn)n>0 définies sur un certain espace probabilisé et à valeurs dans un ensemble E appelé espace d'états qui vérifie une certaine distribution de probabilité conditionnelle :

pour tous : x0,x1,...,xn,y€E,

P(Xn+1=y|X0=x0,X1=X1?..., Xn=xn)= P(Xn+1=y|Xn=xn).

Pluie, neige et soleil.

Au pays des fées, la grenouille en charge du bureau des prévisions météorologiques a fait les observations suivantes :

1) On n'a jamais vu 2 jours ensoleillés consécutifs : P(Bn+1|Bn)=0

2) S'il fait beau un jour donné, on a une chance égale d'avoir de la pluie ou de la neige le lendemain : P(Pn+1|Bn)=P(Nn+1|B,)=0.5

3) S'il pleut ou s'il neige, on a une chance sur deux que le temps se maintienne le jour suivant : P(Pn+1|Pn)=P(Nn+1|Nn)=0.5

4) S'il pleut ou s'il neige, on a une chance sur quatre que le temps change le lendemain :

P(Bn+1|Pn)=P(Bn+1|Nn)=P(Nn+1|Pn)=P(Pn+1|Nn)=0.25

Le temps du jour (n+1) ne dépend que du temps du jour n; on a bien une

Aujourd'hui dans cette rubrique de l'agitation de nos neurones, les chaînes de Markov.

Les chaînes de Markov sont utiles dans l'analyse des événements aléatoires dépendants, plus précisément des événements qui dépendent d'un passé récent.

Si on lance un très grand nombre de fois une pièce de monnaie équilibrée, on obtient, avec une quasi-certitude, autant de faces que de piles. La loi des grands nombres théorise ce fait expérimental. Une pièce de monnaie n'ayant pas de mémoire, les lancers sont indépendants les uns des autres. La loi des grands nombres exprime que, pour des expériences aléatoires répétées de manière indépendante, la fréquence empirique de survenue d'un événement tend vers la probabilité théorique de réalisation de cet événement.

La loi des grands nombres, hélas, n'est pas une panacée. Elle nécessite la propriété d'indépendance. Maints processus aléatoires lui échappent. Il en est ainsi des conditions météorologiques. Le temps du jour dépend du temps de la veille, mais n'est pas influencé par le temps d'il y a un an, où même d'il y a un mois. Dans ce type de  situations, les expériences aléatoires sont en partie dépendantes et dans leur déroulement chronologique, l'avenir est commandé par le passé récent.

Peut-on alors étendre la loi des grands nombres à ce type de processus? Sans précautions, ni restrictions, la réponse est non. Mais, comme l'a montré Andreï Markov, en 1906, il existe une façon d'affaiblir les hypothèses d'indépendance qui permet d'obtenir une réponse positive. Cette théorie est connue sous le nom de "chaînes de Markov".

En jargon probabiliste, une chaîne de Markov en temps discret se présente comme une suite de variables aléatoires (Xn)n>0 définies sur un certain espace probabilisé et à valeurs dans un ensemble E appelé espace d'états qui vérifie une certaine distribution de probabilité conditionnelle :

pour tous : x0,x1,...,xn,y€E,

P(Xn+1=y|X0=x0,X1=X1?..., Xn=xn)= P(Xn+1=y|Xn=xn).

Pluie, neige et soleil.

Au pays des fées, la grenouille en charge du bureau des prévisions météorologiques a fait les observations suivantes :

1) On n'a jamais vu 2 jours ensoleillés consécutifs : P(Bn+1|Bn)=0

2) S'il fait beau un jour donné, on a une chance égale d'avoir de la pluie ou de la neige le lendemain : P(Pn+1|Bn)=P(Nn+1|B,)=0.5

3) S'il pleut ou s'il neige, on a une chance sur deux que le temps se maintienne le jour suivant : P(Pn+1|Pn)=P(Nn+1|Nn)=0.5

4) S'il pleut ou s'il neige, on a une chance sur quatre que le temps change le lendemain :

P(Bn+1|Pn)=P(Bn+1|Nn)=P(Nn+1|Pn)=P(Pn+1|Nn)=0.25

Le temps du jour (n+1) ne dépend que du temps du jour n; on a bien une chaîne de Markov.

La formule des probabilités totales permet d'écrire :

P(Bn+1)P(Bn+1|Bn)P(Bn)+P(Bn+1|Pn)P(Pn)+P(Bn+1|Nn),

soit

P(Bn+1)=0. PBn)+0.25P(Pn)+0.25P(Nn)

On trouve de même :

P(Pn+1)=0.5P(Bn)+0.5P(Pn)+0.25P(Nn)

P(Nn+1)+0.5P(Bn)+0.25P(Pn)=0.5P(Nn).

Ces données peuvent se mettre sous forme matricielle :

P(Bn+1)  (0   0.25   0.25)    (P(Bn))

P(Pn+1)=  (0.5  0.5  0.25) =   (P(Pn))

P(Nn+1)  (0.5  0.25   0.5)   (P(Nn))

que l'on écrira Un+1=TUn où T est la matrice de transition du processus markovien et où Un est le vecteur d'état au temps n.

Au long cours, le vecteur d'état Un sera donné par Un=TnU0 où Tn est la puissance n-ième de la matrice T.

Par exemple, en supposant qu'il fasse beau le premier jour, on obtiendra, au bout d'une semaine :

   (0.199   0.200   0.200)   (1)  = (0.199)  

U7 =   (0.400   0.400   0.399)   (0) = (0.400)

   (0.400   0.399   0.400)   (0) = (0.400)

La probabilité qu'il fasse à nouveau beau une semaine après est donc très voisine de 0.2.

On peut montrer que la matrice T admet le vecteur U=(0.2;0.4;0.4) comme vecteur propre, i.e :

(0.2) = ( 0   0.25   0.25) (0.2)

(0.4) = (0.5  0.5   0.25) (0.4)

(0.4)=  (0.5  0.25   0.5)  (0.4)

et que lim(n->+~) Un=U

Au pays des fées, il y a , pour un jour quelconque 20% de chance d'avoir du soleil, 40% d'avoir de la pluie et 40% d'avoir de la neige.

Les chaînes de Markov au quotidien :

Andreï Markov a appliqué, en 1918, sa toute nouvelle théorie à l'étude de la répartition des voyelles et des consonnes dans la langue russe en analysant les 20000 premières lettres du roman de Pouchkine Eugène Onéguine.

Depuis cette date, la théorie de chaînes de Markov a multiplié ses champs d'application : en physique avec la mécanique statistique, dans l'étude des fils d'attente, en théorie de l'information, dans les algorithmes de reconnaissance vocale, en informatique avec les moteurs de recherche sur Internet, en biologie mathématique avec l'évolution des populations, la propagation des maladies et l'étude de l'ADN, dans l'étude de certains jeux, en musique avec la composition musicale algorithmique et dans bien d'autres domaines, parfois farfelus, comme la génération automatique de simulacres de texte.

Promis, une pause de 30 jours va avoir lieu pour cette rubrique le temps de se reposer.

La formule des probabilités totales permet d'écrire :

P(Bn+1)P(Bn+1|Bn)P(Bn)+P(Bn+1|Pn)P(Pn)+P(Bn+1|Nn),

soit

P(Bn+1)=0. PBn)+0.25P(Pn)+0.25P(Nn)

On trouve de même :

P(Pn+1)=0.5P(Bn)+0.5P(Pn)+0.25P(Nn)

P(Nn+1)+0.5P(Bn)+0.25P(Pn)=0.5P(Nn).

Ces données peuvent se mettre sous forme matricielle :

P(Bn+1)  (0   0.25   0.25)    (P(Bn))

P(Pn+1)=  (0.5  0.5  0.25) =   (P(Pn))

P(Nn+1)  (0.5  0.25   0.5)   (P(Nn))

que l'on écrira Un+1=TUn où T est la matrice de transition du processus markovien et où Un est le vecteur d'état au temps n.

Au long cours, le vecteur d'état Un sera donné par Un=TnU0 où Tn est la puissance n-ième de la matrice T.

Par exemple, en supposant qu'il fasse beau le premier jour, on obtiendra, au bout d'une semaine :

   (0.199   0.200   0.200)   (1)  = (0.199)  

U7 =   (0.400   0.400   0.399)   (0) = (0.400)

   (0.400   0.399   0.400)   (0) = (0.400)

La probabilité qu'il fasse à nouveau beau une semaine après est donc très voisine de 0.2.

On peut montrer que la matrice T admet le vecteur U=(0.2;0.4;0.4) comme vecteur propre, i.e :

(0.2) = ( 0   0.25   0.25) (0.2)

(0.4) = (0.5  0.5   0.25) (0.4)

(0.4)=  (0.5  0.25   0.5)  (0.4)

et que lim(n->+~) Un=U

Au pays des fées, il y a , pour un jour quelconque 20% de chance d'avoir du soleil, 40% d'avoir de la pluie et 40% d'avoir de la neige.

Les chaînes de Markov au quotidien :

Andreï Markov a appliqué, en 1918, sa toute nouvelle théorie à l'étude de la répartition des voyelles et des consonnes dans la langue russe en analysant les 20000 premières lettres du roman de Pouchkine Eugène Onéguine.

Depuis cette date, la théorie de chaînes de Markov a multiplié ses champs d'application : en physique avec la mécanique statistique, dans l'étude des fils d'attente, en théorie de l'information, dans les algorithmes de reconnaissance vocale, en informatique avec les moteurs de recherche sur Internet, en biologie mathématique avec l'évolution des populations, la propagation des maladies et l'étude de l'ADN, dans l'étude de certains jeux, en musique avec la composition musicale algorithmique et dans bien d'autres domaines, parfois farfelus, comme la génération automatique de simulacres de texte.

Promis, une pause de 30 jours va avoir lieu pour cette rubrique le temps de se reposer.