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 l’étude des huit sommets par celle de quatre niveaux.

I — Du cube aux quatre niveaux

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 remplace par son opposée dans $\{0,1\}$ :

$$0\longleftrightarrow1.$$

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

Réciproquement, en modifiant une fois chacune des coordonnées égales à $1$, 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.$$

Comme $x,y,z\in\{0,1\}$, on a $x^2=x$, $y^2=y$ et $z^2=z$. Donc

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

et finalement

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

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) Une permutation des coordonnées permute les trois axes du cube. Elle conserve donc les sommets et les arêtes, et elle 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 ensembles $\mathcal C_0$ et $\mathcal C_3$ ne contiennent chacun qu’un sommet.

Deux sommets d’un même $\mathcal C_k$ se déduisent donc l’un de l’autre par une permutation des coordonnées. Comme la règle de la marche traite les trois directions de la même manière, ils ont le même comportement probabiliste vis-à-vis de $O$ et de $S$.

3. Supposons $D_n=k$. Le sommet $X_n$ possède alors exactement $k$ coordonnées égales à $1$ et $3-k$ coordonnées égales à $0$.

Si le marcheur choisit l’une des $k$ coordonnées égales à $1$, celle-ci devient $0$ et $D_n$ diminue de $1$. Si au contraire il choisit l’une des $3-k$ coordonnées égales à $0$, elle devient $1$ et $D_n$ augmente de $1$. Ainsi

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

et

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

Pour les quatre niveaux, cela donne

$$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).$$

4. (a) À chaque étape, $D_n$ augmente ou diminue de $1$. Sa parité change donc à chaque étape. Comme $D_0=0$,

$$\boxed{D_n\equiv n\pmod 2.}$$

(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.$$

À l’instant $3$, la valeur $3$ n’est possible que par le passage

$$1\longrightarrow2\longrightarrow3.$$

On obtient donc

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

La seule autre valeur possible est $1$, d’où

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

Comme $\mathcal C_3=\{S\}$,

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

(c) Pour aller de $(0,0,0)$ à $(1,1,1)$ en exactement trois étapes, chacune des trois coordonnées doit être modifiée exactement une fois. Il y a $3!=6$ ordres possibles parmi les $3^3=27$ suites équiprobables de trois choix. Ainsi

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

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

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

Depuis $\mathcal C_1$, être dans $S$ deux étapes plus tard impose

$$1\longrightarrow2\longrightarrow3,$$

de probabilité

$$\frac23\times\frac13=\frac29.$$

Depuis $S=\mathcal C_3$, le premier pas conduit nécessairement à $\mathcal C_2$, puis le retour à $\mathcal C_3$ a probabilité $1/3$. La probabilité d’être de nouveau dans $S$ deux étapes plus tard vaut donc $1/3$.

À l’instant $2k+1$, les probabilités d’être respectivement dans $\mathcal C_1$ et dans $\mathcal C_3$ sont $1-q_k$ et $q_k$. Par conséquent

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

De plus,

$$q_0=\mathbb P(X_1=S)=0.$$

Pour résoudre la récurrence, on cherche son point fixe $\ell$ :

$$\ell=\frac29+\frac19\ell,$$

d’où $\ell=1/4$. Ainsi

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

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

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

pour tout $k\geqslant0$.

6. (a) Si $n$ est pair, $D_n$ est pair alors que $S$ appartient au niveau $3$, donc

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

Si $n=2k+1$ est impair, la question précédente donne

$$\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}}$$

(b) Pour $n=3$,

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

ce qui redonne le résultat de la question 4. Pour $n=5$,

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

(c) Aux instants pairs,

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

Aux instants impairs,

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

La suite complète ne converge donc pas.

Aux instants impairs, les quatre sommets accessibles sont les trois sommets de $\mathcal C_1$ et le sommet $S$. Les trois sommets de $\mathcal C_1$ sont symétriques. Leur probabilité commune vaut

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

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

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$ appartient au niveau $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 visite antérieure de $S$ n’est possible. Les événements $\{T=3\}$ et $\{X_3=S\}$ coïncident donc. Par conséquent

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

