[16dcc.git] / stopping.tex

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 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}}$. 
Next, if we add probabilities on the transition graph, iterations can be 
interpreted as Markov chains.

\begin{xpl}
Let us consider for instance  
the graph $\Gamma(f)$ defined 
in Figure~\ref{fig:iteration:f*} and 
the probability function $p$ defined on the set of edges as follows:
$$
p(e) \left\{
\begin{array}{ll}
= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
= \frac{1}{6} \textrm{ otherwise.}
\end{array}
\right.  
$$
The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is 
\[
P=\dfrac{1}{6} \left(
\begin{array}{llllllll}
4&1&1&0&0&0&0&0 \\
1&4&0&0&0&1&0&0 \\
0&0&4&1&0&0&1&0 \\
0&1&1&4&0&0&0&0 \\
1&0&0&0&4&0&1&0 \\
0&0&0&0&1&4&0&1 \\
0&0&0&0&1&0&4&1 \\
0&0&0&1&0&1&0&4 
\end{array}
\right).
\]
\end{xpl}


A specific random walk in this modified hypercube is first 
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 this study with experimental
results that reduce this bound (Sec.~\ref{sub:stop:exp}).
For a general reference on Markov chains,
see~\cite{LevinPeresWilmer2006}, 
and particularly Chapter~5 on stopping times.  


\subsection{Formalizing the Random Walk}\label{sub:stop:formal}

First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total
variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
defined by
$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ It is known that
$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreover, if
$\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}}$. 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}(\varepsilon)$ is the time/steps required
to be sure to be $\varepsilon$-close to the stationary distribution, wherever
the chain starts. 



One can prove that

$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$




% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il 
% 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?}
% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$



Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Bool^{\mathsf{N}}$ valued random
variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping
  time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq
(\Bool^{\mathsf{N}})^{t+1}$ such that $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. 
In other words, the event $\{\tau = t \}$ only depends on the values of 
$(X_0,X_1,\ldots,X_t)$, not on $X_k$ with $k > t$. 
 

Let $(X_t)_{t\in \mathbb{N}}$ be a Markov chain and $f(X_{t-1},Z_t)$ a
random mapping representation of the Markov chain. A {\it randomized
  stopping time} for the Markov chain is a stopping time for
$(Z_t)_{t\in\mathbb{N}}$. If the Markov chain is irreducible and has $\pi$
as stationary distribution, then a {\it stationary time} $\tau$ is a
randomized stopping time (possibly depending on the starting position $X$),
such that  the distribution of $X_\tau$ is $\pi$:
$$\P_X(X_\tau=Y)=\pi(Y).$$

\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$. The following result will be useful~\cite[Proposition~6.10]{LevinPeresWilmer2006},


\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}


%Let $\Bool^n$ be the set of words of length $n$. 
Let $E=\{(X,Y)\mid
X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ or } X\oplus Y \in 0^*10^*\}$.
In other words, $E$ is the set of all the edges in the classical 
${\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}}$ 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 $E_h$ the set $E\setminus\{(X,Y)\mid X\oplus Y =
0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. This is the set of the modified hypercube, 
\textit{i.e.}, the ${\mathsf{N}}$-cube where the Hamiltonian cycle $h$ 
has been removed.

We define the Markov matrix $P_h$ for each line $X$ and 
each column $Y$  as follows:
\begin{equation}
\left\{
\begin{array}{ll}
P_h(X,X)=\frac{1}{2}+\frac{1}{2{\mathsf{N}}} & \\
P_h(X,Y)=0 & \textrm{if  $(X,Y)\notin E_h$}\\
P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$}
\end{array}
\right.
\label{eq:Markov:rairo}
\end{equation} 

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 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}
If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
\end{lmm}

\begin{proof}
Let $\ov{h}$ be bijective.
Let $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ s.t. $h(\ov{h}^{-1}(X))=k$.
Then $(\ov{h}^{-1}(X),X)$ belongs to $E$ and 
$\ov{h}^{-1}(X)\oplus X = 0^{{\mathsf{N}}-k}10^{k-1}$.
Let us suppose $h(X) = h(\ov{h}^{-1}(X))$. In such a case, $h(X) =k$.
By definition of $\ov{h}$, $(X, \ov{h}(X)) \in E $ and 
$X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$.
Thus $\ov{h}(X)= \ov{h}^{-1}(X)$, which leads to $\ov{h}(\ov{h}(X))= X$.
This contradicts the square-freeness of $\ov{h}$.
\end{proof}

Let $Z$ be a random variable that is uniformly distributed over
$\llbracket 1, {\mathsf{N}} \rrbracket \times \Bool$.
For $X\in \Bool^{\mathsf{N}}$, we
define, with $Z=(i,b)$,  
$$
\left\{
\begin{array}{ll}
f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if } b=1 \text{ and } i\neq h(X),\\
f(X,Z)=X& \text{otherwise.} 
\end{array}\right.
$$

