Cours Stage - Chaîne de Markov

Exercice - Chaîne de Markov - Première notion

L'énoncé

Répondre aux questions suivantes 


Question 1

On considère une maison constituée de $3$ pièces selon le schéma ci-dessous.

Capture_d’écran_2020-04-07_à_19.24.53_1

Malgré tous les efforts des propriétaires, une souris est rentrée dans la maison et est maintenant dans la pièce $A$. 
On suppose qu'elle change de pièce toutes les minutes selon le processus suivant :
Si elle est dans la pièce $A$, il y a $1$ chance sur $3$ qu'elle y reste.
Lorsqu'elle est dans la pièce $B$, il y a $1$ chance sur $2$ qu'elle y reste. Si elle change de pièce, elle le fait au hasard parmi les pièces accessibles.
Enfin, si elle atteint la pièce $C$, elle y reste car elle y trouve un succulent morceau de fromage ! 

On souhaite modéliser par une chaîne de Markov la position de la souris au cours du temps.

Justifier tout d'abord qu'il est possible de modéliser cette situation par une chaîne de Markov.

On peut modéliser la situation car il s'agit d'une situation sans mémoire : le changement d'une pièce par la souris ne dépend pas des états passés mais seulement de l'état présent. 

On pourra revoir la vidéo pour trouver la définition. 

Question 2

On suppose ainsi qu'il y a trois états possibles, correspondants aux trois pièces dans laquelle la souris peut se trouver. 

Donner le graphe des états et la matrice de transition de cette situation. 

On commence par déterminer les probabilités manquantes.
La probabilité de passer dans la pièce $B$ sachant que la souris était dans la pièce $A$ est de $1 - \dfrac{1}{3} = \dfrac{2}{3}$. 
Si elle change de pièce depuis la pièce $B$, elle le fait au hasard, c'est à dire qu'elle a dans ce cas $1$ chance sur $2$ d'aller dans la pièce $A$ ou $C$. Comme elle a $1$ chance sur $2$ de rester dans la pièce $B$, la probabilité d'aller dans la pièce $A$ ou $C$ est donc de $\dfrac{1}{2} \times \dfrac{1}{2} = \dfrac{1}{4}$.
Enfin, si elle atteint la pièce $C$, elle y reste car elle mange. Cela signifie que la probabilité de rester dans la pièce $C$ est de $1$ car c'est toujours vrai ! 

On donne donc la matrice de transition, en se rappelant que l'intersection d'une ligne et d'une colonne donne la probabilité de changer de l'état de la ligne vers l'état de la colonne.

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

Un bon moyen de réduire les erreurs est de calculer la somme de chaque ligne qui doit valoir 1.

On donne enfin le graphe des états.

Capture_d’écran_2020-04-07_à_18.07.28

Pour connaitre les probabilités manquantes, on pourra utiliser les évènement contraires. 


Si elle atteint la pièce $C$, elle y reste... quelle est donc la probabilité de rester dans la pièce $C$ ? 

Question 3

On note :
$a_n$ la probabilité que la souris se trouve dans la pièce $A$ au bout de $n$ minutes après son entrée dans la maison,
$b_n$ la probabilité que la souris se trouve dans la pièce $B$ au bout de $n$ minutes,
$c_n$ la probabilité que la souris se trouve dans la pièce $C$ au bout de $n$ minutes
$\Pi_n = ( \begin{array}{ccc} a_n & b_n & c_n \end{array})$ l'état probabiliste correspondant à la position de la souris au bout de $n$ minutes.

Donner $\Pi_0$. 

La souris rentre dans la pièce $A$. Ainsi, à l'instant initial, la souris est dans la pièce $A$. 
Cela signifie que $a_0 = 1$ et $b_0 = c_0 = 0$.
Ainsi, $\Pi_0 = ( \begin{array}{ccc} 1 & 0 & 0 \end{array})$

Dans quelle pièce la souris rentre ?

Question 4

Donner la relation liant $\Pi_{n+1}$ à $\Pi_n$ puis montrer que $\Pi_1= \left( \begin{array}{ccc} \dfrac{1}{3} & \dfrac{2}{3} & 0 \end{array} \right)$

La matrice de transition permet de passer de l'état $n$ à l'état d'après par la relation $\Pi_{n+1} =\Pi_n P $. On n'oubliera pas que l'ordre de la multiplication est important !

