On a vu dans le chapitre précédent que pour avoir
un générateur à sortie
uniforme, il est nécessaire que la matrice d'adjacence du graphe d'itération du
-système soit doublement stochastique. Nous présentons dans cette partie une
-méthode permettant de générer de telles matrices.
-
-Les approches théoriques basées sur la programmation logique par contraintes sur
-domaines finis ne sont pas envisageables en pratique dès que la taille des
-matrices considérées devient suffisamment grande.
-
+système soit doublement stochastique. Nous présentons dans cette partie
+des méthodes effectives permettant de générer de telles matrices.
+La première est basée sur la programmation logique par contraintes
+(Section~\ref{sec:plc}).
+Cependant celle-ci souffre de ne pas passer à l'échelle et ne fournit pas
+une solution en un temps raisonnable dès que la fonction à engendrer
+porte sur un grand nombre de bits.
Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans le
-graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
-arête sortante et une arête entrante.
+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
+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
+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}.
+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
+à~\cite{chgw+14:oip}.
% This aim of this section is to show
\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;
\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
+arithmétiques simples (sommes et produits). Il pourrait théoriquement être
traité par des démarches de programmation logique par contrainte
sur des domaines finis (comme en PROLOG).
L'algorithme donné en Figure~\ref{fig:prolog}
valent True si et seulement si $R$
est le produit matriciel (ou la somme matricielle)
entre $X$ and $Y$ respectivement.
-il n'est pas difficile d'adapter ce code à n'importe quelle valeur
+Il n'est pas difficile d'adapter ce code à n'importe quelle valeur
entière naturelle $\mathsf{N}$.
\begin{figure}[ht]
\end{figure}
Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux
-fonctions $f$ et $g$ si leur graphes
-respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$
+fonctions $f$ et $g$ si leurs graphes
+respectifs $\textsc{giu}(f)$ et $\textsc{giu}(g)$
sont isomorphes.
C'est évidemment une relation d'équivalence.
%\subsection{Analyse de l'approche}\label{sub:prng:ana}
-Exécutée sur un ordinateur personnelle, PROLOG trouve
+Exécutée sur un ordinateur personnel, PROLOG trouve
en moins d'une seconde les
49 solutions pour $n=2$,
dont 2 seulement ne sont pas équivalentes,
Cependant, pour des valeurs de $n$ petites, nous avons
comparé les fonctions non équivalentes selon leur proportion
-à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
+à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})).
(donné à la Figure~\ref{fig:iteration:f*})
est le $3$-cube dans lequel le cycle
$000,100,101,001,011,111,110,010,000$
-a été enlevé. Dans cette figure, le le graphe $\textsc{giu}(f)$ est
+a été enlevé. Dans cette figure, le graphe $\textsc{giu}(f)$ est
en continu tandis que le cycle est en pointillés.
Ce cycle qui visite chaque n{\oe}ud exactement une fois est un
\emph{cycle hamiltonien}.
La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
$n$-cube, produit une matrice doublement stochastique.
\end{theorem}
-\begin{Proof}
+\begin{proof}
Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
une arête entrante $(o,v)$ et une arête sortante $(v,e)$
-est ainsi enlevée.
+sont ainsi enlevées.
Considérons un autre $n$-cube $C_2$ auquel on ajoute les arêtes
pour le rendre complet. La matrice de Markov $M$ correspondante est
remplie de $\frac{1}{2^n}$ et est doublement stochastique.
Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et
$M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
$M$ est donc doublement stochastique.
-\end{Proof}
+\end{proof}
\end{theorem}
-\begin{Proof}
+\begin{proof}
On considère les deux $n$-cubes $C_1$ et $C_2$ définis
dans la preuve du théorème~\ref{th:supprCH}.
Dans $C_1$ on considère le cycle inverse $r$ du cycle
depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui
étend le précédent graphe est ainsi fortement connexe.
-\end{Proof}
+\end{proof}
%Les preuves, relativement directes, sont laissées en exercices au lecteur.
-La génération de cycles hamiltoniens dans le
-$n$-cube, ce qui revient à trouver des \emph{codes de Gray cycliques}. On
-rappelle que les codes de Gray sont des séquences de mots binaires de taille
-fixe ($n$), dont les éléments successifs ne différent que par un seul bit. Un
+Générer un cycle hamiltonien dans le
+$n$-cube revient à trouver un \emph{code de Gray cyclique}. On
+rappelle qu'un code de Gray est une séquence de mots binaires de taille
+fixe ($\mathsf{N}$), dont les éléments successifs ne différent que par un seul bit. Un
code de Gray est \emph{cyclique} si le premier élément et le dernier ne
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
-d'itérations $\textsf{giu}(f)$ \emph{uniforme}. Cette uniformité se traduit par des
+d'itérations $\textsc{giu}(f)$ \emph{uniforme}. Cette uniformité se traduit par des
nombres d'arcs équilibrés entre les \emph{dimensions} du graphe, la dimension
$i$ correspondant aux seules variations du bit $i$ (parmi les $n$ bits au
total). Cette approche revient à chercher des codes de Gray cycliques
\emph{équilibrés}.
-Un code de Gray équilibré peut être défini de la façon suivante :
-
-\begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
- Soit $L = w_1, w_2, \dots, w_{2^n}$ la séquence d'un code de Gray cyclique à
- $n$ bits. Soit $S = s_1, s_2, \dots, s_{2^n}$ la séquence des transitions où
- $s_i$, $1 \le i \le 2^n$ est l'indice du seul bit qui varie entre les mots
- $w_i$ et $w_{i+1}$. Enfin, soit $\textit{NT}_n : \{1,\dots, n\} \rightarrow
- \{0, \ldots, 2^n\}$ la fonction qui au paramètre $i$ associe le \emph{nombre
- de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
- le nombre d'occurrences de $i$ dans $S$.
+On formalise un code de Gray équilibré comme suit.
+Soit $L = w_1, w_2, \dots, w_{2^n}$ la séquence d'un code de Gray cyclique à
+$n$ bits. Soit $S = s_1, s_2, \dots, s_{2^n}$ la séquence des transitions où
+$s_i$, $1 \le i \le 2^n$ est l'indice du seul bit qui varie entre les mots
+$w_i$ et $w_{i+1}$. Enfin, soit $\textit{TC}_n : \{1,\dots, n\} \rightarrow
+\{0, \ldots, 2^n\}$ la fonction qui au paramètre $i$ associe le \emph{nombre
+ de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
+le nombre d'occurrences de $i$ dans $S$.
- Le code $L$ est \textbf{équilibré} si $\forall
- i,j\in\{1,...,n\},~|\textit{NT}_n(i) - \textit{NT}_n(j)| \le 2$. Il est
- \textbf{totalement équilibré} si $\forall
- i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
-\end{Def}
+Le code $L$ est \textbf{équilibré} si $\forall
+i,j\in\{1,...,n\},~|\textit{TC}_n(i) - \textit{TC}_n(j)| \le 2$. Il est
+\textbf{totalement équilibré} si $\forall
+i\in\{1,...,n\},~\textit{TC}_n(i)=\frac{2^n}{n}$.
+
On peut donc déjà déduire qu'il ne peut exister des codes de Gray totalement
équilibrés que pour les systèmes ayant un nombre d'éléments $n=2^k, k>0$. De
-plus, comme dans tout code de Gray cyclique, $\textit{NT}_n(i)$ est pair
+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{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou
+$\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
-vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
+vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.
\begin{xpl}
Soit $L^*=000,100,101,001,011,111,110,010$ le code de Gray correspondant au
\section{Génération de codes de Gray équilibrés par induction}
\label{sec:induction}
-Dans leur article de 2004~\cite{ZanSup04}, Zanten et Suparta proposent un
-algorithme inductif pour générer des codes de Gray équilibrés de $n$ bits à
-partir de codes de $n-2$ bits. Cependant, leur méthode n'est pas
-constructive. En effet, elle effectue des manipulations sur un partitionnement du
-code de Gray initial de $n-2$ bits pour obtenir un code de Gray sur $n$ bits,
-mais le résultat n'est pas systématiquement équilibré. Il est donc nécessaire
-d'évaluer les résultats obtenus à partir de tous les partitionnements réalisables
-en suivant les contraintes spécifiées. Or, le nombre de possibilités augmente
-exponentiellement (voir~\cite{Mons14} pour l'évaluation détaillée), ce qui rend
-déraisonnable tout parcours exhaustif. Une amélioration proposée
-dans~\cite{Mons14} permet de réduire le nombre de partitionnements considérés,
-mais l'ordre de grandeur reste similaire. On constate donc clairement ici la
-nécessité de trouver des algorithmes de génération de codes de Gray équilibrés
-plus efficaces. Ce problème représente une des voies que nous souhaitons
-explorer dans la suite de nos travaux.
-
-Le tableau~\ref{table:nbFunc} donne le nombre de fonctions différentes
-compatibles avec les codes de Gray équilibrés générés par l'approche précédente
-selon le nombre de bits. Il donne donc la taille de la classe des générateurs
-pouvant être produits. Les cas 7 et 8 ne sont que des bornes minimales basées
-sur des sous-ensembles des partitionnements possibles.
-
-\begin{table}[ht]
- \begin{center}
- \begin{tabular}{|l|c|c|c|c|c|}
- \hline
- $n$ & 4 & 5 & 6 & 7 & 8 \\
- \hline
- nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
- \hline
- \end{tabular}
- \end{center}
-\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc}
-\end{table}
-
+De nombreuses approches ont été développées pour résoudre le problème de construire
+un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04},
+selon les propriétés que doit vérifier ce code.
+
+Dans les travaux~\cite{Robinson:1981:CS}, les auteurs
+proposent une approche inductive de construction de code de Gray équilibrés
+(on passe du $\mathsf{N}-2$ à $\mathsf{N}$)
+pour peu que l'utilisateur fournisse une sous-séquence possédant certaines
+propriétés à chaque pas inductif.
+Ce travail a été renforcé dans ~\cite{DBLP:journals/combinatorics/BhatS96}
+où les auteurs donnent une manière explicite de construire une telle sous-séquence.
+Enfin, les auteurs de~\cite{ZanSup04} présentent une extension de l'algorithme de
+\emph{Robinson-Cohn}. La présentation rigoureuse de cette extension leur permet
+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..
+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
+l'extension de l'algorithme de \emph{Robinson-Cohn} pour un
+code de Gray avec $\mathsf{N}-2$ bits
+défini à partir de la séquence $S_{\mathsf{N}-2}$.
-Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-séquences
+$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$
+telles que $S_{\mathsf{N}-2}$ est la concaténation de
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+où $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la séquence vide).
+\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les séquences $u_0, u_1, u_2, \ldots, u_{l-2}$
+ par
+ $\mathsf{N} - 1, u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+ respectivement, où $u'(u,x,y)$ est la séquence $u,x,u^R,y,u$ telle que
+ $u^R$ est $u$, mais dans l'ordre inverse. La séquence obtenue est ensuite notée $U$.
+\item\label{item:VW} Construire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit alors $W'$ définie comme étant égale à $W$ sauf pour les
+deux premiers éléments qui ont été intervertis.
+\item La séquence de transition $S_{\mathsf{N}}$ est la concaténation $U^R, V, W'$.
+\end{enumerate}
+
+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.
+
+\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$
+pour chaque $i$, $1 \le i \le \mathsf{N}$.
+\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.
C'est l'objectif de la section suivante.
-\section{Quantifier l'écart par rapport à la distribution uniforme}
+\section{Quantifier l'écart par rapport à la distribution uniforme}\label{sec:mixing}
On considère ici une fonction construite comme à la section précédente.
On s'intéresse ici à étudier de manière théorique les
itérations définies à l'équation~(\ref{eq:asyn}) pour une
+
+
\begin{xpl}
On considère par exemple le graphe $\textsc{giu}(f)$ donné à la
\textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de
$$
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.
\]
\end{xpl}
+On remarque que dans cette marche on reste sur place avec une probabilité
+
+
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
\P_X(\tau > t)$.
\end{theorem}
-\begin{theorem} \label{prop:stop}
-If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+
+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}[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}
-
-Sans entrer dans les détails de la preuve, on remarque tout d'abord
-que le calcul
-de cette borne n'intègre pas le fait qu'on préfère enlever des
-chemins hamiltoniens équilibrés.
-En intégrant cette contrainte, la borne supérieure pourrait être réduite.
+\end{restatable}
-On remarque ensuite 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
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 ${1}{n}$.
+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 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, 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.
+On peut ainsi conjecturer que cet ordre de grandeur reste le même
+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
+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
+ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$
+est exécuté 10000 fois avec une graine aléatoire. La Figure~\ref{fig:stopping:moy}
+résume ces résultats. Dans celle-ci, un cercle représente une approximation de
+$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
+donnée au paragraphe précédent est sensée.
-\section{Et les itérations généralisées?}
-Le chaptire précédent a présenté un algorithme de
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
+{
+ $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
+ $\textit{image} \leftarrow f(x) $\;
+ \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+ $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+ $x[s] \leftarrow \textit{image}[s]$\;
+ }
+ $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code pour évaluer le temps d'arrêt}
+\label{algo:stop}
+\end{algorithm}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Interpolation du temps d'arrêt}\label{fig:stopping:moy}
+\end{figure}
+
+
+
+
+\section{Et les itérations généralisées?}\label{sec:prng:gray:general}
+Le chapitre précédent a présenté un algorithme de
PRNG construit à partir d'itérations unaires.
On pourrait penser que cet algorithme est peu efficace puisqu'il
dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à
Dans celle-ci la fonction $\textit{Set} : \{1,\ldots,2^n\} \rightarrow
\mathcal{P}(\{1,\ldots n\})$ retourne l'ensemble dont la fonction
caractéristique serait représentée par le nombre donné en argument.
-Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
+Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudrait $\{3,2\}$.
On remarque aussi que l'argument de la fonction $\textit{Random}$
passe de $n$ à $2^n$.
& & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\
& & 16, 24, 13, 12, 29, 8, 10, 42, 41, 0, 5, 2, 4, 6, 11, 34, 9, 32] & & \\
\hline
-
-
-
-
-
-
- &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 87, 126, 119, 84, 123, & 10 & 63 \\
- & & 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 108, 101, 70, & & \\
- & & 117, 96, 67, 102, 113, 64, 79, 30, 95, 124, 83, 91, 121, 24, & & \\
- & & 23, 118, 69, 20, 115, 90, 17, 112, 77, 14, 73, 78, 74, 10, 72, & & \\
- & & 76, 103, 6, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, & & \\
- & & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, & & \\
- & & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, & & \\
- & & 26, 18, 89, 25, 19, 86, 85, 4, 27, 2, 16, 80, 31, 12, 15, 8, & & \\
- & & 3, 11, 13, 9, 5, 22, 21, 68, 7, 66, 65, 1] & & \\
+ \multirow{9}{0.5cm}{7} &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 115, 126, 85, 84, 123, & \multirow{9}{0.5cm}{\textbf{10}} & \multirow{9}{0.5cm}{\textbf{63}} \\
+ & & 98, 81, 120, 109, 78, 105, 110, 99, 107, 104, 108, 101, 118, & & \\
+ & & 117, 96, 103, 66, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, & & \\
+ & & 119, 22, 69, 20, 87, 18, 17, 112, 77, 76, 73, 12, 74, 106, 72, & & \\
+ & & 8, 7, 102, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, & & \\
+ & & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, & & \\
+ & & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, & & \\
+ & & 26, 90, 89, 25, 19, 30, 23, 4, 27, 2, 16, 80, 31, 10, 15, 14, & & \\
+ & & 3, 11, 13, 9, 5, 70, 21, 68, 67, 6, 65, 1] & & \\
\hline
- & $f^{*8}$ &[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,& 9 & 72 \\
- & & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, &&\\
- & & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, &&\\
- & & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, &&\\
- & & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, &&\\
- & & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,&&\\
- & & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, &&\\
- & & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,&&\\
- & & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, &&\\
- & & 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, &&\\
- & & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, &&\\
- & & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120,&&\\
- & & 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81,&&\\
- & & 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, &&\\
- & & 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, &&\\
- & & 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, && \\
- & & 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19,&&\\
- & & 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, &&\\
- & &138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]&&\\
+ \multirow{20}{0.5cm}{8} & $f^{*8}$ &
+[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,&
+\multirow{20}{0.5cm}{9}&
+\multirow{20}{0.5cm}{71}\\
+& & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168,& & \\
+& & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216,& & \\
+& & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209,& & \\
+& & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132,& & \\
+& & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,& & \\
+& & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42,& & \\
+& & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,& & \\
+& & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153,& & \\
+& & 145, 175, 206, 143, 12, 11, 142, 129, 128, 7, 198, 197, 4, 195,& & \\
+& & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114,& & \\
+& & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121,& & \\
+& & 120, 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83,& & \\
+& & 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72,& & \\
+& & 107, 78, 105, 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45,& & \\
+& & 188, 51, 186, 61, 40, 119, 182, 181, 53, 179, 54, 33, 49, 15,& & \\
+& & 174, 47, 60, 171, 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0,& & \\
+& & 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16,& & \\
+& & 24, 13, 10, 29, 14, 3, 138, 41, 136, 39, 134, 133, 5, 131,& & \\
+& & 34, 9, 8]&&\\
\hline
\end{tabular}
\end{scriptsize}
\end{center}
-\label{table:functions}
-\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
-
+\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange}\label{table:functions}
\end{table}
Le tableau~\ref{table:functions} reprend une synthèse de
valeur de $n=7$ et $8$, seules $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}$.
+$\epsilon$ fixée à $10^{-8}$ et pour un mode donné.
Ce nombre d'itérations (\textit{i.e.}, ce temps de mélange)
est stocké dans la troisième
colonne sous la variable $b$.
La variable $b'$ reprend le temps de mélange pour
-l'algorithme~\ref{CI Algorithm}.
-
-Un premier résultat est que ce nouvel algorithme réduit grandement le nombre
+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
+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$).
+
+Un second résultat est que ce nouvel algorithme réduit grandement le nombre
d'itérations suffisant pour obtenir une faible déviation par rapport à une
-distribution uniforme. On constate de plus que ce nombre décroit avec
+distribution uniforme. On constate de plus que ce nombre décroît avec
le nombre d'éléments alors qu'il augmente dans l'approche initiale où
l'on marche.
Le tableau~\ref{table:marchevssaute} donne des instances de
ces valeurs pour $n \in\{4,5,6,7,8\}$ et les fonctions
données au tableau~\ref{table:functions}.
-On constate que le nombre d'appels par bit généré décroit avec $n$ dans le
+On constate que le nombre d'appels par bit généré décroît avec $n$ dans le
cas des itérations généralisées et est toujours plus faible
que celui des itérations unaires.
\hline
\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\
\hline
-\textrm{Unaires} & 19.0 & 22.2905097109 & 23.6954895899 & 25.2661942985 & 27.0\\
+\textrm{Unaires} & 19.0 & 22.3 & 23.7 & 25.3 & 27.0\\
\hline
-\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\
+\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\
\hline
\end{array}
$$
-\section{Tests statistiques}
+\section{Tests statistiques}\label{sec:prng;gray:tests}
La qualité des séquences aléatoires produites par
le générateur des itérations unaires ainsi que
celles issues des itérations généralisées a été évaluée à travers la suite
de tests statistiques développée par le
\emph{National Institute of Standards and Technology} (NIST).
+En interne, c'est l'implantation de l'algorithme de Mersenne Twister qui
+permet de générer la stratégie aléatoire.
+
+
+
+
Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
une valeur
qui est plus grande que $1\%$ signifie
que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
-Le tableau~\ref{fig:TEST} donne une vision synthétique de ces expérimentations.
+Les tableau~\ref{fig:TEST:generalise} donnent
+une vision synthétique de ces expérimentations.
Nous avons évalué les fonctions préfixées par
-$f$ (respecitvement $g$) avec le générateur issu des itérations
+$f$ (respectivement $g$) avec les générateurs issus des itérations
généralisées (resp. unaires).
-%L'expérience a montré notamment que toutes ces fonctions
-%passent avec succès cette batterie de tests.
+Quelle que soit la méthode utilisée, on constate que chacun des
+générateurs passe
+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
+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
+sont basées sur les itérations unaires.
\begin{scriptsize}
-
+\begin{tabular}{|l|r|r|r|r|}
+ \hline
+Test & $f^{*5}$ &$f^{*6}$ &$f^{*7}$ &$f^{*8}$ \\ \hline
+Fréquence (Monobit)& 0.401 (0.97)& 0.924 (1.0)& 0.779 (0.98)& 0.883 (0.99)\\ \hline
+Fréquence ds un bloc& 0.574 (0.98)& 0.062 (1.0)& 0.978 (0.98)& 0.964 (0.98)\\ \hline
+Somme Cumulé*& 0.598 (0.975)& 0.812 (1.0)& 0.576 (0.99)& 0.637 (0.99)\\ \hline
+Exécution& 0.998 (0.99)& 0.213 (0.98)& 0.816 (0.98)& 0.494 (1.0)\\ \hline
+Longue exécution dans un bloc& 0.085 (0.99)& 0.971 (0.99)& 0.474 (1.0)& 0.574 (0.99)\\ \hline
+Rang& 0.994 (0.96)& 0.779 (1.0)& 0.191 (0.99)& 0.883 (0.99)\\ \hline
+Fourier rapide& 0.798 (1.0)& 0.595 (0.99)& 0.739 (0.99)& 0.595 (1.0)\\ \hline
+Patron sans superposition*& 0.521 (0.987)& 0.494 (0.989)& 0.530 (0.990)& 0.520 (0.989)\\ \hline
+Patron avec superposition& 0.066 (0.99)& 0.040 (0.99)& 0.304 (1.0)& 0.249 (0.98)\\ \hline
+Statistiques universelles& 0.851 (0.99)& 0.911 (0.99)& 0.924 (0.96)& 0.066 (1.0)\\ \hline
+Entropie approchée (m=10)& 0.637 (0.99)& 0.102 (0.99)& 0.115 (0.99)& 0.350 (0.98)\\ \hline
+Suite aléatoire *& 0.573 (0.981)& 0.144 (0.989)& 0.422 (1.0)& 0.314 (0.984)\\ \hline
+Suite aléatoire variante *& 0.359 (0.968)& 0.401 (0.982)& 0.378 (0.989)& 0.329 (0.985)\\ \hline
+Série* (m=10)& 0.469 (0.98)& 0.475 (0.995)& 0.473 (0.985)& 0.651 (0.995)\\ \hline
+Complexité linaire& 0.129 (1.0)& 0.494 (1.0)& 0.062 (1.0)& 0.739 (1.0)\\ \hline
+
+\end{tabular}
\end{scriptsize}
-\label{fig:TEST:generalise}
+
\caption{Test de NIST pour les fonctions
- du tableau~\ref{table:functions} selon les itérations généralisées}
+ du tableau~\ref{table:functions} selon les itérations généralisées}\label{fig:TEST:generalise}
\end{table}
\begin{table}[ht]
\centering
\begin{scriptsize}
+\begin{tabular}{|l|r|r|r|r|}
+\hline
+Test & $g^{*5}$& $g^{*6}$& $f^{*7}$& $f^{*8}$\\ \hline
+Fréquence (Monobit)& 0.236 (1.0)& 0.867 (0.99)& 0.437 (0.99)& 0.911 (1.0)\\ \hline
+Fréquence ds un bloc& 0.129 (0.98)& 0.350 (0.99)& 0.366 (0.96)& 0.657 (1.0)\\ \hline
+Somme Cumulé*& 0.903 (0.995)& 0.931 (0.985)& 0.863 (0.995)& 0.851 (0.995)\\ \hline
+Exécution& 0.699 (0.98)& 0.595 (0.99)& 0.181 (1.0)& 0.437 (0.99)\\ \hline
+Longue exécution dans un bloc& 0.009 (0.99)& 0.474 (0.97)& 0.816 (1.0)& 0.051 (1.0)\\ \hline
+Rang& 0.946 (0.96)& 0.637 (0.98)& 0.494 (1.0)& 0.946 (1.0)\\ \hline
+Fourier rapide& 0.383 (0.99)& 0.437 (1.0)& 0.616 (0.98)& 0.924 (0.99)\\ \hline
+Patron sans superposition*& 0.466 (0.990)& 0.540 (0.989)& 0.505 (0.990)& 0.529 (0.991)\\ \hline
+Patron avec superposition& 0.202 (0.96)& 0.129 (0.98)& 0.851 (0.99)& 0.319 (0.98)\\ \hline
+Statistiques universelles& 0.319 (0.97)& 0.534 (0.99)& 0.759 (1.0)& 0.657 (0.99)\\ \hline
+Entropie approchée (m=10)& 0.075 (0.97)& 0.181 (0.99)& 0.213 (0.98)& 0.366 (0.98)\\ \hline
+Suite aléatoire *& 0.357 (0.986)& 0.569 (0.991)& 0.539 (0.987)& 0.435 (0.992)\\ \hline
+Suite aléatoire variante *& 0.398 (0.989)& 0.507 (0.986)& 0.668 (0.991)& 0.514 (0.994)\\ \hline
+Série* (m=10)& 0.859 (0.995)& 0.768 (0.99)& 0.427 (0.995)& 0.637 (0.98)\\ \hline
+Complexité linaire& 0.897 (0.99)& 0.366 (0.98)& 0.153 (1.0)& 0.437 (1.0)\\ \hline
+
+\end{tabular}
+\end{scriptsize}
+
+
+\caption{Test de NIST pour les fonctions
+ du tableau~\ref{table:functions} selon les itérations unaires}\label{fig:TEST:unaire}
+\end{table}
+
+
+\begin{table}[ht]
+ \centering
+ \begin{scriptsize}
+
+\begin{tabular}{|l|r|r|r|r|}
+ \hline
+Test & 5 bits& 6 bits & 7 bits & 8bits \\ \hline
+Fréquence (Monobit)& 0.289 (1.0)& 0.437 (1.0)& 0.678 (1.0)& 0.153 (0.99)\\ \hline
+Fréquence ds un bloc& 0.419 (1.0)& 0.971 (0.98)& 0.419 (0.99)& 0.275 (1.0)\\ \hline
+Somme Cumulé*& 0.607 (0.99)& 0.224 (0.995)& 0.645 (0.995)& 0.901 (0.99)\\ \hline
+Exécution& 0.129 (0.99)& 0.005 (0.99)& 0.935 (0.98)& 0.699 (0.98)\\ \hline
+Longue exécution dans un bloc& 0.514 (1.0)& 0.739 (0.99)& 0.994 (1.0)& 0.834 (0.99)\\ \hline
+Rang& 0.455 (0.97)& 0.851 (0.99)& 0.554 (1.0)& 0.964 (0.99)\\ \hline
+Fourier rapide& 0.096 (0.98)& 0.955 (0.99)& 0.851 (0.97)& 0.037 (1.0)\\ \hline
+Patron sans superposition*& 0.534 (0.990)& 0.524 (0.990)& 0.508 (0.987)& 0.515 (0.99)\\ \hline
+Patron avec superposition& 0.699 (0.99)& 0.616 (0.95)& 0.071 (1.0)& 0.058 (1.0)\\ \hline
+Statistiques universelles& 0.062 (0.99)& 0.071 (1.0)& 0.637 (1.0)& 0.494 (0.98)\\ \hline
+Entropie approchée (m=10)& 0.897 (0.99)& 0.383 (0.99)& 0.366 (1.0)& 0.911 (0.99)\\ \hline
+Suite aléatoire *& 0.365 (0.983)& 0.442 (0.994)& 0.579 (0.992)& 0.296 (0.993)\\ \hline
+Suite aléatoire variante *& 0.471 (0.978)& 0.559 (0.992)& 0.519 (0.987)& 0.340 (0.995)\\ \hline
+Série* (m=10)& 0.447 (0.985)& 0.298 (0.995)& 0.648 (1.0)& 0.352 (0.995)\\ \hline
+Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hline
+
+\end{tabular}
+
+
+
+
+
+
+
\end{scriptsize}
-\label{fig:TEST:unaire}
-\caption{Test de NIST pour les fonctions
- du tableau~\ref{table:functions} selon les itérations unaires}
+
+\caption{Test de NIST pour l'algorithme de Mersenne Twister}\label{fig:TEST:Mersenne}
\end{table}
-%
+
+\section{Conclusion}
+Ce chaptitre 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
+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
+ $\mathsf{N} = 4, 5, 6, 7, 8$.
+
