X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/e4f6e60e4d2af88e0e16f2d680cf4fe3725ea1fc..5e3dba6ade7cdb2d622eec1fd7d7ef5a0a168b4d:/stopping.tex

diff --git a/stopping.tex b/stopping.tex
index 25e458d..e413688 100644
--- 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}
-= \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 
 \[
-P=\dfrac{1}{3} \left(
+P=\dfrac{1}{6} \left(
 \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)
 \]
@@ -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\}.$$
-% 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 
-% 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\}.$$
-% 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})$$
 
 
@@ -167,9 +167,9 @@ We define the Markov matrix $P_h$ for each line $X$ and
 each column $Y$  as follows:
 $$\left\{
 \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)=\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.
 $$ 
@@ -197,14 +197,13 @@ This contradicts the square-freeness of $\ov{h}$.
 \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
-define, with $Z=i$,  
+define, with $Z=(i,b)$,  
 $$
 \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.
 $$
@@ -216,14 +215,14 @@ $$
 
 
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
+%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
 %\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$.  
  
@@ -238,11 +237,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
-$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}$).
 
@@ -254,7 +252,7 @@ lemma.\end{proof}
 
 \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$, 
@@ -262,7 +260,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
-$$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}.$$
@@ -270,39 +268,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 
-$E[\lambda_h]\leq 2{\mathsf{N}}^2$ is established.
+$E[\lambda_h]\leq 8{\mathsf{N}}^2$ is established.
 
 \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
-$\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, intuitively, it is possible to move
-from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{N}$). And in
+But in this case, intutively, 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
-$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
-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}
 
 
 
 
-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
-\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).$$
@@ -311,7 +309,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
-\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}
 
@@ -319,49 +317,24 @@ Let $\ts^\prime$ be the first time that there are exactly ${\mathsf{N}}-1$ fair
 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}
-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 occurs 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}.
@@ -375,7 +348,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. 
-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.