Ainsi, $ \Pi_1 = \Pi_0 \times P = ( \begin{array}{ccc} 1 & 0 & 0 \end{array}) \times \left ( \begin{array}{ccc} \dfrac{1}{3} & \dfrac{2}{3} & 0 \\ \dfrac{1}{4} & \dfrac{1}{2} & \dfrac{1}{4} \\ 0 & 0 & 1 \end{array} \right ) = \left( \begin{array}{ccc} \dfrac{1}{3} & \dfrac{2}{3} & 0 \end{array} \right)$

On pourra utiliser la matrice de transition.

Question 5

On sait que $\Pi_n = \Pi_0 \times P^n$.
A l'aide de la calculatrice, donner le nombre de minutes nécessaires pour que la probabilité que la souris soit en train de manger le fromage soit supérieure à $0,99$. 

On cherche $n$ tel que la probabilité que la souris soit dans la pièce $C$ soit supérieure à $0,99$
On utilise donc la calculatrice pour calculer les puissances de $P$ successives et le produit $\Pi_0 \times P^n$ et on s'arrête lorsque $c_n \geq 0,99$.

On trouve que lorsque $n = 26$ on a $c_{26} \approx 0,9895 \leq 0,99$
De même, on trouve que lorsque $n = 27$ on a $c_{27} \approx 0,9913 \geq 0,99$.

Il faut donc $27$ minutes pour que la probabilité que la souris soit en train de manger le fromage soit supérieure à $0,99$. 

On pourra utiliser la calculatrice pour calculer les puissances de $P$ successives. 

Question 6

On pose $D = \left ( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & \dfrac{5}{6} & 0 \\ 0 & 0 & 1 \end{array} \right )$, $Q = \left ( \begin{array}{ccc} -2 & \dfrac{4}{3} & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right )$ et $Q^{-1} = \left ( \begin{array}{ccc} -\dfrac{3}{10} & \dfrac{2}{5} & -\dfrac{1}{10} \\ \dfrac{3}{10}  & \dfrac{3}{5}  & -\dfrac{9}{10}  \\ 0 & 0 & 1 \end{array} \right )$.

On pose aussi $I_3 = \left ( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right )$ l'identité de rang $3$.

On admet que $P = QDQ^{-1}$.

Montrer que $\Pi_n = \Pi_0 QD^nQ^{-1}$ pour tout $n \in \mathbb{N}^*$

On veut montrer par récurrence la propriété $P_n : " \Pi_n = \Pi_0 QD^nQ^{-1}"$ pour tout $n \in \mathbb{N}^*$.
Tout d'abord, si $n = 1$, $\Pi_0 QD^1Q^{-1} = \Pi_0 P$ d'après l'énoncé.
Donc $\Pi_0 QD^1Q^{-1} =\Pi_0 P=  \Pi_1$.
La propriété est donc vraie au rang 1.

Supposons que la propriété soit vraie au rang $k$ avec $k$ un entier naturel non nul, montrons qu'elle est vraie au rang $k + 1$ :

$\Pi_{k+1} = \Pi_k P$
Or d'après l'hypothèse de récurrence, $\Pi_k = \Pi_0 QD^kQ^{-1}$.
Ainsi, $\Pi_{k+1} = \Pi_0 QD^kQ^{-1} P$.

Or on sait $P = QDQ^{-1}$.
Finalement, $\Pi_{k+1} = \Pi_0 QD^kQ^{-1} P =\Pi_0 QD^kQ^{-1} QDQ^{-1} $, or comme $Q^{-1} Q = I_3$ on a $\Pi_{k+1} = \Pi_0 QD^{k}DQ^{-1} = \Pi_n = \Pi_0 QD^{k+1}Q^{-1}$

La propriété est donc vraie au rang $k + 1$. 

D'après le principe de récurrence, $\Pi_n = \Pi_0 QD^nQ^{-1}$ pour tout $n \in \mathbb{N}^*$.

On pourra raisonner par récurrence.

Question 7

Soit $n \in \mathbb{N}^*$, montrer alors que $\Pi_n = \left( \begin{array}{ccc} \dfrac{2}{5}\times \left ( \dfrac{5}{6} \right )^n & \dfrac{4}{5} \left (\dfrac{5}{6}\right )^n & 1 - \left (\dfrac{5}{6}\right )^{n-1}  \end{array} \right)$

