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}}$.
\begin{xpl}
Let us consider for instance
the graph $\Gamma(f)$ defined
-in \textsc{Figure~\ref{fig:iteration:f*}.} and
+in Figure~\ref{fig:iteration:f*} and
the probability function $p$ defined on the set of edges as follows:
$$
p(e) \left\{
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
+introduced (see Section~\ref{sub:stop:formal}). We further
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
+(see Section~\ref{sub:stop:bound}).
+We finally complete this study with experimental
results that reduce this bound (Sec.~\ref{sub:stop:exp}).
-Notice that for a general references on Markov chains
+For a general reference on Markov chains,
see~\cite{LevinPeresWilmer2006},
and particularly Chapter~5 on stopping times.
$\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has
$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
-Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the
-distribution induced by the $X$-th row of $P$. If the Markov chain induced by
-$P$ has a stationary distribution $\pi$, then we define
+Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. For any
+$X\in \Bool^{\mathsf{N}}$, let $P(X,\cdot)$ be the distribution induced by the
+${\rm bin}(X)$-th row of $P$, where ${\rm bin}(X)$ is the integer whose
+binary encoding is $X$. If the Markov chain induced by $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.
+
+Intuitively 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}
${\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,
-\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$
+$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}
An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair}
at time $t$ if there
exists $0\leq j <t$ such that $Z_{j+1}=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
-In other words, there exist a date $j$ before $t$ where
+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
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}.$$
\end{lmm}
\begin{proof}
-For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq
+For every $X$, every $\ell$, one has $\P(S_{X,\ell}\leq 2)\geq
\frac{1}{4{\mathsf{N}}^2}$.
Let $X_0= X$.
Indeed,
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,$$
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}.
+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=32N^2+16N\ln (N+1)$, one obtains: $\P_X(\tau > t)\leq \frac{1}{4}$.
-Therefore, using the defintion of $t_{\rm mix)}$ and
+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)$.
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
-Hamiltonian cylce, the mixing time is in $\Theta(N\ln N)$.
+is obtained using the coarse Markov Inequality. For the
+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)$.
-In this later context, we claim that the upper bound for the stopping time
+In this latter context, we claim that the upper bound for the stopping time
should be reduced. This fact is studied in the next section.
\subsection{Practical Evaluation of Stopping Times}\label{sub:stop:exp}
Let be given a function $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$
and an initial seed $x^0$.
-The pseudo code given in algorithm~\ref{algo:stop} returns the smallest
+The pseudo code given in Algorithm~\ref{algo:stop} returns the smallest
number of iterations such that all elements $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ are fair. It allows to deduce an approximation of $E[\ts]$
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
-wœ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 stopping time computation}
\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 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. 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 to 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
