Un appartement comporte quatre pièces $A$, $B$, $C$, $D$. Des portes relient $A$ et $B$, $A$ et $C$, $B$ et $C$, $B$ et $D$, $C$ et $D$. On modélise la situation par un graphe non orienté $G$ dont les sommets sont les pièces et les arêtes les portes.
Partie A
- Donner le degré de chaque sommet et le nombre d'arêtes de $G$. Le graphe est-il complet ? connexe ?
- Écrire la matrice d'adjacence $M$ de $G$ (sommets dans l'ordre $A$, $B$, $C$, $D$) et calculer $M^2$.
- On admet que $$M^3=\begin{pmatrix} 2 & 5 & 5 & 2 \\ 5 & 4 & 5 & 5 \\ 5 & 5 & 4 & 5 \\ 2 & 5 & 5 & 2 \end{pmatrix}.$$ Combien existe-t-il de chaînes de longueur $3$ de $A$ à $D$ ? Les écrire. Combien de chaînes fermées de longueur $3$ partent de $B$ ? Les écrire.
Partie B
Un robot aspirateur part de la pièce $A$ à l'instant $0$. Chaque minute, il franchit une des portes de la pièce où il se trouve, choisie au hasard de façon équiprobable. On s'intéresse seulement au type de pièce occupée : état $1$ si le robot est en $A$ ou en $D$, état $2$ s'il est en $B$ ou en $C$. On note $X_n$ l'état à la minute $n$ et on admet que $(X_n)$ est une chaîne de Markov. On pose $p_n=P(X_n=1)$.
- Justifier que la matrice de transition est $P=\begin{pmatrix} 0 & 1 \\ \frac{2}{3} & \frac{1}{3} \end{pmatrix}$.
- Montrer que, pour tout $n\in\mathbb{N}$, $p_{n+1}=-\dfrac{2}{3}p_n+\dfrac{2}{3}$.
- En déduire que, pour tout $n\in\mathbb{N}$, $p_n=\dfrac{2}{5}+\dfrac{3}{5}\left(-\dfrac{2}{3}\right)^n$. Calculer $p_3$.
- Déterminer la limite de $(p_n)$. Vérifier que $\pi=\begin{pmatrix} \frac{2}{5} & \frac{3}{5} \end{pmatrix}$ est une distribution invariante de la chaîne.
- Comparer $\frac{2}{5}$ au quotient de la somme des degrés de $A$ et $D$ par la somme de tous les degrés.
Partie A : le coefficient $(i,j)$ de $M^n$ compte les chaînes de longueur $n$ de $i$ à $j$ ; la diagonale de $M^3$ compte les chaînes fermées.
Partie B, question 1 : lister les voisins de chaque pièce et regarder dans quel état ils se trouvent.
Partie B, question 3 : chercher le réel $\ell$ tel que $\ell=-\frac{2}{3}\ell+\frac{2}{3}$ et étudier la suite $(p_n-\ell)$.
Partie A
-
Degrés : $A$ : $2$, $B$ : $3$, $C$ : $3$, $D$ : $2$. La somme vaut $10$, donc $G$ a $5$ arêtes, ce qui correspond aux $5$ portes. $G$ n'est pas complet : $A$ et $D$ ne sont pas adjacents. Il est connexe : la chaîne $A-B-C-D$ passe par tous les sommets.
-
$$M=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix},\qquad M^2=\begin{pmatrix} 2 & 1 & 1 & 2 \\ 1 & 3 & 2 & 1 \\ 1 & 2 & 3 & 1 \\ 2 & 1 & 1 & 2 \end{pmatrix}.$$ Par exemple, le coefficient $(1,4)$ vaut $0\times 0+1\times 1+1\times 1+0\times 0=2$ (chaînes $A-B-D$ et $A-C-D$) et le coefficient $(2,3)$ vaut $1\times 1+0\times 1+1\times 0+1\times 1=2$ (chaînes $B-A-C$ et $B-D-C$). La diagonale donne les degrés.
-
Le coefficient $(1,4)$ de $M^3$ vaut $2$ : il existe $2$ chaînes de longueur $3$ de $A$ à $D$, à savoir $A-B-C-D$ et $A-C-B-D$. Le coefficient $(2,2)$ vaut $4$ : il existe $4$ chaînes fermées de longueur $3$ partant de $B$ : $B-A-C-B$, $B-C-A-B$, $B-C-D-B$, $B-D-C-B$ (les deux triangles $ABC$ et $BCD$, parcourus dans les deux sens).
Partie B
-
Depuis $A$, les portes mènent en $B$ et en $C$ ; depuis $D$ aussi : depuis l'état $1$, on passe dans l'état $2$ avec probabilité $1$. Depuis $B$, les trois portes mènent en $A$, $C$, $D$ : on va dans l'état $1$ (pièces $A$ ou $D$) avec probabilité $\frac{2}{3}$ et on reste dans l'état $2$ (pièce $C$) avec probabilité $\frac{1}{3}$ ; depuis $C$, les voisins $A$, $B$, $D$ donnent les mêmes probabilités. D'où $$P=\begin{pmatrix} 0 & 1 \\ \frac{2}{3} & \frac{1}{3} \end{pmatrix}.$$
-
Avec $\pi_n=\begin{pmatrix} p_n & 1-p_n \end{pmatrix}$ et $\pi_{n+1}=\pi_nP$, le premier coefficient donne $$p_{n+1}=0\times p_n+\frac{2}{3}(1-p_n)=-\frac{2}{3}p_n+\frac{2}{3}.$$
-
Le réel $\ell$ tel que $\ell=-\frac{2}{3}\ell+\frac{2}{3}$ vérifie $\frac{5}{3}\ell=\frac{2}{3}$, soit $\ell=\frac{2}{5}$. Par soustraction, $p_{n+1}-\frac{2}{5}=-\frac{2}{3}\left(p_n-\frac{2}{5}\right)$ : la suite $\left(p_n-\frac{2}{5}\right)$ est géométrique de raison $-\frac{2}{3}$ et de premier terme $p_0-\frac{2}{5}=1-\frac{2}{5}=\frac{3}{5}$, car le robot part de $A$. Donc $$p_n=\frac{2}{5}+\frac{3}{5}\left(-\frac{2}{3}\right)^n.$$ $p_3=\frac{2}{5}+\frac{3}{5}\times\left(-\frac{8}{27}\right)=\frac{18}{45}-\frac{8}{45}=\frac{2}{9}$. Contrôle avec la récurrence : $p_1=0$, $p_2=\frac{2}{3}$, $p_3=-\frac{4}{9}+\frac{6}{9}=\frac{2}{9}$.
-
Comme $-1<-\frac{2}{3}<1$, $\left(-\frac{2}{3}\right)^n\to 0$, donc $p_n\to\frac{2}{5}$ et $1-p_n\to\frac{3}{5}$. $\pi P=\begin{pmatrix} \frac{2}{5}\times 0+\frac{3}{5}\times\frac{2}{3} & \frac{2}{5}\times 1+\frac{3}{5}\times\frac{1}{3} \end{pmatrix}=\begin{pmatrix} \frac{2}{5} & \frac{3}{5} \end{pmatrix}=\pi$ : $\pi$ est invariante.
-
La somme des degrés de $A$ et $D$ vaut $4$ et la somme de tous les degrés $10$ : le quotient vaut $\frac{4}{10}=\frac{2}{5}$. À long terme, le robot se trouve dans une pièce $A$ ou $D$ avec une probabilité proportionnelle au nombre de portes de ces pièces.
Chaînes de longueur 3 de $A$ à $D$ : 2 ; chaînes fermées depuis $B$ : 4 ; $p_n=\frac{2}{5}+\frac{3}{5}\left(-\frac{2}{3}\right)^n$, $p_3=\frac{2}{9}$, limite $\frac{2}{5}$