${\mathsf{N}}$-cube.
Soit $h: \Bool^{\mathsf{N}} \to [{\mathsf{N}}]$
qui mémorise pour chaque n{\oe}ud $X \in \Bool^{\mathsf{N}}$ quel
-arc est supprimée à partir du cycle hamiltonien,
+arc est supprimé à partir du cycle hamiltonien,
\textit{i.e.} quel bit dans $[{\mathsf{N}} ]$
ne peut pas être inversé.
Supposons $h(X) = h(\ov{h}^{-1}(X))$. Dans un tel cas, $h(X) =k$.
Par définition $\ov{h}$, $(X, \ov{h}(X)) \in E $ et
$X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$.
-Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraine $\ov{h}(\ov{h}(X))= X$ et
-qui contredit le fiat que $\ov{h}$ est anti-involutive.
+Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraîne $\ov{h}(\ov{h}(X))= X$ et
+qui contredit le fait que $\ov{h}$ est anti-involutive.
\end{proof}
Soit $Z$ une variable aléatoire suivant une distribution uniforme sur
\left\{
\begin{array}{ll}
f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{ si } b=1 \text{ et } i\neq h(X),\\
-f(X,Z)=X& \text{otherwise.}
+f(X,Z)=X& \text{sinon.}
\end{array}\right.
\]
Un entier $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ est \emph{équitable}
- au temps $t$ s'il existe $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ anérieure à $t$
+ au temps $t$ s'il existe $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ antérieure à $t$
où le premier élément de la variable aléatoire $Z$ est $l$
(\textit{i.e.}, la stratégie vaut $l$ à la date $j$)
et où le n{\oe}ud $X_j$ permet de traverser l'arc $l$.
-Soit $\ts$ le premier tempsoù touis les éléments de $\llbracket 1, {\mathsf{N}} \rrbracket$
-sont équitables. On a le lemme suiant:%L'entier $\ts$ est un temps d'arrêt pour la chaîne de Markov $(X_t)$.
+Soit $\ts$ le premier temps où tous les éléments de $\llbracket 1, {\mathsf{N}} \rrbracket$
+sont équitables. On a le lemme suivant:%L'entier $\ts$ est un temps d'arrêt pour la chaîne de Markov $(X_t)$.
\begin{lemma}
A chaque étape, le $l^{\textrm{ème}}$ bit est inversé de $0$ à $1$ ou de $1$ à $0$, chaque fois avec la même
probabilité. Ainsi, pour $t\geq \tau_\ell$, le
$\ell^{\textrm{ème}}$ bit de $X_t$ est $0$ ou $1$ avec la même probabilité,
-et ce indépendament de la valeur des autres bits.
+et ce indépendamment de la valeur des autres bits.
\end{proof}
Pour chaque $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$,
soit $S_{X,\ell}$ une variable aléatoire qui compte le nombre d'itérations
-tel qu'en démarant de la configuration $X$ on en atteigne une où
+tel qu'en démarrant de la configuration $X$ on en atteigne une où
$\ell$ est équitable. Plus formellement,
$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ et }Z_t=(\ell,.)\text{ et } X_0=X\}.$$
On peut majorer l'espérance de cette variable aléatoire comme suit.
Dans la configuration $X$ avec $i-1$ bits équitables,
la probabilité d'obtenir un nouveau bit équitable est soit
$1-\frac{i-1}{{\mathsf{N}}}$ si $h(X)$ est équitable,
-et $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas.
+soit $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas.
Ainsi,
$\P (W_i=k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}}.$
Tous les éléments sont en place pour majorer l'espérance de $\ts$.
\begin{theorem}
\label{prop:stop}
-Si $\ov{h}$ est bijective et anti involutive
+Si $\ov{h}$ est bijective et anti- involutive
$\ov{h}(\ov{h}(X))\neq X$, alors
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
\end{theorem}
