pch

[16dcc.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index 3a07e06a67fc073968d7355d2bff8196d485c29f..d72f8bbac8747217a733d0d31587816e84127c14 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -144,7 +144,7 @@ A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
 independent of $\tau$. 
 
 
 independent of $\tau$. 
 
 

-\begin{thrm}
+\begin{thrm}\label{thm-sst}

 If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
 \P_X(\tau > t)$.
 \end{thrm}
 If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
 \P_X(\tau > t)$.
 \end{thrm}


@@ -362,16 +362,27 @@ One can now prove Theorem~\ref{prop:stop}.
 \begin{proof}
 Since $\ts^\prime$ is the time used to obtain $\mathsf{N}-1$ fair bits.
 Assume that the last unfair bit is $\ell$. One has
 \begin{proof}
 Since $\ts^\prime$ is the time used to obtain $\mathsf{N}-1$ fair bits.
 Assume that the last unfair bit is $\ell$. One has

-$\ts=\ts^\prime+S_{X_\tau,\ell}$, and therefore
-$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Therefore,
-Theorem~\ref{prop:stop} is a direct application of
-lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
+$\ts=\ts^\prime+S_{X_\tau,\ell}$, and therefore $E[\ts] =
+E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Therefore, Theorem~\ref{prop:stop} is a
+direct application of lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.

 \end{proof}
 
 \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}$. 
+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)$.
+
+

 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 
 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 

-are more regular and more binding than this constraint.
-In this later context, we claim that the upper bound for the stopping time 
-should be reduced.
+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
+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)$. 
+%In this later context, we claim that the upper bound for the stopping time 
+%should be reduced.