la veille

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 69fb6d8462374bf50a8508cda61e04d087b549c5..b499f1b1975fcc6b7e925e6a21ca9d535721fe8c 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -12,7 +12,7 @@ Une approche plus pragmatique consiste  à supprimer un cycle hamiltonien dans l
 graphe d'itérations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}). 
 Pour obtenir plus rapidement une distribution uniforme, l'idéal serait
 de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit. 
 graphe d'itérations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}). 
 Pour obtenir plus rapidement une distribution uniforme, l'idéal serait
 de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit. 

-Cette forme de cycle est dit équilibré. La section~\ref{sub:gray} établit le
+Cette forme de cycle est dite équilibré. La section~\ref{sub:gray} établit le

 lien avec les codes de Gray équilibrés, étudiés dans la littérature. 
 La section suivante présente une démarche de génération automatique de code de Gray équilibré (section~\ref{sec:induction}).
 La vitesse avec laquelle l'algorithme de PRNG converge en interne vers 
 lien avec les codes de Gray équilibrés, étudiés dans la littérature. 
 La section suivante présente une démarche de génération automatique de code de Gray équilibré (section~\ref{sec:induction}).
 La vitesse avec laquelle l'algorithme de PRNG converge en interne vers 


@@ -20,10 +20,11 @@ une distribution uniforme est étudiée théoriquement et pratiquement à la
 section~\ref{sec:mixing}.
 L'extension du travail aux itérations généralisées est présentée à la 
 section~\ref{sec:prng:gray:general}.
 section~\ref{sec:mixing}.
 L'extension du travail aux itérations généralisées est présentée à la 
 section~\ref{sec:prng:gray:general}.

-Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans 
-ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}.
-Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées 
+Finalement, des instances de PRNGs engendrés selon les méthodes détaillées dans 
+ce chapitre sont présentées en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc}  à~\ref{sub:gray} ont été publiées 

 à~\cite{chgw+14:oip}.
 à~\cite{chgw+14:oip}.

+La section~\ref{sec:mixing} est publiée dans~\cite{ccgh16}.

 
 
 % This aim of this section is to show 
 
 
 % This aim of this section is to show 


@@ -49,13 +50,13 @@ On cherche ainsi toutes les matrices $M$ de taille  $2^{\mathsf{N}}\times 2^{\ma
 configuration $i$ est inférieur à ${\mathsf{N}}$;
 
 \item pour $j \neq i$,  $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$ 
 configuration $i$ est inférieur à ${\mathsf{N}}$;
 
 \item pour $j \neq i$,  $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$ 

-si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
+si et seulement si $M_{ij}$ vaut 1 (et 0 sinon);

 \item pour chaque indice de ligne  $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: 
 la matrice est stochastique à droite; 
 \item pour chaque indice de colonne $j$, 
   $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: 
   la matrice est stochastique à gauche;
 \item pour chaque indice de ligne  $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: 
 la matrice est stochastique à droite; 
 \item pour chaque indice de colonne $j$, 
   $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: 
   la matrice est stochastique à gauche;

-\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;
+\item Tous les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positifs, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;

 \end{enumerate}
 Ce problème s'exprime sur des domaines finis entiers avec des opérateurs  
 arithmétiques simples (sommes et produits). Il pourrait théoriquement être 
 \end{enumerate}
 Ce problème s'exprime sur des domaines finis entiers avec des opérateurs  
 arithmétiques simples (sommes et produits). Il pourrait théoriquement être 


@@ -69,7 +70,7 @@ ici pour  $\mathsf{N} = 2$. Dans ce code,
 \verb+summ(+$X,Y,R$\verb+)+ 
 valent True si et seulement si $R$ 
 est le produit matriciel  (ou la somme matricielle) 
 \verb+summ(+$X,Y,R$\verb+)+ 
 valent True si et seulement si $R$ 
 est le produit matriciel  (ou la somme matricielle) 

-entre  $X$ and $Y$ respectivement. 
+entre  $X$ et $Y$ respectivement. 

 Il n'est pas difficile d'adapter ce code à n'importe quelle valeur 
 entière naturelle  $\mathsf{N}$.  
 
 Il n'est pas difficile d'adapter ce code à n'importe quelle valeur 
 entière naturelle  $\mathsf{N}$.  
 


@@ -120,7 +121,7 @@ Cette approche, basée sur une démarche de type \emph{générer, tester} ne peu
 pas être retenue pour $n$ de grande taille, même 
 en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
 
 pas être retenue pour $n$ de grande taille, même 
 en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
 

-Cependant, pour des valeurs de $n$ petites, nous avons 
+Cependant, pour des petites valeurs de $n$, nous avons 

 comparé les fonctions non équivalentes selon leur proportion
 à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})).
 
 comparé les fonctions non équivalentes selon leur proportion
 à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})).
 


