]> AND Private Git Repository - rairo15.git/blobdiff - stopping.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
reprise conclusion
[rairo15.git] / stopping.tex
index faab606dd0dc97fd112af62443d322ca9c1d906b..25e458d6f4fbd10eef0be22ff643a6c65879583e 100644 (file)
@@ -284,7 +284,7 @@ Indeed,
 $\P(S_{X,\ell}=1)=\frac{1}{{\mathsf{N}}}\geq \frac{1}{{\mathsf{N}}^2}$. 
 \item otherwise, $h(X)=\ell$, then
 $\P(S_{X,\ell}=1)=0$.
-But in this case, intutively, it is possible to move
+But in this case, intuitively, it is possible to move
 from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{N}$). And in
 $\ov{h}^{-1}(X)$ the $l$-th bit can be switched. 
 More formally,
@@ -331,7 +331,7 @@ One has $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}}W_i$.
 At position $X$ with $i-1$ fair bits,
 we  do not obtain a new fair if $Z$ is one of the $i-1$ already fair bits
 or if $Z$ is a new fair bit but $h(X)$ is $Z$.  
-This occures with probability 
+This occurs with probability 
 $p 
 = \frac{i-1}{{\mathsf{N}}} + \frac{n-i+1}{\mathsf{N}}.\frac{1}{\mathsf{N}}
 =\frac{i(\mathsf{N}-1) +1}{\mathsf{N^2}}
@@ -375,7 +375,7 @@ lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
 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 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.