modif algo euclide

[cours-maths-dis.git] / graphes / Markov.tex

\section{Généralités}

\subsection{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$.

\subsection{Définitions}

\begin{Def}[Chaîne de Markov]
Un tel processus est appelé \emph{chaîne de Markov}\index{chaîne de Markov} (à temps discret et avec un ensemble fini d'états), du nom de son inventeur Andrei Andreyevich Markov (1856-1922).
\end{Def}

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.

\begin{Def}[Matrice de transition]
P est appelée \emph{matrice de transition}\index{matrice!de transition} du système.
\end{Def}

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.

\subsection{Exemple}

Pour représenter le passage d'une molécule de phosphore dans un écosystème, nous considérerons quatre états possibles :
\begin{enumerate}
\item la molécule est dans le sol,
\item la molécule est dans l'herbe,
\item la molécule a été absorbée par du bétail,
\item la molécule est sortie de l'écosystème. 
\end{enumerate}

La matrice de transition est la suivante :

$$
P =
\left(
\begin{array}{cccc}
\dfrac{3}{5} & \dfrac{3}{10} & 0 & \dfrac{1}{10} \\
\dfrac{1}{10} & \dfrac{2}{5} & \dfrac{1}{2} & 0 \\
\dfrac{3}{4} & 0 &\dfrac{1}{5} & \dfrac{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 :

\begin{center}
\includegraphics[scale=0.7]{graphes/markov1}
\end{center}


\subsection{Propriétés}
\begin{Th}
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$).
\end{Th}


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 :

\begin{Th}
$p(t) = p(0) P^t$
\end{Th}

\subsection{Exercice}

\begin{Exo}
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:
\begin{itemize}
\item étant immunisé, il peut le rester avec une probabilité 0,9 ou passer à l'état $S$ avec une probabilié 0,1;
\item étant dans l'état $S$, il peut le rester avec une probabilité 0,5 ou passer à l'état $M$ avec une probabilité 0,5;
\item étant malade, il peut le rester avec une probabilité 0,2 ou passer à l'état $I$ avec une probabilité 0,8. 
\end{itemize}

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 :
\begin{itemize}
\item au départ, il est immunisé ($I$);
\item au départ, il est non malade et non immunisé ($S$);
\item au départ, il est malade ($M$). 
\end{itemize}

Pouvez-vous donner des éléments sur la proportion d'individus malades dans la population étudiée?
\end{Exo}




\section{Distribution limite}

\subsection{Présentation}

On constate souvent que la distribution $p(t)$ converge vers une distribution limite $p$ si $t \rightarrow \infty$ .

\begin{Def}
Si tel est le cas, on dit que cette dernière définit un \emph{régime permanent}\index{processus stochastique!régime permanent} du processus stochastique.
\end{Def}

\begin{Rem}
Le régime permanent n'est pas influencé par le choix de la distribution initiale.
\end{Rem}

\subsection{Existence d'une distribution limite}

\begin{Th}
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$.
\end{Th}

\begin{Rem}
La démonstration de cette condition d'existence dépasse le cadre de ce cours.
\end{Rem}

\subsection{Exercices}

\begin{Exo}
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.
\end{Exo}



\begin{Exo}
Soit la matrice stochastique 
$$
P =
\left(
\begin{array}{cccc}
\dfrac{3}{5} & \dfrac{3}{10} & 0 & \dfrac{1}{10} \\
\dfrac{1}{10} & \dfrac{2}{5} & \dfrac{1}{2} & 0 \\
\dfrac{3}{4} & 0 &\dfrac{1}{5} & \dfrac{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.
\end{Exo}

\begin{Exo}
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 :

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Hier & Aujourd'hui & Beau demain & Mauvais demain\\
\hline
Beau & Beau & 0.8 & 0.2 \\
\hline
Beau & Mauvais & 0.4 & 0.6\\
\hline
Mauvais & Beau & 0.6 & 0.4 \\
\hline
Mauvais & Mauvais & 0.1 & 0.9\\
\hline
\end{tabular}
\end{center}

\begin{itemize}
\item Modélisez ce processus à l'aide d'une chaîne de Markov.
\item Calculez le nombre moyen de jours de beau temps par année.
\end{itemize}
\end{Exo}



\begin{Exo}
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é.

\begin{enumerate}
\item Modélisez ce processus à l'aide d'une chaîne de Markov.
\item Montrez que cette chaîne de Markov n'a pas de distribution limite.
\end{enumerate}
\end{Exo}



\section{Chaîne absorbante}
\subsection{Généralités}
\subsubsection{Définitions}
\begin{Def}[\'Etat absorbant]
Un \emph{état absorbant}\index{état!absorbant} est un état que l'on ne quitte plus lorsqu'on y pénètre.
\end{Def}

\begin{Rem}
 Autrement dit, l'état $j$ est absorbant si $p_{jj}=1$.
\end{Rem}

\begin{Def}[Chaîne de Markov absorbante]
Une chaîne de Markov est absorbante si et seulement si:
\begin{enumerate}
\item il y a au moins un état absorbant
\item de tout état non absorbant, on peut atteindre un état absorbant. 
\end{enumerate}
\end{Def}


\begin{Ex}
Par exemple, l'état 4 ci-dessous...

\begin{center}
\includegraphics[scale=0.7]{graphes/markov1}
\end{center}

...est un état absorbant. Comme on peut atteindre cet état depuis tous les autres, la chaîne de Markov est absorbante.
\end{Ex}



\subsubsection{Propriété}

\begin{Th}
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.
\end{Th}



\subsection{Délais d'absorption et probabilité d'absorption}

\subsubsection{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 :
\begin{itemize}
\item Combien de temps faudra-t-il en moyenne pour arriver dans un état absorbant, étant donné son état initial?

\item S'il existe plusieurs états absorbants, quelle est la probabilité de tomber dans un état absorbant donné? 
\end{itemize}

\subsubsection{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 \\
\hline
  &  \\
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,

\begin{center}
\includegraphics[scale=0.7]{graphes/markov1}
\end{center}

nous avons (l'ordre des états est 4-1-2-3) :

$$
P =
\left(
\begin{array}{cccc}
1 & 0 & 0 & 0 \\
\dfrac{1}{10} & \dfrac{3}{5} & \dfrac{3}{10} & 0 \\
0 & \dfrac{1}{10} &\dfrac{2}{5} & \dfrac{1}{2} \\
\dfrac{1}{20} & \dfrac{3}{4} & 0 & \dfrac{1}{5} \\
\end{array}
\right)
$$

\subsubsection{Matrice fondamentale}

\begin{Def}[Matrice fondamentale de la chaîne absorbante]
La matrice $N = (I-Q)^{-1}$ est appelée la \emph{matrice fondamentale de la chaîne absorbante}\index{matrice!fondamentale de la chaîne absorbante}.
\end{Def}


\subsubsection{Résultats}

\begin{Th}
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}$.
\end{Th}


\begin{Th}
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$.
\end{Th}


\begin{Ex}
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
\end{Ex}

\begin{Th}
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$.
\end{Th}

\begin{Ex}
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!
\end{Ex}



\subsection{Exercices}


\begin{Exo}
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.
\begin{enumerate}
\item Représentez cette expérience par une chaîne de Markov.
\item Avec p = 1/3, calculez la probabilité de la ruine du joueur.
\item Avec p = 1/3, calculez la longueur moyenne d'une partie. 
\end{enumerate}
\end{Exo}

\begin{Exo}
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:

\begin{tabular}{|c|c|c|c|c|c|}
\hline
de \ à & Stand 1 & Stand 2 & Stand 3 & Stand 4 & Stand 5\\
\hline
Stand 1 & 0 & 0,8 & 0 & 0 & 0,2\\
\hline
Stand 2 & 0,2 & 0 & 0,5 & 0,3 & 0\\
\hline
Stand 3 & 0 & 0 & 0 & 0,6 & 0,4\\
\hline
Stand 4 & 0,9 & 0 & 0,1 & 0 & 0\\
\hline
Stand 5 & 0,8 & 0 & 0 & 0,2 & 0\\
\hline
\end{tabular}

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)?
\end{Exo}

\begin{Exo}
Considérons une série de jets d'une pièce de monnaie normale. On notera P pour pile et F pour face.
\begin{enumerate}
\item Quelle est la probabilité d'obtenir une séquence PFP avant une séquence PPP?
\item Quel est le nombre de jets nécessaires en moyenne pour réaliser l'une des deux séquences PFP et PPP? 
\end{enumerate}
\end{Exo}


\begin{Exo}[La parade nuptiale des bourdons]
Une séance d'accouplement peut se décomposer en 7 phases:
\begin{description}
\item[Départ (D) :] mise en contact des bourdons mâle et des reines.
\item[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.
\item[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.
\item[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.
\item[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.
\item[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.
\item[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. 
\end{description}

Voici les statistiques obtenues pour 78 séances d'accouplement en laboratoire : par exemple App suivi de T = 202...

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
 & App & T & IF & Acc & ST & SA & Total \\
\hline
D & 78 & 0 & 0 & 0 & 0 & 0 & 78\\
\hline
App & 614 & 202 & 87 & 0 & 16 & 8 & 927\\
\hline
IF & 83 & 0 & 0 & 0 & 3 & 1 & 87\\
\hline
T & 152 & 0 & 0 & 35 & 7 & 8 & 202\\
\hline
\end{tabular}
\end{center}


\begin{enumerate}
\item Dessinez le graphe de transitions d'une parade nuptiale de bourdons.
\item Calculez les probabilités de transition d'un état à un autre et ajoutez-les au graphe.
\item Donnez la matrice correspondante de la chaîne de Markov.
\item 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.
\item 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. 
\end{enumerate}
\end{Exo}


\gsaut
\centerline{\x{Fin du Chapitre}}