X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/e1fe6e435ee452003a7135763d26e2320756398c..bd2919c6b5810121da30faafc9f3b8c6f0155e9e:/stopping.tex diff --git a/stopping.tex b/stopping.tex index 409dd83..989bb9e 100644 --- a/stopping.tex +++ b/stopping.tex @@ -40,11 +40,11 @@ P=\dfrac{1}{6} \left( 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. @@ -376,12 +376,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,36 +383,63 @@ 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} - - - -\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: