preuve-jeff.tex

   1 \documentclass{article}
   2 %\usepackage{prentcsmacro}
   3 %\sloppy
   4 \usepackage[a4paper]{geometry}
   5 \geometry{hmargin=3cm, vmargin=3cm }
   6
   7 \usepackage[latin1]{inputenc}
   8 \usepackage[T1]{fontenc}
   9 \usepackage[english]{babel}
  10 \usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
  11 \usepackage{subfigure,pstricks,pst-node,pst-coil}
  12
  13
  14 \usepackage{url,tikz}
  15 \usepackage{pgflibrarysnakes}
  16
  17 \usepackage{multicol}
  18
  19 \usetikzlibrary{arrows}
  20 \usetikzlibrary{automata}
  21 \usetikzlibrary{snakes}
  22 \usetikzlibrary{shapes}
  23
  24 %% \setlength{\oddsidemargin}{15mm}
  25 %% \setlength{\evensidemargin}{15mm} \setlength{\textwidth}{140mm}
  26 %% \setlength{\textheight}{219mm} \setlength{\topmargin}{5mm}
  27 \newtheorem{theorem}{Theorem}
  28 %\newtheorem{definition}[theorem]{Definition}
  29 % %\newtheorem{defis}[thm]{D\'efinitions}
  30  \newtheorem{example}[theorem]{Example}
  31 % %\newtheorem{Exes}[thm]{Exemples}
  32 \newtheorem{lemma}[theorem]{Lemma}
  33 \newtheorem{proposition}[theorem]{Proposition}
  34 \newtheorem{construction}[theorem]{Construction}
  35 \newtheorem{corollary}[theorem]{Corollary}
  36 % \newtheorem{algor}[thm]{Algorithm}
  37 %\newtheorem{propdef}[thm]{Proposition-D\'efinition}
  38 \newcommand{\mlabel}[1]{\label{#1}\marginpar{\fbox{#1}}}
  39 \newcommand{\flsup}[1]{\stackrel{#1}{\longrightarrow}}
  40
  41 \newcommand{\stirlingtwo}[2]{\genfrac{\lbrace}{\rbrace}{0pt}{}{#1}{#2}}
  42 \newcommand{\stirlingone}[2]{\genfrac{\lbrack}{\rbrack}{0pt}{}{#1}{#2}}
  43
  44 \newenvironment{algo}
  45 { \vspace{1em}
  46 \begin{algor}\mbox
  47 \newline \vspace{-0.1em}
  48 \begin{quote}\begin{rm}}
  49 {\end{rm}\end{quote}\end{algor}\vspace{-1.5em}\vspace{2em}}
  50 %\null \hfill $\diamondsuit$ \par\medskip \vspace{1em}}
  51
  52 \newenvironment{exe}
  53 {\begin{example}\rm }
  54 {\end{example}
  55 %\vspace*{-1.5em}
  56 %\null  \hfill $\triangledown$ \par\medskip}
  57 %\null  \hfill $\triangledown$ \par\medskip \vspace{1em}}
  58 }
  59
  60
  61 \newenvironment{proof}
  62 { \noindent {\sc Proof.\/}  }
  63 {\null  \hfill $\Box$ \par\medskip \vspace{1em}}
  64
  65
  66
  67 \newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
  68 \def \top {1.8}
  69 \def \topt {2.3}
  70 \def \P {\mathbb{P}}
  71 \def \ov {\overline}
  72 \def \ts {\tau_{\rm stop}}
  73 \begin{document}
  74 \label{firstpage}
  75
  76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  77 \section{Mathematical Backgroung}
  78
  79
  80
  81 Let $\pi$, $\mu$ be two distribution on a same set $\Omega$. The total
  82 variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
  83 defined by
  84 $$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ It is known that
  85 $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\mu(x)|.$$ Moreover, if
  86 $\nu$ is a distribution on $\Omega$, one has
  87 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
  88
  89 Let $P$ be the matrix of a markov chain on $\Omega$. $P(x,\cdot)$ is the
  90 distribution induced by the $x$-th row of $P$. If the markov chain induced by
  91 $P$ has a stationary distribution $\pi$, then we define
  92 $$d(t)=\max_{x\in\Omega}\tv{P^t(x,\cdot)-\pi},$$
  93 and
  94
  95 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
  96 One can prove that
  97
  98 $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
  99
 100
 101
 102 %% A {\it coupling} with transition matrix $P$ is a process $(X_t,Y_t)_{t\geq 0}$
 103 %% such that both $(X_t)$ and $(Y_t)$ are markov chains of matric $P$; moreover
 104 %% it is required that if $X_s=Y_s$, then for any $t\geq s$, $X_t=Y_t$.
 105 %% A results provides that if   $(X_t,Y_t)_{t\geq 0}$ is a coupling, then
 106 %% $$d(t)\leq \max_{x,y} P_{x,y}(\{\tau_{\rm couple} \geq t\}),$$
 107 %% with $\tau_{\rm couple}=\min_t\{X_t=Y_t\}$.
 108
 109
 110 Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Omega$ valued random
 111 variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping
 112   time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq
 113 \omega^{t+1}$ such that $\{tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
 114
 115 Let $(X_t)_{t\in \mathbb{N}}$ be a markov chain and $f(X_{t-1},Z_t)$ a
 116 random mapping representation of the markov chain. A {\it randomized
 117   stopping time} for the markov chain is a stopping time for
 118 $(Z_t)_{t\in\mathbb{N}}$. It he markov chain is irreductible and has $\pi$
 119 as stationary distribution, then a {\it stationay time} $\tau$ is a
 120 randomized stopping time (possibily depending on the starting position $x$),
 121 such that  the distribution of $X_\tau$ is $\pi$:
 122 $$\P_x(X_\tau=y)=\pi(y).$$
 123
 124 \begin{proposition}
 125 If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Omega}
 126 \P_x(\tau > t)$.
 127 \end{proposition}
 128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 129 \section{Random walk on the modified Hypercube}
 130
 131
 132 Let $\Omega=\{0,1\}^N$ be the set of words of length $N$. Let $E=\{(x,y)\mid
 133 x\in \Omega, y\in \Omega,\ x=y \text{ or } x\oplus y \in 0^*10^*\}$. Let $h$
 134 be a function from $\Omega$ into $\{1,\ldots,N\}$.
 135
 136 We denote by $E_h$ the set $E\setminus\{(x,y)\mid x\oplus y =
 137 0^{N-h(x)}10^{h(x)-1}\}$. We define the matrix $P_h$ has follows:
 138 $$\left\{
 139 \begin{array}{ll}
 140 P_h(x,y)=0 & \text{ if } (x,y)\notin E_h\\
 141 P_h(x,x)=\frac{1}{2}+\frac{1}{2N} & \\
 142 P_h(x,x)=\frac{1}{2N} & \text{otherwise}\\
 143
 144 \end{array}
 145 \right.
 146 $$
 147
 148 We denote by $\ov{h}$ the function from $\Omega$ into $\omega$ defined
 149 by $x\oplus\ov{h}(x)=0^{N-h(x)}10^{h(x)-1}.$
 150 The function $\ov{h}$ is said {\it square-free} if for every $x\in E$,
 151 $\ov{h}(\ov{h}(x))\neq x$.
 152
 153 \begin{lemma}\label{lm:h}
 154 If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(x))\neq h(x)$.
 155 \end{lemma}
 156
 157 \begin{proof}
 158
 159 \end{proof}
 160
 161 Let $Z$ be a random variable over
 162 $\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we
 163 define, with $Z=(i,x)$,
 164 $$
 165 \left\{
 166 \begin{array}{ll}
 167 f(X,Z)=X\oplus (0^{N-i}10^{i-1}) & \text{if } x=1 \text{ and } i\neq h(X),\\
 168 f(X,Z)=X& \text{otherwise.}
 169 \end{array}\right.
 170 $$
 171
 172
 173
 174 %%%%%%%%%%%%%%%%%%%%%%%%%%%ù
 175 \section{Stopping time}
 176
 177 An integer $\ell\in\{1,\ldots,N\}$ is said {\it fair} at time $t$ if there
 178 exists $0\leq j <t$ such that $Z_j=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
 179
 180
 181 Let $\ts$ be the first time all the elements of $\{1,\ldots,N\}$
 182 are fair. The integer $\ts$ is a randomized stopping time for
 183 the markov chain $(X_t)$.
 184
 185
 186 \begin{lemma}
 187 The integer $\ts$ is a strong stationnary time.
 188 \end{lemma}
 189
 190 \begin{proof}
 191 Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
 192 $Z_{\tau_\ell-1}$ is of the form $(\ell,\delta)$ with $\delta\in\{0,1\}$ and
 193 $\delta=1$ with probability $\frac{1}{2}$ and $\delta=0$ with probability
 194 $\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th
 195 bit of $X_{\tau_\ell}$ is $\delta$. Moving next in the chain, at each step,
 196 the $l$-th bit  is switch from $0$ to $1$ or from $1$ to $0$ each time with
 197 the same probability. Therefore,  for $t\geq \tau_\ell$, the
 198 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
 199 lemma.
 200 \end{proof}
 201
 202 \begin{proposition} \label{prop:stop}
 203 If $\ov{h}$ is bijective and square-free, then
 204 $E[\ts]\leq 8N^2+ N\ln (N+1)$.
 205 \end{proposition}
 206
 207 For each $x\in \Omega$ and $\ell\in\{1,\ldots,N\}$, let $S_{x,\ell}$ be the
 208 random variable counting the number of steps done until reaching from $x$ a state where
 209 $\ell$ is fair. More formaly
 210 $$S_{x,\ell}=\min \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\ell\text{ and } X_0=x\}.$$
 211
 212  We denote by
 213 $$\lambda_h=\max_{x,\ell} S_{x,\ell}.$$
 214
 215
 216 \begin{lemma}\label{prop:lambda}
 217 If $\ov{h}$ is a square-free bijective function, then one has $E[\lambda_h]\leq 8N^2.$
 218 \end{lemma}
 219
 220 \begin{proof}
 221 For every $X$, every $\ell$, one has $\P(S_{X,\ell}\leq 2)\geq
 222 \frac{1}{4N^2}$. Let $X_0=X$. Indeed, if $h(X)\neq \ell$, then
 223 $\P(S_{X,\ell}=1)=\frac{1}{2N}\geq \frac{1}{4N^2}$. If $h(X)=\ell$, then
 224 $\P(S_{X,\ell}=1)=0$. But in this case, intutively, it is possible to move
 225 from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{2N}$). And in
 226 $\ov{h}^{-1}(X)$ the $l$-th bit is switchable. More fromaly,
 227 since $\ov{h}$ is square-free,
 228 $\ov{h}(x)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. It follows
 229 that $(X,\ov{h}^{-1}(X))\in E_h$. We thus have
 230 $P(X_1=\ov{h}^{-1}(X))=\frac{1}{2N}$. Now, by Lemma~\ref{lm:h},
 231 $h(\ov{h}^{-1}(X))\neq h(X)$. Therefore $\P(S_{x,\ell}=2\mid
 232 X_1=\ov{h}^{-1}(X))=\frac{1}{2N}$, proving that $\P(S_{x,\ell}\leq 2)\geq
 233 \frac{1}{4N^2}$.
 234
 235 Therefore, $\P(S_{x,\ell}\geq 3)\leq 1-\frac{1}{4N^2}$. By induction, one
 236 has, for every $i$, $\P(S_{x,\ell}\geq 2i+1)\leq
 237 \left(1-\frac{1}{4N^2}\right)^i$.
 238  Moreover,
 239 since $S_{X,\ell}$ is positive, it is known~\cite[lemma 2.9]{proba}, that
 240 $$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).$$
 241 Since $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, one has
 242 $$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\leq
 243 \P(S_{X,\ell}\geq 1)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq 2i).$$
 244 Consequently,
 245 $$E[S_{x,\ell}]\leq 1+1+2
 246 \sum_{i=1}^{+\infty}\left(1-\frac{1}{4N^2}\right)^i=2+2(4N^2-1)=8N^2,$$
 247 which concludes the proof.
 248 \end{proof}
 249
 250 Let $\ts^\prime$ be the first time that there are exactly $N-1$ fair
 251 elements.
 252
 253 \begin{lemma}\label{lm:stopprime}
 254 One has $E[\ts^\prime]\leq N \ln (N+1).$
 255 \end{lemma}
 256
 257 \begin{proof}
 258 This is a classical  Coupon Collector's like problem. Let $W_i$ be the
 259 random variable counting the number of moves done in the markov chain while
 260 we had exactly $i-1$ fair bits. One has $\ts^\prime=\sum_{i=1}^{N-1}W_i$.
 261  But when we are at position $x$ with $i-1$ fair bits, the probability of
 262  obtaining a new fair bit is either $1-\frac{i-1}{N}$ if $h(x)$ is fair,
 263  or  $1-\frac{i-2}{N}$ if $h(x)$ is not fair. It follows that
 264 $E[W_i]\leq \frac{N}{N-i+2}$. Therefore
 265 $$E[\ts^\prime]=\sum_{i=1}^{N-1}E[W_i]\leq N\sum_{i=1}^{N-1}
 266  \frac{1}{N-i+2}=N\sum_{i=3}^{N+1}\frac{1}{i}.$$
 267
 268 But $\sum_{i=1}^{N+1}\frac{1}{i}\leq 1+\ln(N+1)$. It follows that
 269 $1+\frac{1}{2}+\sum_{i=3}^{N+1}\frac{1}{i}\leq 1+\ln(N+1).$
 270 Consequently,
 271 $E[\ts^\prime]\leq N (-\frac{1}{2}+\ln(N+1))\leq N\ln(N+1)$.
 272 \end{proof}
 273
 274 One can now prove Proposition~\ref{prop:stop}.
 275
 276 \begin{proof}
 277 One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,
 278 Proposition~\ref{prop:stop} is a direct application of
 279 lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
 280 \end{proof}
 281
 282 \end{document}