Il est des expressions, des noms de concepts ou de lois scientifiques qui interpellent : Principe d'incertitude, théorème du reste chinois, principe de moindre action, ... et il y a les chaînes de Markov. Les chaînes de Markov sont un outil mathématique issu des probabilités et dont les domaines d'applications sont assez vastes : intelligence artificielle, génétique, météorologie, ...

C'est le mathématicien russe Andreï Markov qui, en 1902, proposa cet outil. Son objectif est de permettre d'appliquer certains calculs de probabilité à des problèmes où la loi des grands nombres est inopérante. Qu'est-ce que la loi des grands nombres ? En fait il en existe deux. L'une dite faible, l'autre forte. Mais toutes les deux expriment le fait qu'il existe une corrélation entre la probabilité calculée et celle observée d'une succession d'évènements. Par exemple si on joue à pile ou face. Après un grand nombre de lancés, on s'aperçoit que le nombre de fois où la pièce est tombée sur pile ou face est à peu près la même, ce qui correspond aux probabilités que l'on obtiendrait après calcul. Toutefois la loi des grands nombre a un gros problème. Elle implique que chaque évènement soit indépendant. Or dans la réalité, il existe de nombreuses situations où un évènement peut voir sa probabilité de réalisation modifiée en fonction de la réalisation d'un autre évènement. Par exemple en météo on sait que la probabilité d'avoir une tempête s'il a fait beau la journée d'avant n'est pas la même que s'il a plu. A priori la loi des grands nombres et certaines réalités semblent totalement incompatibles. C'est là où interviennent les chaînes de Markov. Elles intègrent un peu de dépendance entre les évènements. Plus exactement, dans une suite d'évènements, elles permettent de calculer un évènement qui se passe au temps 't', en prenant en compte l'évènement au temps 't-1' et seulement cet évènement.

Ce qui est amusant avec les chaînes de Markov, c'est que ça ne fait pas seulement appel aux mathématiques du calcul des probabilités, mais aussi à la théorie des graphes (graphes orientés) et à l'algèbre linéaire (matrice de transition). Toutefois l'utilisation de multiples outils mathématiques rend parfois difficile la compréhension de base des chaînes de Markov surtout que c'est un outil puissant, mais pas enseigné de manière systématique dans tous les domaines. Nous commencerons par un exemple simple, que nous commenterons et qui, de fil en aiguille, nous amènera à découvrir et comprendre les chaînes de markov.

Bonne lecture :)

Julie a un cellulaire avec un forfait mensuel de 2 heures. Afin de bien gérer son forfait, elle constate que :

- Si au cours du mois, elle a dépassé son forfait, la probabilité qu'elle le dépasse le mois suivant est de 1/5

- Si elle n'a pas dépassé son forfait, la probabilité qu'elle le dépasse le mois suivant est de 2/5.

La question qui nous intéresse à présent est l'évolution de la probabilité de dépassement de forfait pour Julie. Ce type de question permet d'utiliser les chaînes de Markov, car la probabilité, à un mois donné, de dépasser ou non son forfait dépend de la probabilité du mois précédent.

La première chose à faire avec les chaînes de Markov c'est de déterminer les états. Ici il y en a deux qu'on appelle aussi évènement.

- Evènement A : Julie a dépassé son forfait

- Evènement B : Julie n'a pas dépassé son forfait

Comme ces évènements évoluent dans le temps, on note An, Julie a dépassé son forfait au mois n, et Bn, Julie n'a pas dépassé son forfait au mois n.

La probabilité de dépassement pour un mois n donné est pour les deux évènements

- an = P(An)

- bn = P(Bn)

On a par définition en probabilité, an + bn = 1, c'est-à-dire que la somme des probabilités des évènements vaut 1. Dans le cas présent, la probabilité bn est le complémentaire de an ce qui s'exprime par bn = 1 - an. Il nous suffit donc de connaître pour le premier mois la probabilité de l'evènement A. On va supposer que a1 = P(A1) = 1/2.

Nous allons à présent construire le graphe associé à cette chaîne de Markov qui permettra d'exprimer et de visualiser les relations de probabilité entre un mois n et n+1. Nous définirons ensuite la matrice de transition qui permet de calculer les probabilités pour un mois n+1, n+2, ..., n+m.

Le graphe exprime les différents évènements et leur relation. Nous avons ici deux évènements. On dessine donc 2 points ou 2 cercles symbolisant chacun les évènements : A = a dépassé son forfait, B = n'a pas dépassé son forfait.

On doit à présent dessiner les relations entre ces évènements. On prend chaque point indépendamment. En partant du point A, deux situations peuvent arriver. Soit on a dépassé le forfait, dans ce cas on fait une flèche qui revient à A parce que A représente l'évènement : a dépassé son forfait. Si on ne l'a pas dépassé, alors on fait une flèche en direction de B. En partant du point B, on peut avoir deux évènements. Si on a dépassé le forfait, alors on fait une flèche vers A, si on ne l'a pas dépassé, alors une flèche qui va vers B car B représente l'évènement : n'a pas dépassé son forfait.

Chaque flèche représente l'évolution d'une probabilité d'un mois à un autre en fonction du mois précédent. Comme il s'agit de probabilité, on peut écrire à côté de chaque flèche la valeur de sa probabilité.

Comment vérifier qu'un graphe probabiliste est juste ? La somme des probabilités des flèches partant d'un point doit être égale à 1.

Pour le point A on a 1/5 + 4/5 = 1. Pour B on a 2/5 + 3/5 = 1. Le graphe semble être juste.

