Une marche aléatoire dans un cube

Le point central du problème est que les huit sommets ne jouent pas huit rôles différents. Les permutations des trois axes conservent le cube, le sommet de départ $O$ et le sommet opposé $S$ : elles permettent donc de remplacer les huit sommets par quatre couches.

I — Huit sommets, mais seulement quatre distances

1. (a) Dans le cube unité, deux sommets sont reliés par une arête exactement lorsque leurs coordonnées diffèrent en une seule position : une coordonnée passe de $0$ à $1$ ou de $1$ à $0$, tandis que les deux autres restent inchangées.

À chaque étape, le marcheur choisit donc l’une des trois coordonnées, chacune avec probabilité $1/3$, et la bascule :

$$0\longleftrightarrow1.$$

(b) Soit $V=(x,y,z)$. Chacune des coordonnées égales à $1$ doit être modifiée au moins une fois pour aller de $O=(0,0,0)$ à $V$. Tout chemin utilise donc au moins $x+y+z$ arêtes.

Réciproquement, en modifiant une fois chacune de ces coordonnées, on atteint $V$ en exactement $x+y+z$ étapes. Ainsi

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

(c) Dans le repère orthonormé,

$$OV^2=x^2+y^2+z^2.$$

Or $x,y,z\in\{0,1\}$, donc $x^2=x$, $y^2=y$ et $z^2=z$. Par conséquent

$$OV^2=x+y+z=\delta(V),$$

d’où

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

Les quatre couches correspondent ainsi aux distances euclidiennes $0,1,\sqrt2,\sqrt3$ à $O$.

2. (a) On obtient

$$\mathcal C_0=\{(0,0,0)\},$$ $$\mathcal C_1=\{(1,0,0),(0,1,0),(0,0,1)\},$$ $$\mathcal C_2=\{(1,1,0),(1,0,1),(0,1,1)\},$$

et

$$\mathcal C_3=\{(1,1,1)\}=\{S\}.$$

Leurs nombres d’éléments sont donc respectivement

$$1,\qquad3,\qquad3,\qquad1.$$

(b) Permuter les coordonnées revient à permuter les trois axes du cube. Cette opération conserve les sommets et les arêtes, et fixe $O=(0,0,0)$ ainsi que $S=(1,1,1)$.

Dans $\mathcal C_1$, chaque sommet possède exactement une coordonnée égale à $1$ ; une permutation peut placer ce $1$ dans n’importe quelle position. De même, dans $\mathcal C_2$, une permutation peut envoyer n’importe quelle paire de positions occupées par des $1$ sur n’importe quelle autre. Les couches $\mathcal C_0$ et $\mathcal C_3$ ne contiennent chacune qu’un sommet.

Ainsi, deux sommets d’une même couche se déduisent toujours l’un de l’autre par une permutation des coordonnées.

(c) La règle aléatoire traite les trois directions de la même manière, et les symétries précédentes fixent aussi $O$ et $S$. Deux sommets appartenant à une même couche ont donc exactement le même comportement probabiliste relativement à $O$ et à $S$, à permutation des axes près.

[IDÉE] Les huit sommets peuvent désormais être remplacés par les quatre couches de tailles $1,3,3,1$.

3. (a) Si $D_n=k$, alors $X_n\in\mathcal C_k$. Ses coordonnées $(x,y,z)$ vérifient donc

$$x+y+z=k.$$

Comme elles valent toutes $0$ ou $1$, exactement $k$ coordonnées sont égales à $1$ et $3-k$ sont égales à $0$.

(b) Choisir l’une des $k$ coordonnées égales à $1$ la transforme en $0$ : $D_n$ diminue alors de $1$. Comme chacune des trois coordonnées est choisie avec probabilité $1/3$,

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

De même, choisir l’une des $3-k$ coordonnées égales à $0$ la transforme en $1$, donc

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

(c) Les transitions sont donc

$$0\longrightarrow1\quad(1),$$ $$1\longrightarrow0\quad\left(\frac13\right), \qquad 1\longrightarrow2\quad\left(\frac23\right),$$ $$2\longrightarrow1\quad\left(\frac23\right), \qquad 2\longrightarrow3\quad\left(\frac13\right),$$

et

$$3\longrightarrow2\quad(1).$$

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

