Labyrinthe aléatoire: probabilité de sortir au hasard
Exercice corrigé - Maths expertes, terminale générale
Énoncé
Sortir aléatoirement d'un labyrinthe
On démarre dans le labyrinthe suivant dans la pièce A, la sortie se situe en G.
On se déplace suivant la règle suivante: lorsque je suis dans une pièce je me déplace forcément dans une autre pièce adjacente et accessible et au hasard, avec équiprobabilité. Lorsque j'arrive en G, bien sûr, je suis arrivé et je ne repars pas en arrière: je reste à coup sûr en G ensuite.
On note
la distribution des probabilités de se trouver dans chaque pièce (numérotées dans l'ordre alphabétique) après
déplacements.
Comme on part de A, on a donc initialement
(3,5.2)
\psline(1,8)(1,6)(2,6)(2,5.2)
\psline(2,4.8)(2,4)(1,4)(1,2)(2,2)(2,1)
\psline(2,1)(4,1)(4,2)(4.8,2)(4.8,4)(4,4)(4,4.8)
\psline(4,5.2)(4,6)(6,6)(6,5.2)
\psline(6,5.2)(8,5.2)(8,6)(10,6)
\psline(6,4.8)(8,4.8)(8,4)(10,4)
\psline(6,4.8)(6,4)(5.2,4)(5.2,2)(6,2)(6,1)(10,1)
\rput(1.3,8.6){A}
\rput(8.8,8.6){B}
\rput(1.3,5){C}
\rput(5,5){D}
\rput(1.3,1.3){E}
\rput(5,1.3){F}
\rput(9,5){G}
\end{pspicture}\]](/Generateur-Devoirs/Mex/markov/exlaby/4.png)
On démarre dans le labyrinthe suivant dans la pièce A, la sortie se situe en G.
On se déplace suivant la règle suivante: lorsque je suis dans une pièce je me déplace forcément dans une autre pièce adjacente et accessible et au hasard, avec équiprobabilité. Lorsque j'arrive en G, bien sûr, je suis arrivé et je ne repars pas en arrière: je reste à coup sûr en G ensuite.
On note
Comme on part de A, on a donc initialement
(3,5.2)
\psline(1,8)(1,6)(2,6)(2,5.2)
\psline(2,4.8)(2,4)(1,4)(1,2)(2,2)(2,1)
\psline(2,1)(4,1)(4,2)(4.8,2)(4.8,4)(4,4)(4,4.8)
\psline(4,5.2)(4,6)(6,6)(6,5.2)
\psline(6,5.2)(8,5.2)(8,6)(10,6)
\psline(6,4.8)(8,4.8)(8,4)(10,4)
\psline(6,4.8)(6,4)(5.2,4)(5.2,2)(6,2)(6,1)(10,1)
\rput(1.3,8.6){A}
\rput(8.8,8.6){B}
\rput(1.3,5){C}
\rput(5,5){D}
\rput(1.3,1.3){E}
\rput(5,1.3){F}
\rput(9,5){G}
\end{pspicture}\]](/Generateur-Devoirs/Mex/markov/exlaby/4.png)
- On considère le graphe probabiliste dont les sommets sont les différentes pièces du labyrinthe numérotées dans l'ordre alphabétique.
Écrire la matrice
de transition associée à ce graphe.
- Calculer la distribution de probabilités
et interpréter ce résultat.
- Calculer la probabilité de sortir du labyrinthe en 5 déplacements.
- Calculer la probabilité de sortir du labyrinthe en 10 déplacements.
- Calculer la probabilité de sortir du labyrinthe en 20 déplacements.
- Combien de déplacements faut-il prévoir pour avoir au moins une chance sur deux de sortir de ce labyrinthe ?
- Je lance un dé à six faces bien équilibré pour choisir au hasard la pièce à partir de laquelle je démarre le labyrinthe: si j'obtiens un 1 je démarre le labyrinthe en 1, si j'obtiens un deux je le démarre en B, …
Commbien de déplacements faut-il alors prévoir pour avoir au moins une chance sur deux de sortir de ce labyrinthe ?
Correction
Correction
-
![\[M=\lp\begin{array}{*7c}
0 & \frac12 & \frac12 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
\frac12 & 0 & 0 & 0 & \frac12 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & \frac12 & \frac12\\
0 & 0 & \frac12 & 0 & 0 & \frac12 & 0 \\
0 & 0 & 0 & \frac12 & \frac12 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1
\enar\rp\]](/Generateur-Devoirs/Mex/markov/exlaby_c/1.png)
- On a
![\[\pi_1=\pi_0M=\lp\begin{array}{*7c}0&\frac12&\frac12&0&0&0&0\enar\rp\]](/Generateur-Devoirs/Mex/markov/exlaby_c/2.png)
On commence en A et après un déplacement, on une chance sur deux d'être en B et une chance sur deux d'être en C, et aucune chance d'être ailleurs en 1 déplacement.
Ce résultat se trouve directement, dans la définition même du labyrinthe, sans avoir à faire le calcul matriciel.
- Pour sortir en 5 déplamcents, il n'y a qu'un seule possibilité, se déplacer toujours vers la sortie, soit le chemin A-C-E-F-D-G.
À chaque déplacement, il y a une chance sur deux d'aller dans la bonne direction, soit la probabilité de sortir en exacetement 5 déplacements:
![\[p=\lp\dfrac12\rp^5=\dfrac1{2^5}=\dfrac1{32}\simeq0,031\]](/Generateur-Devoirs/Mex/markov/exlaby_c/3.png)
On peut aussi calculer la distribution complète des probabilités au bout de 5 déplacements:
![\[\begin{array}{ll}\pi_5&=\pi_0M^5\\[.5em]&\simeq\lp\begin{array}{*7c}0 & 0,312 & 0,469 & 0 & 0 & 0,188 & 0.031\enar\rp\enar\]](/Generateur-Devoirs/Mex/markov/exlaby_c/4.png)
- On calcule la distribution des probabilités au bout de 10 déplacements, soit
![\[\begin{array}{ll}\pi_{10}&=\pi_0M^{10}\\[.5em]&\simeq\lp\begin{array}{*7c}0.45 & 0 & 0 & 0.11 & 0.31 & 0 & 0.13\enar\rp\enar\]](/Generateur-Devoirs/Mex/markov/exlaby_c/5.png)
On trouve donc que la probabilité de sortir du labyrinthe, c'est-à-dire d'être en G, est d'environ 0,13.
- On calcule de même pour 20 déplacements,
![\[\begin{array}{ll}\pi_{20}&=\pi_0M^{20}\\[.5em]&\simeq\lp\begin{array}{*7c}0.311&0&0&0,083&0,227&0 &0,378]\enar\rp\enar\]](/Generateur-Devoirs/Mex/markov/exlaby_c/6.png)
On trouve donc que cette fois la probabilité de sortir du labyrinthe est d'environ 0,378.
- La probabilité de sortir du labyrinthe croît bien sûr lorsqu'on augmente le nombre
de déplacements, et en testant avec la calculatrice on trouve que la probabilité de sortie est d'environ 0,495 pour 26 déplacements et est d'environ 0,529 pour 27 déplacements.
Il faut donc prévoir
déplacements pour avoir plus d'une chance sur deux de sortir de ce labyrinthe, en s'y déplaçant au hasard.
- La distribution initiale est maintenant
![\[\pi_0=\lp\begin{array}{ccccccc}\dfrac16&\dfrac16&\dfrac16&\dfrac16&\dfrac16&\dfrac16&0\enar\rp\]](/Generateur-Devoirs/Mex/markov/exlaby_c/9.png)
et on reprend alors les calculs de la question précédente en calculant successivement les matrices
jusqu'à ce que le dernier éléments de cette matrice, donc la probabilité
, soit supérieur ou égal à 0,5.
On trouve cette fois
.
Tag:Chaines de Markov
Voir aussi:
Quelques devoirs
en maths expertes sur les graphes et chaînes de Markov: calcul du nombre de chemins d'une longueur donnée dans un graphe et promenade aléatoire dans un labyrinthe.
sur les graphes et chaînes de Markov. Evolution probabiliste et états stables. Traffic aérien entre 4 villes et équilibre de gaz entre deux réservoirs
