X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/236f25b2f3a081b11c71bedad6d044d695ce2cca..31468b39be240f447015be22c252d515b2dcfdac:/stopping.tex?ds=sidebyside

diff --git a/stopping.tex b/stopping.tex
index fb0b9e0..7514341 100644
--- a/stopping.tex
+++ b/stopping.tex
@@ -65,12 +65,13 @@ distribution induced by the $X$-th row of $P$. 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}.$$
 
+\ANNOT{incohÃ©rence de notation $X$ : entier ou dans $B^N$ ?}
 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  
+\textit{i.e.}, is the time until the matrix $X$ \ANNOT{pas plutÃ´t $P$ ?} of a Markov chain  
 is $\epsilon$-close to a stationary distribution.
 
 
@@ -114,7 +115,7 @@ $$\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
+A stopping time $\tau$ is a \emph{strong stationary time} if $X_{\tau}$ is
 independent of $\tau$. 
 
 
@@ -376,12 +377,6 @@ number of iterations such that all elements $\ell\in \llbracket 1,{\mathsf{N}} \
 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)}
@@ -389,39 +384,59 @@ wÅsmaller than the upper bound given in theorem~\ref{prop:stop}.
 
 $\textit{nbit} \leftarrow 0$\;
 $x\leftarrow x^0$\;
-$\textit{visited}\leftarrow\emptyset$\;
-
-\While{$\left\vert{\textit{visited}}\right\vert < \mathsf{N} $}
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
 {
-        $ s \leftarrow \textit{Random}(n)$ \;
+        $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
         $\textit{image} \leftarrow f(x) $\;
-        \If{$x[s] \neq \textit{image}[s]$}{
-            $\textit{visited} \leftarrow \textit{visited} \cup \{s\}$
+        \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+            $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+            $x[s] \leftarrow \textit{image}[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}
+\caption{Pseudo Code of stoping time calculus }
 \label{algo:stop}
 \end{algorithm}
 
+Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 
+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. The 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
+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)$.
 
 
 
-\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}
+
+
+% \begin{table}
+% $$
+% \begin{array}{|*{14}{l|}}
+% \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 \\
+% \hline
+% \end{array}
+% $$
+% \caption{Average Stopping Time}\label{table:stopping:moy}
+% \end{table}
+
+\begin{figure}
+\centering
+\includegraphics[scale=0.5]{complexity}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+
 
 %%% Local Variables:
 %%% mode: latex
