ajout espace bib

[rairo15.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index e4136889a4471c8ddaa8fe68bb5245fa4878a646..3a07e06a67fc073968d7355d2bff8196d485c29f 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -81,7 +81,9 @@ 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.
 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.  

 
 
 
 
 
 


@@ -138,11 +140,14 @@ 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).$$
 
 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{Theo}
+\begin{thrm}

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

-\end{Theo}
+\end{thrm}

 
 
 %Let $\Bool^n$ be the set of words of length $n$. 
 
 
 %Let $\Bool^n$ be the set of words of length $n$. 


@@ -165,14 +170,16 @@ has been removed.
 
 We define the Markov matrix $P_h$ for each line $X$ and 
 each column $Y$  as follows:
 
 We define the Markov matrix $P_h$ for each line $X$ and 
 each column $Y$  as follows:

-$$\left\{
+\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.
 \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}} $, 
 
 We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function 
 such that for any $X \in \Bool^{\mathsf{N}} $, 


@@ -180,9 +187,9 @@ $(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$. 
 
 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{Lemma}\label{lm:h}
+\begin{lmm}\label{lm:h}

 If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
 If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.

-\end{Lemma}
+\end{lmm}

 
 \begin{proof}
 Let $\ov{h}$ be bijective.
 
 \begin{proof}
 Let $\ov{h}$ be bijective.


@@ -231,9 +238,9 @@ are fair. The integer $\ts$ is a randomized stopping time for
 the Markov chain $(X_t)$.
 
 
 the Markov chain $(X_t)$.
 
 

-\begin{Lemma}
+\begin{lmm}

 The integer $\ts$ is a strong stationary time.
 The integer $\ts$ is a strong stationary time.

-\end{Lemma}
+\end{lmm}

 
 \begin{proof}
 Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
 
 \begin{proof}
 Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable


@@ -250,10 +257,10 @@ 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}
 
 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
 lemma.\end{proof}
 

-\begin{Theo} \label{prop:stop}
+\begin{thrm} \label{prop:stop}

 If $\ov{h}$ is bijective and square-free, then
 If $\ov{h}$ is bijective and square-free, then

-$E[\ts]\leq 8{\mathsf{N}}^2+ {\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
-\end{Theo}
+$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
 
 For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, 
 let $S_{X,\ell}$ be the


@@ -262,15 +269,17 @@ 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\}.$$
 
 $\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}.$$
-
+%  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 8{\mathsf{N}}^2$ is established.

 
 

-\end{Lemma}
+\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
 
 \begin{proof}
 For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq


@@ -282,17 +291,17 @@ Indeed,
 $\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$.
 $\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, intutively, it is possible to move
+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
 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},
+$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
 $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}$.
+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}
 
 
 \end{itemize}
 
 


@@ -313,12 +322,11 @@ $$E[S_{X,\ell}]\leq 1+1+2
 which concludes the proof.
 \end{proof}
 
 which concludes the proof.
 \end{proof}
 

-Let $\ts^\prime$ be the first time that there are exactly ${\mathsf{N}}-1$ fair
-elements. 
+Let $\ts^\prime$ be the time used to get all the bits but one fair.

 
 

-\begin{Lemma}\label{lm:stopprime}
-One has $E[\ts^\prime]\leq {\mathsf{N}} \ln ({\mathsf{N}}+1).$
-\end{Lemma}
+\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
 
 \begin{proof}
 This is a classical  Coupon Collector's like problem. Let $W_i$ be the


@@ -326,21 +334,36 @@ 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,
 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. It follows that 
-$E[W_i]\leq \frac{{\mathsf{N}}}{{\mathsf{N}}-i+2}$. Therefore
-$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq {\mathsf{N}}\sum_{i=1}^{{\mathsf{N}}-1}
- \frac{1}{{\mathsf{N}}-i+2}={\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.$$
+ 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,
 
 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 {\mathsf{N}} (-\frac{1}{2}+\ln({\mathsf{N}}+1))\leq {\mathsf{N}}\ln({\mathsf{N}}+1)$.
+$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}
 \end{proof}
 
 One can now prove Theorem~\ref{prop:stop}.
 
 \begin{proof}

-One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,
+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}
 Theorem~\ref{prop:stop} is a direct application of
 lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
 \end{proof}


@@ -348,7 +371,7 @@ lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
 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. 
 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 
+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.
 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.