This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $
issued from an hypercube where an Hamiltonian path has been removed
-as described in previous section.
+as described in the previous section.
Notice that the iteration graph is always a subgraph of
${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the
edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$.
${\mathsf{N}}$-cube.
Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$.
Intuitively speaking $h$ aims at memorizing for each node
-$X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle,
+$X \in \Bool^{\mathsf{N}}$ whose edge is removed in the Hamiltonian cycle,
\textit{i.e.}, which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$
cannot be switched.
We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function
such that for any $X \in \Bool^{\mathsf{N}} $,
$(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
-The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$,
+The function $\ov{h}$ is said to be {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$,
$\ov{h}(\ov{h}(X))\neq X$.
\begin{lmm}\label{lm:h}
In other words, there exists a date $j$ before $t$ where
the first element of the random variable $Z$ is exactly $l$
(\textit{i.e.}, $l$ is the strategy at date $j$)
-and where the configuration $X_j$ allows to traverse the edge $l$.
+and where the configuration $X_j$ allows to cross the edge $l$.
Let $\ts$ be the first time all the elements of $\llbracket 1, {\mathsf{N}} \rrbracket$
are fair. The integer $\ts$ is a randomized stopping time for
are more regular and more binding than this constraint.
Moreover, the bound
is obtained using the coarse Markov Inequality. For the
-classical (lazzy) random walk the $\mathsf{N}$-cube, without removing any
+classical (lazy) random walk the $\mathsf{N}$-cube, without removing any
Hamiltonian cycle, the mixing time is in $\Theta(N\ln N)$.
We conjecture that in our context, the mixing time is also in $\Theta(N\ln
N)$.
\end{algorithm}
Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$,
-10 functions have been generated according to method presented in Section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
+10 functions have been generated according to the method presented in Section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
is executed 10000 times with a random seed. Figure~\ref{fig:stopping:moy}
-summarizes these results. In this one, a circle represents the
+summarizes these results. A circle represents the
approximation of $E[\ts]$ for a given $\mathsf{N}$.
The line is the graph of the function $x \mapsto 2x\ln(2x+8)$.
It can firstly
be observed that the approximation is largely
smaller than the upper bound given in Theorem~\ref{prop:stop}.
It can be further deduced that the conjecture of the previous section
-is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.
+is realistic according to the graph of $x \mapsto 2x\ln(2x+8)$.
