Chaîne de Markov

Selon les auteurs, une chaîne de Markov est généralement un processus de Markov à temps discret ou un processus de Markov à temps discret ainsi qu'à espace d'états discret.



Catégories :

Processus stochastique - Physique statistique - Statistiques

Page(s) en rapport avec ce sujet :

  • en moyenne faut-il pour atteindre l'état 1 ? Exercice 2. On représente le cursus d'un étudiant de Licence par une chaîne de Markov définie comme suit : la... (source : math-info.univ-paris5)

Selon les auteurs, une chaîne de Markov est généralement un processus de Markov à temps discret ou un processus de Markov à temps discret ainsi qu'à espace d'états discret. En mathématiques, un processus de Markov est un processus stochastique possédant la propriété de Markov : de manière simplifiée, la prédiction du futur, sachant le présent, n'est pas rendue plus précise par des éléments d'information supplémentaires concernant le passé. Les processus de Markov portent le nom de leur découvreur, Andreï Markov.

Un processus de Markov à temps discret est une séquence de variables aléatoires à valeurs dans l'espace des états, qu'on notera dans la suite. La valeur est l'état du processus à l'instant Les applications où l'espace d'états est fini ou dénombrable sont innombrables : on parle alors de chaîne de Markov ou de chaînes de Markov à espace d'états discret. Les propriétés principales des processus de Markov généraux, par exemple les propriétés de récurrence et d'ergodicité, s'énoncent ou se démontrent plus simplement dans le cas des chaînes de Markov à espace d'états discret. Cet article concerne exactement les chaînes de Markov à espace d'états discret.

Andrei Markov a publié les premiers résultats sur les chaînes de Markov à espace d'états fini en 1906. Une généralisation à un espace d'états illimité dénombrable a été publiée par Kolmogorov en 1936. Les processus de Markov sont liés au mouvement brownien ainsi qu'à l'hypothèse ergodique, deux sujets de physique statistique qui ont été particulièrement importants au début du XXe siècle.

Propriété de Markov faible

Article détaillé : Propriété de Markov.

Définitions

C'est la propriété caractéristique d'une chaîne de Markov : en gros, la prédiction du futur à partir du présent n'est pas rendue plus précise par des éléments d'information supplémentaires concernant le passé, car toute l'information utile pour la prédiction du futur est contenue dans l'état présent du processus. La propriété de Markov faible possède plusieurs formes équivalentes qui reviennent toutes à constater que la loi conditionnelle de sachant le passé, i. e. sachant est une fonction de seul :

\begin{align}\forall n\ge 0, \forall (i_0,\ldots,i_{n-1},i,j)&\in Eˆ{n+2},
\\
\mathbb{P}\Big(X_{n+1}=j&\mid\, X_0=i_0, X_1=i_1,\ldots, X_{n-1}=i_{n-1},X_n=i\Big) = \mathbb{P}\left(X_{n+1}=j\mid X_n=i\right).
\end{align}

On suppose le plus fréquemment les chaînes de Markov homogènes, i. e. on suppose que le mécanisme de transition ne change pas au cours du temps. La propriété de Markov faible prend alors la forme suivante :

\begin{align}\forall n\ge 0, \forall (i_0,\ldots,i_{n-1},i,j)&\in Eˆ{n+2},
\\
\mathbb{P}\Big(X_{n+1}=j&\mid\, X_0=i_0, X_1=i_1,\ldots, X_{n-1}=i_{n-1},X_n=i\Big) = \mathbb{P}\left(X_{1}=j\mid X_0=i\right).
\end{align}

Cette forme de la propriété de Markov faible est plus forte que la forme précédente, et entraîne surtout que

\forall n\ge 0, \forall (i,j)\in Eˆ{2},\qquad\mathbb{P}\left(X_{n+1}=j\mid X_n=i\right) = \mathbb{P}\left(X_{1}=j\mid X_0=i\right).

Dans la suite de l'article on ne considèrera que des chaînes de Markov homogènes. Pour une application intéressante des chaînes de Markov non homogènes à l'optimisation combinatoire, voir l'article Recuit simulé. Il existe une propriété de Markov forte, liée à la notion de temps d'arrêt : cette propriété de Markov forte est principale pour la démonstration de résultats importants (divers critères de récurrence, loi forte des grands nombres pour les chaînes de Markov). Elle est énoncée dans l'article "Propriété de Markov".

Critère

Critère essentiel — Soit une suite de variables aléatoires indépendantes et de même loi, à valeurs dans un espace, et soit une application mesurable de dans Supposons que la suite est définie par la relation de récurrence :

