après remarques tof

[hdrcouchot.git] / annexePreuveStopping.tex

diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex
index 5b77e95305a1ac9d0d77f07359e06b3bb3e88c5e..75d05e471221bce31595c3682adb60c496e22483 100644 (file)
--- 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
 ${\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é.
 
 \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}$.
 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 
 \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),\\
 \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.
 \]
 
 \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} 
 
 
 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$.  
  
 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}
 
 
 \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é,
 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}
 
 
 \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
 
 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.
 $\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,
 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}}}.$
 
 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}
 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}
 $\ov{h}(\ov{h}(X))\neq X$, alors
 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
 \end{theorem}