main.tex et prng.tex

[16dcc.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index e86176a9481d32da89949a0c30b6eb330bf6ee5c..1ac699934cc93a9f5bd6be19b60b634d87c42596 100644 (file)
--- 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}
 0&0&0&0&1&0&4&1 \\
 0&0&0&1&0&1&0&4 
 \end{array}

-\right)
+\right).

 \]
 \end{xpl}
 
 \]
 \end{xpl}
 


@@ -69,9 +69,13 @@ and
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 
 
 $$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
 
 
 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}
 
 
 \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
 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}
 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}$.
 \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)$.
 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. 
 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
 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)$.
 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)$.