\forall n\ge 0,\qquad X_{n+1}=f\left(X_n,Y_{n}\right),

et supposons que la suite est indépendante de Alors est une chaîne de Markov homogène.

Collectionneur de vignettes (coupon collector)  :

Petit Pierre fait la collection des portraits des onze joueurs de l'équipe nationale de football, qu'il trouve sur des vignettes au sein de l'emballage des tablettes de chocolat Cémoi ; chaque fois qu'il achète une tablette il a une chance sur 11 de tomber sur le portrait du joueur n° (pour tout). On note l'état de la collection de Petit Pierre, après avoir ouvert l'emballage de sa -ème tablette de chocolat. est une chaîne de Markov partant de, car elle rentre dans le cadre précédent pour le choix puisque

 X_{n+1}=X_n\cup\{Y_n\},

où les variables aléatoires sont des variables aléatoires indépendantes et uniformes sur  : ce sont les numéros successifs des vignettes tirées des tablettes de chocolat. Le temps moyen indispensable pour compléter la collection (ici le nombre de tablettes que Petit Pierre doit acheter en moyenne pour compléter sa collec') est , pour une collection de vignettes au total, de où est le -ème nombre harmonique. A titre d'exemple, tablettes de chocolat.

Remarques :
  • La propriété de Markov découle de l'indépendance des elle reste vraie quand les ont des lois différentes, et quand la "relation de récurrence" dépend de Les hypothèses faites en sus de l'indépendance sont là seulement pour assurer l'homogénéité de la chaîne de Markov.
  • Le critère est essentiel en cela que toute chaîne de Markov homogène peut être simulée via une récurrence de la forme pour une fonction bien choisie. On peut même choisir et choisir des variables indépendantes et uniformes sur l'intervalle [0, 1], ce qui est commode pour l'étude de chaînes de Markov via des méthodes de Monte-Carlo.

Probabilités de transition

Définition

Définition — Le nombre est nommé probabilité de transition de l'état à l'état en un pas, ou bien probabilité de transition de l'état à l'état s'il n'y a pas d'ambiguité. On note fréquemment ce nombre

p_{i,j} = \mathbb{P}\left(X_{1}=j\mid X_0=i\right).
  • La famille de nombres est nommée matrice de transition, noyau de transition, ou opérateur de transition de la chaîne de Markov.

Le vocabulaire matrice de transition est la plus utilisée, mais elle n'est appropriée, en toute rigueur, que quand, pour un entier Quand est fini, par exemple de cardinal on peut toujours numéroter les éléments de arbitrairement de 1 à ce qui règle le problème, mais imparfaitement, car cette renumérotation est contre-intuitive dans énormément d'exemples.

Modèle d'Ehrenfest : les deux chiens et leurs puces :

Deux chiens se partagent puces de la manière suivante : à chaque instant, une des puces est choisie au hasard et saute alors d'un chien à l'autre. L'état du dispositif est décrit par un élément où

x_{i} = 0\text{ ou }1\text{ selon que la puce n}ˆ{\circ}\ i\text{ est sur le 1er ou sur le 2eme chien.}

Alors possède éléments, mais les numéroter de 1 à serait malcommode pour suivre l'évolution du dispositif, qui consiste à choisir une des coordonnées de au hasard ainsi qu'à changer sa valeur. Si on veut comprendre le dispositif moins en détail (car on n'est pas capable de reconnaître une puce d'une autre), on peut se contenter d'étudier le nombre de puces sur le chien n°1, ce qui revient à choisir Ici encore, pour la compréhension, il serait dommage de renuméroter les états de 1 à Notons que pour cette nouvelle modélisation,

p_{k,k+1} = \tfrac{N-k}N\text{ et }p_{k,k-1} = \tfrac{k}N,

puisque, par exemple, le nombre de puces sur le dos du chien n°1 passe de k à k-1 si c'est une de ces k puces qui est choisie pour sauter, parmi les N puces présentes dans le "système". Ce modèle porte plus fréquemment le nom de "modèle des urnes d'Ehrenfest". Il a été introduit en 1907 par Tatiana et Paul Ehrenfest pour illustrer certains des «paradoxes» apparus dans les fondements de la mécanique statistique naissante, et pour modéliser le bruit rose. Le modèle des urnes d'Ehrenfest était reconnu par le mathématicien Mark Kac [1] comme «... certainement l'un des modèles les plus instructifs de toute la physique...»

Plutôt que de renuméroter les états à partir de 1, il est par conséquent plus ergonomique dans énormément de cas d'accepter des matrices finies ou illimitées dont les lignes et colonnes sont "numérotées" avec éléments de Le produit de deux telles "matrices", et, est alors défini particulièrement naturellement par

(AB)_{i,j} = \sum_{\ell\in E}a_{i,\ell}b_{\ell,j},

par ressemblance avec la formule plus classique du produit de deux matrices carrées de taille

(AB)_{i,j} = \sum_{k=1}ˆna_{i,k}b_{k,j}.

Propriétés

Proposition — La matrice de transition est stochastique : la somme des termes de n'importe quelle ligne de donne toujours 1.

\forall i\in E, \quad\sum_{j\in E}p_{i,j}=1.

Proposition —  La loi de la chaîne de Markov est caractérisée par le couple constitué de sa matrice de transition et de sa loi d'origine (la loi de)  : pour tout la loi jointe de est donnée par

\mathbb{P}\left(X_{0}=i_0,X_{1}=i_1,\ldots,X_{n-1}=i_{n-1},X_{n}=i_n\right)=\mathbb{P}\left(X_{0}=i_0\right)\ p_{i_{0},i_1}\,p_{i_{1},i_2}\,\ldots\,p_{i_{n-2},i_{n-1}}\,p_{i_{n-1},i_n}.

Quand on étudie une chaîne de Markov spécifique, sa matrice de transition est généralement bien définie et fixée tout au long de l'étude, mais la loi d'origine peut changer lors de l'étude et les notations doivent refléter la loi d'origine reconnue sur le moment : si à un moment de l'étude on considère une chaîne de Markov de loi d'origine définie par alors les probabilités sont notées et les espérances sont notées Surtout, si on dit que la chaîne de Markov part de les probabilités sont notées et les espérances sont notées

Puissances de la matrice de transition

Pour la probabilité de transition en pas, ne dépend pas de  :

Proposition — La matrice de transition en pas, est égale à la puissance -ème de la matrice de transition On note

pˆ{(k)}_{i,j}=\mathbb{P}\left(X_{n+k}=j\mid X_n=i\right),

et

Pˆk=\left(pˆ{(k)}_{i,j}\right)_{(i,j)\in Eˆ2}.

Par une simple application de la formule des probabilités totales, on en déduit les lois marginales de la chaîne de Markov.

Corollaire — La loi de est donnée par

\mathbb{P}\left(X_{n+k}=j\right)=\sum_{i\in E}\mathbb{P}\left(X_{n}=i\right)pˆ{(k)}_{i,j}.

En particulier,

\mathbb{P}\left(X_{n}=j\right)=\sum_{i\in E}\mathbb{P}\left(X_{0}=i\right)pˆ{(n)}_{i,j}.

En écriture matricielle, si la loi de est reconnue comme un vecteur-ligne avec cela se reformule en :

\mu_{n+k}=\mu_{n}Pˆk\quad\text{ et }\quad \mu_{n}=\mu_{0}Pˆn.

Classification des états

Graphe de la marche du cavalier sur l'échiquier (quart Sud-Ouest de l'échiquier).
Article détaillé : Graphe d'une chaîne de Markov et classification des états.

