[rairo15.git] / stopping.tex

This section considers functions $f: \Bool^n \rightarrow \Bool^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.
 




First of all, let $\pi$, $\mu$ be two distributions on $\Bool^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^n} |\pi(A)-\mu(A)|.$$ It is known that
$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^n}|\pi(X)-\mu(X)|.$$ Moreover, if
$\nu$ is a distribution on $\Bool^n$, one has
$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$

Let $P$ be the matrix of a Markov chain on $\Bool^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^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^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^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).$$


\begin{Theo}
If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^n}
\P_X(\tau > t)$.
\end{Theo}


%Let $\Bool^n$ be the set of words of length $n$. 
Let $E=\{(X,Y)\mid
X\in \Bool^n, Y\in \Bool^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 
$n$-cube. 
Let $h$ be a function from $\Bool^n$ into $\llbracket 1, n \rrbracket$.
Intuitively speaking $h$ aims at memorizing for each node 
$X \in \Bool^n$ which edge is removed in the Hamiltonian cycle,
\textit{i.e.} which bit in $\llbracket 1, n \rrbracket$ 
cannot be switched.



We denote by $E_h$ the set $E\setminus\{(X,Y)\mid X\oplus Y =
0^{n-h(X)}10^{h(X)-1}\}$. This is the set of the modified hypercube, 
\textit{i.e.}, the $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:
$$\left\{
\begin{array}{ll}
P_h(X,X)=\frac{1}{2}+\frac{1}{2n} & \\
P_h(X,Y)=0 & \textrm{if  $(X,Y)\notin E_h$}\\
P_h(X,Y)=\frac{1}{2n} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$}
\end{array}
\right.
$$ 

We denote by $\ov{h} : \Bool^n \rightarrow \Bool^n$ the function 
such that for any $X \in \Bool^n $, 
$(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{n-h(X)}10^{h(X)-1}$. 
The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^n$,
$\ov{h}(\ov{h}(X))\neq X$. 

\begin{Lemma}\label{lm:h}
If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
\end{Lemma}

\begin{proof}
Let $\ov{h}$ be bijective.
Let $k\in \llbracket 1, 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^{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^{n-h(X)}10^{h(X)-1} = 0^{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, n \rrbracket \times \Bool$.
For $X\in \Bool^n$, we
define, with $Z=(i,b)$,  
$$
\left\{
\begin{array}{ll}
f(X,Z)=X\oplus (0^{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,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, n \rrbracket$
are fair. The integer $\ts$ is a randomized stopping time for
the Markov chain $(X_t)$.


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

\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{Theo} \label{prop:stop}
If $\ov{h}$ is bijective and square-free, then
$E[\ts]\leq 8n^2+ n\ln (n+1)$. 
\end{Theo}

For each $X\in \Bool^n$ and $\ell\in\llbracket 1,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{Lemma}\label{prop:lambda}
If $\ov{h}$ is a square-free bijective function, then the inequality 
$E[\lambda_h]\leq 8n^2$ is established.

\end{Lemma}

\begin{proof}
For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq
\frac{1}{4n^2}$. 
Let $X_0= X$.
Indeed, 
\begin{itemize}
\item if $h(X)\neq \ell$, then
$\P(S_{X,\ell}=1)=\frac{1}{2n}\geq \frac{1}{4n^2}$. 
\item otherwise, $h(X)=\ell$, then
$\P(S_{X,\ell}=1)=0$.
But in this case, intutively, 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}{2N}$. 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}{2N}$, proving that $\P(S_{x,\ell}\leq 2)\geq
\frac{1}{4N^2}$.
\end{itemize}




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

Let $\ts^\prime$ be the first time that there are exactly $n-1$ fair
elements. 

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

\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}^{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}{n}$ if $h(X)$ is fair,
 or  $1-\frac{i-2}{n}$ if $h(X)$ is not fair. It follows that 
$E[W_i]\leq \frac{n}{n-i+2}$. Therefore
$$E[\ts^\prime]=\sum_{i=1}^{n-1}E[W_i]\leq n\sum_{i=1}^{n-1}
 \frac{1}{n-i+2}=n\sum_{i=3}^{n+1}\frac{1}{i}.$$

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

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

\begin{proof}
One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,
Theorem~\ref{prop:stop} is a direct application of
lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
\end{proof}