From: Pierre-Cyrille Héam <pheam@femto-st.fr>
Date: Mon, 27 Jun 2016 12:49:08 +0000 (+0200)
Subject: pch, section 6
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/commitdiff_plain/3147e770da18dc984025737bc802ba0e0bff6977?ds=sidebyside;hp=bd2919c6b5810121da30faafc9f3b8c6f0155e9e

pch, section 6
---

diff --git a/main.pdf b/main.pdf
index 4f393a0..49fc144 100644
Binary files a/main.pdf and b/main.pdf differ
diff --git a/stopping.tex b/stopping.tex
index 989bb9e..aa13c9a 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}
 
@@ -69,9 +69,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$ 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 staionary distribution, wherever
+the chain starts. 
 
 
 
@@ -115,7 +119,7 @@ $$\P_X(X_\tau=Y)=\pi(Y).$$
 
 
 A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
-independent of $\tau$. 
+independent of $\tau$. The following result will be useful~\cite[Proposition~6.10]{LevinPeresWilmer2006},
 
 
 \begin{thrm}\label{thm-sst}
@@ -231,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}
@@ -345,7 +350,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)$.
@@ -354,11 +359,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)$.