WikiMath
This is Wordpress NewsPaper Theme converted to PmWiki
Chaines De Markov
Généralités
Présentation
Généralement, un processus stochastique est une suite d'expériences dont le résultat dépend du hasard.
Ici, nous admettrons qu'en certains temps 0, 1, 2, ..., t, nous observons un système. Celui-ci peut se trouver dans l'un des états d'une collection finie d'états possibles. L'observation du système est ainsi considérée comme une expérience dont le résultat (aléatoire) est l'état dans lequel se trouve le système.
Nous supposons que nous connaissons pour chaque paire d'états $i$ et $j$, et pour chaque instant $t$, la probabilité $p_{ij}(t)$ que le processus soit dans l'état $j$ à l'instant $t+1$ étant donné qu'il se trouve dans l'état $i$ à l'instant $t$. De plus, la probabilité $p_{ij}(t)$ sera supposée ne pas dépendre de $t$.
Définitions
Définition (Chaîne de Markov)
Un tel processus est appelé chaîne de Markov (à temps discret et avec un ensemble fini d'états), du nom de son inventeur Andrei Andreyevich Markov (1856-1922).
Avec ces hypothèses, nous pouvons décrire le système en donnant l'ensemble ${u_1, ..., u_m}$ des états $u_i$ possibles et une matrice $P$ de dimensions $m \times m$ dont le terme $p_{ij}$ est la probabilité que le processus soit dans l'état $j$ à l'instant $t+1$ étant donné qu'il se trouve dans l'état $i$ à l'instant $t$, pour tout t.
Définition (Matrice de transition)
P est appelée matrice de transition du système.
On représente généralement P par un graphe orienté G dont les sommets correspondent aux m états et les arcs aux couples ordonnés d'états (i,j) tels que pij>0.
Exemple
Pour représenter le passage d'une molécule de phosphore dans un écosystème, nous considérerons quatre états possibles :
- la molécule est dans le sol,
- la molécule est dans l'herbe,
- la molécule a été absorbée par du bétail,
- la molécule est sortie de l'écosystème.
La matrice de transition est la suivante :
$P =\left(\begin{array}{cccc} 3/5 & 3/10 & 0 & 1/10 \\ 1/10 & 2/5 & 1/2 & 0 \\ 3/4 & 0 & 1/5 & 1/20 \\0 & 0 & 0 & 1 \\\end{array}\right)$
Remarquez que la somme de chaque ligne vaut 1. Cette matrice correspond au graphe ci-dessous :
Propriétés
Théorème
La probabilité $p_{ij}(t)$ que le système soit dans l'état $j$ au temps $t$ sachant qu'il était dans l'état $i$ au temps 0 est donné par $(P^t)_{i,j}$ (le terme $i,j$ de la $t$-ième puissance de $P$).
Si on ne connaît pas l'état initial, on peut donner un vecteur de probabilité $p(0) = (p_1(0), ..., p_m(0))$ où $p_i(0)$ est la probabilité que le système se trouve dans l'état $i$ au temps 0. Si $p(t)$ est le vecteur donnant les probabilités d'occupation des états au temps $t$ (autrement dit la distribution), nous avons :
Théorème
$p(t) = p(0) P^t$
Exercice
Exercice : Un individu vit dans un milieu où il est susceptible d'attraper une maladie par piqûre d'insecte. Il peut être dans l'un des trois états suivants: immunisé ($I$), malade ($M$), non malade et non immunisé ($S$). D'un mois à l'autre, son état peut changer selon les règles suivantes:
- étant immunisé, il peut le rester avec une probabilité 0,9 ou passer à l'état $S$ avec une probabilié 0,1;
- étant dans l'état $S$, il peut le rester avec une probabilité 0,5 ou passer à l'état $M$ avec une probabilité 0,5;
- étant malade, il peut le rester avec une probabilité 0,2 ou passer à l'état $I$ avec une probabilité 0,8.
Tracez un graphe probabiliste pour décrire cette situation et écrivez la matrice de transition. Calculez l'état de probabilité de l'individu au bout de trois mois, de six mois, d'un an, de deux ans, pour chacune des situations suivantes :
- au départ, il est immunisé ($I$);
- au départ, il est non malade et non immunisé ($S$);
- au départ, il est malade ($M$).
Pouvez-vous donner des éléments sur la proportion d'individus malades dans la population étudiée?
Distribution limite
Présentation
On constate souvent que la distribution $p(t)$ converge vers une distribution limite $p$ si $t \rightarrow \infty$ .
Définition :
Si tel est le cas, on dit que cette dernière définit un régime permanent du processus stochastique.
Remarque : Le régime permanent n'est pas influencé par le choix de la distribution initiale.
Existence d'une distribution limite
Théorème
Si la matrice de transition $P$ est telle qu'une au moins de ses puissances n'a que des termes strictement positifs, alors $p(t) \longrightarrow p$ quelle que soit la distribution initiale $p(0)$ et $P^t \longrightarrow P^*$ lorsque $t\longrightarrow \infty$.
$p$ est un vecteur de probabilité strictement positif et $P*$ une matrice dont toutes les lignes sont identiques au vecteur limite $p$. En plus, $pP*=p$.
Remarque : La démonstration de cette condition d'existence dépasse le cadre de ce cours.
Exercices
Exercice : Soit la matrice stochastique $P = \left(\begin{array}{ccc}0,5 & 0,5 & 0\\0,5 & 0 & 0,5 \\0 & 1 & 0 \\\end{array}\right)$
Montrez que la chaîne de Markov définie par $P$ converge et calculez la distribution limite.
Exercice : Soit la matrice stochastique $P =\left(\begin{array}{cccc} 3/5 & 3/10 & 0 & 1/10 \\ 1/10 & 2/5 & 1/2 & 0 \\ 3/4 & 0 & 1/5 & 1/20 \\0 & 0 & 0 & 1 \\\end{array}\right)$
Montrez que la chaîne de Markov définie par P converge et calculez la distribution limite.
Exercice : Un service de météo a constaté après de longues années que le temps qu'il fera demain dépend essentiellement du temps qu'il faisait hier et du temps qu'il fait aujourd'hui. Les probabilités de transition ont été établies ainsi :
| $Hier $ | $ Aujourd'hui $ | $ Beau demain $ | $ Mauvais demain$ |
| $Beau $ | $ Beau $ | $ 0.8 $ | $ 0.2 $ |
| $Beau $ | $ Mauvais $ | $ 0.4 $ | $ 0.6$ |
| $Mauvais $ | $ Beau $ | $ 0.6 $ | $ 0.4 $ |
| $Mauvais $ | $ Mauvais $ | $ 0.1 $ | $ 0.9$ |
- Modélisez ce processus à l'aide d'une chaîne de Markov.
- Calculez le nombre moyen de jours de beau temps par année.
Exercice : Un ivrogne se déplace dans les quatre bistrots d'un village, d'une manière bien personnelle : en sortant d'un bistrot, il lance une pièce de monnaie pour savoir dans lequel des deux autres bistrots les plus proches il entrera.
Ces quatre bistrots forment les sommets d'un carré.
- Modélisez ce processus à l'aide d'une chaîne de Markov.
- Montrez que cette chaîne de Markov n'a pas de distribution limite.
Chaîne absorbante
Généralités
Définitions
Définition (État absorbant)
Un état absorbant est un état que l'on ne quitte plus lorsqu'on y pénètre.
Remarque : Autrement dit, l'état $j$ est absorbant si $p_{jj}=1$.
Définition (Chaîne de Markov absorbante)
Une chaîne de Markov est absorbante si et seulement si:
- il y a au moins un état absorbant
- de tout état non absorbant, on peut atteindre un état absorbant.
Exemple : Par exemple, l'état 4 ci-dessous...
...est un état absorbant. Comme on peut atteindre cet état depuis tous les autres, la chaîne de Markov est absorbante.
Propriété
Théorème
Pour toute chaîne de Markov absorbante et pour tout état de départ, la probabilité de se trouver dans un état absorbant au temps $t$ tend vers 1 lorsque $t$ tend vers l'infini.
Délais d'absorption et probabilité d'absorption
Présentation
Lorsque l'on a affaire à une chaîne de Markov absorbante, on est généralement intéressé par les deux questions suivantes :
- Combien de temps faudra-t-il en moyenne pour arriver dans un état absorbant, étant donné son état initial?
- S'il existe plusieurs états absorbants, quelle est la probabilité de tomber dans un état absorbant donné?
Forme canonique de P
Si une chaîne de Markov est absorbante, on placera au début les états absorbants; on aura alors une matrice de transition de la forme :
$\left(\begin{array}{c|c}I & O \\ R & Q \\& \\\end{array}\right)$
$I$ est une matrice unité et 0 une matrice de 0.
Dans l'exemple du phospore vu précédemment,
nous avons (l'ordre des états est 4-1-2-3) :
$P =\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\ 1/10 & 3/5 & 3/10 & 0 \\ 0 & 1/10 & 2/5 & 1/2 \\ 1/20 & 3/4 & 0 & 1/5 \\\end{array}\right)$
Matrice fondamentale
Définition (Matrice fondamentale de la chaîne absorbante)
La matrice $N = (I-Q)^{-1}$ est appelée la matrice fondamentale de la chaîne absorbante.
Résultats
Théorème
Le nombre moyen $e_{ij}$ de passages à l'état $j$ (non absorbant) avant l'absorption quand on part de l'état $i$ (non absorbant) est donnée par $e_{ij}= (N)_{ij}$.
Théorème
Le nombre moyen d'étapes avant absorption sachant que l'on part de l'état $i$ (non absorbant) est la somme des termes de la $i$-ème ligne de $N$.
Exemple : Toujours dans l'exemple du phosphore, on a:
$Q =\left(\begin{array}{ccc}\frac{3}{5} & \frac{3}{10} & 0\\\frac{1}{10} & \frac{2}{5} & \frac{1}{2}\\\frac{3}{4} & 0 & \frac{1}{5}\end{array} \right), I-Q = \left(\begin{array}{ccc}\frac{2}{5} & \frac{-3}{10} & 0\\ \frac{1}{10} & \frac{3}{5} & -\frac{1}{2}\\ \frac{3}{4} & 0 & \frac{4}{5}\end{array} \right), \textrm{ d'où } N = (I-Q)-1 =\left(\begin{array}{ccc}\frac{320}{37} & \frac{160}{37} & \frac{100}{37}\\\frac{910}{111} & \frac{640}{111} & \frac{400}{111}\\\frac{300}{37} & \frac{150}{37} & \frac{140}{37}\end{array} \right)$
D'où le nombre moyen d'étapes avant absorption en partant de l'état 1: (320 + 160 + 100) / 37 = 15.67
Théorème
Dans une chaîne de Markov absorbante avec $P$ mise sous forme canonique, le terme $b_{ij}$ de la matrice $B = NR$ est la probabilité d'absorption par l'état absorbant $j$ sachant que l'on part de l'état $i$.
Exemple : Dans l'exemple du phosphore, on a:
$R =\left( \begin{array}{c}\frac{1}{10}\\0\\\frac{1}{20}\end{array}\right) \textrm{ d'où } B = N R = \left(\begin{array}{ccc}\frac{320}{37} & \frac{160}{37} & \frac{100}{37}\\\frac{910}{111} & \frac{640}{111} & \frac{400}{111}\\\frac{300}{37} & \frac{150}{37} & \frac{140}{37}\end{array} \right) \left( \begin{array}{c}\frac{1}{10}\\0\\\frac{1}{20}\end{array}\right) = \left( \begin{array}{c}1\\1\\1\end{array}\right)$ La probabilité d'être absorbé par l'unique état absorbant est 1 quel que soit l'état initial!
Exercices
Exercice : Considérons un joueur qui possède 2 francs initialement. À chaque étape du jeu il peut gagner 1 franc avec probabilité p ou perdre 1 franc avec probabilité 1-p. Il s'arrête lorsqu'il a gagné 4 francs ou lorsqu'il a tout perdu.
- Représentez cette expérience par une chaîne de Markov.
- Avec p = 1/3, calculez la probabilité de la ruine du joueur.
- Avec p = 1/3, calculez la longueur moyenne d'une partie.
Exercice : Monsieur X se rend au Salon du Livre de Rigoleville dans l'espoir de trouver enfin un exemplaire du livre de Stendhal Le Rose et le Vert. Le Salon compte cinq stands et les organisateurs se sont amusés aux cours des années précédentes à construire la matrice des probabilités de transition des visteurs d'un stand à un autre:
| $de \ à $ | $ Stand 1 $ | $ Stand 2 $ | $ Stand 3 $ | $ Stand 4 $ | $ Stand 5$ |
| $Stand 1 $ | $ 0 $ | $ 0,8 $ | $ 0 $ | $ 0 $ | $ 0,2$ |
| $Stand 2 $ | $ 0,2 $ | $ 0 $ | $ 0,5 $ | $ 0,3 $ | $ 0$ |
| $Stand 3 $ | $ 0 $ | $ 0 $ | $ 0 $ | $ 0,6 $ | $ 0,4$ |
| $Stand 4 $ | $ 0,9 $ | $ 0 $ | $ 0,1 $ | $ 0 $ | $ 0$ |
| $Stand 5 $ | $ 0,8 $ | $ 0 $ | $ 0 $ | $ 0,2 $ | $ 0$ |
Sachant que seuls les stands 4 et 5 disposent du livre recherché et que Monsieur X commence par visiter le stand 1, quelle est la probabilité qu'il achète son livre au stand 4 plutôt qu'au stand 5 (Monsieur X achètera le premier exemplaire qu'il trouvera)?
Exercice : Considérons une série de jets d'une pièce de monnaie normale. On notera P pour pile et F pour face.
- Quelle est la probabilité d'obtenir une séquence PFP avant une séquence PPP?
- Quel est le nombre de jets nécessaires en moyenne pour réaliser l'une des deux séquences PFP et PPP?
Exercice : [La parade nuptiale des bourdons] Une séance d'accouplement peut se décomposer en 7 phases:
- Départ (D)
- mise en contact des bourdons mâle et des reines.
- Approche (App)
- un mâle se dirige vers la reine. Il s'approche à courte distance. Il est le comportement le plus fréquent et souvent suivi d'une récidive.
- Inspection de la femelle (IF)
- le mâle suit la reine avec ses antennes tendues vers elle. Il inspecte souvent la reine au niveau de la tête (région où se trouvent les glandes produisant les phéromones sexuelles), mais parfois au niveau de l'abdomen.
- Tentative d'accouplement (T)
- le mâle s'approche de la reine, il s'accroche à elle. Il frotte de ses pattes antérieures l'extrémité de l'abdomen de la femelle. Il sort ses génitalias (appareil reproducteur) et tente de pénétrer la reine.
- Accouplement (Acc)
- lors de l'accouplement, le comportement du mâle se caractérise par des mouvements de battements des pattes sur l'extrémité de l'abdomen de la reine.
- Sortie par abandon du mâle (SA)
- lors de la séquence de 15 minutes, le bourdon mâle peut adopter un comportement indifférent vis-à-vis de la reine; il sort de la parade nuptiale et n'y revient jamais.
- Sortie pour dépassement du temps (ST)
- l'observation est limitée à 15 minutes. Après cette durée, la probabilité d'accouplement peut être considérée comme presque nulle.
Voici les statistiques obtenues pour 78 séances d'accouplement en laboratoire : par exemple App suivi de T = 202...
| $ App $ | $ T $ | $ IF $ | $ Acc $ | $ ST $ | $ SA $ | $ Total $ | |
| $D $ | $ 78 $ | $ 0 $ | $ 0 $ | $ 0 $ | $ 0 $ | $ 0 $ | $ 78$ |
| $App $ | $ 614 $ | $ 202 $ | $ 87 $ | $ 0 $ | $ 16 $ | $ 8 $ | $ 927$ |
| $IF $ | $ 83 $ | $ 0 $ | $ 0 $ | $ 0 $ | $ 3 $ | $ 1 $ | $ 87$ |
| $T $ | $ 152 $ | $ 0 $ | $ 0 $ | $ 35 $ | $ 7 $ | $ 8 $ | $ 202$ |
- Dessinez le graphe de transitions d'une parade nuptiale de bourdons.
- Calculez les probabilités de transition d'un état à un autre et ajoutez-les au graphe.
- Donnez la matrice correspondante de la chaîne de Markov.
- Adaptez votre programme simulant une chaîne de Markov (voir exercice 1 sur l'introduction aux chaînes de Markov) à la situation présente. Utilisez ce programme pour simuler une parade nuptiale de bourdons.
- Cette chaîne de Markov est une chaîne absorbante. Quel est le nombre moyen d'étapes avant absorption? Trouvez le résultat théoriquement et par simulation.