(c) Pour tout instant impair $n>3$, le marcheur peut avoir atteint $S$ avant l’instant $n$, l’avoir quitté, puis être revenu en $S$ à l’instant $n$. Ainsi $\{T=n\}$ impose que l’on soit en $S$ à l’instant $n$, mais l’événement $\{X_n=S\}$ n’impose pas qu’il s’agisse de la première visite.

On a donc, pour tout entier impair $n>3$,

$$\boxed{\{T=n\}\subsetneq\{X_n=S\}.}$$

8. Après une étape, le marcheur est nécessairement dans $\mathcal C_1$. Tant que $S$ n’a pas été atteint, tout instant impair correspond encore à un sommet de $\mathcal C_1$, puisque les seuls niveaux impairs sont $1$ et $3$ et que $\mathcal C_3=\{S\}$.

Depuis $\mathcal C_1$, la probabilité d’atteindre $S$ exactement deux étapes plus tard vaut, comme à la question 5,

$$\frac29.$$

Il est impossible d’atteindre $S$ au premier de ces deux pas, car ce premier pas conduit au niveau $0$ ou au niveau $2$. Si le marcheur n’atteint pas $S$ au second pas, il se retrouve donc à nouveau dans $\mathcal C_1$ à un instant impair. La probabilité de ne pas atteindre $S$ pendant un tel bloc de deux étapes vaut

$$1-\frac29=\frac79.$$

Pour avoir $T=2k+1$, il faut échouer pendant les $k-1$ premiers blocs de deux étapes, puis réussir au bloc suivant. Ainsi, pour tout $k\geqslant1$,

$$\boxed{\mathbb P(T=2k+1)=\left(\frac79\right)^{k-1}\frac29.}$$

Cette formule redonne bien $\mathbb P(T=3)=2/9$ pour $k=1$.

9. (a) Par la symétrie établie à la question 2, deux sommets d’un même niveau ont le même comportement vis-à-vis de $S$. Le nombre moyen d’étapes restantes ne dépend donc que du niveau.

Si le marcheur est déjà en $S=\mathcal C_3$, aucune étape supplémentaire n’est nécessaire :

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

(b) Depuis $\mathcal C_0$, le premier pas mène nécessairement à $\mathcal C_1$. Une étape est consommée, puis il reste en moyenne $m_1$ étapes :

$$m_0=1+m_1.$$

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

$$m_1=1+\frac13m_0+\frac23m_2.$$

Depuis $\mathcal C_2$, le premier pas mène à $\mathcal C_1$ avec probabilité $2/3$ et à $\mathcal C_3$ avec probabilité $1/3$. On obtient donc

$$m_2=1+\frac23m_1+\frac13m_3.$$

Avec $m_3=0$,

$$\boxed{ \begin{cases} m_0=1+m_1,\\ m_1=1+\dfrac13m_0+\dfrac23m_2,\\ m_2=1+\dfrac23m_1,\\ m_3=0. \end{cases}}$$

Le terme $1$ présent dans les trois premières relations compte le premier pas qui vient d’être effectué.

(c) On remplace

$$m_0=1+m_1, \qquad m_2=1+\frac23m_1$$

dans l’équation de $m_1$ :

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

Donc

$$m_1=2+\frac79m_1,$$

et par conséquent

$$\boxed{m_1=9.}$$

On en déduit

$$\boxed{m_0=10}$$

et

$$\boxed{m_2=7.}$$

Le marcheur part de $O\in\mathcal C_0$. Le nombre moyen d’étapes nécessaires pour atteindre $S$ est donc

$$\boxed{\mathbb E(T)=10.}$$

La même réduction géométrique a ainsi servi trois fois : pour calculer une probabilité de position, pour déterminer la loi de la première arrivée et pour obtenir le temps moyen d’atteinte.

Sources

[SOURCE] Levin et Peres — Markov Chains and Mixing Times. Lien direct