$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Exercices corrigés - Marches aléatoires

Enoncé
Soit $E=\{1,\dots,d\}$ un ensemble fini. On appelle marche aléatoire sur $E$ une suite $(X_n)$ de variables aléatoires à valeurs dans $E$ telle que, pour tout $i,j\in\{1,\dots,d\}^2$, il existe $p_{i,j}\geq 0$ tel que, pour tout $n\geq 1$, $P(X_n=i|X_{n-1}=j)=p_{i,j}$. On appelle matrice de transition de la marche aléatoire la matrice $A=(p_{i,j})_{1\leq i,j\leq d}$.
  1. Démontrer que, pour tout $j\in\{1,\dots,d\}$, on a $\sum_{i=1}^d p_{i,j}=1$.
  2. Une puce se déplace sur un triangle de la façon suivante. Si elle est sur un sommet, elle se déplace de façon équiprobable sur l'un des deux autres sommets (elle ne peut rester sur place). Donner la matrice de transition $A$ dans ce cas.
  3. On appelle matrice état au temps $n$ la matrice colonne $U_n=\left(\begin{array}c P(X_n=1)\\ \vdots \\ P(X_n=d)\end{array}\right)$. Démontrer que, pour tout $n\geq 1$, on a $U_n=A^n U_0$.
  4. On dit que la marche aléatoire est convergente si la suite $(U_n)$ est convergente. Démontrer que si la marche aléatoire est convergente, ce ne peut être que vers un état stable de la marche, c'est-à-dire vers une solution de $AU=U$.
  5. Le cas $d=2$: on considère dans cette question une marche aléatoire à deux états, on note $A=\left(\begin{array}{cc} 1-p &q\\ p&1-q\end{array}\right)$ et $U_n=\left(\begin{array}c p_n\\ q_n\end{array}\right)$. Démontrer que, pour tout $n\geq 1$, on a $p_{n+1}=(1-p-q)p_n+q$. En déduire que les suites $(p_n)$ et $(q_n)$ sont convergentes vers des réels que l'on précisera.
  6. On retourne à l'étude de la marche aléatoire sur le triangle.
    1. Démontrer, sans aucun calcul, que la matrice $A$ est diagonalisable.
    2. Démontrer que pour tout entier $n$, on a $$A=\left(\begin{array}{ccc} u_n&v_n&v_n\\ v_n&u_n&v_n\\ v_n&v_n&u_n \end{array}\right)$$ où $$u_n=\frac 13\left(1-\left(\frac 12\right)^{n-1}\right)\textrm{ et }v_n=\frac 13\left(1-\left(\frac 12\right)^n\right).$$
    3. En déduire que, quelque soit l'état initial $U_0$, la suite $(U_n)$ est convergente.
Corrigé
Enoncé
On considère un carré $ABCD$ et son centre $O$. On note $\Gamma=\{A,B,C,D,O\}$. Une puce se déplace aléatoirement en sautant d'un point de $\Gamma$ à un autre. La seule contrainte est que, si un saut relie deux sommets du carré, ceux-ci sont adjacents. Par exemple, une puce se trouvant en $A$ peut sauter en $B$, $D$ ou $O$; une puce se trouvant en $O$ peut sauter en $A$, $B$, $C$ ou $D$. A chaque saut, tous les déplacements possibles sont équiprobables. La puce ne reste pas deux fois de suite au même endroit. Au départ, c'est à dire avant son premier saut, la puce se trouve au point $O$ Pour tout entier $n\geq 1$, on note $O_n$ l'évènement "la puce se trouve au point $O$ à l'issue de son $n$-ème saut". On note $p_n=P(O_n)$. On a donc $p_0=1$. On définit de même les évènements $A_n$, $B_n$, $C_n$ et $D_n$.
  1. Calculer $p_1$ et $p_2$.
  2. Pour tout entier naturel $n\geq 1$ démontrer les égalités $$P(A_n)=P(B_n)=P(C_n)=P(D_n).$$ On pourra raisonner par récurrence sur $n$.
    1. Démontrer que pour tout entier naturel $n$, $p_{n+1}=\frac13(1-p_n)$.
    2. En déduire la valeur de $p_n$ pour $n\in\mathbb N$.
    3. Quelle proportion du temps la puce passe-t-elle sur chacun des points de $\Gamma$ ?
