X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/c069ead2bda7032833d2d7f3d0851906ec4d22f0..d509acd9cc478541bd9cf2f33686e60f3b77cce5:/stopping.tex?ds=inline diff --git a/stopping.tex b/stopping.tex index a6b821a..284fc49 100644 --- a/stopping.tex +++ b/stopping.tex @@ -249,7 +249,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 -$$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}.$$ @@ -296,8 +301,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 -$$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,$$ @@ -427,7 +438,7 @@ is realistic according the graph of $x \mapsto 2x\ln(2x+8)$. % \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 \\ +% \mathsf{N} & 21.8 & 28.4 & 35.4 & 42.5 & 50 & 57.7 & 65.6& 73.5 & 81.6 & 90 & 98.3 & 107.1 & 115.7 \\ % \hline % \end{array} % $$ @@ -436,7 +447,7 @@ is realistic according the graph of $x \mapsto 2x\ln(2x+8)$. \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}