Une marche aléatoire dans un cube

Un marcheur se déplace uniquement sur les sommets d’un cube. À chaque étape, il choisit au hasard l’une des trois arêtes issues du sommet où il se trouve, chacune avec la probabilité $1/3$, indépendamment des choix précédents, puis rejoint l’autre extrémité de cette arête.

On place le cube dans un repère orthonormé : ses sommets ont pour coordonnées les triplets $(x,y,z)$ avec $x,y,z\in\{0,1\}$. Le marcheur part du sommet

$$O=(0,0,0)$$

et l’on s’intéresse au sommet opposé

$$S=(1,1,1).$$

On note $X_n$ le sommet occupé après $n$ étapes, avec $X_0=O$. Aucune théorie des chaînes de Markov ou des graphes n’est supposée : tout ce qui sera utilisé sera construit à partir du cube, des probabilités conditionnelles et des suites.

I — Huit sommets, mais seulement quatre distances

1. Soit $V=(x,y,z)$ un sommet du cube.

(a) Justifier que deux sommets sont reliés par une arête si et seulement si leurs coordonnées diffèrent exactement en une position. En déduire qu’à chaque étape le marcheur choisit l’une des trois coordonnées et remplace $0$ par $1$, ou $1$ par $0$.

(b) On note $\delta(V)$ le nombre minimal d’arêtes à parcourir pour aller de $O$ à $V$. Montrer que

$$\delta(V)=x+y+z.$$

(c) Montrer que la distance euclidienne $OV$ vérifie

$$OV=\sqrt{\delta(V)}.$$

Ainsi, la distance en nombre d’arêtes à $O$ découpe aussi les sommets du cube en couches géométriques autour de $O$.

2. Pour $k\in\{0,1,2,3\}$, on pose

$$\mathcal C_k=\{V\text{ sommet du cube}\mid \delta(V)=k\}.$$

(a) Déterminer explicitement les quatre ensembles $\mathcal C_0,\mathcal C_1,\mathcal C_2,\mathcal C_3$ et leurs nombres d’éléments.

(b) Une permutation des trois coordonnées $(x,y,z)$ laisse le cube inchangé et fixe $O$ ainsi que $S$. Montrer que, pour chaque $k$, deux sommets quelconques de $\mathcal C_k$ se déduisent l’un de l’autre par une telle permutation.

(c) Expliquer pourquoi, pour étudier la marche relativement à $O$ et à $S$, les sommets d’une même couche peuvent être traités de la même façon. C’est le premier gain de symétrie : les huit sommets vont pouvoir être regroupés en quatre états.

3. On pose désormais

$$D_n=\delta(X_n).$$

Supposons que $D_n=k$.

(a) Montrer que le sommet $X_n$ possède exactement $k$ coordonnées égales à $1$ et $3-k$ coordonnées égales à $0$.

(b) En déduire les probabilités conditionnelles

$$\mathbb P(D_{n+1}=k-1\mid D_n=k)=\frac{k}{3},$$

et

$$\mathbb P(D_{n+1}=k+1\mid D_n=k)=\frac{3-k}{3}.$$

(c) Écrire explicitement les transitions possibles depuis chacun des quatre niveaux $0,1,2,3$, avec leurs probabilités.

II — Où est le marcheur après $n$ étapes ?

4. La variable $D_n$ ne peut prendre que les valeurs $0,1,2,3$.

(a) Montrer qu’à chaque étape sa valeur augmente ou diminue de $1$. En déduire que $D_n$ a toujours la même parité que $n$.

(b) Déterminer la loi de $D_2$, puis celle de $D_3$. En déduire

$$\mathbb P(X_3=S)=\frac{2}{9}.$$

(c) Retrouver cette probabilité par un raisonnement de dénombrement : parmi les $3^3$ suites possibles de trois choix de coordonnées, combien conduisent de $O$ à $S$ ?

5. Pour $k\geqslant0$, on définit

$$q_k=\mathbb P(X_{2k+1}=S).$$

