Ajout exemple 3-cube pour algo Wild

[16dcc.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index 1ac699934cc93a9f5bd6be19b60b634d87c42596..9d7e74f374970e7d835203cef4d985973ec8c53a 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -1,6 +1,6 @@
 This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ 
 issued from an hypercube where an Hamiltonian path has been removed
 This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ 
 issued from an hypercube where an Hamiltonian path has been removed

-as described in previous section.
+as described in the previous section.

 Notice that the iteration graph is always a subgraph of 
 ${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the 
 edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$. 
 Notice that the iteration graph is always a subgraph of 
 ${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the 
 edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$. 


@@ -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},
 


@@ -135,8 +137,8 @@ In other words, $E$ is the set of all the edges in the classical
 ${\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 
 ${\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,
-\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ 
+$X \in \Bool^{\mathsf{N}}$ whose edge is removed in the Hamiltonian cycle,
+\textit{i.e.}, which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ 

 cannot be switched.
 
 
 cannot be switched.
 
 


@@ -162,7 +164,7 @@ P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$}
 We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function 
 such that for any $X \in \Bool^{\mathsf{N}} $, 
 $(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 
 We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function 
 such that for any $X \in \Bool^{\mathsf{N}} $, 
 $(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}}$,
+The function $\ov{h}$ is said to be {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$,

 $\ov{h}(\ov{h}(X))\neq X$. 
 
 \begin{lmm}\label{lm:h}
 $\ov{h}(\ov{h}(X))\neq X$. 
 
 \begin{lmm}\label{lm:h}


@@ -206,10 +208,10 @@ $$
 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$) 
 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$.  
+and where the configuration $X_j$ allows to cross the edge $l$.  

  
 Let $\ts$ be the first time all the elements of $\llbracket 1, {\mathsf{N}} \rrbracket$
 are fair. The integer $\ts$ is a randomized stopping time for
  
 Let $\ts$ be the first time all the elements of $\llbracket 1, {\mathsf{N}} \rrbracket$
 are fair. The integer $\ts$ is a randomized stopping time for


@@ -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)$.
 


@@ -363,20 +376,20 @@ The calculus doesn't consider (balanced) Hamiltonian cycles, which
 are more regular and more binding than this constraint.
 Moreover, the bound
 is obtained using the coarse Markov Inequality. For the
 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
-Hamiltonian cylce, the mixing time is in $\Theta(N\ln N)$. 
+classical (lazy) random walk the  $\mathsf{N}$-cube, without removing any
+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,21 +414,21 @@ $\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}
-summarizes these results. In this one, a circle represents the 
+10 functions have been generated according to the 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. 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
 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 
 It can be further deduced  that the conjecture of the previous section 

-is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.
+is realistic according to the graph of $x \mapsto 2x\ln(2x+8)$.

 
 
 
 
 
 


@@ -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}