Analyse à un pas et chaînes de Markov

1. Marche aléatoire sur les sommets d'un carré.

On considère une marche aléatoire sur les sommets d'un carré $ABCD$.
Lorsqu'on est sur un sommet, on se déplace sur un des deux sommets placés sur la même arête (i.e. $B$ ou $D$ si on est en $A$), avec probabilité $ \displaystyle \frac{ 1 }{ 3 } $ dans chaque cas, ou on reste sur place avec probabilité $ \displaystyle \frac{ 1 }{ 3 } $. On effectue ainsi $n\in\mathbb{N}$ déplacements indépendants, toujours selon le même processus.
On suppose qu'initialement on se trouve en $A$.
On pose $A_n$ = "après $n$ déplacements on se trouve sur le sommet A", et $a_n=\mathbb{P}(A_n)$.
On définit de même $B_n$, $C_n$, $D_n$, $b_n$, $c_n$ et $d_n$.

1. Donner un système de relations de récurrence vérifiées par les quatre suites réelles $ (a_n)_{ n \in \mathbb{N} } $, $ (b_n)_{ n \in \mathbb{N} } $, $ (c_n)_{ n \in \mathbb{N} } $ et $ (d_n)_{ n \in \mathbb{N} } $.
2. Ecrire ce système de relations à l'aide d'une relation matricielle.

On considère les matrices $M=\displaystyle \frac{1}{3} \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}$ $\quad B=3M-I_4$ $\quad J = \displaystyle \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix} \quad$ et $\quad K = \displaystyle \begin{pmatrix} 1 & -1 & 1 & -1 \\ -1 & 1 & -1 & 1 \\ 1 & -1 & 1 & -1 \\ -1 & 1 & -1 & 1 \end{pmatrix}$.

3. Vérifier que, pour tout $n\geq1$: $$B^n= 2^{n-2}J+(-1)^n2^{n-2}K$$ En déduire à l'aide de la formule du binôme que, pour tout $n\geq1$: $$M^n=\frac{1}{3^n}I_4+\frac{1}{4}\left(1-\frac{1}{3^n}\right)J+\frac{1}{4}\left(\left(\frac{-1}{3}\right)^n-\left(\frac{1}{3}\right)^n\right)K$$
4. En déduire l'expression de $a_n$, $b_n$, $c_n$ et $d_n$ en fonction de $n$.
5. Déterminer $ \displaystyle \underset{ n \rightarrow + \infty }{ \lim } a_n $ , $ \displaystyle \underset{ n \rightarrow + \infty }{ \lim } b_n $ , $ \displaystyle \underset{ n \rightarrow + \infty }{ \lim } c_n $ et $ \displaystyle \underset{ n \rightarrow + \infty }{ \lim } d_n $ . Interprétation?

CORRECTION [ afficher/masquer ]

1. Soit $n\in\mathbb{N}$ fixé. Après $n$ déplacements, on se trouve en $A$, $B$, $C$ ou $D$, et il est évident qu'on ne peut pas se trouver à deux positions différentes simultanément. Autrement dit les évènements $A_n$, $B_n$, $C_n$ et $D_n$ forment un système complet d'évènements.
   On procède par analyse à un pas. La formule des probabilités totales donne donc : $$\mathbb{P}(A_{n+1})=\mathbb{P}_{A_n}(A_{n+1})\mathbb{P}(A_n) +\mathbb{P}_{B_n}(A_{n+1})\mathbb{P}(B_n)+\mathbb{P}_{C_n}(A_{n+1})\mathbb{P}(C_n) +\mathbb{P}_{D_n}(A_{n+1})\mathbb{P}(D_n)$$ Or l'énoncé nous donne : $$\mathbb{P}_{A_n}(A_{n+1})=\frac{1}{3}\qquad\mathbb{P}_{B_n}(A_{n+1}) =\frac{1}{3}\qquad \mathbb{P}_{C_n}(A_{n+1})=0\qquad \mathbb{P}_{D_n}(A_{n+1})=\frac{1}{3}$$ On obtient donc la relation : $$a_{n+1}=\frac{1}{3}(a_n+b_{n}+d_{n})$$ On procède de même pour calculer $b_{n+1}=\mathbb{P}(B_{n+1})$, $c_{n+1}=\mathbb{P}(C_{n+1})$ et $d_{n+1}=\mathbb{P}(D_{n+1})$.
   Au final, on a donc le système de relations de récurrence suivant, pour tout $n\in\mathbb{N}$: $$\begin{array}{rcl} a_{n+1}& =& \frac{1}{3} a_{n} + \frac{1}{3} b_{n} + \frac{1}{3} d_{n} \\ b_{n+1} &=& \frac{1}{3} a_{n} + \frac{1}{3} b_{n} + \frac{1}{3}c_{n} \\ c_{n+1}& =& \frac{1}{3} b_{n} + \frac{1}{3} c_{n} + \frac{1}{3} d_{n} \\ d_{n+1} &=& \frac{1}{3} a_{n} + \frac{1}{3} c_{n} + \frac{1}{3} d_{n} \end{array}$$
2. Pour $n\in\mathbb{N}$, on note $\displaystyle X_n=\begin{pmatrix}a_n\\b_n\\c_n\\d_n \end{pmatrix}$ et $M=\displaystyle \frac{1}{3}\begin{pmatrix} 1&1&0&1\\ 1&1&1&0\\ 0&1&1&1\\ 1&0&1&1\\ \end{pmatrix}$.
   Le système précédent s'écrit alors: $\forall n\in\mathbb{N}$, $X_{n+1}=M\times X_{n}$.
3. • Vérifions la première formule par récurrence.
     On a: $B=\frac{1}{2}(J-K)$, donc la formule est vraie pour $n=1$.
     Supposons la formule vraie à un rang $n\geq1$ fixé. On a : $$\begin{array}{rcl} B^{n+1}&=&B\times B^n=\frac{1}{2} (J-K) \times \big[ 2^{n-2} J + (-1)^n 2^{n-2} K \big] \\ &=& 2^{n-3} J^2 + (-1)^n 2^{n-3} J K - 2^{n-3} K J - (-1)^n 2^{n-3} K^2 \end{array}$$ Des calculs simples donnent que: $J^2=4J$, $K^2=4K$ et $JK=KJ=0$. D'où : $$ B^{n+1} = 2^{n-1} J - (-1)^n 2^{n-1} K =2^{(n+1)-2} J +( -1)^{n+1} 2^{(n+1)-2} K $$ La formule est donc vraie au rang $n+1$.
     D'après le principe de récurrence, la formule est donc vraie pour tout $n\geq1$.
   • On remarque que: $\displaystyle M=\frac{1}{3}(B+I_4)$. Alors, comme $B$ et $I_4$ commutent, la formule du binôme donne que, pour tout $n\geq1$ : $$\begin{array}{rcl} M^n&=&\displaystyle\frac{1}{3^n}\sum_{k=0}^n\binom{n}{k}B^k I_4^{n-k} \\ &=&\displaystyle \frac{1}{3^n} I_4 + \frac{1}{3^n} \sum_{k=1}^n \binom{n}{k}B^k\\ &=&\displaystyle\frac{1}{3^n} I_4 + \frac{1}{3^n} \times \frac{1}{4} \times \left( \sum_{k=1}^n\binom{n}{k}2^{k} \right) J \displaystyle+\frac{1}{3^n} \times \frac{1}{4} \times \left( \sum_{k=1}^n\binom{n}{k}(-2)^{k} \right) K \end{array}$$ donc : $$M^n= \frac{1}{3^n} I_4 + \frac{1}{4\times 3^n} \left(3^n-1\right)J + \frac{1}{4\times 3^n} \left((-1)^n-1\right) K $$ Finalement, pour tout $n\geq1$ : $$ M^n = \frac{1}{3^n} I_4 + \frac{1}{4} \left( 1-\frac{1}{3^n} \right) J + \frac{1}{4} \left( \left( \frac{-1}{3} \right)^n-\left( \frac{1}{3} \right)^n \right) K$$
4. Une rapide récurrence permet de montrer que: $\forall n\in\mathbb{N}$, $X_n=M^nX_0$.
   De plus $\displaystyle X_0=\begin{pmatrix}1\\0\\0\\0 \end{pmatrix}$ puisqu'on est en A au départ.
   On obtient : $$ \forall n\geq1,\quad X_n=\begin{pmatrix} \displaystyle\frac{1}{3^n} + \frac{1}{4} \left( 1-\frac{1}{3^n} \right) + \frac{1}{4} \left( \left( \frac{-1}{3} \right)^n - \frac{1}{3^n} \right) \\ \displaystyle \frac{1}{4} \left( 1-\frac{1}{3^n} \right) - \frac{1}{4} \left( \left( \frac{-1}{3} \right)^n - \frac{1}{3^n} \right) \\ \displaystyle\frac{1}{4} \left( 1-\frac{1}{3^n} \right) + \frac{1}{4} \left( \left( \frac{-1}{3} \right)^n - \frac{1}{3^n} \right) \\ \displaystyle \frac{1}{4} \left( 1 - \frac{1}{3^n} \right) - \frac{1}{4} \left( \left( \frac{-1}{3}\right)^n - \frac{1}{3^n} \right) \end{pmatrix} $$ Finalement, pour tout $n\geq1$ : $$\begin{array}{lll} \displaystyle a_{n}=\frac{1}{4\times 3^n}\big(3^n+2+(-1)^n\big)&\qquad& \displaystyle b_{n}=\frac{1}{4\times 3^n}\big(3^n-(-1)^n\big)\quad \\ \displaystyle c_{n}=\frac{1}{4\times 3^n}\big(3^n-2+(-1)^n\big)&\qquad& \displaystyle d_{n}=\frac{1}{4\times 3^n}\big(3^n+(-1)^n\big)\end{array}$$ et $a_0=1$, $b_0=c_0=d_0=0$.
5. Pour $(a_n)_{n\geq1}$, on remarque que, pour tout $n\geq1$ : $$a_n=\frac{1}{4}\left(1+\frac{2}{3^n}+\left(\frac{-1}{3}\right)^n\right)$$ Comme $\displaystyle \frac{1}{3}<1$, on a donc: $\displaystyle \lim_{n\to+\infty}a_n=\frac{1}{4}$.
   Le même raisonnement donne que: $\displaystyle \lim_{n\to+\infty}b_n=\displaystyle \lim_{n\to+\infty}c_n =\displaystyle \lim_{n\to+\infty}d_n=\frac{1}{4}$.
   On peut en donner l'interprétation suivante: au bout d'un très grand nombre de déplacements, on se trouve de façon équiprobable sur n'importe quel sommet du carré.

MASQUER