stopping.tex

   1
   2
   3 %% A {\it coupling} with transition matrix $P$ is a process $(X_t,Y_t)_{t\geq 0}$
   4 %% such that both $(X_t)$ and $(Y_t)$ are markov chains of matric $P$; moreover
   5 %% it is required that if $X_s=Y_s$, then for any $t\geq s$, $X_t=Y_t$.
   6 %% A results provides that if   $(X_t,Y_t)_{t\geq 0}$ is a coupling, then
   7 %% $$d(t)\leq \max_{x,y} P_{x,y}(\{\tau_{\rm couple} \geq t\}),$$
   8 %% with $\tau_{\rm couple}=\min_t\{X_t=Y_t\}$.
   9
  10
  11 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  12 \section{Random walk on the modified Hypercube}
  13
  14
  15 Let $\Omega=\{0,1\}^N$ be the set of words of length $N$. Let $E=\{(x,y)\mid
  16 x\in \Omega, y\in \Omega,\ x=y \text{ or } x\oplus y \in 0^*10^*\}$. Let $h$
  17 be a function from $\Omega$ into $\{1,\ldots,N\}$.
  18
  19 We denote by $E_h$ the set $E\setminus\{(x,y)\mid x\oplus y =
  20 0^{N-h(x)}10^{h(x)-1}\}$. We define the matrix $P_h$ has follows:
  21 $$\left\{
  22 \begin{array}{ll}
  23 P_h(x,y)=0 & \text{ if } (x,y)\notin E_h\\
  24 P_h(x,x)=\frac{1}{2}+\frac{1}{2N} & \\
  25 P_h(x,x)=\frac{1}{2N} & \text{otherwise}\\
  26
  27 \end{array}
  28 \right.
  29 $$
  30
  31 We denote by $\ov{h}$ the function from $\Omega$ into $\omega$ defined
  32 by $x\oplus\ov{h}(x)=0^{N-h(x)}10^{h(x)-1}.$
  33 The function $\ov{h}$ is said {\it square-free} if for every $x\in E$,
  34 $\ov{h}(\ov{h}(x))\neq x$.
  35
  36 \begin{Lemma}\label{lm:h}
  37 If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(x))\neq h(x)$.
  38 \end{Lemma}
  39
  40 \begin{Proof}
  41
  42 \end{Proof}
  43
  44 Let $Z$ be a random variable over
  45 $\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we
  46 define, with $Z=(i,x)$,
  47 $$
  48 \left\{
  49 \begin{array}{ll}
  50 f(X,Z)=X\oplus (0^{N-i}10^{i-1}) & \text{if } x=1 \text{ and } i\neq h(X),\\
  51 f(X,Z)=X& \text{otherwise.}
  52 \end{array}\right.
  53 $$
  54
  55 The pair $f,Z$ is a random mapping representation of $P_h$.
  56
  57
  58
  59
  60 %%%%%%%%%%%%%%%%%%%%%%%%%%%ù
  61 \section{Stopping time}
  62
  63 An integer $\ell\in\{1,\ldots,N\}$ is said {\it fair} at time $t$ if there
  64 exists $0\leq j <t$ such that $Z_j=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
  65
  66
  67 Let $\ts$ be the first time all the elements of $\{1,\ldots,N\}$
  68 are fair. The integer $\ts$ is a randomized stopping time for
  69 the markov chain $(X_t)$.
  70
  71
  72 \begin{Lemma}
  73 The integer $\ts$ is a strong stationnary time.
  74 \end{Lemma}
  75
  76 \begin{proof}
  77 Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
  78 $Z_{\tau_\ell-1}$ is of the form $(\ell,\delta)$ with $\delta\in\{0,1\}$ and
  79 $\delta=1$ with probability $\frac{1}{2}$ and $\delta=0$ with probability
  80 $\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th
  81 bit of $X_{\tau_\ell}$ is $\delta$. By symetry, for $t\geq \tau_\ell$, the
  82 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
  83 lemma.
  84 \end{proof}
  85
  86 \begin{Theo} \label{prop:stop}
  87 If $\ov{h}$ is bijective and square-free, then
  88 $E[\ts]\leq 8N^2+ N\ln (N+1)$.
  89 \end{Theo}
  90
  91 For each $x\in \Omega$ and $\ell\in\{1,\ldots,N\}$, let $S_{x,\ell}$ be the
  92 random variable counting the number of steps done until reaching from $x$ a state where
  93 $\ell$ is fair. More formaly
  94 $$S_{x,\ell}=\min \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\ell\text{ and } X_0=x\}.$$
  95
  96  We denote by
  97 $$\lambda_h=\max_{x,\ell} S_{x,\ell}.$$
  98
  99
 100 \begin{Lemma}\label{prop:lambda}
 101 If $\ov{h}$ is a square-free bijective function, then one has $E[\lambda_h]\leq 8N^2.$
 102 \end{Lemma}
 103
 104 \begin{proof}
 105 For evey $x$, every $\ell$, one has $\P(S_{x,\ell})\leq 2)\geq
 106 \frac{1}{4N^2}$. Indeed, if $h(x)\neq \ell$, then
 107 $\P(S_{x,\ell}=1)=\frac{1}{2N}\geq \frac{1}{4N^2}$. If $h(x)=\ell$, then
 108 $\P(S_{x,\ell}=1)=0$. Let $X_0=x$. Since $\ov{h}$ is square-free,
 109 $\ov{h}(\ov{h}^{-1}(x))\neq x$. It follows that $(x,\ov{h}^{-1}(x))\in E_h$.
 110 Thefore $P(X_1=\ov{h}^{-1}(x))=\frac{1}{2N}$. Now,
 111 by Lemma~\ref{lm:h},  $h(\ov{h}^{-1}(x))\neq h(x)$. Therefore
 112 $\P(S_{x,\ell}=2\mid X_1=\ov{h}^{-1}(x))=\frac{1}{2N}$, proving that
 113 $\P(S_{x,\ell}\leq 2)\geq \frac{1}{4N^2}$.
 114
 115 Therefore, $\P(S_{x,\ell}\geq 2)\leq 1-\frac{1}{4N^2}$. By induction, one
 116 has, for every $i$, $\P(S_{x,\ell}\geq 2i)\leq
 117 \left(1-\frac{1}{4N^2}\right)^i$.
 118  Moreover,
 119 since $S_{x,\ell}$ is positive, it is known~\cite[lemma 2.9]{}, that
 120 $$E[S_{x,\ell}]=\sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq i).$$
 121 Since $\P(S_{x,\ell}\geq i)\geq \P(S_{x,\ell}\geq i+1)$, one has
 122 $$E[S_{x,\ell}]=\sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq i)\leq
 123 \P(S_{x,\ell}\geq 1)+2 \sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq 2i).$$
 124 Consequently,
 125 $$E[S_{x,\ell}]\leq 1+2
 126 \sum_{i=1}^{+\infty}\left(1-\frac{1}{4N^2}\right)^i=1+2(4N^2-1)=8N^2-2,$$
 127 which concludes the proof.
 128 \end{proof}
 129
 130 Let $\ts^\prime$ be the first time that there are exactly $N-1$ fair
 131 elements.
 132
 133 \begin{Lemma}\label{lm:stopprime}
 134 One has $E[\ts^\prime]\leq N \ln (N+1).$
 135 \end{Lemma}
 136
 137 \begin{proof}
 138 This is a classical  Coupon Collector's like problem. Let $W_i$ be the
 139 random variable counting the number of moves done in the markov chain while
 140 we had exactly $i-1$ fair bits. One has $\ts^\prime=\sum_{i=1}^{N-1}W_i$.
 141  But when we are at position $x$ with $i-1$ fair bits, the probability of
 142  obtaining a new fair bit is either $1-\frac{i-1}{N}$ if $h(x)$ is fair,
 143  or  $1-\frac{i-2}{N}$ if $h(x)$ is not fair. It follows that
 144 $E[W_i]\leq \frac{N}{N-i+2}$. Therefore
 145 $$E[\ts^\prime]=\sum_{i=1}^{N-1}E[W_i]\leq N\sum_{i=1}^{N-1}
 146  \frac{1}{N-i+2}=N\sum_{i=3}^{N+1}\frac{1}{i}.$$
 147
 148 But $\sum_{i=1}^{N+1}\frac{1}{i}\leq 1+\ln(N+1)$. It follows that
 149 $1+\frac{1}{2}+\sum_{i=3}^{N+1}\frac{1}{i}\leq 1+\ln(N+1).$
 150 Consequently,
 151 $E[\ts^\prime]\leq N (-\frac{1}{2}+\ln(N+1))\leq N\ln(N+1)$.
 152 \end{proof}
 153
 154 One can now prove Theo~\ref{prop:stop}.
 155
 156 \begin{proof}
 157 One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,
 158 Theorem~\ref{prop:stop} is a direct application of
 159 lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
 160 \end{proof}
 161
 162 \end{document}