Soit $n \in \mathbb{N}^*$,
On utilise le résultat de la question précédente : $\Pi_n = \Pi_0 QD^nQ^{-1}$.
Ainsi,$ \Pi_n = ( \begin{array}{ccc} 1 & 0 & 0 \end{array}) \times \left ( \begin{array}{ccc} -2 & \dfrac{4}{3} & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right ) \times \left ( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & \left ( \dfrac{5}{6} \right )^n & 0 \\ 0 & 0 & 1 \end{array} \right ) \times \left ( \begin{array}{ccc} -\dfrac{3}{10} & \dfrac{2}{5} & -\dfrac{1}{10} \\ \dfrac{3}{10}  & \dfrac{3}{5}  & -\dfrac{9}{10}  \\ 0 & 0 & 1 \end{array} \right )$. 

C'est à dire $ \Pi_n =\left   ( \begin{array}{ccc} -2 & \dfrac{4}{3} & 1 \end{array}\right ) \times \left ( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & \left ( \dfrac{5}{6} \right )^n & 0 \\ 0 & 0 & 1 \end{array} \right ) \times \left ( \begin{array}{ccc} -\dfrac{3}{10} & \dfrac{2}{5} & -\dfrac{1}{10} \\ \dfrac{3}{10}  & \dfrac{3}{5}  & -\dfrac{9}{10}  \\ 0 & 0 & 1 \end{array} \right )$.

Donc $ \Pi_n = \left   ( \begin{array}{ccc} 0 & \dfrac{4}{3} \times \left (\dfrac{5}{6} \right )^n & 1 \end{array}\right ) \times \left ( \begin{array}{ccc} -\dfrac{3}{10} & \dfrac{2}{5} & -\dfrac{1}{10} \\ \dfrac{3}{10}  & \dfrac{3}{5}  & -\dfrac{9}{10}  \\ 0 & 0 & 1 \end{array} \right )$.

Finalement, $ \Pi_n = \left( \begin{array}{ccc} \dfrac{2}{5}\times \left ( \dfrac{5}{6} \right )^n & \dfrac{4}{5} \left (\dfrac{5}{6}\right )^n & 1 - \left (\dfrac{5}{6}\right )^{n-1}  \end{array} \right)$

On utilisera le résultat de la question précédente.

Question 8

Retrouver le résultat de la question 5. 

On sait que pour tout $n \in \mathbb{N}^*$,
$c_n = 1 - \left (\dfrac{5}{6}\right )^{n-1}$. 
On cherche $n$ tel que $c_n \geq 0,99 \iff 1 - \left (\dfrac{5}{6}\right )^{n-1} \geq 0,99 \iff 0,01 \geq \left (\dfrac{5}{6}\right )^{n-1} \iff \ln(0,01) \geq (n-1) \ln \left (\dfrac{5}{6}\right ) $.
Cela revient à dire que $ c_n \geq 0,99 \iff n - 1 \geq \dfrac{\ln(0,01)}{\ln \left (\dfrac{5}{6}\right )}$.
Or $\dfrac{\ln(0,01)}{\ln \left (\dfrac{5}{6}\right )} + 1 \approx 26,26$.
On retrouve bien le fait qu'au bout de $27$ minutes, la probabilité que la souris mange du fromage est supérieure à 0,99. 

On utilisera la question précédente. 

Question 9

Quel est l'état limite du système et était-il prévisible ? 

On calcule $\lim \limits _{n \to+ \infty} \Pi_n$ et cela revient à calculer $\lim \limits _{n \to+ \infty}  a_n$ puis $\lim \limits _{n \to+ \infty}  b_n$ puis $\lim \limits _{n \to+ \infty}  c_n$.

Or $\dfrac{5}{6} < 1$, donc $\lim \limits _{n \to+ \infty} \left (\dfrac{5}{6}\right )^n = 0$.
Ainsi,  $\lim \limits _{n \to+ \infty}  a_n = \dfrac{2}{5} \times 0 = 0$, $\lim \limits _{n \to+ \infty}  b_n = \dfrac{4}{5}\times 0 = 0$ et $\lim \limits _{n \to+ \infty}  c_n = 1 - 0 = 0$.

Comme la souris ne ressort pas de la pièce $C$, au bout d'un certain temps, elle y est forcément et n'en bouge plus !

On pourra calculer les limites de $a_n$, $b_n$ et $c_n$.