reprise de l'intro

[rairo15.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index faab606dd0dc97fd112af62443d322ca9c1d906b..d3b4f4d4c1ff44127c30b3dcd93765f54aa2e367 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -20,23 +20,23 @@ the probability function $p$ defined on the set of edges as follows:
 $$
 p(e) \left\{
 \begin{array}{ll}
 $$
 p(e) \left\{
 \begin{array}{ll}

-= \frac{1}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
-= \frac{1}{3} \textrm{ otherwise.}
+= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
+= \frac{1}{6} \textrm{ otherwise.}

 \end{array}
 \right.  
 $$
 The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is 
 \[
 \end{array}
 \right.  
 $$
 The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is 
 \[

-P=\dfrac{1}{3} \left(
+P=\dfrac{1}{6} \left(

 \begin{array}{llllllll}
 \begin{array}{llllllll}

-1&1&1&0&0&0&0&0 \\
-1&1&0&0&0&1&0&0 \\
-0&0&1&1&0&0&1&0 \\
-0&1&1&1&0&0&0&0 \\
-1&0&0&0&1&0&1&0 \\
-0&0&0&0&1&1&0&1 \\
-0&0&0&0&1&0&1&1 \\
-0&0&0&1&0&1&0&1 
+4&1&1&0&0&0&0&0 \\
+1&4&0&0&0&1&0&0 \\
+0&0&4&1&0&0&1&0 \\
+0&1&1&4&0&0&0&0 \\
+1&0&0&0&4&0&1&0 \\
+0&0&0&0&1&4&0&1 \\
+0&0&0&0&1&0&4&1 \\
+0&0&0&1&0&1&0&4 

 \end{array}
 \right)
 \]
 \end{array}
 \right)
 \]


@@ -102,21 +102,21 @@ $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$
 and
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 and
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$

-% One can prove that
+One can prove that

 
 

-% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
+$$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 
 
 
 
 
 % It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il 

-% un intérêt dans la preuve ensuite.}
+% un intérêt dans la preuve ensuite.}

 
 
 
 %and
 % $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 
 
 
 %and
 % $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$

-% One can prove that \JFc{Ou cela a-t-il été fait?}
+% 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})$$
 
 
 % $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
 
 


@@ -165,14 +165,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}
 \begin{array}{ll}

-P_h(X,X)=\frac{1}{{\mathsf{N}}} & \\
+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)=0 & \textrm{if  $(X,Y)\notin E_h$}\\

-P_h(X,Y)=\frac{1}{{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in 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.
 \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}} $, 


@@ -197,14 +199,13 @@ This contradicts the square-freeness of $\ov{h}$.
 \end{proof}
 
 Let $Z$ be a random variable that is uniformly distributed over
 \end{proof}
 
 Let $Z$ be a random variable that is uniformly distributed over

-$\llbracket 1, {\mathsf{N}}$.
+$\llbracket 1, {\mathsf{N}} \rrbracket \times \Bool$.

 For $X\in \Bool^{\mathsf{N}}$, we
 For $X\in \Bool^{\mathsf{N}}$, we

-define, with $Z=i$,  
+define, with $Z=(i,b)$,  

 $$
 \left\{
 \begin{array}{ll}
 $$
 \left\{
 \begin{array}{ll}

-%f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if } b=1 \text{ and } i\neq h(X),\\
-f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if $i\neq h(X)$},\\
+f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if } b=1 \text{ and } i\neq h(X),\\

 f(X,Z)=X& \text{otherwise.} 
 \end{array}\right.
 $$
 f(X,Z)=X& \text{otherwise.} 
 \end{array}\right.
 $$


@@ -216,14 +217,14 @@ $$
 
 
 
 
 
 

-%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
+%%%%%%%%%%%%%%%%%%%%%%%%%%%ù

 %\section{Stopping time}
 
 An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair} 
 at time $t$ if there
 %\section{Stopping time}
 
 An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair} 
 at time $t$ if there

-exists $0\leq j <t$ such that $Z_{j+1}=\ell$ and $h(X_j)\neq \ell$.
-In other words, there exist a date $j$ before $t$ where
-the random variable $Z$ is  $l$ 
+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$.  
  
 (\textit{i.e.}, $l$ is the strategy at date $j$) 
 and where the configuration $X_j$ allows to traverse the edge $l$.  
  


@@ -238,11 +239,10 @@ The integer $\ts$ is a strong stationary time.
 
 \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

-$Z_{\tau_\ell}$ is of the form $\ell$ %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
+$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}$).
 
 bit of $X_{\tau_\ell}$ 
 is $0$ or $1$ with the same probability ($\frac{1}{2}$).
 


@@ -254,7 +254,7 @@ lemma.\end{proof}
 
 \begin{Theo} \label{prop:stop}
 If $\ov{h}$ is bijective and square-free, then
 
 \begin{Theo} \label{prop:stop}
 If $\ov{h}$ is bijective and square-free, then

-$E[\ts]\leq {\mathsf{N}}^2+ (\mathsf{N}+2)(\ln(\mathsf{N})+2)$. 
+$E[\ts]\leq 8{\mathsf{N}}^2+ {\mathsf{N}}\ln ({\mathsf{N}}+1)$. 

 \end{Theo}
 
 For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, 
 \end{Theo}
 
 For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, 