Pour, on dit que est accessible à partir de si et uniquement s'il existe tel que 0. \ " src="http ://upload. wikimedia. org/math/d/7/8/d78c5ffd26f0a00c6308b683886388d4. png" /> On note :

<img class=

La relation communiquer, notée est une relation d'équivalence. Lorsque on parle de classe en parlant des états d'une chaîne de Markov, c'est général aux classes d'équivalence pour la relation qu'on fait référence. Si l'ensemble des états communiquent, la chaîne de Markov est dite irréductible.

La relation être accessible, notée couvre aux classes d'équivalence : pour deux classes et, on a

\{C\leftarrow Cˆ{\prime}\}\quad\Leftrightarrow\quad\left\{\exists (i,j)\in C\times Cˆ{\prime},\qquad i\leftarrow j\right\}\quad\Leftrightarrow\quad\left\{\forall (i,j)\in C\times Cˆ{\prime},\qquad i\leftarrow j\right\}.

La relation est une relation d'ordre entre les classes d'équivalence.


Une classe est dite finale si elle ne conduit à aucune autre, i. e. si la classe est minimale pour la relation Sinon, elle est dite transitoire. L'appartenance à une classe finale ou transitoire a des conséquences sur les propriétés probabilistes d'un état de la chaîne de Markov, surtout sur son statut d'état récurrent ou d'état transient. Le nombre et la nature des classes finales dicte la structure de la totalité des probabilités stationnaires, qui résument de manière précise le comportement asymptotique de la chaîne de Markov, comme on peut le voir à la prochaine section et dans les deux exemples détaillés à la fin de cette page.

