+De nombreuses approches ont été developpé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 autheurs 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.
+
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-sequences
+$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 sequences $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} Contruire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit alors $W'$ définie commé é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 concatenation $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éoreme suivante montre que c'est possible et sa preuve explique comment le faire.
+
+
+\begin{theorem}\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{theorem}
+
+La preuve de ce théorème est donnée en annexes~\ref{anx:generateur}.
+
+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}
+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ération 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{2}{3} \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}
+
+
+
+
+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 on $\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\}.$$
+
+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}
+
+
+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{theorem} \label{prop:stop}
+Si $\ov{h}$ is 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}
+
+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}$.
+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
+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 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 algorithm~\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 fonctionss 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 resultats. 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 cosntate que l'approximation de $E[\ts]$ est largement inférieure
+à la borne quadratique donnée au thérè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 of stoping time calculus }
+\label{algo:stop}
+\end{algorithm}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+
+
+
+\section{Et les itérations généralisées?}
+Le chaptire 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)$ vaudraitt $\{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}.
+ 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
+ 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}
+
+
