[rairo15.git] / stopping.tex

\documentclass{article}
%\usepackage{prentcsmacro}
%\sloppy
\usepackage[a4paper]{geometry}
\geometry{hmargin=3cm, vmargin=3cm }

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc} 
\usepackage[english]{babel}
\usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
\usepackage{subfigure,pstricks,pst-node,pst-coil}


\usepackage{url,tikz}
\usepackage{pgflibrarysnakes}

\usepackage{multicol}

\usetikzlibrary{arrows}
\usetikzlibrary{automata}
\usetikzlibrary{snakes}
\usetikzlibrary{shapes}

%% \setlength{\oddsidemargin}{15mm}
%% \setlength{\evensidemargin}{15mm} \setlength{\textwidth}{140mm}
%% \setlength{\textheight}{219mm} \setlength{\topmargin}{5mm}
\newtheorem{theorem}{Theorem}
%\newtheorem{definition}[theorem]{Definition}
% %\newtheorem{defis}[thm]{D\'efinitions}
 \newtheorem{example}[theorem]{Example}
% %\newtheorem{Exes}[thm]{Exemples}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{algor}[thm]{Algorithm}
%\newtheorem{propdef}[thm]{Proposition-D\'efinition}
\newcommand{\mlabel}[1]{\label{#1}\marginpar{\fbox{#1}}}
\newcommand{\flsup}[1]{\stackrel{#1}{\longrightarrow}}

\newcommand{\stirlingtwo}[2]{\genfrac{\lbrace}{\rbrace}{0pt}{}{#1}{#2}}
\newcommand{\stirlingone}[2]{\genfrac{\lbrack}{\rbrack}{0pt}{}{#1}{#2}}

\newenvironment{algo}
{ \vspace{1em}
\begin{algor}\mbox
\newline \vspace{-0.1em}
\begin{quote}\begin{rm}} 
{\end{rm}\end{quote}\end{algor}\vspace{-1.5em}\vspace{2em}}
%\null \hfill $\diamondsuit$ \par\medskip \vspace{1em}}

\newenvironment{exe}
{\begin{example}\rm } 
{\end{example}
%\vspace*{-1.5em}
%\null  \hfill $\triangledown$ \par\medskip}
%\null  \hfill $\triangledown$ \par\medskip \vspace{1em}}
}


\newenvironment{proof}
{ \noindent {\sc Proof.\/}  }
{\null  \hfill $\Box$ \par\medskip \vspace{1em}}



\newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
\def \top {1.8}
\def \topt {2.3}
\def \P {\mathbb{P}}
\def \ov {\overline}
\def \ts {\tau_{\rm stop}}
\begin{document}
\label{firstpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Mathematical Backgroung}



Let $\pi$, $\mu$ be two distribution on a same set $\Omega$. The total
variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
defined by
$$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ It is known that
$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\mu(x)|.$$ Moreover, if
$\nu$ is a distribution on $\Omega$, one has
$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$

Let $P$ be the matrix of a markov chain on $\Omega$. $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\Omega}\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)$.


%% A {\it coupling} with transition matrix $P$ is a process $(X_t,Y_t)_{t\geq 0}$
%% such that both $(X_t)$ and $(Y_t)$ are markov chains of matric $P$; moreover
%% it is required that if $X_s=Y_s$, then for any $t\geq s$, $X_t=Y_t$.
%% A results provides that if   $(X_t,Y_t)_{t\geq 0}$ is a coupling, then
%% $$d(t)\leq \max_{x,y} P_{x,y}(\{\tau_{\rm couple} \geq t\}),$$
%% with $\tau_{\rm couple}=\min_t\{X_t=Y_t\}$.


Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Omega$ 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
\omega^{t+1}$ such that $\{tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_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}}$. It he markov chain is irreductible and has $\pi$
as stationary distribution, then a {\it stationay time} $\tau$ is a
randomized stopping time (possibily depending on the starting position $x$),
such that  the distribution of $X_\tau$ is $\pi$:
$$\P_x(X_\tau=y)=\pi(y).$$

\begin{proposition}
If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Omega}
\P_x(\tau > t)$.
\end{proposition}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Random walk on the modified Hypercube}


Let $\Omega=\{0,1\}^N$ be the set of words of length $N$. Let $E=\{(x,y)\mid
x\in \Omega, y\in \Omega,\ x=y \text{ or } x\oplus y \in 0^*10^*\}$. Let $h$
be a function from $\Omega$ into $\{1,\ldots,N\}$.

We denote by $E_h$ the set $E\setminus\{(x,y)\mid x\oplus y =
0^{N-h(x)}10^{h(x)-1}\}$. We define the matrix $P_h$ has follows:
$$\left\{
\begin{array}{ll}
P_h(x,y)=0 & \text{ if } (x,y)\notin E_h\\
P_h(x,x)=\frac{1}{2}+\frac{1}{2N} & \\
P_h(x,x)=\frac{1}{2N} & \text{otherwise}\\

\end{array}
\right.
$$ 

We denote by $\ov{h}$ the function from $\Omega$ into $\omega$ defined
by $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 E$,
$\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}

\end{proof}

Let $Z$ be a random variable over
$\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we
define, with $Z=(i,x)$,  
$$
\left\{
\begin{array}{ll}
f(X,Z)=X\oplus (0^{N-i}10^{i-1}) & \text{if } x=1 \text{ and } i\neq h(X),\\
f(X,Z)=X& \text{otherwise.} 
\end{array}\right.
$$

The pair $f,Z$ is a random mapping representation of $P_h$.




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

An integer $\ell\in\{1,\ldots,N\}$ is said {\it fair} at time $t$ if there
exists $0\leq j <t$ such that $Z_j=(\ell,\cdot)$ and $h(X_j)\neq \ell$.

 
Let $\ts$ be the first time all the elements of $\{1,\ldots,N\}$
are fair. The integer $\ts$ is a randomized stopping time for
the markov chain $(X_t)$.


\begin{lemma}
The integer $\ts$ is a strong stationnary time.
\end{lemma}

\begin{proof}
Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
$Z_{\tau_\ell-1}$ is of the form $(\ell,\delta)$ with $\delta\in\{0,1\}$ and
$\delta=1$ with probability $\frac{1}{2}$ and $\delta=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 $\delta$. By symetry, 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{proposition} \label{prop:stop}
If $\ov{h}$ is bijective and square-free, then
$E[\ts]\leq 8N^2+ N\ln (N+1)$. 
\end{proposition}

For each $x\in \Omega$ and $\ell\in\{1,\ldots,N\}$, let $S_{x,\ell}$ be the
random variable counting the number of steps done until reaching from $x$ a state where
$\ell$ is fair. More formaly
$$S_{x,\ell}=\min \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\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 one has $E[\lambda_h]\leq 8N^2.$
\end{lemma}

\begin{proof}
For evey $x$, every $\ell$, one has $\P(S_{x,\ell})\leq 2)\geq
\frac{1}{4N^2}$. Indeed, if $h(x)\neq \ell$, then
$\P(S_{x,\ell}=1)=\frac{1}{2N}\geq \frac{1}{4N^2}$. If $h(x)=\ell$, then
$\P(S_{x,\ell}=1)=0$. Let $X_0=x$. Since $\ov{h}$ is square-free,
$\ov{h}(\ov{h}^{-1}(x))\neq x$. It follows that $(x,\ov{h}^{-1}(x))\in E_h$.
Thefore $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}$.

Therefore, $\P(S_{x,\ell}\geq 2)\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]{}, 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)+2 \sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq 2i).$$
Consequently,
$$E[S_{x,\ell}]\leq 1+2
\sum_{i=1}^{+\infty}\left(1-\frac{1}{4N^2}\right)^i=1+2(4N^2-1)=8N^2-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 Proposition~\ref{prop:stop}.

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

\end{document}