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

Markov et la Belle au bois dormant

Piste rouge 5 septembre 2014  - Rédigé 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.

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

  • Markov et la Belle au bois dormant

    le 7 septembre 2014 à 12:07, par amic

    Article sympa, je ne connaissais pas ce paradoxe de la Belle au bois dormant, qui est assez simple à présenter, avec une jolie conclusion.

    Bon, j’aurais plus imaginé que la machine à laver soit celle du prince charmant, pour changer. Si le boulot d’Aurore est de dormir, j’imagine que celui du prince charmant est plus salissant ;-)

    Répondre à ce message
  • Markov et la Belle au bois dormant

    le 8 septembre 2014 à 14:45, par Philippe Gay

    Merci ! Vous pourrez trouver d’autres paradoxes sur probas-enigmes.
    Mon premier article devait s’intituler « L’Argument de l’Apocalypse… selon Madame Michu », mais cela risquait d’être perçu comme trop sexiste. A tort, car Madame Michu était elle aussi perspicace ! Alors on a changé le titre en « L’Argument de l’Apocalypse… selon la Répression des fraudes ».
    Maintenant, si Aurore dort, on peut imaginer le prince charmant réparer la machine à laver ou le modem d’Aurore, en cas de panne, pendant que nos expérimentateurs terminent leurs tests.

    Répondre à ce message
  • Markov et la Belle au bois dormant

    le 17 septembre 2014 à 10:57, par LéoGR

    L’article est très clair sur les chaines de Markov homogènes à nombre d’états fini. Pour le paradoxe de la Belle au bois dormant, le vecteur propre donne alors les probabilités des différents réveils (S1,S2 et S3) après « un grand nombre de réveils » (théoriquement, une infinité de réveils).
    Aussi, dans quelle mesure le vecteur propre de cette chaine doit-il être le repère que doit utiliser la Belle au réveil pour définir son degré de croyance, dans une expérience unique ?
    En effet, dans cette chaine de Markov, le premier réveil est soit un réveil Face, soit un réveil Pile (l’état initial n’étant pas probabilisé). Si le premier réveil est un réveil Face alors le deuxième a une chance sur 2 d’être un réveil Face. Si le premier réveil est un réveil Pile alors le deuxième réveil est nécessairement un réveil Pile. Dans les deux cas, un deuxième réveil aura nécessairement lieu. Dans une expérience unique de la Belle, le premier réveil a une chance sur deux d’être un réveil Face et le deuxième réveil (s’il a lieu) n’a aucune chance d’être un réveil Face. Dans une expérience unique, un deuxième réveil n’a qu’une chance sur deux d’avoir lieu.
    Le vecteur propre de la chaine de markov proposée n’est-il pas le repère que doit utiliser la Belle dans une version (voir Bostrom 2006) où la Belle est soumise à une infinité d’expériences avec oublie entre les réveils et entre les expériences ?

    Répondre à ce message
    • Markov et la Belle au bois dormant

      le 17 septembre 2014 à 19:32, par Philippe Gay

      Merci LeoGR pour votre intervention.

      Il y a deux démonstrations de la BABD dans cet article :

      1. La première se base sur une expérience unique et Aurore répond :
          * en connaissant les probabilités connues des trois éléments qu’elle est susceptible de rencontrer ;

          * puis en appliquant le principe suivant : à la probabilité la plus grande correspond la réponse à choisir. C’est le principe de maximum de vraisemblance. Il est par exemple utilisé par les codes correcteurs d’erreurs en télécoms. Une autre stratégie serait moins « payante ». (Je remercie Gérard Grancher qui a mis en exergue ce point digne d’intérêt.)

      2. La seconde utilise bien sûr la chaîne de Markov qui simule une répétition infinie de cette expérience et obtient le même résultat. Une remarque souvent faite en cours : peu importe que ce soit Aurore qui fasse disons 100 fois l’expérience ou que ce soit 100 personnes qui la fassent une fois : cela revient à faire la même chose. Ces 100 (ou plus) expériences et à plus forte raison une infinité, donne les probabilités sur une seule : c’est une application de la Loi des grands nombres. Plus le nombre d’essais est grand et plus nos expérimentateurs auront de chance de mesurer de façon précise les probabilités.

      Il y a cohérence entre les deux démonstrations. Il n’y a pas lieu de dissocier les probabilités sur un tirage et celles sur plusieurs. Ce serait remettre en cause les bases théoriques et l’expérience quotidienne. D’ailleurs, comment la probabilité sur un tirage peut être différente après une infinité de tirages ? Il faudrait fournir aux expérimentateurs une pièce magique...

      Vous dites « … Dans une expérience unique, un deuxième réveil n’a qu’une chance sur deux d’avoir lieu. » Oui, mais cela est vrai pour pour tous les réveils… et on a équiprobabilité entre les trois cas. Donc l’objection ne tiens pas. Mais on peut faire autrement, comme expliqué sur http://probas-enigmes.pagesperso-orange.fr/Aurore.html ou sur http://probas-enigmes.pagesperso-orange.fr/Article_PDF.html . Peu importe, à chacun de choisir sa méthode.

      La question n’est pas de savoir si l’on passe de probabilités (1/2,1/2) à (1/3, 1/3, 1/3), mais de voir ce que chaque démonstration sous-entend.

      J’ai créé différents problèmes où l’on voit ce passage de probabilités (1/2,1/2) à (1/3, 1/3,1/3) sur http://probas-enigmes.pagesperso-orange.fr/index.html .

      Je me suis demandé si l’on pouvait imaginer des problèmes où l’on verrait au contraire un passage de (1/2, 1/2) à (1/2, 1/4, 1/4). (Je sais que cela vous tiens à cœur, alors je me suis prêté au jeu.) Il faut pour cela un autre processus : http://probas-enigmes.pagesperso-orange.fr/Vishy.html . Et là, un nouveau graphe de Markov est (presque) nécessaire pour voir la différence de structure avec la BABD !

      J’ai été un peu long. Effectivement, cet article aborde plusieurs sujets différents si l’on fouille un peu.

      Répondre à ce message
  • Markov et la Belle au bois dormant

    le 19 mai à 14:25, 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 ou Vie2) = 1/2 est exactement celui de la Belle au bois dormant.

    Répondre à ce message
  • Markov et la Belle au bois dormant

    le 19 mai à 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
    • Markov et la Belle au bois dormant

      le 19 mai à 17:07, par Philippe Gay

      Pour maîtriser les chaînes de Markov, il faut un peu de pratique.

      1) La convergence vers les valeurs propres prend du temps si l’on simule un grand nombre de multiplications de matrices de transitions. C’est pour cela que la recherche des valeurs propres est la méthode à préférer, même si sur le plan pédagogique les deux ont leur importance. Si l’on se donne la peine de faire le calcul de cette multiplication (avec un tableur ou un logiciel comme Matlab), on voit assez vite que l’on devient proche de (1/3, 1/3, 1/3) quelles que soient les valeurs initiales choisies. On a là une petite matrice et ce n’est pas trop pénible. (Pour des matrices plus larges, il faut effectivement éviter cette méthode et passer par les valeurs propres.) Une remarque importante : la probabilité EST la probabilité. ELLE NE CHANGE PAS. C’est notre approche intellectuelle qui nous fait croire que le résultat évolue (ce qui serait absurde). En fait, c’est simplement nos observations qui se rapprochent de la valeur cherchée. On a un graphe qui simule une infinité de tirages. La loi des grands nombres permet d’affirmer que l’on « mesure » les bonnes probabilités. Si vous testez une simple pièce de monnaie (sans chaîne de Markov), il faut là aussi un grand nombre de lancers pour vérifier qu’elle est bien équilibrée. Il n’y a pas d’erreur à ce niveau.

      2) Le graphe montre tous les passages d’Aurore dans les trois états. Il répond à la question « Où sera Aurore après un grand nombre de transitions ? ». C’est la question que se posent les expérimentateurs, Aurore ou un simple spectateur. Tous auront la même réponse, soit (1/3, 1/3, 1/3). Sauf que les expérimentateurs voient tous les réveils, Aurore les fait tous, mais ne se rappelle que d’un seul, et le spectateur qui passe n’en voit qu’un et un seul. Peu importe : c’est comme une urne où prendre une boule ou plusieurs ne changerait pas les probabilités. Il n’y a pas d’erreur à ce niveau non plus.

      Le problème des « Vies de Vishy » que j’ai créé avait bien pour but de créer un équivalent inédit à ce problème de la Belle au bois dormant.

      Répondre à ce message
  • Markov et la Belle au bois dormant

    le 19 mai à 20:03, par J.Bennetier

    Merci de m’avoir lu et répondu.
    Que l’on prenne une valeur approchée ou la valeur 1/3 lors d’un réveil au rang n de la chaîne de Markov il s’agit toujours d’une probabilité calculée par un observateur qui assiste, comme vous le notez, à un seul réveil. Ce calcul ne s’applique pas, comme le prétendent les tieristes, au cas de Aurore qui peut être réveillée deux fois.
    Vous convenez que les problèmes des Vies de Vishy et de la Belle au bois dormant sont identiques. La solution du problème des Vies devrait être la même que celle que vous donnez pour le problème de la Belle c’est-à-dire P(VieUnique) = P(vie1) = P(Vie2) = 1/3 or la solution donnée dans votre article est P(VieUnique) = 1/2 et P(vie1) = P(Vie2) = 1/4. Il me semble qu’il y a là une contradiction.

    Répondre à ce message
    • Markov et la Belle au bois dormant

      le 19 mai à 20:27, par Philippe Gay

      Si je suis votre raisonnement, Aurore et un observateur verraient des probabilités différentes ? Franchement, je ne vois pas pourquoi. Il y a quelque chose qui m’échappe.

      Prenons un exemple plus simple. Si je jette une pièce de monnaie équilibrée, je verrai toujours les probabilités pour Pile et Face de 1/2, quel que soit l’état de ma mémoire ou le nombre de lancers. Et si quelqu’un passe à côté de moi, il verrait lui aussi ces mêmes probabilités même si sa mémoire est différente de la mienne et s’il ne compte pas les lancers de la même façon. Pour moi et pour cette nouvelle personne, c’est le même graphe de Markov, même si le nombre de « lectures » diffère.

      (Pour les Vies de Vishy, il y a effectivement des ressemblances, mais aussi des différences. Pardon pour ma précédente intervention. Quelle que soit votre opinion, on peut dire ceci : si c’est le même graphe même probabilités. Sinon, on ne peut pas conclure.)

      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