X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/d69591c41135e899d27072006db6af016df62445..66ea391a3e386a6ed3b47d5011977ca136f65ad2:/stopping.tex

diff --git a/stopping.tex b/stopping.tex
index 3a07e06..d72f8bb 100644
--- 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$. 
 
 
-\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}
@@ -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
-$\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}
 
+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 
-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.