Plus qu’un objet, un outil : la chaîne de Markov !

Markov et la Belle au bois dormant

Piste rouge Le 5 septembre 2014  - Ecrit par  Philippe Gay Voir les commentaires (9)

En 1913, le mathématicien russe Andreï Markov (1856 - 1922) eut l’idée d’analyser de façon statistique la succession des lettres dans le roman « Eugène Onéguine » d’Alexandre Pouchkine. Il nota que l’apparition de celles-ci dépendait fortement des précédentes (on parle de contraintes). Cette remarque reste valable quels que soient la langue ou l’alphabet. Il conforta ainsi une idée qu’il avait développée dès 1906 et on appela par la suite « chaîne de Markov » tout graphe qui décrivait en termes de probabilité les relations entre des événements et leurs prédécesseurs.

Comment traiter de probabilités si celles-ci changent en fonction des tirages déjà effectués ? Cela semble insurmontable. Pourtant, beaucoup de problèmes restent accessibles à condition de connaître un outil adéquat : la chaîne de Markov.

Avant d’entamer le sujet, on analysera un problème classique, « La Belle au bois dormant ». Puis on présentera d’autres exemples traités avec la théorie mise au point par Markov. Et pour conclure, on adaptera cet outil à la Belle au bois dormant qui bénéficiera ainsi d’une seconde démonstration.

La Belle au bois dormant

Il s’agit un paradoxe connu : celui de la Belle au bois dormant  [1].

Le dimanche soir, les expérimentateurs endorment la Belle, appelons-la Aurore, puis font un tirage au sort avec une pièce non truquée :

  • Face  : on réveille Aurore le lundi matin et les expérimentateurs ont un entretien avec elle ;
  • Pile  : on réveille Aurore le lundi matin et les expérimentateurs ont un entretien avec elle, puis ils l’endorment à nouveau avec un traitement qui lui fait oublier la journée du lundi ; les expérimentateurs la réveillent une seconde fois le mardi matin et ont un second entretien avec elle.

Aurore est bien au courant de cette procédure. Lors de chacun des entretiens, on demande à Aurore si selon elle on a tiré pile ou face le dimanche soir. Deux points de vue divergent :

  • Pour les expérimentateurs, il y a bien une chance sur deux pour tirer pile ou face le dimanche soir ;
  • Mais les jours suivants la situation est plus subtile : face occasionne deux fois moins de réveils que pile (et aussi les lundis sont bien sûr plus nombreux que les mardis).

À chaque réveil, Aurore fait le raisonnement suivant :

  • il existe pour elle trois cas possibles : face-lundi, pile-lundi et pile-mardi ;
  • face-lundi et pile-lundi ont la même probabilité (on dit que ces deux cas sont équiprobables) car on suppose la pièce bien équilibrée ;
  • pile-lundi et pile-mardi ont la même probabilité aussi car le protocole les rend aussi fréquents l’un que l’autre ;
  • ces trois cas (qu’elle ne peut pas dissocier) sont donc équiprobables.

Parmi ces trois cas, un est pour face et deux pour pile. On applique la définition des probabilités : le rapport entre le nombre de cas favorables (pour pile ou face) divisé par le nombre de cas total (ici $3$).

Aurore répond :

  • face avec une probabilité de $1/3$
  • et pile avec une probabilité de $2/3$.

Elle a un esprit vraiment très méthodique [2] [3] !

La pièce de monnaie non truquée

Passons maintenant à notre première chaîne de Markov. Examinons les tirages successifs d’une simple pièce de monnaie, juste pour mettre en place les notions de base [4].

Lançons cette pièce de monnaie plusieurs fois de suite. On note les instants : $ t $, $ t+1 $, $ t+2 $, $ t+3 $... Elle possède ce qu’on appelle deux états possibles que l’on note $S_1$ et $S_2$, pour respectivement pile et face.

