X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/523864c862215a63c5133568a9771f5b8f60c89e..HEAD:/annexePreuveStopping.tex?ds=sidebyside

diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex
index 5b77e95..75d05e4 100644
--- a/annexePreuveStopping.tex
+++ b/annexePreuveStopping.tex
@@ -46,7 +46,7 @@ En d'autres mots, $E$ est l'ensemble des tous les arcs du
 ${\mathsf{N}}$-cube. 
 Soit $h: \Bool^{\mathsf{N}} \to [{\mathsf{N}}]$ 
 qui mÃ©morise pour chaque n{\oe}ud $X \in \Bool^{\mathsf{N}}$ quel
-arc est supprimÃ©e Ã  partir du cycle hamiltonien,
+arc est supprimÃ© Ã  partir du cycle hamiltonien,
 \textit{i.e.} quel bit dans  $[{\mathsf{N}} ]$ 
 ne peut pas Ãªtre inversÃ©.
 
@@ -97,8 +97,8 @@ $\ov{h}^{-1}(X)\oplus X = 0^{{\mathsf{N}}-k}10^{k-1}$.
 Supposons $h(X) = h(\ov{h}^{-1}(X))$. Dans un tel cas, $h(X) =k$.
 Par dÃ©finition  $\ov{h}$, $(X, \ov{h}(X)) \in E $ et
 $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$.
-Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraine $\ov{h}(\ov{h}(X))= X$ et 
-qui contredit le fiat que $\ov{h}$ est anti-involutive.
+Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraÃ®ne $\ov{h}(\ov{h}(X))= X$ et 
+qui contredit le fait que $\ov{h}$ est anti-involutive.
 \end{proof}
 
 Soit $Z$ une variable alÃ©atoire suivant une distribution uniforme sur 
@@ -108,7 +108,7 @@ Pour $X\in \Bool^{\mathsf{N}}$, on dÃ©finit avec  $Z=(i,b)$,
 \left\{
 \begin{array}{ll}
 f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{ si } b=1 \text{ et } i\neq h(X),\\
-f(X,Z)=X& \text{otherwise.} 
+f(X,Z)=X& \text{sinon.} 
 \end{array}\right.
 \]
 
@@ -121,13 +121,13 @@ X_t= f(X_{t-1},Z_t).
 
 
 Un entier $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ est  \emph{Ã©quitable} 
- au temps $t$ s'il existe  $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ anÃ©rieure Ã   $t$ 
+ au temps $t$ s'il existe  $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ antÃ©rieure Ã   $t$ 
 oÃ¹ le premier Ã©lÃ©ment de la variable alÃ©atoire  $Z$ est $l$ 
 (\textit{i.e.}, la stratÃ©gie vaut $l$ Ã  la date $j$) 
 et oÃ¹ le n{\oe}ud $X_j$ permet de traverser l'arc  $l$.  
  
-Soit $\ts$ le premier tempsoÃ¹ touis les Ã©lÃ©ments de $\llbracket 1, {\mathsf{N}} \rrbracket$ 
-sont  Ã©quitables.  On a le lemme suiant:%L'entier $\ts$ est un temps d'arrÃªt pour la chaÃ®ne de Markov $(X_t)$.
+Soit $\ts$ le premier temps oÃ¹ tous les Ã©lÃ©ments de $\llbracket 1, {\mathsf{N}} \rrbracket$ 
+sont  Ã©quitables.  On a le lemme suivant:%L'entier $\ts$ est un temps d'arrÃªt pour la chaÃ®ne de Markov $(X_t)$.
 
 
 \begin{lemma}
@@ -147,7 +147,7 @@ est $0$ ou $1$ avec la mÃªme probabilitÃ©  ($\frac{1}{2}$).
 A chaque Ã©tape, le $l^{\textrm{Ã¨me}}$ bit  est inversÃ© de $0$ Ã  $1$ ou de $1$ Ã  $0$, chaque fois avec la mÃªme 
 probabilitÃ©. Ainsi,  pour $t\geq \tau_\ell$, le
 $\ell^{\textrm{Ã¨me}}$ bit de $X_t$ est $0$ ou $1$ avec la mÃªme probabilitÃ©,
-et ce indÃ©pendament de la valeur des autres bits.
+et ce indÃ©pendamment de la valeur des autres bits.
 \end{proof}
 
 
@@ -158,7 +158,7 @@ et ce indÃ©pendament de la valeur des autres bits.
 
 Pour chaque $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$, 
 soit $S_{X,\ell}$ une variable alÃ©atoire qui compte le nombre d'itÃ©rations
-tel qu'en dÃ©marant de la configuration  $X$ on en atteigne une oÃ¹ 
+tel qu'en dÃ©marrant de la configuration  $X$ on en atteigne une oÃ¹ 
 $\ell$  est Ã©quitable. Plus formellement, 
 $$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ et }Z_t=(\ell,.)\text{ et } X_0=X\}.$$
 On peut majorer l'espÃ©rance de cette variable alÃ©atoire comme suit.
@@ -227,7 +227,7 @@ $i-1$ bits Ã©quitables. On a $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}-1}W_i$.
 Dans la configuration $X$ avec $i-1$ bits Ã©quitables,
 la probabilitÃ© d'obtenir un nouveau bit Ã©quitable est soit
 $1-\frac{i-1}{{\mathsf{N}}}$ si $h(X)$ est Ã©quitable,
-et $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas. 
+soit $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas. 
 
 Ainsi, 
 $\P (W_i=k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}}.$
@@ -257,7 +257,7 @@ ce qui termine la preuve du lemme.
 Tous les Ã©lÃ©ments sont en place pour majorer l'espÃ©rance de $\ts$. 
 \begin{theorem}
 \label{prop:stop}
-Si $\ov{h}$ est bijective et anti involutive 
+Si $\ov{h}$ est bijective et anti- involutive 
 $\ov{h}(\ov{h}(X))\neq X$, alors
 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
 \end{theorem}