4. (a) Une étape retourne exactement une coordonnée. La somme des coordonnées augmente donc de $1$ si l’on retourne un $0$, et diminue de $1$ si l’on retourne un $1$. Ainsi

$$D_{n+1}-D_n\in\{-1,1\}.$$

Comme $D_0=0$, la parité change à chaque étape. On en déduit par récurrence

$$\boxed{D_n\equiv n\pmod2.}$$

(b) Après une étape, $D_1=1$. Depuis le niveau $1$,

$$\mathbb P(D_2=0)=\frac13, \qquad \mathbb P(D_2=2)=\frac23.$$

Pour être au niveau $3$ à l’instant $3$, il faut ensuite effectuer la transition $2\to3$, de probabilité $1/3$. D’où

$$\mathbb P(D_3=3)=\frac23\times\frac13=\frac29.$$

La seule autre valeur possible à l’instant $3$ est $1$, donc

$$\mathbb P(D_3=1)=1-\frac29=\frac79.$$

Ainsi

$$\boxed{\mathbb P(X_3=S)=\frac29,}$$

car $\mathcal C_3=\{S\}$.

(c) Pour aller de $(0,0,0)$ à $(1,1,1)$ en exactement trois étapes, chacune des trois coordonnées doit être retournée exactement une fois. Il y a

$$3!=6$$

ordres possibles parmi les $3^3=27$ suites équiprobables de trois choix. On retrouve

$$\mathbb P(X_3=S)=\frac6{27}=\frac29.$$

5. (a) Depuis $\mathcal C_1$, atteindre $\mathcal C_3$ deux étapes plus tard impose

$$1\longrightarrow2\longrightarrow3.$$

Cette succession a pour probabilité

$$\frac23\times\frac13=\boxed{\frac29}.$$

(b) Depuis $\mathcal C_3$, le premier pas conduit nécessairement à $\mathcal C_2$, puis il faut revenir à $\mathcal C_3$, ce qui a probabilité $1/3$. Ainsi

$$\boxed{\mathbb P(D_{n+2}=3\mid D_n=3)=\frac13.}$$

(c) À l’instant $2k+1$, la parité impose que le marcheur soit dans $\mathcal C_1$ ou dans $\mathcal C_3$. Ces deux événements ont pour probabilités respectives $1-q_k$ et $q_k$.

La formule des probabilités totales donne donc

$$q_{k+1}=\frac29(1-q_k)+\frac13q_k =\boxed{\frac29+\frac19q_k}.$$

Enfin,

$$\boxed{q_0=\mathbb P(X_1=S)=0,}$$

puisque trois changements de coordonnées sont nécessaires pour atteindre $S$ depuis $O$.

6. (a) Le nombre $1/4$ est un point fixe de la récurrence car

$$\frac14=\frac29+\frac19\times\frac14.$$

Ainsi

$$q_{k+1}-\frac14=\frac19\left(q_k-\frac14\right).$$

La suite $v_k=q_k-1/4$ est donc géométrique de raison $1/9$. Comme $v_0=-1/4$,

$$v_k=-\frac{1}{4\,9^k},$$

et finalement

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

(b) Si $n$ est pair, $D_n$ est pair alors que $S$ appartient à $\mathcal C_3$, donc $\mathbb P(X_n=S)=0$. Si $n=2k+1$ est impair, la formule précédente s’applique. Pour tout $n\geqslant0$,

$$\boxed{ \mathbb P(X_n=S)= \begin{cases} 0,& n\text{ pair},\\[4pt] \displaystyle \frac14\left(1-\frac1{9^{(n-1)/2}}\right),& n\text{ impair}. \end{cases}}$$

(c) Pour $n=3$, on trouve

$$\frac14\left(1-\frac19\right)=\frac29,$$

comme à la question 4. Pour $n=5$,

$$\boxed{\mathbb P(X_5=S)=\frac14\left(1-\frac1{81}\right)=\frac{20}{81}.}$$

Enfin,

$$\boxed{\lim_{k\to+\infty}\mathbb P(X_{2k+1}=S)=\frac14.}$$

(d) Aux instants impairs, seuls les trois sommets de $\mathcal C_1$ et le sommet $S$ sont accessibles. Les trois sommets de $\mathcal C_1$ sont symétriques : chacun a donc pour probabilité

$$\frac{1-q_k}{3}\longrightarrow\frac{1-1/4}{3}=\frac14.$$