Passons d’un instant $t$ à l’instant $t+1$, on obtient quatre transitions possibles :

  • de l’état $S_1$ vers $S_1$ (on reste dans le même état : on a tiré pile deux fois de suite),
  • $S_1$ vers $S_2$,
  • $S_2$ vers $S_1$,
  • et $S_2$ vers $S_2$.

Supposons que cette pièce soit non truquée et bien équilibrée, chacune des transitions a autant de chance d’apparaître. Leurs probabilités (que l’on appelle probabilités de transitions) sont donc égales (là aussi on dit équiprobables).

Regroupons sur un dessin ces 2 états et ces quatre transitions. On obtient ce que l’on nomme communément un graphe. En réalité un cas particulier de graphe : une chaîne de Markov.


Figure 1 : Chaîne de Markov pour une pièce non-truquée.

Sur cette chaîne de Markov, les états sont notés par des cercles et les transitions par des flèches partant de l’état initial vers l’état final et ayant une valeur qui est la probabilité de transition. La somme des probabilités sortant d’un état est toujours égale à 1.

À chaque instant $t$, le processus emprunte un chemin sur l’une des flèches sortant de l’état où il était.

La pièce de monnaie magique

Imaginons qu’il existe une pièce magique définie par le graphe ci-dessous. Attention, la probabilité de tirer pile ou face dépend ici du fait que vous venez de tirer pile ou face ! Cette pièce est très difficile à fabriquer.

Les quatre flèches montrent de façon simple une situation pourtant complexe :

  • l’état à l’instant $t+1$ dépend de de celui à l’instant $t$,
  • et si vous produisez un second tirage, les états à l’instant $t+2$ dépendent de ceux à l’instant $t+1$,
  • on peut continuer ainsi à l’infini : cela revient à changer sans arrêt d’état sur le graphe.


Figure 2 : Chaîne de Markov pour une pièce truquée.

À un instant $t$ donné, pour chaque état $S$, on a une probabilité d’apparition. Toujours pour chaque instant $t$, on peut regrouper toutes ces probabilités sous forme d’un vecteur. Pour la pièce magique, les composantes sont les probabilités d’être à l’état $S_1$ ou $S_2$ à un instant $t$ :

\[\vec{V_t} = \begin{pmatrix}P(S_1) \\ P(S_2)\end{pmatrix}\]

Par exemple, si on observe Pile, le vecteur devient $\vec{V_t} =\begin{pmatrix}1 \\ 0\end{pmatrix}$.

Pour Face : $\vec{V_t} =\begin{pmatrix}0 \\ 1\end{pmatrix}$.

Dans le cas général : $\vec{V_t} =\begin{pmatrix}p \\ 1-p\end{pmatrix}$ (avec $p$ prenant toute valeur entre zéro et un).

La somme de toutes les probabilités composant un vecteur vaut un.

On aimerait connaître le vecteur à l’instant suivant $t+1$, le connaissant à l’instant précédent $t$. Pour chaque état $S$ il faut additionner tout ce qui « vient » des autres états à l’instant $t$. Ayant ici deux états, on obtient deux égalités utilisant deux variables :

\[\begin{align} P_{t+1}(S_1)&=& 0,60.P_{t}(S_1) + 0,75.P_{t}(S_2) \\ P_{t+1}(S_2)&=& 0,40.P_{t}(S_1) + 0,25.P_{t}(S_2) \end{align}\]

Cette écriture devient vite lourde, surtout si l’on passe à l’instant t+2, puis t+3 ! Mais on remarque aussi que les opérations sont linéaires [5].
En un tel cas, mieux vaut utiliser les notations matricielles. Cela permet d’utiliser des opérations que l’on peut soit maîtriser par la théorie, soit avec des logiciels abordables par beaucoup.

Plutôt que manipuler des lignes d’équations, on définit la matrice de transitions $T$. Cette définition est importante, parce qu’elle permet d’obtenir une relation matricielle relativement concise, valable pour chaque instant $t$ et pour chaque vecteur $V$ :

\[\begin{align} \vec{V_{t+1}} &=& T \times \vec{V_t}\\ \end{align}\]

Et $T$ s’obtient soit par la lecture du graphe, soit par la lecture du système d’équations.

\[\begin{align} \vec{V_{t+1}} &=& \begin{pmatrix}0,60& 0,75 \\ 0,40 & 0,25\end{pmatrix}. \vec{V_t} \end{align}\]

Connaissant le vecteur $\vec{V}$ à l’instant $t$, on déduit celui à l’instant $t+1$ [6].

Quelle que soit la situation (pièce truquée, processus automatique ou équipements télécoms), cette matrice est toujours carrée. Elle a autant de lignes et de colonnes que d’états (ici deux). Comme la somme des valeurs des flèches sortantes est égale à 1, la somme des termes d’une colonne est aussi égale à $1$.

Si l’on part de l’état initial $\begin{pmatrix}1 \\ 0\end{pmatrix}$ on obtient à l’instant suivant :

\[\begin{align} \vec{V_{t+1}} &=& \begin{pmatrix}0,60& 0,75 \\ 0,40 & 0,25\end{pmatrix}. \begin{pmatrix}1 \\ 0\end{pmatrix} \\ \vec{V_{t+1}} &=& \begin{pmatrix}0,6 \\ 0,4 \end{pmatrix} \end{align}\]

On n’obtient pas l’équiprobabilité $\begin{pmatrix}1/2 \\ 1/2\end{pmatrix}$. La pièce est donc bien truquée !

Maintenant, regardons ce qui se passe aux instants suivants :

\[\begin{align} \vec{V_{t+n}} &=& T^n\vec{V_t}. \end{align}\]

La situation évolue. On obtient successivement :

\[ \begin{pmatrix}0,6 \\ 0,4 \end{pmatrix}, \begin{pmatrix}0,66 \\ 0,34 \end{pmatrix}, \begin{pmatrix}0,651 \\ 0,349 \end{pmatrix} ... \]

Il est important de noter que la somme des termes de chaque vecteur $\vec{V}$ reste égale à $1$.
Autre point important : si on augmente le nombre de tirages, cela revient à refaire le produit matriciel un grand nombre de fois et on s’approche d’un vecteur ayant sensiblement la valeur [7] :

\[\begin{align} \vec{V_{p}} &=& \begin{pmatrix}0,652174... \\ 0,347826... \end{pmatrix} \end{align}\]

Ce vecteur issu de la matrice de transition [8] a pour propriété la relation suivante [9] :

\[\begin{align} \vec{V_{p}} &=& T.\vec{V_{p}} \end{align}\]

Au bout d’un temps « assez long », ce vecteur issu de la matrice de transitions [10] montre les probabilités d’obtenir Face ou Pile. Autre point important : ce vecteur ne dépend pas des valeurs de départ [11]. Ici un grand nombre d’observations montre que cette pièce magique au comportement étrange donne en moyenne :

\[\begin{align} \vec{V} &=& \begin{pmatrix} 15/23 \\ 8/23 \end{pmatrix} \end{align}\]

Cette pièce magique n’est pas équitable !

Tir à l’arc

Pendant qu’Aurore se prête à l’expérimentation, son Prince charmant s’entraîne au tir à l’arc. Il respecte les règles suivantes. Il effectue un tir à 50 mètres. S’il réussit il passe à 60 mètres, sinon il retente sa chance à 50 mètres. A 60 mètres, s’il réussit il passe à 70 mètres, sinon il revient à 50 mètres. A 70 mètres, s’il réussit il passe à 80 mètres, sinon il revient à 60 mètres. A 80 mètres, s’il réussit il reste à cette distance, sinon il revient à 70 mètres.

