fzf

[16dcc.git] / stopping.tex

Let thus be given such kind of map.
This article focuses on studying its iterations according to
the equation~(\ref{eq:asyn}) with a given strategy.
First of all, this can be interpreted as walking into its iteration graph 
where the choice of the edge to follow is decided by the strategy.
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 \textsc{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}


% % Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
% % which is defined for two distributions $\pi$ and $\mu$ on the same set 
% % $\Bool^n$  by:
% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ 
% % It is known that
% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$

% % Let then $M(x,\cdot)$ be the
% % distribution induced by the $x$-th row of $M$. If the Markov chain
% % induced by
% % $M$ has a stationary distribution $\pi$, then we define
% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
% Intuitively $d(t)$ is the largest deviation between
% the distribution $\pi$ and $M^t(x,\cdot)$, which 
% is the result of iterating $t$ times the function.
% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} 
% with respect to $\varepsilon$ is given by
% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
% It defines the smallest iteration number 
% that is sufficient to obtain a deviation lesser than $\varepsilon$.
% Notice that the upper and lower bounds of mixing times cannot    
% directly be computed with eigenvalues formulae as expressed 
% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work  
% only consider reversible Markov matrices whereas we do no restrict our 
% matrices to such a form.







This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ 
issued from an hypercube where an Hamiltonian path has been removed.
A specific random walk in this modified hypercube is first 
introduced. We further detail
a theoretical study on the length of the path 
which is sufficient to follow to get a uniform distribution.
Notice that for a general references on Markov chains
see~\cite{LevinPeresWilmer2006}
, and particularly Chapter~5 on stopping times.  




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}}$. $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
$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$

and

$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
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).$$

A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
independent of $\tau$. 


\begin{thrm}
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}}$ which 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 {\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 exist 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$.  
 
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}$).

 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
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
$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.)\text{ and } X_0=X\}.$$

%  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
$$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).$$
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}

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 
are more regular and more binding than this constraint.
In this later context, we claim that the upper bound for the stopping time 
should be reduced.