@@ -162,9 +163,9 @@ $$
 \end{table}
 \end{xpl}
 
 \end{table}
 \end{xpl}
 

-Une analyse syntaxique de ces fonctions ne permet pas, à priori, 
+Une analyse syntaxique de ces fonctions ne permet pas, a priori, 

 de déduire des règles permettant de construire de nouvelles
 de déduire des règles permettant de construire de nouvelles

-fonction dont le temps de mélange serait faible.
+fonctions dont le temps de mélange serait faible.

 Cependant, le graphe $\textsc{giu}(f^*)$ 
 (donné à la Figure~\ref{fig:iteration:f*})
 est le $3$-cube dans lequel le cycle 
 Cependant, le graphe $\textsc{giu}(f^*)$ 
 (donné à la Figure~\ref{fig:iteration:f*})
 est le $3$-cube dans lequel le cycle 


@@ -320,9 +321,9 @@ hamiltonien $c$.
 Aucun arc n'appartient à la fois  à $r$ et à $c$: 
 en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
 Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.
 Aucun arc n'appartient à la fois  à $r$ et à $c$: 
 en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
 Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.

-Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds.
-Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles 
-depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui
+Le cycle $r$ est évidemment un cycle hamiltonien et contient tous les n{\oe}uds.
+Tous les n{\oe}uds de $C_1$ dans lesquels $c$ a été enlevé sont accessibles 
+depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsc{giu}$ qui

 étend le précédent graphe est ainsi fortement connexe. 
 
 \end{proof}
 étend le précédent graphe est ainsi fortement connexe. 
 
 \end{proof}


@@ -371,7 +372,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
 $\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}
 vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.
 
 \begin{xpl}


@@ -407,7 +408,7 @@ Enfin, les auteurs de~\cite{ZanSup04} présentent une extension de l'algorithme
 principalement de prouver que si $\mathsf{N}$ est une puissance de 2, 
 le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et 
 que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits 
 principalement de prouver que si $\mathsf{N}$ est une puissance de 2, 
 le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et 
 que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits 

-si  $S_{\mathsf{N}-2}$ l'est aussi.. 
+si  $S_{\mathsf{N}-2}$ l'est aussi. 

 Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement  
 un code de Gray (totalement) équilibré. 
 Cette section montre que ceci est vrai en rappelant tout d'abord
 Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement  
 un code de Gray (totalement) équilibré. 
 Cette section montre que ceci est vrai en rappelant tout d'abord


@@ -435,17 +436,17 @@ deux premiers éléments qui ont été intervertis.
 
 L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé
 comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré.
 
 L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé
 comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré.

-La théorème suivante montre que c'est possible et sa preuve,
-donnée en annexes~\ref{anx:generateur}, explique comment le faire. 
+Le théorème suivant montre que c'est possible et sa preuve,
+donnée en annexe~\ref{anx:generateur}, explique comment le faire. 

 
 \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$. 
 
 \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} extension telle que 
-le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ 
-sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ 
+Il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
+de l'algorithme de \emph{Robinson-Cohn}  telle que 
+les nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ 
+valent tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ 

 pour chaque  $i$, $1 \le i \le \mathsf{N}$.
 \end{restatable}
 
 pour chaque  $i$, $1 \le i \le \mathsf{N}$.
 \end{restatable}
 


@@ -461,11 +462,11 @@ stratégie donnée.
 Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un 
 graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la 
 stratégie.
 Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un 
 graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la 
 stratégie.

-On remarque que ce graphe d'itération est toujours un sous graphe 
+On remarque que ce graphe d'itérations est toujours un sous graphe 

 du   ${\mathsf{N}}$-cube augmenté des 
 boucles sur chaque sommet, \textit{i.e.}, les arcs
 $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. 
 du   ${\mathsf{N}}$-cube augmenté des 
 boucles sur chaque sommet, \textit{i.e.}, les arcs
 $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. 

-Ainsi, le travail ci dessous répond à la question de 
+Ainsi, le travail ci-dessous répond à la question de 

 définir la longueur du chemin minimum dans ce graphe pour 
 obtenir une distribution uniforme.
 Ceci se base sur la théorie des chaînes de Markov.
 définir la longueur du chemin minimum dans ce graphe pour 
 obtenir une distribution uniforme.
 Ceci se base sur la théorie des chaînes de Markov.


@@ -477,6 +478,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 +487,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,7 +510,17 @@ P=\dfrac{1}{6} \left(
 \]
 \end{xpl}
 
 \]
 \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} seraient 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 
 
 
 Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 


@@ -518,7 +531,7 @@ $$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$
 On sait que 
 $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
 De plus, si 
 On sait que 
 $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
 De plus, si 

-$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a 
+$\nu$ est une distribution sur $\Bool^{\mathsf{N}}$, on a 

 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
 
 Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. 
 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
 
 Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. 


@@ -531,72 +544,35 @@ $$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\}.$$
 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}.
-
-
-\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}
+Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire 
+pour être proche de la distribution stationnaire à $\varepsilon$ près, 
+peu importe la configuration de départ. On a le théorème suivant démontré en annexe~\ref{anx:generateur}.

 
 
 
 

-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 
+x
+\leq \lceil\log_2(\varepsilon^{-1})
+(32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1)) 
+\] 
+\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 d'un majorant 
-du temps d'arrêt.   

 
 
 Sans entrer dans les détails de la preuve, on remarque aussi
 
 
 Sans entrer dans les détails de la preuve, on remarque aussi


@@ -605,7 +581,7 @@ 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.
 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, ce majorant  pourrait être réduite.
+En intégrant cette contrainte, ce majorant  pourrait être réduit.

 
 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.
 
 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 +590,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
 
 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 
 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 +600,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 
 $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 

-à le majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture 
+au majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture 

 donnée au paragraphe précédent est sensée.
 
 
 donnée au paragraphe précédent est sensée.
 
 


@@ -648,7 +624,7 @@ $\textit{fair}\leftarrow\emptyset$\;
 }
 \Return{$\textit{nbit}$}\;
 %\end{scriptsize}
 }
 \Return{$\textit{nbit}$}\;
 %\end{scriptsize}

