X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/3fc31015143d2bab7226a54390f3e1c5eba8f4d5..30a7ec2b1746fb3abfe8780a43625bb768842228:/stopping.tex?ds=inline

diff --git a/stopping.tex b/stopping.tex
index 142da7f..bb95663 100644
--- a/stopping.tex
+++ b/stopping.tex
@@ -1,6 +1,6 @@
 This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ 
 issued from an hypercube where an Hamiltonian path has been removed
-as described in previous section.
+as described in the previous section.
 Notice that the iteration graph is always a subgraph of 
 ${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the 
 edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$. 
@@ -137,7 +137,7 @@ In other words, $E$ is the set of all the edges in the classical
 ${\mathsf{N}}$-cube. 
 Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$.
 Intuitively speaking $h$ aims at memorizing for each node 
-$X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle,
+$X \in \Bool^{\mathsf{N}}$ whose edge is removed in the Hamiltonian cycle,
 \textit{i.e.}, which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ 
 cannot be switched.
 
@@ -164,7 +164,7 @@ P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$}
 We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function 
 such that for any $X \in \Bool^{\mathsf{N}} $, 
 $(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 
-The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$,
+The function $\ov{h}$ is said to be {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$,
 $\ov{h}(\ov{h}(X))\neq X$. 
 
 \begin{lmm}\label{lm:h}
@@ -211,7 +211,7 @@ exists $0\leq j <t$ such that $Z_{j+1}=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
 In other words, there exists a date $j$ before $t$ where 
 the first element of the random variable $Z$ is exactly $l$ 
 (\textit{i.e.}, $l$ is the strategy at date $j$) 
-and where the configuration $X_j$ allows to traverse the edge $l$.  
+and where the configuration $X_j$ allows to cross the edge $l$.  
  
 Let $\ts$ be the first time all the elements of $\llbracket 1, {\mathsf{N}} \rrbracket$
 are fair. The integer $\ts$ is a randomized stopping time for
@@ -366,7 +366,8 @@ Now using Markov Inequality, one has $\P_X(\tau > t)\leq \frac{E[\tau]}{t}$.
 With $t_n=32N^2+16N\ln (N+1)$, one obtains:  $\P_X(\tau > t_n)\leq \frac{1}{4}$. 
 Therefore, using the definition 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)$.
+$t_{\rm mix}(\frac{1}{4})\leq 32N^2+16N\ln (N+1)=O(N^2)$ and that 
+
 
 
 Notice that the calculus of the stationary time upper bound is obtained
@@ -376,7 +377,7 @@ The calculus doesn't consider (balanced) Hamiltonian cycles, which
 are more regular and more binding than this constraint.
 Moreover, the bound
 is obtained using the coarse Markov Inequality. For the
-classical (lazzy) random walk the  $\mathsf{N}$-cube, without removing any
+classical (lazy) random walk the  $\mathsf{N}$-cube, without removing any
 Hamiltonian cycle, 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)$.
@@ -419,16 +420,16 @@ $\textit{fair}\leftarrow\emptyset$\;
 \end{algorithm}
 
 Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 
-10 functions have been generated according to method presented in Section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
+10 functions have been generated according to the method presented in Section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
 is executed 10000 times with a random seed. Figure~\ref{fig:stopping:moy}
-summarizes these results. In this one, a circle represents the 
+summarizes these results. A circle represents the 
 approximation of $E[\ts]$ for a given $\mathsf{N}$.
 The line is the graph of the function $x \mapsto 2x\ln(2x+8)$. 
 It can firstly 
 be observed that the approximation is largely
 smaller than the upper bound given in Theorem~\ref{prop:stop}.
 It can be further deduced  that the conjecture of the previous section 
-is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.
+is realistic according to the graph of $x \mapsto 2x\ln(2x+8)$.