Soit

<img class=Probabilité stationnaire d'une chaîne de Markov.


La classification des états et leur période se lisent de manière simple sur le graphe de la chaîne de Markov. Cependant, si l'ensemble des éléments de la matrice de transition sont strictement positifs, la chaîne de Markov est irréductible et apériodique : dessiner le graphe de la chaîne de Markov est alors superflu.

Loi stationnaire

Définition

Il peut exister une ou plusieurs mesures sur l'espace d'états telles que :

 \pi = \pi\,P,

ou bien toujours

\forall j\in E,\qquad \pi_j = \sum_{i\in E}\pi_i\,p_{i,j}.

Une telle mesure est nommée une mesure stationnaire. Une mesure stationnaire est une fonction propre de la transposée de la matrice de transition, associée à la valeur propre 1. Elle est nommée probabilité stationnaire ou loi stationnaire si elle remplit les conditions supplémentaires :

  • \forall i\in E, \qquad \pi_i\ \ge\ 0,
  • \sum_{i\in E}\pi_i\ =\ 1.

Si la loi d'origine de la chaîne de Markov (i. e. la loi de) est une probabilité stationnaire alors pour tout la loi de est D'une façon plus générale, la chaîne de Markov est un processus stationnaire si et uniquement si sa loi d'origine est une probabilité stationnaire.

Existence et unicité

Article détaillé : Récurrence et transience d'une chaîne de Markov.

Dans le cas des chaînes de Markov à espace d'états discret, certaines propriétés du processus déterminent s'il existe ou non une probabilité stationnaire, et si elle est unique ou non :

  • une chaîne de Markov est irréductible si tout état est accessible à partir de n'importe quel autre état ;
  • un état est récurrent positif si l'espérance du temps de premier retour en cet état, partant de cet état, est finie.

Si une chaîne de Markov possède au moins un état récurrent positif, alors il existe une probabilité stationnaire. S'il existe une probabilité stationnaire telle que 0\ " src="http ://upload. wikimedia. org/math/2/8/6/286dd41952dab6437217b2255705b62d. png" />, alors l'état est récurrent positif, et réciproquement.

Théorème — Si une chaîne de Markov possède une seule classe finale alors il existe au plus une probabilité stationnaire. On a alors équivalence entre les 3 propositions :

  • il existe une unique probabilité stationnaire, notée
  • il existe un état récurrent positif,
  • tous les états de la classe finale sont récurrents positifs.

On a de plus l'équivalence

<img class=Loi forte des grands nombres et ergodicité

Dans le cas d'une chaîne de Markov irréductible et récurrente positive, la loi forte des grands nombres est en vigueur : la moyenne d'une fonction sur les instances de la chaîne de Markov est égale à sa moyenne selon sa probabilité stationnaire. Plus exactement, sous l'hypothèse

\sum_{i\in E} |f(i)|\,\pi_i\ < +\infty,

on a presque sûrement :

 \lim_{n}\; \frac{1}{n} \; \sum_{k=0}ˆ{n-1} f(X_k)
  \ =\ \sum_{i\in E} f(i)\,\pi_i\ =\ \pi f.

La moyenne de la valeur des instances est par conséquent, sur le long terme, égale à l'espérance suivant la probabilité stationnaire. Surtout, cette équivalence sur les moyennes s'applique si est la fonction indicatrice d'un sous-ensemble de l'espace des états :

 \lim_{n}\; \frac{1}{n} \; \sum_{k=0}ˆ{n-1} \chi_A(X_k)\ 
=\ \sum_{i\in A}\ \pi_i\ =\ \pi(A).

Cela permet d'approcher la probabilité stationnaire par la distribution empirique (qui est un histogramme construit à partir d'une séquence spécifique), comme par exemple dans le cas de la marche aléatoire avec barrière.

En particulier, si le processus est construit en prenant la probabilité stationnaire comme loi d'origine, le shift défini par

 x=(x_0,x_1,x_2,\dots)\in Eˆ{\mathbb{N}}\quad\rightarrow\quad \theta\,x=(x_1,x_2,x_3,\dots)

