X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/523864c862215a63c5133568a9771f5b8f60c89e..refs/heads/master:/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}