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

diff --git a/stopping.tex b/stopping.tex
index 7514341..539d653 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}
 
@@ -60,19 +60,25 @@ $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreov
 $\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has
 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
 
-Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the
-distribution induced by the $X$-th row of $P$. If the Markov chain induced by
-$P$ has a stationary distribution $\pi$, then we define
+Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. For any
+$X\in \Bool^{\mathsf{N}}$, let $P(X,\cdot)$ be the distribution induced by the
+${\rm bin}(X)$-th row of $P$, where ${\rm bin}(X)$ is the integer whose
+binary encoding is $X$. 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$ ?}
+%\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$ \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 +120,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 +237,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 +251,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 +303,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 +363,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 +372,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 +440,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 +449,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}