À un instant impair, la parité montre que le marcheur se trouve nécessairement dans $\mathcal C_1$ ou dans $\mathcal C_3=\{S\}$.

(a) Si le marcheur est dans $\mathcal C_1$, calculer la probabilité qu’il soit dans $\mathcal C_3$ deux étapes plus tard.

(b) S’il est dans $\mathcal C_3$, calculer la probabilité qu’il soit à nouveau dans $\mathcal C_3$ deux étapes plus tard.

(c) À l’aide de la formule des probabilités totales, établir la relation de récurrence

$$q_{k+1}=\frac{2}{9}+\frac{1}{9}q_k.$$

Déterminer aussi $q_0$.

6. La récurrence précédente contient déjà toute l’évolution aux instants impairs.

(a) Montrer que la suite définie par

$$v_k=q_k-\frac14$$

est géométrique, puis en déduire que, pour tout $k\geqslant0$,

$$q_k=\frac14\left(1-\frac{1}{9^k}\right).$$

(b) Donner une formule de $\mathbb P(X_n=S)$ valable pour tout entier $n\geqslant0$, en distinguant selon la parité de $n$.

(c) Vérifier en particulier la valeur obtenue pour $n=3$, calculer $\mathbb P(X_5=S)$, puis déterminer la limite de $\mathbb P(X_{2k+1}=S)$ lorsque $k$ tend vers l’infini.

(d) Aux instants impairs, les quatre sommets accessibles sont les trois sommets de $\mathcal C_1$ et le sommet $S$. Utiliser la symétrie pour interpréter la limite précédente. La suite complète $\bigl(\mathbb P(X_n=S)\bigr)$ converge-t-elle lorsque $n$ tend vers l’infini ?

III — Être au sommet opposé, ou l’atteindre pour la première fois

7. On note $T$ le nombre d’étapes nécessaires pour atteindre $S$ pour la première fois :

$$T=\min\{n\geqslant0\mid X_n=S\}.$$

(a) Montrer que $T\geqslant3$ et que $T$ est nécessairement impair.

(b) Expliquer pourquoi $\mathbb P(T=3)=2/9$, mais pourquoi, pour un instant ultérieur, la probabilité $\mathbb P(X_n=S)$ ne représente pas en général la probabilité d’atteindre $S$ pour la première fois à l’instant $n$.

(c) Si le marcheur se trouve dans $\mathcal C_k$, montrer qu’il existe un chemin de longueur $3-k$ qui conduit directement à $S$. En déduire que, quel que soit un sommet de départ différent de $S$, la probabilité d’atteindre $S$ au cours des trois prochaines étapes est au moins $1/27$.

Dans la suite, on admettra que cette observation suffit à garantir que le nombre moyen d’étapes avant d’atteindre $S$ est fini.

8. Pour $k\in\{0,1,2,3\}$, on note $m_k$ le nombre moyen d’étapes supplémentaires nécessaires pour atteindre $S$ lorsque le marcheur se trouve dans un sommet de $\mathcal C_k$. La question 2 justifie que ce nombre ne dépend que de $k$, et non du sommet précis de la couche.

(a) Justifier que $m_3=0$. En examinant uniquement le premier pas effectué depuis chacune des couches $\mathcal C_0,\mathcal C_1,\mathcal C_2$, établir

$$m_0=1+m_1,$$ $$m_1=1+\frac13m_0+\frac23m_2,$$

et

$$m_2=1+\frac23m_1.$$

Dans chaque égalité, expliquer le rôle du terme $1$.

(b) Résoudre ce système et déterminer $m_0,m_1,m_2$.

(c) En déduire la valeur exacte de $\mathbb E(T)$ lorsque le marcheur part de $O$.

Le cube possède huit sommets, mais ses symétries ont ramené toute la marche à quatre couches. La parité a encore réduit l’étude à deux états aux instants impairs, puis les mêmes quatre couches ont suffi pour calculer un temps moyen de première atteinte. La géométrie n’était donc pas un décor : c’est elle qui a rendu les probabilités calculables exactement.