Ajout exemple 3-cube pour algo Wild

[16dcc.git] / stopping.tex

diff --git a/stopping.tex b/stopping.tex
index 142da7f9afc3f748cbeed7447e5813fd068e1534..9d7e74f374970e7d835203cef4d985973ec8c53a 100644 (file)
--- 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
 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}}$. 
 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 
 ${\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.
 
 \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}$. 
 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}
 $\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$) 
 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
  
 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


@@ -376,7 +376,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
 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)$.
 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 +419,16 @@ $\textit{fair}\leftarrow\emptyset$\;
 \end{algorithm}
 
 Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 
 \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}
 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 
 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)$.