préserve la mesure, ce qui fait de la chaîne de Markov un dispositif dynamique. La loi forte des grands nombres entraine tandis que la chaîne de Markov est un dispositif dynamique ergodique. L'ergodicité est à la fois plus forte que la loi forte des grands nombres car on peut en déduire, par exemple, que a pour limite presque sûre mais elle est aussi plus faible car elle réclame habituellement la stationnarité de la chaîne de Markov, ce qui n'est pas le cas de la loi forte des grands nombres.

Convergence vers la loi stationnaire

Si la chaîne de Markov est irréductible, récurrente positive et apériodique, alors converge vers une matrice dont chaque ligne est l'unique distribution stationnaire Surtout, la loi de converge vers indépendamment de la loi d'origine Dans le cas d'un espace d'état fini, cela se prouve par le théorème de Perron-Frobenius. Notons qu'il est naturel que la suite définie par récurrence par la relation ait, peut-être, pour limite un point fixe de cette transformation, i. e. une solution de l'équation

Chaînes de Markov à espace d'états fini

Si une chaîne de Markov est irréductible et si son espace d'états est fini, tous ses états sont récurrents positifs. La loi forte des grands nombres est alors en vigueur.

D'une façon plus générale, l'ensemble des éléments d'une classe finale finie sont récurrents positifs, que l'espace d'états soit fini ou bien illimité dénombrable.

Notation

Dans les formules qui précèdent, l'élément (i, j) est la probabilité de la transition de i à j. La somme des éléments d'une ligne vaut toujours 1 et la distribution stationnaire est donnée par le vecteur propre gauche de la matrice de transition.

On rencontre quelquefois des matrices de transition dans lesquelles le terme (i, j) est la probabilité de transition de j vers i, auquel cas la matrice de transition est simplement la transposée de celle décrite ici. La somme des éléments d'une colonne vaut alors 1. Qui plus est , la distribution stationnaire du dispositif est alors donnée par le vecteur propre droit de la matrice de transition, au lieu du vecteur propre gauche.

Exemple : Doudou le hamster

Doudou, le hamster paresseux, ne connaît que trois lieux dans sa cage : les copeaux où il dort, la mangeoire où il mange et la roue où il fait de l'exercice. Ses journées sont assez identiques les unes aux autres, et son activité se représente facilement par une chaîne de Markov. L'ensemble des minutes, il peut soit changer d'activité, soit continuer celle qu'il était en train de faire. L'appellation processus sans mémoire n'est absolument pas exagérée pour parler de Doudou.

  • Lorsqu'il dort, il a 9 chances sur 10 de ne pas se réveiller la minute suivante.
  • Lorsqu'il se réveille, il y a 1 chance sur 2 qu'il aille manger et 1 chance sur 2 qu'il parte faire de l'exercice.
  • Le repas ne dure qu'une minute, après il fait autre chose.
  • Après avoir mangé, il y a 3 chances sur 10 qu'il parte courir dans sa roue, mais en particulier 7 chances sur 10 qu'il retourne dormir.
  • Courir est fatigant ; il y a 8 chances sur 10 qu'il retourne dormir au bout d'une minute. Sinon il continue en oubliant qu'il est déjà légèrement fatigué.

Diagrammes

