From: couchot Date: Sun, 15 Mar 2015 15:27:08 +0000 (+0100) Subject: modifications de la partie stopping time et calcul de la borne dans les exp X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/f7f2b1f98aa13a31b26d9cdccd417f4f1c44bc8b modifications de la partie stopping time et calcul de la borne dans les exp --- diff --git a/prng.tex b/prng.tex index 8b2f78f..5025b4e 100644 --- a/prng.tex +++ b/prng.tex @@ -86,11 +86,11 @@ Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ &$E[\tau]$\\ \hline %%%%% n= 4 -$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&\\ +$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&154\\ \hline %%%%% n= 5 $\textcircled{b}$& -[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & \\ +[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & 236\\ & 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4] &&&\\ @@ -104,7 +104,7 @@ $\textcircled{b}$& &&&\\ $\textcircled{c}$& 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, -&6&88&\\ +&6&88&335\\ & 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] &&&\\ @@ -121,7 +121,7 @@ $\textcircled{c}$& &&&\\ $\textcircled{d}$& 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66, -&7 & 99&\\ +&7 & 99&450\\ & 101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38, @@ -171,7 +171,7 @@ $\textcircled{d}$& &&&\\ $\textcircled{e}$& 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, -&8&110&\\ +&8&110&582\\ & 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106, &&&\\ diff --git a/stopping.tex b/stopping.tex index 9cc720c..3a07e06 100644 --- 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. - +Notice that for a general references on Markov chains +see~\cite{LevinPeresWilmer2006} +, and particularly Chapter~5 on stopping times. @@ -138,6 +140,9 @@ 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).$$ +A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is +independent of $\tau$. + \begin{thrm} If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} @@ -254,7 +259,7 @@ lemma.\end{proof} \begin{thrm} \label{prop:stop} If $\ov{h}$ is bijective and square-free, then -$E[\ts]\leq 8{\mathsf{N}}^2+ {\mathsf{N}}\ln ({\mathsf{N}}+1)$. +$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$, @@ -264,14 +269,16 @@ 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\}.$$ - We denote by -$$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$ +% We denote by +% $$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$ \begin{lmm}\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. - +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} @@ -284,7 +291,7 @@ 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$. -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, @@ -315,11 +322,10 @@ $$E[S_{X,\ell}]\leq 1+1+2 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{lmm}\label{lm:stopprime} -One has $E[\ts^\prime]\leq {\mathsf{N}} \ln ({\mathsf{N}}+1).$ +One has $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$ \end{lmm} \begin{proof} @@ -328,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, - 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, -$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} -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} @@ -350,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. -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.