La construction du graphe est ici finalement assez simple car totalement symétrique, mais ce n'est pas toujours le cas. De plus le nombre d'évènements ou d'états est limité à 2. Pour les besoins de l'explication, on a pris un exemple assez simple mais ne vous imaginez pas que tous les exemples le sont.

Nous allons voir comment, à partir du graphe, construire une matrice. Ensuite nous verrons comment, à partir de cette matrice, calculer les probabilités de dépassement de forfait pour un mois donné.

Une chaîne de Markov à 2 états donne une matrice carrée à 2 lignes 2 colonnes, et plus généralement une chaîne de Markov à n états donne une matrice carrée à n lignes et n colonnes (Attention la généralisation que je viens de faire à n états est une déduction. Effectivement je n'ai jamais vu de démonstration à cela, mais aucun exemple contraire non plus d'où la généralisation).

Pour construire la matrice, il suffit de jouer à la bataille navale. On donne des lettre aux lignes : A, B, .. et des lettres aux colonnes : A, B, ...

Ensuite on cherche la probabilité d'aller de A->A. On regarde le graphe, on récupère la valeur de la flèche qui va de A->A et on l'inscrit à l'intersection de la colonne A et de la ligne A. Pour la probabilité de A->B, B->B et B->A même chose. On obtient finalement la matrice suivante :

Pour l'instant, nous avons vu comment construire le graphe d'une chaîne de Markov, puis à partir de ce dernier la matrice de transition. Calculons à présent les probabilités de dépassement de forfait.

En fait dans une chaîne de Markov la probabilité Pn au mois n s'écrit P(an,bn,...), ou an, bn, ... représente les différents états de la chaîne de Markov. Dans notre cas, on a deux états donc an et bn, pour n=1, on a an = 1/2 (voir début de l'article) et bn = 1 - an = 1/2 soit P(1/2,1/2). On dit que la probabilité à l'étape n est donnée par la matrice ligne P et on a la relation suivante :

P_n * M = P_n+1

On nomme la matrice M une matrice de transition car elle fait la transition entre une période n et n+1.

Calculons P₂ = M * P₁ ce qui nous donnera a2 et b2 par la même occasion la probabilité a2 de dépassement de forfait pour Julie au bout d'un mois.

Lorsqu'on multiplie deux matrices, la matrice résultante a un nombre de lignes t de colonne égale au plus petit dénominateur commun des deux matrices. Ainsi une matrice ligne de 2 éléments avec une matrice carrée de 4 éléments produira une matrice ligne de 2 éléments.

Pour trouver un élément de la matrice résultante, on multiplie les éléments d'une ligne de la matrice à gauche par les éléments d'une colonne de la matrice à droite.

La multiplication de matrice n'est pas commutative, c'est-à-dire que si P = AxB cela n'implique pas que P = BxA. Dans certains cas particuliers, cela peut être vrai mais l'opération de multiplication de matrice ne le garantie pas.

Pour en savoir plus sur le calcul matriciel, je vous invite à lire notre article :

• A quoi servent les matrices dans un moteur 3D ?

Comment calculer P_n+2, P_n+3, ... ? On peut évidemment calculer période par période, mais c'est un peu long. La formule que nous avons vu a une propriété intéressante :

P_n * M¹ = P_n+1

P_n * M² = P_n+2

...

P_n * M^m = P_n+m

Pour connaître l'évolution d'une probabilité au bout de m période, il suffit de multiplier m fois la matrice de transition par elle-même.

Lorsqu'on calcule P₂, P₃, ... on se rend compte que la matrice P_n tend vers les valeurs (a_n=1/3 b_n=2/3) Selon la formule P_n = P * Mⁿ implique que les probabilités tendent aussi vers des valeurs constantes. Lorsque cela se produit, on dit que la loi de probabilité est stationnaire et la chaîne de Markov est dite irréductible. En fait il existe plusieurs types de chaînes de Markov et elles dépendent du type des états qui constituent cette chaîne.

Etat récurrent :
Cela signifie que toute trajectoire dans le graphe probabiliste revient en ce point au moins une infinité de fois, et y revient certainement en un temps fini. Le passage en ce point est récurrent.

Etat transitoire :
Il existe des trajectoires du graphe probabiliste qui reviennent en ce point un nombre fini de fois. On transite par ce point mais pas une infinité de fois sinon c'est un état récurrent.

Etat absorbant :
Etat dans lequel aucune trajectoire ne pointe vers d'autres points (état). Lorsque dans un graphe on passe par un état absorbant.

Chaîne de Markov irréductible :
Chaîne dont tous les états communiquent. On peut donc passer d'un point à un autre soit directement soit par l'intermédiaire d'autres points. on dit aussi si tout état est atteignable à partir de tout autre état si la probabilité de passage de tout état à un autre est strictement positive

Chaîne récurrente :
Cas particulier d'une chaîne irréductible dont tous les états sont récurrents. Une chaîne récurrente a la propriété lim pn = M lorsque n->l'infini. La matrice de transition tend vers une matrice M.

Chaîne périodique :
Cas particulier des chaînes récurrentes dont la matrice de transition admet la relation suivante P = P₂ = ... = P_n.

Chaîne absorbante :
Chaîne composée d'au moins un état absorbant et si tous les états non absorbants peuvent atteindre ce point.

• Cours Irem (institut de recherche de l'enseignement des mathématiques)
  
  
• Cours sur les chaînes de Markov (niveau agrégation)
  
  
• Exemple d'application des chaînes de markov
  
  
• Autre cours sur les chaînes de Markov