Les diagrammes peuvent montrer l'ensemble des flèches, chacune représentant une probabilité de transition. Cependant, c'est plus lisible si :

  • on ne dessine pas les flèches de probabilité zéro (transition impossible)  ;
  • on ne dessine pas les boucles (flèche d'un état vers lui-même) . Cependant elles existent ; leur probabilité est sous-entendue car on sait que la somme des probabilités des flèches partant de chaque état doit être égale à 1.

Matrice de transition

La matrice de transition de ce dispositif est la suivante (les lignes et les colonnes correspondent dans l'ordre aux états représentés sur le graphe par copeaux, mangeoire, roue)  :

 P =\begin{bmatrix}
0,9 & 0,05 & 0,05 \\
0,7 & 0 & 0,3 \\
0,8 & 0 & 0,2 \\
\end{bmatrix}

Prévisions

Prenons l'hypothèse que Doudou dort lors de la première minute de l'étude.

  \mathbf{x}ˆ{(0)} = \begin{bmatrix}
        1 & 0 & 0
    \end{bmatrix}

Au bout d'une minute, on peut prédire :


    \mathbf{x}ˆ{(1)} = \mathbf{x}ˆ{(0)} P  = 
\begin{bmatrix}
        1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0,9 & 0,05 & 0,05 \\
0,7 & 0 & 0,3 \\
0,8 & 0 & 0,2 \\
\end{bmatrix}

= \begin{bmatrix}
        0,9 & 0,05 & 0,05
  \end{bmatrix}

Ainsi, après une minute, on a 90 % de chances que Doudou dorme toujours, 5 % qu'il mange et 5 % qu'il coure.


    \mathbf{x}ˆ{(2)} = \mathbf{x}ˆ{(1)} P  = \mathbf{x}ˆ{(0)} Pˆ2  = 
\begin{bmatrix}
        1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0,9 & 0,05 & 0,05 \\
0,7 & 0 & 0,3 \\
0,8 & 0 & 0,2 \\
\end{bmatrix}ˆ2

    = \begin{bmatrix}
        0,885 & 0,045 & 0,07
    \end{bmatrix}

Après 2 minutes, il y a 4, 5 % de chances que le hamster mange.

Généralement, pour n minutes :


    \mathbf{x}ˆ{(n)} = \mathbf{x}ˆ{(n-1)} P

    \mathbf{x}ˆ{(n)} =  \mathbf{x}ˆ{(0)} Pˆn

La théorie montre qu'au bout d'un certain temps, la loi de probabilité est indépendante de la loi d'origine. Notons la q :


    \mathbf{q} = \lim_{n \to \infty} \mathbf{x}ˆ{(n)}

On obtient la convergence si et uniquement si la chaîne est apériodique et irréductible. C'est le cas dans notre exemple, on peut par conséquent écrire :


\begin{align}
     P  & =   \begin{bmatrix}
                0,9 & 0,05 & 0,05 \\
                0,7 & 0 & 0,3 \\
                0,8 & 0 & 0,2 \\
                \end{bmatrix}
\\
         \mathbf{q} P   & =  \mathbf{q} \qquad \mbox{(} \mathbf{q} \mbox{ est la loi invariante par rapport a } P \mbox{.)}
\\
        & =  \mathbf{q} I
\\
        \mathbf{q} (I - P) & =  \mathbf{0}
\\
        & =  \mathbf{q} \left( \begin{bmatrix}
            1 & 0 & 0 \\
            0 & 1 & 0 \\
            0 & 0 & 1 \\
        \end{bmatrix}
        - \begin{bmatrix}
                0,9 & 0,05 & 0,05 \\
                0,7 & 0 & 0,3 \\
                0,8 & 0 & 0,2 \\
           \end{bmatrix} \right) 
\\
       & =   \mathbf{q} \begin{bmatrix}
            0,1 & -0,05 & -0,05 \\
            -0,7 & 1 & -0,3 \\
            -0,8 & 0 & 0,8 \\
        \end{bmatrix}
\\
&= \begin{bmatrix}
q_1 & q_2 & q_3
\end{bmatrix}\begin{bmatrix}
            0,1 & -0,05 & -0,05 \\
            -0,7 & 1 & -0,3 \\
            -0,8 & 0 & 0,8 \\
\end{bmatrix}
\\
&=
\begin{bmatrix}
0 & 0 & 0
\end{bmatrix}
\end{align}

Sachant que q1 + q2 + q3 = 1, on obtient :

\begin{bmatrix}
q_1 & q_2 & q_3
\end{bmatrix} 
= \begin{bmatrix}
0,884 & 0,0442 & 0,0718
\end{bmatrix}

Doudou passe 88, 4 % de son temps à dormir !

Illustration de l'impact du modèle

L'exemple qui suit a pour but de montrer l'importance de la modélisation du dispositif. Une bonne modélisation sert à répondre à des questions complexes avec des calculs simples.

On étudie une civilisation (fictive) constituée de plusieurs classes sociales, et dans laquelle les individus peuvent passer d'une classe à l'autre. Chaque étape représentera un an. On considérera une lignée plutôt qu'un individu, pour éviter d'obtenir des citoyens bicentenaires. Les différents statuts sociaux sont au nombre de quatre :

  • esclave ;
  • libre ;
  • citoyen ;
  • haut-fonctionnaire.

Dans cette société :

  • les esclaves peuvent rester esclaves ou devenir des hommes libres (en achetant leur liberté ou en étant affranchis généreusement par leur maître)  ;
  • les hommes libres peuvent rester libres ou bien vendre leur liberté (pour payer leurs dettes, etc. ) ou encore devenir citoyens (ici encore par mérite ou en achetant le titre de citoyen)  ;
  • les citoyens sont citoyens à vie et transmettent leur citoyenneté à leur lignée (on pourrait croire que le nombre de citoyens tend à augmenter et qu'au bout d'un certain temps, tous sont citoyens mais historiquement, dans les civilisations qui suivaient ce schéma, les citoyens sont décimés par les guerres et de nouveaux esclaves arrivent régulièrement de l'étranger). Ils peuvent aussi se porter candidats lors des élections annuelles pour devenir hauts-fonctionnaires (magistrats). Au terme de leur mandat, ils peuvent être réélus ou redevenir de simples citoyens.

Pour compliquer légèrement l'exemple et montrer ainsi l'étendue des applications des chaînes de Markov, nous considérerons que les fonctionnaires sont élus pour plusieurs années. Donc, l'avenir d'un individu fonctionnaire dépend du temps depuis lequel il est fonctionnaire. Nous sommes par conséquent dans le cas d'une chaîne de Markov non homogène. Heureusement, nous pouvons facilement nous ramener à une chaîne homogène. En effet, il suffit de rajouter un état artificiel pour chaque année du mandat. Au lieu d'avoir un état 4 : Fonctionnaire, nous aurons un état :

  • 4 : Fonctionnaire en début de mandat ;
  • 5 : Fonctionnaire en seconde année de mandat ;
  • etc.

Les probabilités reliant deux états artificiels consécutifs (troisième et quatrième année par exemple) sont de valeur 1 car on considère que tout mandat commencé se termine (on pourrait modéliser le contraire en changeant la valeur de ces probabilités). Fixons la durée des mandats à deux ans, le contingent des fonctionnaires étant renouvelable par moitié chaque année. On a alors le graphe suivant :

Graphe2.jpeg

Pour modéliser des élections qui ne seraient pas annuelles, il faudrait de même ajouter des états fictifs (année d'élection, un an depuis la dernière élection, etc. ).

La matrice P s'écrit alors :


\mathbf{P}=\begin{bmatrix}
	\frac{97}{98} & \frac{1}{98} & 0 & 0 & 0 \\
	\frac{2}{73} & \frac{65}{73} & \frac{6}{73} & 0 & 0 \\
	0 & 0 & \frac{12}{13} & \frac{1}{13} & 0 \\
	0 & 0 & 0 & 0 & 1 \\
	0 & 0 & \frac{7}{8} & \frac{1}{8} & 0 		
\end{bmatrix}

Comme cela est expliqué plus haut, Pn donne les probabilités de transition en n étapes. Par conséquent  pˆ{n}_{ij} est la probabilité d'être dans l'état j au bout de n années pour une lignée partie de la classe sociale i. Pour savoir ce que devient un esclave au bout de n ans, il suffit par conséquent d'écrire :


\begin{bmatrix}1 & 0 & 0 & 0 & 0 \end{bmatrix} \times \mathbf Pˆ{(n)} = \begin{bmatrix}
p_1ˆ{(n)} \\
p_2ˆ{(n)} \\
p_3ˆ{(n)}  \\
p_4ˆ{(n)}  \\
p_5ˆ{(n)} 
\end{bmatrix}

p_iˆ{n} est la probabilité d'être dans la classe sociale i au bout de n années sachant que la lignée étudiée est partie de l'état d'esclave.

Si on connaît les effectifs de chaque classe sociale à l'an 0, il suffit alors de calculer :

\frac1\mathrm{lign\acute ees} \times \begin{bmatrix}\rm esclaves&\rm libres &\rm citoyens &\rm \acute elus_1 &\rm \acute elus_2 \end{bmatrix} \times \mathbf Pˆ{n} = Y

On obtient ainsi la répartition de la population dans les différentes classes sociales (au bout de n années). En multipliant ce vecteur Y par l'effectif total de la population, on obtient les effectifs de chaque classe au bout de n années.

Posons-nous désormais la question suivante : «Au bout de n années, combien de lignées auront déjà eu un haut fonctionnaire ayant terminé son mandat ?»

La réponse est différente du nombre de mandats effectués en n années car il y a possibilité d'être réélu. Répondre à cette question semble complexe (encore faudrait-il que ce soit envisageable). En réalité, il suffit de changer la modélisation du problème. Passons par conséquent à une nouvelle modélisation pour répondre à cette question. (Par contre, elle ne permet pas de répondre aux questions précédentes d'où la présentation des deux modèles. )

Il suffit de modifier ainsi le graphe :

Graphe4.JPG

On ajoute un sommet absorbant car une fois qu'une lignée a fini un mandat, on ne tient plus compte d'elle.

Si certains lecteurs font preuve d'esprit critique, ils diront peut-être que le modèle est faux car les lignées comportant un élu ne participent plus aux élections. Il n'en est rien. En effet, le nombre d'élus est proportionnel au nombre de citoyens. Ne pas réinjecter les anciens hauts-fonctionnaires parmi les candidats ne change par conséquent en rien la probabilité pour un citoyen d'être élu car, la population des citoyens étant plus restreinte, le nombre de postes offerts l'est aussi. Ce modèle sert à répondre avec exactitude à la question posée.

On a par conséquent une nouvelle matrice de transition :


\mathbf{Q}=
\begin{bmatrix}
	\frac{97}{98} & \frac{1}{98} & 0 & 0 & 0 & 0 \\
	\frac{2}{73} & \frac{65}{73} & \frac{6}{73} & 0 & 0 & 0 \\
	0 & 0 & \frac{12}{13} & \frac{1}{13} & 0 & 0 \\
	0 & 0 & 0 & 0 & 1 & 0\\
	0 & 0 & 0 & 0 & 0 & 1 \\	
	0 & 0 & 0 & 0 & 0 & 1 	
\end{bmatrix}

En faisant les mêmes calculs qu'aux questions précédentes on obtient en dernière ligne du vecteur solution le pourcentage de lignées ayant accompli au moins un mandat ou bien l'effectif (si on multiplie par l'effectif total de la population). C'est à dire, modéliser à nouveau le problème sert à répondre à la question qui semblait si compliquée par un simple calcul de puissances d'une matrice.

Applications

  • Les dispositifs Markoviens sont particulièrement présents en physique spécifiquement en physique statistique. D'une façon plus générale l'hypothèse markovienne est fréquemment invoquée quand des probabilités sont utilisées pour modéliser l'état d'un dispositif, en supposant cependant que l'état futur du dispositif peut être déduit du passé avec un historique assez faible.
  • Le célèbre article de 1948 de Claude Shannon, A mathematical theory of communication, qui fonde la théorie de l'information, débute en introduisant la notion d'entropie à partir d'une modélisation Markovienne de la langue anglaise. Il montre ainsi le degré de prédictibilité de la langue anglaise, pourvu d'un simple modèle d'ordre 1. Quoique simples, de tels modèles permettent de bien représenter les propriétés statistiques des dispositifs et de réaliser des prédictions efficaces sans décrire la structure complète des dispositifs.
  • En compression, la modélisation markovienne permet la réalisation de techniques de codage entropique particulièrement efficaces, comme le codage arithmétique. De très nombreux algorithmes en reconnaissance des formes ou en intelligence artificielle comme par exemple l'algorithme de Viterbi, utilisé dans la grande majorité des dispositifs de téléphonie mobile pour la correction d'erreurs, font l'hypothèse d'un processus markovien sous-jacent.
  • L'indice de popularité d'une page Web (PageRank) tel qu'il est utilisé par Google est défini par une chaîne de Markov. Il est défini par la probabilité d'être dans cette page à partir d'un état quelconque de la chaine de Markov représentant le Web. Si N est le nombre de pages Web connues, et une page i a ki liens, alors sa probabilité de transition vers une page liée (vers laquelle elle pointe) est p_iˆl= \tfrac{1-q}{k_i}+\tfrac qN et p_iˆ{nl}=\tfrac qN pour l'ensemble des autres (pages non liées). Notons qu'on a bien k_i p_iˆl+(N-k_i) p_iˆ{nl}=1. Le paramètre q vaut à peu près 0, 15.
  • Les chaînes de Markov sont un outil essentiel pour modéliser les processus en théorie des files d'attente et en statistiques.
  • Les chaînes de Markov fondent les dispositifs de Bonus/Malus mis au point par les actuaires des sociétés d'assurances automobiles (la probabilité d'avoir n accidents au cours de l'année t étant conditionnée par le nombre d'accidents en t-1)
  • Les chaînes de Markov sont aussi utilisées en bioinformatique pour modéliser les relations entre symboles successifs d'une même séquence (de nucléotides par exemple), en allant au-delà du modèle polynomial. Les modèles markoviens cachés ont aussi diverses utilisations, telles que la segmentation (définition de frontières de régions au sein de séquences de gènes ou de protéines dont les propriétés chimiques fluctuent), l'alignement multiple, la prédiction de fonction, ou la découverte de gènes (les modèles markoviens cachés sont plus «flexibles» que les définitions strictes de type codon start + multiples codons + codons stop et ils sont par conséquent plus adaptés pour les eucaryotes (à cause de la présence d'introns dans le génome de ceux-ci) ou pour la découverte de pseudo-gènes).

Voir aussi

Liens externes

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Cha%C3%AEne_de_Markov.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu