X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d81b15b2024adaf639e9d4a85934a5b5722c1bf1..d4e1bfa4290a182013268daf63d78c1f4fce5b55:/14Secrypt.tex?ds=inline

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 76e635b..858a8e5 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
@@ -371,7 +371,7 @@ plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{TC}_n(i)$  est  pair
 $\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
 différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec
 $\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
-$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
+$\textit{TC}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
 vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.
 
 \begin{xpl}
@@ -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,7 +509,17 @@ P=\dfrac{1}{6} \left(
 \]
 \end{xpl}
 
+On remarque que dans cette marche on reste sur place avec une probabilité égale 
+à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin
+lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$.
+Les probabilités usuelles que l'on appliquerait aux transitions de 
+l'algorithme~\ref{CI Algorithm} serait quant à elles uniformément égales 
+à $\frac{1}{\mathsf{N}}$.
+Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme. 
 
+Cependant, l'étude théorique de référence~\cite{LevinPeresWilmer2006}
+considère cette marche comme cadre. S'inspirant de 
+celle-ci, le travail suivant se replace donc dans ce cadre théorique.
 
 
 Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 
@@ -531,81 +543,41 @@ $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$
 et
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-
-Un résultat classique est
-
-$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-
-
-
-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  
-\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 
-$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. 
-En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs 
-de  
-$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$. 
  
-
-Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et 
-$f(X_{t-1},Z_t)$  une représentation fonctionnelle de celle-ci. 
-Un \emph{temps d'arrêt aléatoire} pour la chaîne de 
-Markov  est un temps d'arrêt pour 
-$(Z_t)_{t\in\mathbb{N}}$.
-Si la chaîne de Markov  est irréductible et a $\pi$
-comme distribution stationnaire, alors un 
-\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
-(qui peut dépendre de la configuration initiale $X$),
-tel que la distribution de $X_\tau$ est $\pi$:
-$$\P_X(X_\tau=Y)=\pi(Y).$$
-
-
-Un temps d'arrêt  $\tau$ est qualifié de  \emph{fort} si  $X_{\tau}$ 
-est indépendant de  $\tau$.  On a les deux théorèmes suivants, dont les 
-démonstrations sont données en annexes~\ref{anx:generateur}.
+Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire 
+pour être proche de la distribution stationnaire à $\varepsilon$ prêt, 
+peut importe la configuration de départ. On a le théorème suivant démontré en annexes~\ref{anx:generateur}.
 
 
-\begin{theorem}
-Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
-\P_X(\tau > t)$.
-\end{theorem}
-
-
-Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction 
-telle que pour $X \in \Bool^{\mathsf{N}} $, 
-$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 
-La fonction $\ov{h}$ est dite  {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
-$\ov{h}(\ov{h}(X))\neq X$. 
+\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix}
+\label{theo:tmps:mix}
+On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de 
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+\[
+p(e) \left\{
+\begin{array}{ll}
+= \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
+= \frac{1}{2\mathsf{N}} \textrm{ sinon.}
+\end{array}
+\right.  
+\]
 
+La chaîne de Markov associée converge vers la distribution uniforme et 
 
-\begin{theorem} \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}
+\[
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2).
+\] 
+\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
-l'algorithme~\ref{CI Algorithm}. En effet dans la section présente, 
-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 
-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.
@@ -614,7 +586,7 @@ dans le contexte du $\mathsf{N}$-cube privé d'un chemin hamiltonien.
 
 On peut évaluer ceci pratiquement: pour une fonction
 $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
-$x^0$, le code donné à l'algorithme  ~\ref{algo:stop} retourne le 
+$x^0$, le code donné à l'algorithme~\ref{algo:stop} retourne le 
 nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$
 en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$, 
 $ 3 \le \mathsf{N} \le 16$, 10 fonctions ont été générées comme dans 
@@ -624,7 +596,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.
 
 
@@ -1084,13 +1056,13 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl
 
 
 \section{Conclusion}
-Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir 
+Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir 
 de codes de Gray équilibrés. Une méthode complètement automatique de
 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