@@ -262,7 +262,7 @@ 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
 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\}.$$
+$$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}.$$


@@ -270,39 +270,39 @@ $$\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 
 
 \begin{Lemma}\label{prop:lambda}
 If $\ov{h}$ is a square-free bijective function, then the inequality 

-$E[\lambda_h]\leq 2{\mathsf{N}}^2$ is established.
+$E[\lambda_h]\leq 8{\mathsf{N}}^2$ is established.

 
 \end{Lemma}
 
 \begin{proof}
 
 \end{Lemma}
 
 \begin{proof}

-For every $X$, every $\ell$, one has $\P(S_{X,\ell}\leq 2)\geq
-\frac{1}{{\mathsf{N}}^2}$. 
+For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq
+\frac{1}{4{\mathsf{N}}^2}$. 

 Let $X_0= X$.
 Indeed, 
 \begin{itemize}
 \item if $h(X)\neq \ell$, then
 Let $X_0= X$.
 Indeed, 
 \begin{itemize}
 \item if $h(X)\neq \ell$, then

-$\P(S_{X,\ell}=1)=\frac{1}{{\mathsf{N}}}\geq \frac{1}{{\mathsf{N}}^2}$. 
+$\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
 \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}{N}$). And in
+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
 $\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}{{\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}{{\mathsf{N}}}$, proving that $\P(S_{x,\ell}\leq 2)\geq
-\frac{1}{{\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}
 
 
 
 

-Therefore, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{{\mathsf{N}}^2}$. By induction, one
+Therefore, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. By induction, one

 has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq
 has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq

-\left(1-\frac{1}{{\mathsf{N}}^2}\right)^i$.
+\left(1-\frac{1}{4{\mathsf{N}}^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).$$
  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).$$


@@ -311,7 +311,7 @@ $$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
 \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}{{\mathsf{N}}^2}\right)^i=2+2({\mathsf{N}}^2-1)=2{\mathsf{N}}^2,$$
+\sum_{i=1}^{+\infty}\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i=2+2(4{\mathsf{N}}^2-1)=8{\mathsf{N}}^2,$$

 which concludes the proof.
 \end{proof}
 
 which concludes the proof.
 \end{proof}
 


@@ -319,49 +319,24 @@ Let $\ts^\prime$ be the first time that there are exactly ${\mathsf{N}}-1$ fair
 elements. 
 
 \begin{Lemma}\label{lm:stopprime}
 elements. 
 
 \begin{Lemma}\label{lm:stopprime}

-One has $E[\ts^\prime]\leq (\mathsf{N}+2)(\ln(\mathsf{N})+2)$.
+One has $E[\ts^\prime]\leq {\mathsf{N}} \ln ({\mathsf{N}}+1).$

 \end{Lemma}
 
 \begin{proof}
 \end{Lemma}
 
 \begin{proof}

-This is a classical  Coupon Collector's like problem. Let $W_i$ 
-be the time to obtain the $i$-th fair bit
-after $i-1$ fair bits have been obtained.
-One has $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}}W_i$.
-
-At position $X$ with $i-1$ fair bits,
-we  do not obtain a new fair if $Z$ is one of the $i-1$ already fair bits
-or if $Z$ is a new fair bit but $h(X)$ is $Z$.  
-This occures with probability 
-$p 
-= \frac{i-1}{{\mathsf{N}}} + \frac{n-i+1}{\mathsf{N}}.\frac{1}{\mathsf{N}}
-=\frac{i(\mathsf{N}-1) +1}{\mathsf{N^2}}
-$. 
-The random variable $W_i$ has a geometric distribution 
-\textit{i.e.}, $P(W_i = k) = p^{k-1}.(1-p)$ and 
-$E(W_i) = \frac{\mathsf{N^2}}{i(\mathsf{N}-1) +1}$.
-Therefore
-$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}}E[W_i]
-=\frac{\mathsf{N^2}}{\mathsf{N}(\mathsf{N}-1) +1}  + \sum_{i=1}^{{\mathsf{N}}-1}E[W_i].$$
-
-A simple study of the function $\mathsf{N} \mapsto \frac{\mathsf{N^2}}{\mathsf{N}(\mathsf{N}-1) +1}$ shows that it is bounded by $\frac{4}{3} \leq 2$.
-For the second term, we successively have 
-$$
-\sum_{i=1}^{{\mathsf{N}}-1}E[W_i] 
-= \mathsf{N}^2\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i(\mathsf{N}-1) +1} 
-\leq \mathsf{N}^2\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i(\mathsf{N}-1)} 
-\leq \frac{\mathsf{N}^2}{\mathsf{N}-1}\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i} 
-\leq (\mathsf{N}+2)\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i} 
-$$
-
-
-It is well known that 
-$\sum_{i=1}^{{\mathsf{N}}-1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}-1)$.
-It follows that
-$2+(\mathsf{N}+2)\sum_{i=1}^{{\mathsf{N}}-1}\frac{1}{i}
-\leq 
-2+(\mathsf{N}+2)(\ln(\mathsf{N}-1)+1)
-\leq 
-(\mathsf{N}+2)(\ln(\mathsf{N})+2)$.
+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}^{{\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}.$$
+
+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)$.

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