-\caption{Pseudo Code pour évaluer le temps d'arrêt}
+\caption{Pseudo-code pour évaluer le temps d'arrêt}

 \label{algo:stop}
 \end{algorithm}
 
 \label{algo:stop}
 \end{algorithm}
 


@@ -711,7 +687,7 @@ généralisées.
   définie par 
   $M = \dfrac{1}{2^n} \check{M}$.
   Si $\textsc{gig}(f)$ est fortement connexe, alors 
   définie par 
   $M = \dfrac{1}{2^n} \check{M}$.
   Si $\textsc{gig}(f)$ est fortement connexe, alors 

-  la sortie du générateur de nombres pseudo aléatoires détaillé par 
+  la sortie du générateur de nombres pseudo-aléatoires détaillé par 

   l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.
   l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.


@@ -723,8 +699,9 @@ Elle n'est donc pas rappelée.
 \begin{xpl}
 
   On reprend l'exemple donné à la section~\ref{sec:plc}.
 \begin{xpl}
 
   On reprend l'exemple donné à la section~\ref{sec:plc}.

-  Dans le $3$-cube, le cycle hamiltonien défini par la séquence
-  $000,100,101,001,011,111,110,010,000$ a été supprimé engendrant 
+  On considère le cycle hamiltonien défini par la séquence
+  $000,100,101,001,011,111,110,010,000$. En supprimant celui-ci dans 
+  le $3$-cube, cela engendre 

   la fonction $f^*$ définie par 
   $$f^*(x_1,x_2,x_3)=
   (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
   la fonction $f^*$ définie par 
   $$f^*(x_1,x_2,x_3)=
   (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},


@@ -855,7 +832,7 @@ fonctions qui  ont été  générées selon  la méthode détaillée
 à la  section~\ref{sec:hamiltonian}.
 Pour  chaque nombre $n=3$,  $4$, $5$ et $6$,
 tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les
 à la  section~\ref{sec:hamiltonian}.
 Pour  chaque nombre $n=3$,  $4$, $5$ et $6$,
 tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les

-valeur de $n=7$ et $8$,  seules $10^{5}$ cycles ont été évalués.  Parmi
+valeur de $n=7$ et $8$,  seuls $10^{5}$ cycles ont été évalués.  Parmi

 toutes  les fonctions  obtenues en  enlevant du  $n$-cube ces  cycles,  n'ont été
 retenues que celles  qui minimisaient le temps de mélange relatif  à une valeur de
 $\epsilon$ fixée à $10^{-8}$ et pour un mode donné.  
 toutes  les fonctions  obtenues en  enlevant du  $n$-cube ces  cycles,  n'ont été
 retenues que celles  qui minimisaient le temps de mélange relatif  à une valeur de
 $\epsilon$ fixée à $10^{-8}$ et pour un mode donné.  


@@ -865,7 +842,7 @@ colonne sous la variable $b$.
 La variable $b'$ reprend le temps de mélange pour
 l'algorithme~\ref{CI Algorithm}. 
 On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations, 
 La variable $b'$ reprend le temps de mélange pour
 l'algorithme~\ref{CI Algorithm}. 
 On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations, 

-il peut avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps 
+il peut y avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps 

 de mélange est construit à partir de la matrice de Markov et que celle-ci dépend 
 du mode, une fonction peut être optimale pour un mode et  ne pas l'être pour l'autre
 (c.f. pour $n=5$).
 de mélange est construit à partir de la matrice de Markov et que celle-ci dépend 
 du mode, une fonction peut être optimale pour un mode et  ne pas l'être pour l'autre
 (c.f. pour $n=5$).


@@ -879,8 +856,8 @@ l'on marche.
 Cela s'explique assez simplement. Depuis une configuration initiale, le nombre 
 de configurations qu'on ne peut pas atteindre en une itération est de: 
 \begin{itemize}
 Cela s'explique assez simplement. Depuis une configuration initiale, le nombre 
 de configurations qu'on ne peut pas atteindre en une itération est de: 
 \begin{itemize}

-\item $2^n-n$ en unaire. Ceci représente un rapport de 
-  $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$ 
+\item $2^n-n-1$ en unaire. Ceci représente un rapport de 
+  $\dfrac{2^n-n-1}{2^n} = 1-\dfrac{n-1}{2^n}$ 

   de toutes les configurations; plus $n$ est grand, 
   plus ce nombre est proche de $1$, et plus grand devient le nombre 
   d'itérations nécessaires pour atteinte une déviation faible;
   de toutes les configurations; plus $n$ est grand, 
   plus ce nombre est proche de $1$, et plus grand devient le nombre 
   d'itérations nécessaires pour atteinte une déviation faible;


@@ -929,7 +906,7 @@ $$
 \end{array}
 $$
 \caption{Nombre moyen 
 \end{array}
 $$
 \caption{Nombre moyen 

-  d'appels à un générateurs binaire par bit généré}\label{table:marchevssaute}
+  d'appels à un générateur binaire par bit généré}\label{table:marchevssaute}

 \end{table}
 
 
 \end{table}
 
 


@@ -954,7 +931,7 @@ permet de générer la stratégie aléatoire.
  que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
 
 
  que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
 
 

-Les tableau~\ref{fig:TEST:generalise} donnent
+Les tableaux~\ref{fig:TEST:generalise} donnent

 une vision synthétique de ces expérimentations. 
 Nous avons évalué les fonctions préfixées par 
 $f$ (respectivement $g$) avec les générateurs issus des itérations 
 une vision synthétique de ces expérimentations. 
 Nous avons évalué les fonctions préfixées par 
 $f$ (respectivement $g$) avec les générateurs issus des itérations 


@@ -964,10 +941,10 @@ générateurs passe
 avec succès le test de NIST. 
 
 Interpréter ces résultats en concluant que ces générateurs sont 
 avec succès le test de NIST. 
 
 Interpréter ces résultats en concluant que ces générateurs sont 

-tous équivalents serait erroné: la meilleur des 
+tous équivalents serait erroné: la meilleure des 

 méthodes basées sur le mode des itérations
 généralisées (pour $n=8$ par exemple) 
 méthodes basées sur le mode des itérations
 généralisées (pour $n=8$ par exemple) 

-est au moins deux fois plus rapide que la meilleur de celles qui 
+est au moins deux fois plus rapide que la meilleure de celles qui 

 sont basées sur les itérations unaires.
 
 
 sont basées sur les itérations unaires.
 
 


@@ -1084,7 +1061,7 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl
 
 
 \section{Conclusion}
 
 
 \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. 
 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.