L’énoncé complet est résumé ci-dessous sous forme de graphe et de matrice où l’on a ajouté les probabilités de transitions (elles ont été communiquées par le maître-archer qui entraîne le Prince charmant [12]). L’un des avantages de la chaîne de Markov réside dans la représentation simple de processus longs à décrire de façon littérale : un dessin vaut mieux qu’un long discours !


Figure 3 : Chaîne de Markov pour l’entraînement au tir à l’arc.

\[\begin{align} \vec{V} &=& \begin{pmatrix} 0,5 && 0,6 && 0 && 0 \\ 0,5 && 0 && 0,7 && 0 \\ 0 && 0,4 && 0 && 0,8\\ 0 && 0 && 0,3 && 0,2 \\ \end{pmatrix} \end{align}\]

On suppose que le Prince charmant commence à 50 mètres (en fait ce point de départ n’a ici que peu d’importance). Au bout d’un temps assez long, quelles sont les probabilités de voir le Prince charmant à des distances de 50, 60, 70 et 80 mètres ?

La réponse est apportée par le vecteur issu [13] de la matrice de transitions $T$ :

\[\vec{V_p} \approx \begin{pmatrix} 0,402 \\ 0,335 \\ 0,191 \\ 0,072 \\ \end{pmatrix} \]

À l’aide de ce vecteur on peut aussi calculer la valeur moyenne de la distance où le Prince charmant effectue ses tirs.

\[ d_{moyen} \approx 0,402 \times 50 + 0,335 \times 60 + 0,191 \times 70 + 0,072 \times 80 \approx 59,3 \quad \text{ mètres} \]

On reconnaît un cas particulier de moyenne pondérée : on pondère chaque distance suivant les probabilités trouvées ; la somme de toutes les probabilités valant $1$, le dénominateur est absent.

Un problème à l’énoncé ardu soulève moins de difficultés une fois connues les bases des chaînes de Markov.

La Belle au bois dormant (2)

Pendant ce temps les expérimentateurs, en bons statisticiens, décident de renouveler l’expérience sur plusieurs semaines de rang afin de conforter leurs conclusions.

De notre côté vérifions que la chaîne de Markov reste cohérente avec ce nouveau protocole. On définit nos états [14] :

  • Lundi - Face,
  • Lundi - Pile,
  • Mardi - Pile.

On obtient le graphe et la matrice de transition suivants :


Figure 4 : Chaîne de Markov pour les tests de la Belle au bois dormant.

\[\begin{align} T &=& \begin{pmatrix} 0,5 & 0 & 0,5 \\ 0,5 & 0 & 0,5 \\ 0 & 1 & 0 \end{pmatrix} \end{align}\]

Après un état $S_1$, le test de la semaine est terminé. On passe au dimanche suivant et le protocole recommence avec un nouveau tirage au sort. Ainsi, après $S_1$ succède soit un autre état $S_1$ avec une probabilité $1/2$, soit $S_2$ avec là aussi une probabilité de $1/2$. Ces transitions figurent sur le graphe par des traits en pointillés.

Après un état $S_3$, on obtient là aussi la fin du test hebdomadaire. Après $S_3$ succède soit un autre état $S_1$ avec une probabilité $1/2$, soit $S_2$ avec une probabilité de $1/2$. Ces transitions figurent sur le graphe par des traits mixtes.

La matrice $T$ possède beaucoup de termes nuls. Cela traduit un nombre important de flèches absentes sur le graphe. On dit qu’elle est creuse et certaines de ces matrices obtiennent ainsi des simplifications notables [15], tant pour un calcul littéral que pour un calcul numérique.

Cette matrice de transitions fournit le vecteur :
\[\begin{align} \vec{V_p} &=& \begin{pmatrix}1/3 \\ 1/3 \\ 1/3 \end{pmatrix} \end{align}\]

Si je ne considère que les réveils d’Aurore, j’observe à nouveau qu’elle est réveillée deux fois plus souvent par Pile que par Face.

\[ \begin{align} P(Face) &=& 1/3 \\ P(Pile) &=& 2/3 \end{align} \]

On retrouve les mêmes probabilités que celles détaillées au premier paragraphe.

Conclusion

Les chaînes de Markov procurent des visualisations graphique et matricielle agréables même pour des problèmes ardus. Leur analyse reste simple dans beaucoup de cas. Automatisme, régulation, télécoms [16], nombreux sont les secteurs utilisateurs de cet outil mathématique.

Il n’est pas nécessaire d’avoir une maîtrise totale du calcul matriciel et des graphes pour utiliser la plupart des chaînes de Markov. Un calcul numérique peut être mené avec des logiciels courants tels R, Matlab ou Scilab [17], ou même un tableur [18].

Annexe : La machine à laver et le modem

Une petite curiosité : peut-on avoir des états qui obtiennent une probabilité nulle. La réponse est clairement oui. Il suffit d’avoir une chaîne de Markov avec une forme particulière et... d’attendre un peu.

Imaginons la machine à laver d’Aurore. Si elle fonctionne correctement à l’instant t, elle a une probabilité $p$ de fonctionner à l’instant $t+1$ et $1-p$ de tomber en panne. Si elle est en panne à l’instant $t$, elle le reste à l’instant $t+1$.

Le graphe et la matrice correspondants figurent ci-dessous :


Figure 5 : Chaîne de Markov pour l’état de marche d’une machine à laver.

\[\begin{align} T &=& \begin{pmatrix} 0,9 & 0,0 \\ 0,1 & 1,0 \end{pmatrix} \end{align}\]

Et le vecteur issu de la matrice de transition est $\vec{V} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} $.

Ici l’état $S_1$ a disparu. Il est regrettable que l’état stable soit la panne ! Il suffit d’attendre, elle finira bien par arriver !

Mais dans d’autres processus, il est au contraire important que certains états $S$ disparaissent le plus vite possible. Par exemple, la probabilité de l’état « Recherche » d’un modem doit diminuer le plus vite possible, tandis que celui de l’état « Normal » devenir proche de $1$ le plus vite possible.

Ces états qui disparaissent sont simples à repérer. Ils n’ont pas de flèches entrantes venant d’un autre état [19].

Post-scriptum :

La rédaction d’Images des Maths et l’auteur remercient les relecteurs Vincent Beck et Gérard Grancher pour leur lecture attentive et leurs commentaires enrichissants.
L’auteur remercie également Serge Cantat pour son soutien constant depuis le début.

Article édité par Serge Cantat

Notes

