sdcs

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 69fb6d8462374bf50a8508cda61e04d087b549c5..e36720bc6db746db7d4df3115cb2c2f57bbc24d1 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -477,6 +477,8 @@ particulièrement au chapitre sur les temps d'arrêt.
 
 
 
 
 
 

+
+

 \begin{xpl}
 On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
 \textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 
 \begin{xpl}
 On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
 \textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 


@@ -484,7 +486,7 @@ probabilités $p$ définie sur l'ensemble des arcs comme suit:
 $$
 p(e) \left\{
 \begin{array}{ll}
 $$
 p(e) \left\{
 \begin{array}{ll}

-= \frac{2}{3} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
+= \frac{1}{2} + \frac{1}{6} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\

 = \frac{1}{6} \textrm{ sinon.}
 \end{array}
 \right.  
 = \frac{1}{6} \textrm{ sinon.}
 \end{array}
 \right.  


@@ -507,6 +509,9 @@ P=\dfrac{1}{6} \left(
 \]
 \end{xpl}
 
 \]
 \end{xpl}
 

+On remarque que dans cette marche on reste sur place avec une probabilité
+
+

 
 
 
 
 
 


@@ -541,7 +546,7 @@ $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(
 
 Soit $(X_t)_{t\in \mathbb{N}}$ une suite de  variables aléatoires de 
 $\Bool^{\mathsf{N}}$.
 
 Soit $(X_t)_{t\in \mathbb{N}}$ une suite de  variables aléatoires de 
 $\Bool^{\mathsf{N}}$.

-une variable aléatoire $\tau$ dans $\mathbb{N}$ est un  
+Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un  

 \emph{temps d'arrêt} pour la suite
 $(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
 (\Bool^{\mathsf{N}})^{t+1}$ tel que 
 \emph{temps d'arrêt} pour la suite
 $(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
 (\Bool^{\mathsf{N}})^{t+1}$ tel que 


@@ -582,11 +587,12 @@ La fonction $\ov{h}$ est dite  {\it anti-involutive} si pour tout $X\in \Bool^{\
 $\ov{h}(\ov{h}(X))\neq X$. 
 
 
 $\ov{h}(\ov{h}(X))\neq X$. 
 
 

-\begin{theorem} \label{prop:stop}
+\begin{restatable}[Majoration du temps d'arrêt]{theorem}{theostopmajorant}
+\label{prop:stop}

 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)$. 
 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}
+\end{restatable}

 
 Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
 On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement
 
 Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
 On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement

diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex
index 6bbd41f6395295422c86a05215e7964369e9a73e..510dcefb92f74906c15de600b5f18ca01ffa8c15 100644 (file)
--- a/annexePreuveStopping.tex
+++ b/annexePreuveStopping.tex
@@ -261,10 +261,7 @@ the same probability. Therefore,  for $t\geq \tau_\ell$, the
 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
 lemma.\end{proof}
 
 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
 lemma.\end{proof}
 

-\begin{theorem} \label{prop:stop}
-If $\ov{h}$ is bijective and square-free, then
-$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
-\end{theorem}
+\theostopmajorant*

 
 For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, 
 let $S_{X,\ell}$ be the
 
 For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, 
 let $S_{X,\ell}$ be the