0&0&0&0&1&0&4&1 \\
0&0&0&1&0&1&0&4
\end{array}
-\right)
+\right).
\]
\end{xpl}
$P$ has a stationary distribution $\pi$, then we define
$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$
+\ANNOT{incohérence de notation $X$ : entier ou dans $B^N$ ?}
and
$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-Intuitively speaking, $t_{\rm mix}$ is a mixing time
-\textit{i.e.}, is the time until the matrix $X$ of a Markov chain
-is $\epsilon$-close to a stationary distribution.
+%% Intuitively speaking, $t_{\rm mix}$ is a mixing time
+%% \textit{i.e.}, is the time until the matrix $X$ of a Markov chain
+%% is $\epsilon$-close to a stationary distribution.
+
+Intutively speaking, $t_{\rm mix}(\varepsilon)$ is the time/steps required
+to be sure to be $\varepsilon$-close to the stationary distribution, wherever
+the chain starts.
\subsection{Upper bound of Stopping Time}\label{sub:stop:bound}
-
A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
-independent of $\tau$.
+independent of $\tau$. The following result will be useful~\cite[Proposition~6.10]{LevinPeresWilmer2006},
\begin{thrm}\label{thm-sst}
Moving next in the chain, at each step,
the $l$-th bit is switched from $0$ to $1$ or from $1$ to $0$ each time with
the same probability. Therefore, for $t\geq \tau_\ell$, the
-$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
+$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, and
+independently of the value of the other bits, proving the
lemma.\end{proof}
\begin{thrm} \label{prop:stop}
\end{proof}
Now using Markov Inequality, one has $\P_X(\tau > t)\leq \frac{E[\tau]}{t}$.
-With $t=32N^2+16N\ln (N+1)$, one obtains: $\P_X(\tau > t)\leq \frac{1}{4}$.
+With $t_n=32N^2+16N\ln (N+1)$, one obtains: $\P_X(\tau > t_n)\leq \frac{1}{4}$.
Therefore, using the defintion 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)$.
Notice that the calculus of the stationary time upper bound is obtained
under the following constraint: for each vertex in the $\mathsf{N}$-cube
there are one ongoing arc and one outgoing arc that are removed.
-The calculus does not consider (balanced) Hamiltonian cycles, which
+The calculus doesn't consider (balanced) Hamiltonian cycles, which
are more regular and more binding than this constraint.
Moreover, the bound
-is obtained using Markov Inequality which is frequently coarse. For the
-classical random walkin the $\mathsf{N}$-cube, without removing any
+is obtained using the coarse Markov Inequality. For the
+classical (lazzy) random walk the $\mathsf{N}$-cube, without removing any
Hamiltonian cylce, 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 generaed 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 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. The Figure~\ref{fig:stopping:moy}
summarizes these results. In this one, a circle represents the
approximation of $E[\ts]$ for a given $\mathsf{N}$.