Les quatre sommets accessibles deviennent donc asymptotiquement équiprobables aux instants impairs.

En revanche, pour tout instant pair,

$$\mathbb P(X_n=S)=0.$$

La sous-suite des instants pairs tend vers $0$ tandis que celle des instants impairs tend vers $1/4$. Par conséquent, la suite complète $\bigl(\mathbb P(X_n=S)\bigr)$ ne converge pas.

[IDÉE] La marche conserve une mémoire très simple de la géométrie du cube : sa parité. À chaque étape, on passe d’une moitié des sommets à l’autre.

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

7. (a) Pour atteindre $S=(1,1,1)$ depuis $O=(0,0,0)$, les trois coordonnées doivent avoir été modifiées un nombre impair de fois. Il faut donc au moins trois étapes. De plus, $S$ se trouve dans la couche $3$, donc la parité de la question 4 impose que tout instant d’arrivée en $S$ soit impair. Ainsi

$$\boxed{T\geqslant3\quad\text{et}\quad T\text{ est impair}.}$$

(b) À l’instant $3$, aucune arrivée antérieure en $S$ n’est possible. Les événements $\{T=3\}$ et $\{X_3=S\}$ coïncident donc, d’où

$$\boxed{\mathbb P(T=3)=\frac29.}$$

À un instant ultérieur, le marcheur peut au contraire avoir déjà visité $S$, l’avoir quitté puis y être revenu. L’événement $\{X_n=S\}$ ne décrit donc plus nécessairement une première arrivée.

(c) Tant que $S$ n’a pas encore été atteint, le marcheur appartient à une couche $\mathcal C_k$ avec $k\in\{0,1,2\}$. Son sommet possède exactement $3-k$ coordonnées égales à $0$. En retournant chacune de ces coordonnées une fois et aucune autre, on atteint $S$ en $3-k$ étapes.

La probabilité de suivre une telle suite déterminée de choix est

$$\left(\frac13\right)^{3-k}.$$

Comme $1\leqslant3-k\leqslant3$,

$$\left(\frac13\right)^{3-k}\geqslant\frac1{27}.$$

Ainsi, depuis tout sommet différent de $S$, la probabilité d’atteindre $S$ au cours des trois prochaines étapes est au moins $1/27$. En répétant ce raisonnement sur des blocs de trois étapes tant que $S$ n’a pas été atteint, la probabilité d’une attente très longue est dominée par une décroissance géométrique. C’est l’idée qui justifie la finitude admise de l’espérance de $T$.

8. (a) Si le marcheur est déjà dans $\mathcal C_3=\{S\}$, aucune étape supplémentaire n’est nécessaire :

$$\boxed{m_3=0.}$$

Depuis $\mathcal C_0$, le premier pas conduit nécessairement à $\mathcal C_1$. Une étape a été effectuée, puis il reste en moyenne $m_1$ étapes :

$$\boxed{m_0=1+m_1.}$$

Depuis $\mathcal C_1$, le premier pas conduit à $\mathcal C_0$ avec probabilité $1/3$ et à $\mathcal C_2$ avec probabilité $2/3$. Ainsi

$$\boxed{m_1=1+\frac13m_0+\frac23m_2.}$$

Enfin, depuis $\mathcal C_2$, le premier pas conduit à $\mathcal C_1$ avec probabilité $2/3$ et à $\mathcal C_3$ avec probabilité $1/3$. Comme $m_3=0$,

$$\boxed{m_2=1+\frac23m_1.}$$

Dans chacune de ces relations, le terme $1$ compte le premier pas qui vient d’être effectué.

(b) En remplaçant $m_0=1+m_1$ et $m_2=1+(2/3)m_1$ dans l’équation de $m_1$, on obtient

$$m_1=1+\frac13(1+m_1)+\frac23\left(1+\frac23m_1\right)=2+\frac79m_1.$$

Donc $(2/9)m_1=2$, soit $m_1=9$. Il vient alors $m_0=10$, $m_2=7$ et, avec $m_3=0$, le système est entièrement résolu.

(c) Le marcheur part de $O$, unique sommet de $\mathcal C_0$. Par définition de $m_0$, on obtient donc directement $\boxed{\mathbb E(T)=10}$.

Sources

[SOURCE] D. A. Levin et Y. Peres, Markov Chains and Mixing Times, 2e édition, pour le contexte général des marches aléatoires sur les graphes : Lien direct.