Ajout diapos présentation PRNG

[16dcc.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index aa13c9ab8812ba567820cbfe01c38196ecbbe83a..142da7f9afc3f748cbeed7447e5813fd068e1534 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -10,7 +10,7 @@ interpreted as Markov chains.
 \begin{xpl}
 Let us consider for instance  
 the graph $\Gamma(f)$ defined 
 \begin{xpl}
 Let us consider for instance  
 the graph $\Gamma(f)$ defined 

-in \textsc{Figure~\ref{fig:iteration:f*}.} and 
+in Figure~\ref{fig:iteration:f*} and 

 the probability function $p$ defined on the set of edges as follows:
 $$
 p(e) \left\{
 the probability function $p$ defined on the set of edges as follows:
 $$
 p(e) \left\{


@@ -39,13 +39,13 @@ P=\dfrac{1}{6} \left(
 
 
 A specific random walk in this modified hypercube is first 
 
 
 A specific random walk in this modified hypercube is first 

-introduced (See section~\ref{sub:stop:formal}). We further 
+introduced (see Section~\ref{sub:stop:formal}). We further 

  study this random walk in a theoretical way to 
 provide an upper bound of fair sequences 
  study this random walk in a theoretical way to 
 provide an upper bound of fair sequences 

-(See section~\ref{sub:stop:bound}).
-We finally complete these study with experimental
+(see Section~\ref{sub:stop:bound}).
+We finally complete this study with experimental

 results that reduce this bound (Sec.~\ref{sub:stop:exp}).
 results that reduce this bound (Sec.~\ref{sub:stop:exp}).

-Notice that for a general references on Markov chains
+For a general reference on Markov chains,

 see~\cite{LevinPeresWilmer2006}, 
 and particularly Chapter~5 on stopping times.  
 
 see~\cite{LevinPeresWilmer2006}, 
 and particularly Chapter~5 on stopping times.  
 


@@ -60,11 +60,14 @@ $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreov
 $\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has
 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
 
 $\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has
 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
 

-Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the
-distribution induced by the $X$-th row of $P$. If the Markov chain induced by
-$P$ has a stationary distribution $\pi$, then we define
+Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. For any
+$X\in \Bool^{\mathsf{N}}$, let $P(X,\cdot)$ be the distribution induced by the
+${\rm bin}(X)$-th row of $P$, where ${\rm bin}(X)$ is the integer whose
+binary encoding is $X$. If the Markov chain induced by $P$ has a stationary
+distribution $\pi$, then we define

 $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$
 
 $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$
 

+%\ANNOT{incohérence de notation $X$ : entier ou dans $B^N$ ?}

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


@@ -73,8 +76,8 @@ $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 %% \textit{i.e.}, is the time until the matrix $X$ of a Markov chain  
 %% is $\epsilon$-close to a stationary distribution.
 
 %% \textit{i.e.}, is the time until the matrix $X$ of a Markov chain  
 %% is $\epsilon$-close to a stationary distribution.
 

-Intutively speaking,  $t_{\rm mix}(\varepsilon)$ is the time/steps required
-to be sure to be $\varepsilon$-close to the staionary distribution, wherever
+Intuitively speaking,  $t_{\rm mix}(\varepsilon)$ is the time/steps required
+to be sure to be $\varepsilon$-close to the stationary distribution, wherever

 the chain starts. 
 
 
 the chain starts. 
 
 


@@ -117,7 +120,6 @@ $$\P_X(X_\tau=Y)=\pi(Y).$$
 
 \subsection{Upper bound of Stopping Time}\label{sub:stop:bound}
 
 
 \subsection{Upper bound of Stopping Time}\label{sub:stop:bound}
 

-

 A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
 independent of $\tau$. The following result will be useful~\cite[Proposition~6.10]{LevinPeresWilmer2006},
 
 A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
 independent of $\tau$. The following result will be useful~\cite[Proposition~6.10]{LevinPeresWilmer2006},
 


@@ -136,7 +138,7 @@ ${\mathsf{N}}$-cube.
 Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$.
 Intuitively speaking $h$ aims at memorizing for each node 
 $X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle,
 Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$.
 Intuitively speaking $h$ aims at memorizing for each node 
 $X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle,

-\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ 
+\textit{i.e.}, which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ 

 cannot be switched.
 
 
 cannot be switched.
 
 


@@ -206,7 +208,7 @@ $$
 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,\cdot)$ and $h(X_j)\neq \ell$.
 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,\cdot)$ and $h(X_j)\neq \ell$.

-In other words, there exist a date $j$ before $t$ where 
+In other words, there exists 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$.  
 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$.  


@@ -249,7 +251,12 @@ 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\}.$$
+\[
+\begin{array}{rcl}
+S_{X,\ell}&=&\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.) \\
+&& \qquad \text{ and } X_0=X\}.
+\end{array}
+\]

 
 %  We denote by
 % $$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$
 
 %  We denote by
 % $$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$


@@ -264,7 +271,7 @@ $E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ is established.
 \end{lmm}
 
 \begin{proof}
 \end{lmm}
 
 \begin{proof}

-For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq
+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, 
 \frac{1}{4{\mathsf{N}}^2}$. 
 Let $X_0= X$.
 Indeed, 


@@ -296,8 +303,14 @@ has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq
 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).$$
 Since $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, one has
 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).$$
 Since $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, one has

-$$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).$$
+\[
+\begin{array}{rcl}
+  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)\\
+&& \qquad +2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).
+\end{array}
+\]

 Consequently,
 $$E[S_{X,\ell}]\leq 1+1+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,$$
 Consequently,
 $$E[S_{X,\ell}]\leq 1+1+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,$$


@@ -346,12 +359,12 @@ 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
 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}.
+direct application of Lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.

 \end{proof}
 
 Now using Markov Inequality, one has $\P_X(\tau > t)\leq \frac{E[\tau]}{t}$.
 With $t_n=32N^2+16N\ln (N+1)$, one obtains:  $\P_X(\tau > t_n)\leq \frac{1}{4}$. 
 \end{proof}
 
 Now using Markov Inequality, one has $\P_X(\tau > t)\leq \frac{E[\tau]}{t}$.
 With $t_n=32N^2+16N\ln (N+1)$, one obtains:  $\P_X(\tau > t_n)\leq \frac{1}{4}$. 

-Therefore, using the defintion of $t_{\rm mix)}$ and
+Therefore, using the definition of $t_{\rm mix}$ and

 Theorem~\ref{thm-sst}, it follows that
 $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$.
 
 Theorem~\ref{thm-sst}, it follows that
 $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$.
 


@@ -364,19 +377,19 @@ are more regular and more binding than this constraint.
 Moreover, the bound
 is obtained using the coarse Markov Inequality. For the
 classical (lazzy) random walk the  $\mathsf{N}$-cube, without removing any
 Moreover, the bound
 is obtained using the coarse Markov Inequality. For the
 classical (lazzy) random walk the  $\mathsf{N}$-cube, without removing any

-Hamiltonian cylce, the mixing time is in $\Theta(N\ln N)$. 
+Hamiltonian cycle, the mixing time is in $\Theta(N\ln N)$. 

 We conjecture that in our context, the mixing time is also in $\Theta(N\ln
 N)$.
 
 
 We conjecture that in our context, the mixing time is also in $\Theta(N\ln
 N)$.
 
 

-In this later context, we claim that the upper bound for the stopping time 
+In this latter context, we claim that the upper bound for the stopping time 

 should be reduced. This fact is studied in the next section.
 
 \subsection{Practical Evaluation of Stopping Times}\label{sub:stop:exp}
  
 Let be given a function $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$
 and an initial seed $x^0$.
 should be reduced. This fact is studied in the next section.
 
 \subsection{Practical Evaluation of Stopping Times}\label{sub:stop:exp}
  
 Let be given a function $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$
 and an initial seed $x^0$.

-The pseudo code given in algorithm~\ref{algo:stop} returns the smallest 
+The pseudo code given in Algorithm~\ref{algo:stop} returns the smallest 

 number of iterations such that all elements $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ are fair. It allows to deduce an approximation of $E[\ts]$
 by calling this code many times with many instances of function and many 
 seeds.
 number of iterations such that all elements $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ are fair. It allows to deduce an approximation of $E[\ts]$
 by calling this code many times with many instances of function and many 
 seeds.


@@ -401,19 +414,19 @@ $\textit{fair}\leftarrow\emptyset$\;
 }
 \Return{$\textit{nbit}$}\;
 %\end{scriptsize}
 }
 \Return{$\textit{nbit}$}\;
 %\end{scriptsize}

-\caption{Pseudo Code of stoping time calculus }
+\caption{Pseudo Code of stopping time computation}

 \label{algo:stop}
 \end{algorithm}
 
 Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 
 \label{algo:stop}
 \end{algorithm}
 
 Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 

-10 functions have been generaed according to method presented in section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
-is executed 10000 times with a random seed. The Figure~\ref{fig:stopping:moy}
+10 functions have been generated according to method presented in Section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
+is executed 10000 times with a random seed. Figure~\ref{fig:stopping:moy}

 summarizes these results. In this one, a circle represents the 
 approximation of $E[\ts]$ for a given $\mathsf{N}$.
 The line is the graph of the function $x \mapsto 2x\ln(2x+8)$. 
 It can firstly 
 be observed that the approximation is largely
 summarizes these results. In this one, a circle represents the 
 approximation of $E[\ts]$ for a given $\mathsf{N}$.
 The line is the graph of the function $x \mapsto 2x\ln(2x+8)$. 
 It can firstly 
 be observed that the approximation is largely

-smaller than the upper bound given in theorem~\ref{prop:stop}.
+smaller than the upper bound given in Theorem~\ref{prop:stop}.

 It can be further deduced  that the conjecture of the previous section 
 is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.
 
 It can be further deduced  that the conjecture of the previous section 
 is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.
 


@@ -427,7 +440,7 @@ is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.
 % \hline
 % \mathsf{N}  & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\
 % \hline
 % \hline
 % \mathsf{N}  & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\
 % \hline

-% \mathsf{N}  & 21.8 & 28.4 & 35.4 & 42.5 & 50 & 57.7 & 65.6& 73.5 & 81.6 & 90 & 98.3 & 107.1 & 16 \\
+% \mathsf{N}  & 21.8 & 28.4 & 35.4 & 42.5 & 50 & 57.7 & 65.6& 73.5 & 81.6 & 90 & 98.3 & 107.1 & 115.7 \\

 % \hline
 % \end{array}
 % $$
 % \hline
 % \end{array}
 % $$


@@ -436,7 +449,7 @@ is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.
 
 \begin{figure}
 \centering
 
 \begin{figure}
 \centering

-\includegraphics[scale=0.5]{complexity}
+\includegraphics[width=0.49\textwidth]{complexity}

 \caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
 \end{figure}
 
 \caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
 \end{figure}