The Markov chain is thus defined as 
$$
X_t= f(X_{t-1},Z_t)
$$



%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
%\section{Stopping time}

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 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 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
the Markov chain $(X_t)$.


\begin{lmm}
The integer $\ts$ is a strong stationary time.
\end{lmm}

\begin{proof}
Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
$Z_{\tau_\ell}$ is of the form $(\ell,b)$ %with $\delta\in\{0,1\}$ and
such that 
$b=1$ with probability $\frac{1}{2}$ and $b=0$ with probability
$\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th
bit of $X_{\tau_\ell}$ 
is $0$ or $1$ with the same probability ($\frac{1}{2}$).
This probability is independent of the value of the other bits.



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,  and
independently of the value of the other bits, proving the
lemma.\end{proof}

\begin{thrm} \label{prop:stop}
If $\ov{h}$ is bijective and square-free, then
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
\end{thrm}

For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, 
let $S_{X,\ell}$ be the
random variable that counts the number of steps 
from $X$ until we reach a configuration where
$\ell$ is fair. More formally
\[
\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}.$$


\begin{lmm}\label{prop:lambda}
Let $\ov{h}$ is a square-free bijective function. Then
for all $X$ and 
all $\ell$, 
the inequality 
$E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ is established.
\end{lmm}

\begin{proof}
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, 
\begin{itemize}
\item if $h(X)\neq \ell$, then
$\P(S_{X,\ell}=1)=\frac{1}{2{\mathsf{N}}}\geq \frac{1}{4{\mathsf{N}}^2}$. 
\item otherwise, $h(X)=\ell$, then
$\P(S_{X,\ell}=1)=0$.
But in this case, intuitively, it is possible to move
from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{2N}$). And in
$\ov{h}^{-1}(X)$ the $l$-th bit can be switched. 
More formally,
since $\ov{h}$ is square-free,
$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. It follows
that $(X,\ov{h}^{-1}(X))\in E_h$. We thus have
$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$. Now, by Lemma~\ref{lm:h},
$h(\ov{h}^{-1}(X))\neq h(X)$. Therefore $\P(S_{x,\ell}=2\mid
X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$, proving that $\P(S_{x,\ell}\leq 2)\geq
\frac{1}{4{\mathsf{N}}^2}$.
\end{itemize}




Therefore, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. By induction, one
has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq
\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i$.
 Moreover,
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
\[
\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,$$
which concludes the proof.
\end{proof}

Let $\ts^\prime$ be the time used to get all the bits but one fair.

\begin{lmm}\label{lm:stopprime}
One has $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$
\end{lmm}

\begin{proof}
This is a classical  Coupon Collector's like problem. Let $W_i$ be the
random variable counting the number of moves done in the Markov chain while
we had exactly $i-1$ fair bits. One has $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}-1}W_i$.
 But when we are at position $X$ with $i-1$ fair bits, the probability of
 obtaining a new fair bit is either $1-\frac{i-1}{{\mathsf{N}}}$ if $h(X)$ is fair,
 or  $1-\frac{i-2}{{\mathsf{N}}}$ if $h(X)$ is not fair. 

Therefore,
$\P (W_i=k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}}.$
Consequently, we have $\P(W_i\geq k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}-i+1}.$
It follows that $E[W_i]=\sum_{k=1}^{+\infty} \P (W_i\geq k)\leq {\mathsf{N}} \frac{{\mathsf{N}}-i+2}{({\mathsf{N}}-i+1)^2}\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2}$.



It follows that 
$E[W_i]\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2}$. Therefore
$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq 
4{\mathsf{N}}\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{{\mathsf{N}}-i+2}=
4{\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.$$

But $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. It follows that
$1+\frac{1}{2}+\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1).$
Consequently,
$E[\ts^\prime]\leq 
4{\mathsf{N}} (-\frac{1}{2}+\ln({\mathsf{N}}+1))\leq 
4{\mathsf{N}}\ln({\mathsf{N}}+1)$.
\end{proof}

One can now prove Theorem~\ref{prop:stop}.

\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}.
\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 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 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 (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 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 
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.

\begin{algorithm}[ht]
%\begin{scriptsize}
\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
\KwOut{a number of iterations $\textit{nbit}$}

$\textit{nbit} \leftarrow 0$\;
$x\leftarrow x^0$\;
$\textit{fair}\leftarrow\emptyset$\;
\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
{
        $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
        $\textit{image} \leftarrow f(x) $\;
        \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]$\;
          }
        $\textit{nbit} \leftarrow \textit{nbit}+1$\;
}
\Return{$\textit{nbit}$}\;
%\end{scriptsize}
\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}{|*{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: