0&0&0&0&1&0&4&1 \\
0&0&0&1&0&1&0&4
\end{array}
-\right)
+\right).
\]
\end{xpl}
A specific random walk in this modified hypercube is first
introduced (See section~\ref{sub:stop:formal}). We further
-theoretical study this random walk to
-provide a upper bound of fair sequences
+ study this random walk in a theoretical way to
+provide an upper bound of fair sequences
(See section~\ref{sub:stop:bound}).
We finally complete these study with experimental
-results that reduce this bound (Sec.~\ref{sub:stop:stop}).
+results that reduce this bound (Sec.~\ref{sub:stop:exp}).
Notice that for a general references on Markov chains
see~\cite{LevinPeresWilmer2006},
and particularly Chapter~5 on stopping times.
$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.
% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il
-% un intérêt dans la preuve ensuite.}
+% un intérêt dans la preuve ensuite.}
%and
% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% One can prove that \JFc{Ou cela a-t-il été fait?}
+% One can prove that \JFc{Ou cela a-t-il été fait?}
% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
\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}
+\begin{thrm}\label{thm-sst}
If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
\P_X(\tau > t)$.
\end{thrm}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
+%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
%\section{Stopping time}
An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair}
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}
random variable that counts the number of steps
from $X$ until we reach a configuration where
$\ell$ is fair. More formally
-$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.)\text{ and } X_0=X\}.$$
+\[
+\begin{array}{rcl}
+S_{X,\ell}&=&\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.) \\
+&& \qquad \text{ and } X_0=X\}.
+\end{array}
+\]
% We denote by
% $$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$
since $S_{X,\ell}$ is positive, it is known~\cite[lemma 2.9]{proba}, that
$$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).$$
Since $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, one has
-$$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\leq
-\P(S_{X,\ell}\geq 1)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).$$
+\[
+\begin{array}{rcl}
+ E[S_{X,\ell}]&=&\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\\
+&\leq&
+\P(S_{X,\ell}\geq 1) +\P(S_{X,\ell}\geq 2)\\
+&& \qquad +2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).
+\end{array}
+\]
Consequently,
$$E[S_{X,\ell}]\leq 1+1+2
\sum_{i=1}^{+\infty}\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i=2+2(4{\mathsf{N}}^2-1)=8{\mathsf{N}}^2,$$
\begin{proof}
Since $\ts^\prime$ is the time used to obtain $\mathsf{N}-1$ fair bits.
Assume that the last unfair bit is $\ell$. One has
-$\ts=\ts^\prime+S_{X_\tau,\ell}$, and therefore
-$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Therefore,
-Theorem~\ref{prop:stop} is a direct application of
-lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
+$\ts=\ts^\prime+S_{X_\tau,\ell}$, and therefore $E[\ts] =
+E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Therefore, Theorem~\ref{prop:stop} is a
+direct application of lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
\end{proof}
+Now using Markov Inequality, one has $\P_X(\tau > t)\leq \frac{E[\tau]}{t}$.
+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 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)$.
+
+
In this later context, we claim that the upper bound for the stopping time
should be reduced. This fact is studied in the next section.
by calling this code many times with many instances of function and many
seeds.
-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]$
-is executed 10000 times with a random seed. The table~\ref{table:stopping:moy}
-summarizes results. It can be observed that the approximation is largely
-smaller than the upper bound given in theorem~\ref{prop:stop}.
-
\begin{algorithm}[ht]
%\begin{scriptsize}
\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
$\textit{nbit} \leftarrow 0$\;
$x\leftarrow x^0$\;
-$\textit{visited}\leftarrow\emptyset$\;
-
-\While{$\left\vert{\textit{visited}}\right\vert < \mathsf{N} $}
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
{
- $ s \leftarrow \textit{Random}(n)$ \;
+ $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
$\textit{image} \leftarrow f(x) $\;
- \If{$x[s] \neq \textit{image}[s]$}{
- $\textit{visited} \leftarrow \textit{visited} \cup \{s\}$
+ \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+ $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+ $x[s] \leftarrow \textit{image}[s]$\;
}
- $x[s] \leftarrow \textit{image}[s]$\;
$\textit{nbit} \leftarrow \textit{nbit}+1$\;
}
\Return{$\textit{nbit}$}\;
%\end{scriptsize}
-\caption{Pseudo Code of the stoping time calculus}
+\caption{Pseudo Code of stoping time calculus }
\label{algo:stop}
\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]$
+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}$.
+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)$.
-\begin{table}
-$$
-\begin{array}{|*{15}{l|}}
-\hline
-\mathsf{N} & 3 & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\
-\hline
-\mathsf{N} & 3 & 10.9 & 5 & 17.7 & 7& 25 & 9 & 32.7& 11 & 40.8 & 13 & 49.2 & 15 & 16 \\
-\hline
-\end{array}
-$$
-\caption{Average Stopping Time}\label{table:stopping:moy}
-\end{table}
+
+
+% \begin{table}
+% $$
+% \begin{array}{|*{14}{l|}}
+% \hline
+% \mathsf{N} & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\
+% \hline
+% \mathsf{N} & 21.8 & 28.4 & 35.4 & 42.5 & 50 & 57.7 & 65.6& 73.5 & 81.6 & 90 & 98.3 & 107.1 & 115.7 \\
+% \hline
+% \end{array}
+% $$
+% \caption{Average Stopping Time}\label{table:stopping:moy}
+% \end{table}
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{complexity}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End:
