X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d81b15b2024adaf639e9d4a85934a5b5722c1bf1..01003216d61845263ad195f3ecf7334817d60407:/14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 76e635b..e36720b 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -340,7 +340,7 @@ diffÃ©rent que par un seul bit.
 \section{Lien avec les codes de Gray cycliques (totalement) Ã©quilibrÃ©s}
 \label{sub:gray}
 
-La borne  infÃ©rieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
+Un minorant du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
     \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnÃ©e  dans~\cite{Feder2009NTB},
 indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
 cette  difficultÃ©,  nous  nous   restreignons  aux  codes  induisant  un  graphe
@@ -438,16 +438,16 @@ comment sÃ©lectionner des sous-sÃ©quences qui assurent que le code obtenu est Ã©
 La thÃ©orÃ¨me suivante montre que c'est possible et sa preuve,
 donnÃ©e en annexes~\ref{anx:generateur}, explique comment le faire. 
 
-
-\begin{theorem}\label{prop:balanced}
+\begin{restatable}[Existence d'un code de Gray Ã©quilibrÃ©]{theorem}{theograyequilibre}
+\label{prop:balanced}
 Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ dÃ©fini par 
 $a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. 
 il existe une sÃ©quence $l$ dans l'Ã©tape~(\ref{item:nondet}) de l'extension
-de l'algorithme de \emph{Robinson-Cohn}  telle que 
+de l'algorithme de \emph{Robinson-Cohn} extension telle que 
 le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ 
 sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ 
 pour chaque  $i$, $1 \le i \le \mathsf{N}$.
-\end{theorem}
+\end{restatable}
 
 Ces fonctions Ã©tant gÃ©nÃ©rÃ©es, on s'intÃ©resse Ã  Ã©tudier Ã  quelle vitesse 
 un gÃ©nÃ©rateur les embarquant converge vers la distribution uniforme.
@@ -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 
@@ -484,7 +486,7 @@ probabilitÃ©s $p$ dÃ©finie sur l'ensemble des arcs comme suit:
 $$
 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.  
@@ -507,6 +509,9 @@ P=\dfrac{1}{6} \left(
 \]
 \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}}$.
-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 
@@ -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$. 
 
 
-\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)$. 
-\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
@@ -595,17 +601,17 @@ la probabilitÃ© de rester dans une configuration donnÃ©e
 est fixÃ©e Ã  $\frac{1}{2}+\frac{1}{2n}$.
 Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$.
 Cette version, qui reste davantage sur place que l'algorithme original,
-a Ã©tÃ© introduite pour simplifier le calcul de la borne sup 
+a Ã©tÃ© introduite pour simplifier le calcul d'un majorant 
 du temps d'arrÃªt.   
 
 
 Sans entrer dans les dÃ©tails de la preuve, on remarque aussi
-que le calcul  de cette borne impose uniquement que 
+que le calcul  de ce majorant impose uniquement que 
 pour chaque n{\oe}ud du $\mathsf{N}$-cube 
 un arc entrant et un arc sortant sont supprimÃ©s.
 Le fait qu'on enlÃ¨ve un cycle  hamiltonien et que ce dernier 
 soit Ã©quilibrÃ© n'est pas pris en compte.
-En intÃ©grant cette contrainte, la borne supÃ©rieure pourrait Ãªtre rÃ©duite.
+En intÃ©grant cette contrainte, ce majorant  pourrait Ãªtre rÃ©duite.
 
 En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
 marche alÃ©atoire classique paresseuse dans le $\mathsf{N}$-cube.
@@ -624,7 +630,7 @@ rÃ©sume ces rÃ©sultats. Dans celle-ci, un cercle  reprÃ©sente une approximation
 $E[\ts]$ pour un  $\mathsf{N}$ donnÃ© tandis que la courbe est une reprÃ©sentation de 
 la fonction $x \mapsto 2x\ln(2x+8)$. 
 On  constate que l'approximation de $E[\ts]$ est largement infÃ©rieure 
-Ã  la borne quadratique donnÃ©e au thÃ©orÃ¨me~\ref{prop:stop} et que la conjecture 
+Ã  le majorant quadratique donnÃ© au thÃ©orÃ¨me~\ref{prop:stop} et que la conjecture 
 donnÃ©e au paragraphe prÃ©cÃ©dent est sensÃ©e.
 
 
@@ -1090,7 +1096,7 @@ construction de ce type de codes a Ã©tÃ© prÃ©sentÃ©e Ã©tendant les mÃ©thodes
 existantes. 
 Dans le cas des itÃ©rations unaires, 
 l'algorithme qui en dÃ©coule a un temps de mÃ©lange qui a 
-une borne sup quadratique de convergence vers la distribution uniforme. 
+un majorant quadratique de convergence vers la distribution uniforme. 
 Pratiquement,  ce temps de mÃ©lange se rapproche de $N\ln N$.
 Les expÃ©rimentations au travers de la batterie de test de NIST ont montrÃ©
 que toutes les propriÃ©tÃ©s statistiques sont obtenues pour