Corrigé
Enoncé
Un appartement est formé de deux pièces $A$ et $B$ reliées entre elles par une porte ouverte. Seule la pièce $B$ possède une fenêtre ouverte. Une guêpe, qui s'était endormie dans la pièce $A$ se réveille à l'instant 0. On estime que :
  • quand la guêpe est dans la pièce $A$ à l'instant $n$ (exprimé en minutes), elle est encore dans cette pièce une minute après avec probabilité 1/3.
  • quand la guêpe est dans la pièce $B$ à l'instant $n$, elle retourne dans la pièce $A$ une minute après avec probabilité 1/4 et reste dans la pièce $B$ avec probabilité 1/2.
  1. Dans cette question, quand la guêpe sort de l'appartement, elle ne revient plus. On introduit les évènements
    • $A_n$ : "la guêpe est dans la pièce $A$ à l'instant $n$''
    • $B_n$ : "la guêpe est dans la pièce $B$ à l'instant $n$''
    • $E_n$ : ''la guêpe est à l'extérieur de l'appartement à l'instant $n$".
    Enfin, on note $a_n$, $b_n$ et $e_n$ les probabilités respectives de ces évènements et $U_n=\begin{pmatrix}a_n\\b_n\\e_n\end{pmatrix}$.
    1. Décrire la matrice de transition $M$ telle que pour tout $n\ge 0$, $U_{n+1}=MU_n$.
    2. On note $X_n=\begin{pmatrix}a_n\\b_n\end{pmatrix}$. Montrer qu'il existe une matrice $Q$ que l'on déterminera telle que pour tout $n\ge 0$, $X_{n+1}=QX_n$.
    3. Montrer qu'il existe un réel $\lambda$ que l'on déterminera tel que $Q^2=\lambda Q$.
    4. Calculer la probabilité que, $n$ minutes après son réveil, la guêpe ne se trouve plus dans l'appartement.
    5. Au bout de combien de temps, cette probabilité devient-elle supérieure à 0,999 ?
    6. On note $T$ le premier instant où la guêpe se trouve à l'extérieur de l'appartement. Que vaut $P(T=1)$ ? Pour $n\ge 2$, calculer $P(T=n)$.
    7. Que représente $e_n$ vis à vis de la variable aléatoire $T$ ?
    8. Montrer que $P(T<+\infty)=1$.
  2. On suppose maintenant que, lorsque la guêpe est sortie, elle revient dans la pièce $B$ avec probabilité 0,1. Les notations sont les mêmes que lors de la question 1.
    1. Que devient la matrice de transition $M$ dans cette situation ?
    2. (Question bonus) Donner, sous un logiciel de calcul formel de votre choix, les commandes permettant d'obtenir les valeurs propres et les vecteurs propres de la matrice $M$.
    3. L'utilisation de Xcas donne les valeurs propres suivantes pour $M$ $$1,(-\sqrt{514}+22)/60,(\sqrt{514}+22)/60$$ ainsi que les vecteurs propres associés $$\begin{pmatrix} 3 & 2\sqrt{514}+34&-2\sqrt{514}+34\\ 8&-2\sqrt{514}-64&2\sqrt{514}-64\\ 20&30&30 \end{pmatrix} $$ En déduire que la suite $(U_n)$ converge.
    4. On note $U_\infty$ la limite de la suite $(U_n)$. Justifier que $U_\infty=MU_\infty$ et en déduire la valeur de $U_\infty$.
Indication
Corrigé
Exercice 4 - Marche aléatoire dans un jeu vidéo [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On désire mettre au point un jeu vidéo dont le principe est le suivant : un joueur traverse successivement plusieurs salles d’un château. Lorsqu’il entre dans une salle, celle-ci peut être vide, sinon le joueur y rencontre des monstres qu’il doit affronter et vaincre avant de passer à la salle suivante. La partie s’arrête lorsque le joueur traverse successivement deux salles vides. On admet que le joueur réussit toujours à vaincre les monstres rencontrés dans une salle. Le jeu prévoit un nombre éventuellement illimité de salles et le joueur commence la partie dans la salle numéro 1.
On note $M_i$ l’évènement : "le joueur rencontre des monstres dans la salle numéro $i$". On admet que les différents évènements $M_i$ sont mutuellement indépendants et qu'il existe $p\in ]0,1[$ tel que $P(M_i)=p$ pour tout $i\geq 1$.
Soit enfin $X$ la variable aléatoire réelle égale au nombre de salles à traverser pour finir la partie.
  1. Question préliminaire : pour $x\in ]-1,1[$, rappeler la valeur de la somme $S(x)=\sum_{n\geq 0}x^n$. Prouver ensuite la convergence et donner la valeur de la somme $T(x)=\sum_{n\geq 2}n x^n$.
  2. Quelles sont les valeurs possibles prises par la variable aléatoire $X$?
  3. Décrire à l'aide des évènements $M_i$ les évènements $(X=2)$, $(X=3)$, $(X=4)$.
  4. En déduire la valeur de $P(X=2)$, $P(X=3)$ et $P(X=4)$.
  5. Pour $n\geq 2$, on note $q_n=P(X=n)$. Démontrer, en utilisant le système complet d'évènements $M_1,\overline{M_1}$ qu'il existe deux constantes $a$ et $b$ à déterminer en fonction de $p$ telles que, pour tout $n\geq 4$, $$q_n=aq_{n-1}+bq_{n-2}.$$
  6. On suppose désormais que $p=1/3$.
    1. Vérifier que, pour $n\geq 4$, $$q_n=\frac13 q_{n-1}+\frac 29 q_{n-2}.$$
    2. En déduire la valeur de $q_n$ pour $n\geq 2$.
    3. En déduire que $E(X)=15/4$. Comment interprétez-vous ce résultat?
Indication
Corrigé