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