resolution conflit

[16dcc.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index d72f8bbac8747217a733d0d31587816e84127c14..409dd83c971a5402faba645fedce5ebf85c777ae 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -1,11 +1,6 @@
-
-
-
-Let thus be given such kind of map.
-This article focuses on studying its iterations according to
-the equation~(\ref{eq:asyn}) with a given strategy.
-First of all, this can be interpreted as walking into its iteration graph 
-where the choice of the edge to follow is decided by the strategy.
+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.

 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}}$. 


@@ -43,50 +38,19 @@ P=\dfrac{1}{6} \left(
 \end{xpl}
 
 
 \end{xpl}
 
 

-% % Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
-% % which is defined for two distributions $\pi$ and $\mu$ on the same set 
-% % $\Bool^n$  by:
-% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ 
-% % It is known that
-% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
-
-% % Let then $M(x,\cdot)$ be the
-% % distribution induced by the $x$-th row of $M$. If the Markov chain
-% % induced by
-% % $M$ has a stationary distribution $\pi$, then we define
-% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
-% Intuitively $d(t)$ is the largest deviation between
-% the distribution $\pi$ and $M^t(x,\cdot)$, which 
-% is the result of iterating $t$ times the function.
-% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} 
-% with respect to $\varepsilon$ is given by
-% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% It defines the smallest iteration number 
-% that is sufficient to obtain a deviation lesser than $\varepsilon$.
-% Notice that the upper and lower bounds of mixing times cannot    
-% directly be computed with eigenvalues formulae as expressed 
-% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work  
-% only consider reversible Markov matrices whereas we do no restrict our 
-% matrices to such a form.
-
-
-
-
-
-
-
-This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ 
-issued from an hypercube where an Hamiltonian path has been removed.

 A specific random walk in this modified hypercube is first 
 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.
+introduced (See section~\ref{sub:stop:formal}). We further 
+theoretical study this random walk to 
+provide a upper bound of fair sequences 
+(See section~\ref{sub:stop:bound}).
+We finally complete these study with experimental
+results that reduce this bound (Sec.~\ref{sub:stop:stop}).

 Notice that for a general references on Markov chains
 Notice that for a general references on Markov chains

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

 
 
 
 

+\subsection{Formalizing the Random Walk}\label{sub:stop:formal}

 
 First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total
 variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
 
 First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total
 variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is


@@ -104,6 +68,13 @@ $$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\}.$$

+
+Intuitively speaking, $t_{\rm mix}$ is a mixing time 
+\textit{i.e.}, is the time until the matrix $X$ of a Markov chain  
+is $\epsilon$-close to a stationary distribution.
+
+
+

 One can prove that
 
 $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
 One can prove that
 
 $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$


@@ -112,13 +83,13 @@ $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(
 
 
 % 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})$$
 
 


@@ -140,6 +111,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).$$
 
 such that  the distribution of $X_\tau$ is $\pi$:
 $$\P_X(X_\tau=Y)=\pi(Y).$$
 

+\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$. 
 
 A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
 independent of $\tau$. 
 


@@ -222,7 +196,7 @@ $$
 
 
 
 
 
 

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

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


@@ -250,8 +224,11 @@ $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}$).
 $\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}$).

+This probability is independent of the value of the other bits.
+
+

 
 

- Moving next in the chain, at each step,
+Moving next in the chain, at each step,

 the $l$-th bit  is switched from $0$ to $1$ or from $1$ to $0$ each time with
 the same probability. Therefore,  for $t\geq \tau_\ell$, the
 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
 the $l$-th bit  is switched from $0$ to $1$ or from $1$ to $0$ each time with
 the same probability. Therefore,  for $t\geq \tau_\ell$, the
 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the


@@ -378,11 +355,70 @@ 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 
 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 

-are more regular and more binding than this constraint. Moreover, the bound
+are more regular and more binding than this constraint.
+Moreover, the bound

 is obtained using Markov Inequality which is frequently coarse. For the
 classical random walkin the  $\mathsf{N}$-cube, without removing any
 Hamiltonian cylce, the mixing time is in $\Theta(N\ln N)$. 
 We conjecture that in our context, the mixing time is also in $\Theta(N\ln
 is obtained using Markov Inequality which is frequently coarse. For the
 classical random walkin the  $\mathsf{N}$-cube, without removing any
 Hamiltonian cylce, 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)$. 
-%In this later context, we claim that the upper bound for the stopping time 
-%should be reduced.
+N)$.
+
+
+In this later 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$.
+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.
+
+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 table~\ref{table:stopping:moy}
+summarizes results. It can be observed that the approximation is largely
+wœsmaller than the upper bound given in theorem~\ref{prop:stop}.
+
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{visited}\leftarrow\emptyset$\;
+
+\While{$\left\vert{\textit{visited}}\right\vert < \mathsf{N} $}
+{
+        $ s \leftarrow \textit{Random}(n)$ \;
+        $\textit{image} \leftarrow f(x) $\;
+        \If{$x[s] \neq \textit{image}[s]$}{
+            $\textit{visited} \leftarrow \textit{visited} \cup \{s\}$
+          }
+        $x[s] \leftarrow \textit{image}[s]$\;
+        $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code of the stoping time calculus}
+\label{algo:stop}
+\end{algorithm}
+
+
+
+
+\begin{table}
+$$
+\begin{array}{|*{15}{l|}}
+\hline
+\mathsf{N}  & 3 & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\
+\hline
+\mathsf{N}  & 3 & 10.9 & 5 & 17.7 & 7& 25 & 9 & 32.7& 11 & 40.8 & 13 & 49.2 & 15 & 16 \\
+\hline
+\end{array}
+$$
+\caption{Average Stopping Time}\label{table:stopping:moy}
+\end{table}