[1À ce sujet on peut lire l’article suivant : « La Belle au bois dormant, la fin du monde et les extraterrestres » par Jean-Paul Delahaye. © Pour la science -N° 309 juillet 2003. Article ici.

[2Il existe différentes méthodes pour arriver à ce résultat ; comme cité plus haut, on peut lire J.-P. Delahaye à ce sujet.

Quelle que soit celle choisie, on aboutit à un constat : les expérimentateurs et Aurore ne voyant pas les mêmes ensembles d’événements, ils obtiennent des résultats numériques différents.

[3Si les expérimentateurs demandaient à Aurore de parier, elle aurait intérêt à choisir « pile » systématiquement et gagnerait 2 fois sur 3. On appelle ce concept le maximum de vraisemblance ; il est utilisé dans les télécoms pour les codes correcteurs d’erreurs. Si par contre Aurore répondait 1 fois sur 3 « face » et 2 fois sur 3 « pile », elle gagnerait un peu moins souvent : 5 fois sur 9.

[4On peut dire les premiers maillons !

[5Deux propriétés caractérisent la linéarité du système.

  • La première est la suivante : si l’on multiplie les deux coordonnées du vecteur $V_t$ par un même nombre $a$, celle de $V_{t+1}$ sont multipliées par $a$ aussi.
  • La seconde est plus difficile à expliquer. Supposons que $V_t$ soit somme de deux autres vecteurs $X_t$ et $Y_t$. Appliquons les formules pour déduire $X_{t+1}$ et $Y_{t+1}$. Alors $V_{t+1}$ sera égal à la somme de $X_{t+1}$ et $Y_{t+1}$.

[6La notation du texte est celle des matrices de passage, notion classique abordée au niveau Licence. Toutefois les probabilistes utilisent une autre convention :

\[\begin{align} \pi_{t+1} &=& \pi_{t} \times P\\ \end{align}\]

Avec :

  • les différents $\pi$ qui sont les transposés des vecteurs-colonnes $\vec{V}$ correspondants et deviennent des vecteurs-lignes,
  • et $P$ qui est la transposée de $T$ (toutes deux sont des matrices carrées de même dimension).

Naturellement les deux conventions procurent les mêmes résultats.

[7Il existe cependant des matrices $T$ ayant des formes particulières et donnant plusieurs vecteurs de ce type. En un tel cas, un calcul trop sommaire ne montrerait qu’une seule réponse fonction des valeurs de départ.

[8Ce vecteur est appelé vecteur propre. Ce terme est en fait issu de la théorie du calcul matriciel.

[9Résoudre ce type d’équation est étudié au niveau Licence pour des dimensions limitées (guère plus que 3 ou 4 états). Heureusement, comme affirmé en conclusion, des logiciels professionnels ou accessibles à tous peuvent donner totale satisfaction si l’on ne cherche que des valeurs numériques.

[10On ne traitera pas ici le cas où il existerait plusieurs vecteurs propres acceptables.

[11Si comme averti plus tôt, ce vecteur est unique.

[12On suppose que ce maître-archer (que je remercie pour sa patience) a assisté à suffisamment d’entraînements pour pouvoir estimer avec une bonne précision le déroulement de la séance à venir !

[13Pour les spécialistes, il vaut mieux dire « vecteur propre ».

[14On peut ajouter des états : dimanche soir, pile-mardi ou autres et vérifier que l’on aboutit aux mêmes résultats.

[15Suivant leurs formes, on les appelle matrice diagonale, matrice bande, matrice triangulaire, matrice blocs, etc. pour les plus connues.

[16Alexandru Spătaru (1987), Fondement de la théorie de la transmission de l’information, Presses Polytechniques Romandes

[17Ces trois logiciels sont de conception proche. R est un environnement d’analyse de données statistiques. Matlab semble offrir plus de fonctionnalités sous forme d’extensions. R et Scilab sont libres.

[18Ce qui a été le cas ici. Un tableur offre une fonction intégrée pour le produit matriciel.

[19On peut ajouter que les états qui persistent sont tout aussi simples à repérer : ils n’ont qu’une seule flèche sortante de probabilité $1$ qui revient sur elle-même.

Partager cet article

Pour citer cet article :

Philippe Gay — «Markov et la Belle au bois dormant» — Images des Mathématiques, CNRS, 2014

Crédits image :

Image à la une - La Belle au bois dormant, illustration de Gustave Doré (1867).

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • Markov et la Belle au bois dormant

    le 19 mai 2016 à 14:27, par J.Bennetier

    Je partage l’avis de LeoGR concernant l’argument des chaînes de Markov qui me semble contenir deux erreurs .
    (1) Quelque soit la situation initiale les probabilités qu’un réveil quelconque se trouve dans l’une 3 situations Lundi-Pile, Lundi-Face ou Mardi-Pile ne valent jamais (1/3,1/3,1/3), sauf après une infinité de lancers, ce que l’expérimentateur pourrait trouver un peu long.
    (2) Cet argument conduit à estimer la probabilité d’être dans l’une des 3 situations lors d’un réveil quelconque, c’est-à-dire la probabilité estimée par un observateur extérieur à l’expérience et non pas par Aurore elle-même.
    P.S. A mon avis le cas des 3 vies de Vishy où P(VieUnique) = P(vie1 et Vie2) = 1/2 est exactement identique à celui de la Belle au bois dormant.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM