A specific random walk in this modified hypercube is first
introduced (See section~\ref{sub:stop:formal}). We further
-theoretical study this random walk to
-provide a 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
-results that reduce this bound (Sec.~\ref{sub:stop:stop}).
+results that reduce this bound (Sec.~\ref{sub:stop:exp}).
Notice that for a general references on Markov chains
see~\cite{LevinPeresWilmer2006},
and particularly Chapter~5 on stopping times.
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)}
$\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}
-
-
-
-\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}
+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
+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}{|*{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
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End:
