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 $\pi_n$ la distribution des probabilités de se trouver dans chaque pièce (numérotées dans l'ordre alphabétique) après $n$ déplacements.
Comme on part de A, on a donc initialement $\pi_0=\lp\begin{array}{ccccccc}1&0&0&0&0&0&0\enar\rp$

\[\psset{unit=.5cm}\begin{pspicture}(0,0)(10,10)
  \psline(.6,.6)(.6,9.4)(10,9.4)(10,6)
  \psline(10,4)(10,.6)(.6,.6)  
  \psline(1,8)(2,8)(2,9)(8,9)(8,8)(10,8)(10,9.4)
  \psline(2,5.2)(4,5.2)\psline(2,4.8)(4,4.8)\psline[linewidth=2pt](3,4.8)(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}\]

  1. 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 $M$ de transition associée à ce graphe.
  2. Calculer la distribution de probabilités $\pi_1$ et interpréter ce résultat.
  3. Calculer la probabilité de sortir du labyrinthe en 5 déplacements.
  4. Calculer la probabilité de sortir du labyrinthe en 10 déplacements.
  5. Calculer la probabilité de sortir du labyrinthe en 20 déplacements.
  6. Combien de déplacements faut-il prévoir pour avoir au moins une chance sur deux de sortir de ce labyrinthe ?
  7. 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


  1. \[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\]


  2. On a
    \[\pi_1=\pi_0M=\lp\begin{array}{*7c}0&\frac12&\frac12&0&0&0&0\enar\rp\]

    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.
  3. 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\]



    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\]

  4. 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\]

    On trouve donc que la probabilité de sortir du labyrinthe, c'est-à-dire d'être en G, est d'environ 0,13.
  5. 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\]

    On trouve donc que cette fois la probabilité de sortir du labyrinthe est d'environ 0,378.
  6. La probabilité de sortir du labyrinthe croît bien sûr lorsqu'on augmente le nombre $n$ 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 $n=27$ déplacements pour avoir plus d'une chance sur deux de sortir de ce labyrinthe, en s'y déplaçant au hasard.
  7. La distribution initiale est maintenant
    \[\pi_0=\lp\begin{array}{ccccccc}\dfrac16&\dfrac16&\dfrac16&\dfrac16&\dfrac16&\dfrac16&0\enar\rp\]

    et on reprend alors les calculs de la question précédente en calculant successivement les matrices $\pi_n=\pi_OM^n$ jusqu'à ce que le dernier éléments de cette matrice, donc la probabilité $\pi_n=P(X_n=G)$, soit supérieur ou égal à 0,5.
    On trouve cette fois $n=17$.


Tag:Chaines de Markov

Autres sujets au hasard: Lancer de dés



Voir aussi:

Quelques devoirs


LongPage: h2: 3 - h3: 0