+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}$.
+
+\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é.
+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$.
+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}
+
+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}\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
+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.
+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}}$.
+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.
+Pour une référence
+générale à ce sujet on pourra se référer
+au livre~\cite{LevinPeresWilmer2006},
+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
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+$$
+p(e) \left\{
+\begin{array}{ll}
+= \frac{1}{2} + \frac{1}{6} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
+= \frac{1}{6} \textrm{ sinon.}
+\end{array}
+\right.
+$$
+La matrice $P$ de la chaîne de Markov associée à $f^*$
+est
+\[
+P=\dfrac{1}{6} \left(
+\begin{array}{llllllll}
+4&1&1&0&0&0&0&0 \\
+1&4&0&0&0&1&0&0 \\
+0&0&4&1&0&0&1&0 \\
+0&1&1&4&0&0&0&0 \\
+1&0&0&0&4&0&1&0 \\
+0&0&0&0&1&4&0&1 \\
+0&0&0&0&1&0&4&1 \\
+0&0&0&1&0&1&0&4
+\end{array}
+\right)
+\]
+\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
+$\Bool^{\mathsf{N}}$.
+La distance de \og totale variation\fg{} entre $\pi$ et $\mu$
+est notée $\tv{\pi-\mu}$ et est définie par
+$$\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
+$\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}}$.
+$P(X,\cdot)$ est la distribution induite par la $X^{\textrm{ème}}$ colonne
+de $P$.
+Si la chaîne de Markov induite par
+$P$ a une distribution stationnaire $\pi$, on définit alors
+$$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\}.$$
+
+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}.
+
+
+\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
+
+\[
+\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}
+
+
+
+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é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.
+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
+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.
+
+
+\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 à
+chaque itération qu'un seul élément de $[n]$.
+On pourrait penser à un algorithme basé sur les itérations généralisées,
+c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque
+itération.
+C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après.
+
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{une fonction $f$, un nombre d'itérations $b$,
+une configuration initiale $x^0$ ($n$ bits)}
+\KwOut{une configuration $x$ ($n$ bits)}
+$x\leftarrow x^0$\;
+$k\leftarrow b $\;
+\For{$i=1,\dots,k$}
+{
+$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
+$x\leftarrow{F_{f_g}(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{PRNG basé sur les itérations généralisées.}
+\label{CI Algorithm:prng:g}
+\end{algorithm}
+
+Par rapport à l'algorithme~\ref{CI Algorithm} seule
+la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est différente.
+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)$ vaudrait $\{3,2\}$.
+On remarque aussi que l'argument de la fonction $\textit{Random}$
+passe de $n$ à $2^n$.
+
+On a le théorème suivant qui étend le théorème~\ref{thm:prng:u} aux itérations
+généralisées.
+
+\begin{theorem}\label{thm:prng:g}
+ Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{gig}(f)$ son
+ graphe des itérations généralisées, $\check{M}$ la matrice d'adjacence
+ correspondante à ce graphe
+ et $M$ une matrice $2^n\times 2^n$
+ 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
+ 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.
+\end{theorem}
+
+La preuve de ce théorème est la même que celle du théorème~\ref{thm:prng:u}.
+Elle n'est donc pas rappelée.
+
+\begin{xpl}
+
+ On reprend l'exemple donné à la section~\ref{sec:plc}.
+ 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},
+\overline{x_1}.\overline{x_3} + x_1x_2).
+$$
+
+Le graphe $\textsc{gig}(f^*)$ est représenté à la
+Figure~\ref{fig:iteration:f*}.
+La matrice de Markov $M$ correspondante est donnée à
+la figure~\ref{fig:markov:f*}.
+
+\begin{figure}[ht]
+ \begin{center}
+ \subfigure[Graphe $\textsc{gig}(f^*)$
+ \label{fig:iteration:f*}]{
+ \begin{minipage}{0.55\linewidth}
+ \centering
+ \includegraphics[width=\columnwidth]{images/iter_f}%
+ \end{minipage}
+ }%
+ \subfigure[Matrice de Markov associée au $\textsc{gig}(f^*)$
+ \label{fig:markov:f*}]{%
+ \begin{minipage}{0.35\linewidth}
+ \begin{scriptsize}
+ \begin{center}
+ $ \dfrac{1}{4} \left(
+ \begin{array}{cccccccc}
+ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+
+ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
+
+ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
+
+ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+
+ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
+
+ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+
+ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+
+ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+
+ \end{array} \right) $
+ \end{center}
+ \end{scriptsize}
+ \end{minipage}
+ }%
+ \caption{Représentations de $f^*(x_1,x_2,x_3)=
+ (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
+ \overline{x_1}.\overline{x_3} + x_1x_2)$.}\label{fig1}
+ \end{center}
+\end{figure}
+\end{xpl}
+
+
+
+\begin{table}[ht]
+ \begin{center}
+ \begin{scriptsize}
+ \begin{tabular}{|c|c|l|c|c|}
+ \hline
+ $n$ & fonction & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$ & $b$ & $b'$ \\
+ \hline
+ 4 & $f^{*4}$ & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8] & \textbf{17} & \textbf{38} \\
+ \hline
+ \multirow{4}{0.5cm}{5}& $f^{*5}$ & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, & \textbf{13} & 48 \\
+ & & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4] & & \\
+ \cline{2-5}
+ & $g^{*5}$ & [29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, & 15 & \textbf{47} \\
+ & & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0, 16
+ & & \\
+
+ \hline
+ \multirow{8}{0.5cm}{6}& $f^{*6}$ &
+ [55, 60, 45, 56, 58, 42, 61, 40, 53, 50, 52, 54, 59, 34, 33, & \multirow{4}{0.5cm}{\textbf{11}}& \multirow{4}{0.5cm}{55}\\
+& & 49, 39, 62, 47, 46, 11, 43, 57, 8, 37, 6, 36, 4, 51, 38, 1, & & \\
+& & 48, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\
+& & 16, 24, 13, 12, 29, 44, 10, 14, 41, 0, 15, 2, 7, 5, 35, 3, 9, 32] & &\\
+ \cline{2-5}
+&$g^{*6}$ & [55, 60, 45, 44, 43, 62, 61, 48, 53, 50, 52, 36, 59, 51, 33, & \multirow{4}{0.5cm}{12}& \multirow{4}{0.5cm}{\textbf{54}}\\
+ & & 49, 15, 14, 47, 46, 35, 58, 57, 56, 7, 54, 39, 37, 3, 38, 1, & & \\
+ & & 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
+ \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
+ \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}
+\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
+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
+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é.
+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}.
+On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations,
+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$).
+
+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écroît avec
+le nombre d'éléments alors qu'il augmente dans l'approche initiale où
+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}
+\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;
+\item $2^n-2^{n-1}$ dans le cas généralisé,
+ soit la moitié de toutes les configurations
+ quel que soit $n$; seul 1 bit reste constant tandis que tous les autres peuvent changer. Plus $n$ grandit, plus la proportion de bits constants diminue.
+\end{itemize}
+
+Cependant, dans le cas généralisé, chaque itération a une complexité
+plus élevée puisqu'il est nécessaire d'invoquer un générateur
+produisant un nombre pseudo-aléatoire dans $[2^{n}]$ tandis qu'il suffit
+que celui-ci soit dans $[n]$ dans le cas unaire.
+Pour comparer les deux approches,
+on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1).
+
+Dans le cas généralisé, si l'on effectue $b$ itérations,
+à chacune d'elles, la stratégie génère un nombre entre
+$1$ et $2^n$. Elle fait donc $n$ appels à ce générateur.
+On fait donc au total $b*n$ appels pour $n$ bits et
+donc $b$ appels pour 1 bit généré en moyenne.
+Dans le cas unaire, si l'on effectue $b'$ itérations,
+à chacune d'elle, la stratégie génère un nombre entre
+$1$ et $n$.
+Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur binaire en moyenne.
+La démarche fait donc au total $b'*\ln(n)/\ln(2)$ appels pour $n$ bits et
+donc $b'*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
+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é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.
+
+
+
+\begin{table}[ht]
+$$
+\begin{array}{|l|l|l|l|l|l|}
+\hline
+\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\
+\hline
+\textrm{Unaires} & 19.0 & 22.3 & 23.7 & 25.3 & 27.0\\
+\hline
+\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\
+\hline
+\end{array}
+$$
+\caption{Nombre moyen
+ d'appels à un générateur binaire par bit généré}\label{table:marchevssaute}
+\end{table}
+
+
+
+
+\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\%$.
+
+
+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
+généralisées (resp. unaires).
+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 meilleure 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 meilleure de celles qui
+sont basées sur les itérations unaires.
+
+
+
+
+%%%%%%%%% Relancer pour n=6, n=7, n=8
+%%%%%%%%% Recalculer le MT
+%%%%%%%%% Regenerer les 10^6 bits
+%%%%%%%%% Evaluer sur NIST
+
+\begin{table}[ht]
+ \centering
+ \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}
+
+
+\caption{Test de NIST pour les fonctions
+ 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}
+
