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
With $t_n=32N^2+16N\ln (N+1)$, one obtains: $\P_X(\tau > t_n)\leq \frac{1}{4}$.
Therefore, using the definition of $t_{\rm mix}$ and
Theorem~\ref{thm-sst}, it follows that
-$t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$.
+$t_{\rm mix}(\frac{1}{4})\leq 32N^2+16N\ln (N+1)=O(N^2)$ and that
+
Notice that the calculus of the stationary time upper bound is obtained
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)$.
