X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/31468b39be240f447015be22c252d515b2dcfdac..d509acd9cc478541bd9cf2f33686e60f3b77cce5:/stopping.tex?ds=inline diff --git a/stopping.tex b/stopping.tex index 7514341..284fc49 100644 --- a/stopping.tex +++ b/stopping.tex @@ -33,7 +33,7 @@ P=\dfrac{1}{6} \left( 0&0&0&0&1&0&4&1 \\ 0&0&0&1&0&1&0&4 \end{array} -\right) +\right). \] \end{xpl} @@ -70,9 +70,13 @@ 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$ \ANNOT{pas plutôt $P$ ?} of a Markov chain -is $\epsilon$-close to a stationary distribution. +%% 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. + +Intutively speaking, $t_{\rm mix}(\varepsilon)$ is the time/steps required +to be sure to be $\varepsilon$-close to the stationary distribution, wherever +the chain starts. @@ -114,9 +118,8 @@ $$\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$. The following result will be useful~\cite[Proposition~6.10]{LevinPeresWilmer2006}, \begin{thrm}\label{thm-sst} @@ -232,7 +235,8 @@ This probability is independent of the value of the other bits. 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 +$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, and +independently of the value of the other bits, proving the lemma.\end{proof} \begin{thrm} \label{prop:stop} @@ -245,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}.$$ @@ -292,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,$$ @@ -346,7 +361,7 @@ direct application of lemma~\ref{prop:lambda} and~\ref{lm:stopprime}. \end{proof} Now using Markov Inequality, one has $\P_X(\tau > t)\leq \frac{E[\tau]}{t}$. -With $t=32N^2+16N\ln (N+1)$, one obtains: $\P_X(\tau > t)\leq \frac{1}{4}$. +With $t_n=32N^2+16N\ln (N+1)$, one obtains: $\P_X(\tau > t_n)\leq \frac{1}{4}$. Therefore, using the defintion of $t_{\rm mix)}$ and Theorem~\ref{thm-sst}, it follows that $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$. @@ -355,11 +370,11 @@ $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$. 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 +The calculus doesn't consider (balanced) Hamiltonian cycles, which 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 +is obtained using the coarse Markov Inequality. For the +classical (lazzy) random walk 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)$. @@ -423,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} % $$ @@ -432,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}