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
\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
\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}$.
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})).
\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
-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
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}
\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
$\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}
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{theorem}\label{prop:balanced}
+\begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre}
+\label{prop:balanced}
Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par
$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$.
-il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
+Il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
de l'algorithme de \emph{Robinson-Cohn} telle que
-le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$
-sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$
+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{theorem}
+\end{restatable}
Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse
un générateur les embarquant converge vers la distribution uniforme.
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}}$.
-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.
+
+
\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é é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
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}}$.
et
$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-
-Un résultat classique est
-
-$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-
-
-
-Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de
-$\Bool^{\mathsf{N}}$.
-une variable aléatoire $\tau$ dans $\mathbb{N}$ est un
-\emph{temps d'arrêt} pour la suite
-$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
-(\Bool^{\mathsf{N}})^{t+1}$ tel que
-$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
-En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs
-de
-$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$.
-
-Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et
-$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci.
-Un \emph{temps d'arrêt aléatoire} pour la chaîne de
-Markov est un temps d'arrêt pour
-$(Z_t)_{t\in\mathbb{N}}$.
-Si la chaîne de Markov est irréductible et a $\pi$
-comme distribution stationnaire, alors un
-\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
-(qui peut dépendre de la configuration initiale $X$),
-tel que la distribution de $X_\tau$ est $\pi$:
-$$\P_X(X_\tau=Y)=\pi(Y).$$
-
-
-Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$
-est indépendant de $\tau$. On a les deux théorèmes suivants, dont les
-démonstrations sont données en annexes~\ref{anx:generateur}.
+Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire
+pour être proche de la distribution stationnaire à $\varepsilon$ près,
+peu importe la configuration de départ. On a le théorème suivant démontré en annexe~\ref{anx:generateur}.
-\begin{theorem}
-Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
-\P_X(\tau > t)$.
-\end{theorem}
-
-
-Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction
-telle que pour $X \in \Bool^{\mathsf{N}} $,
-$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
-La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
-$\ov{h}(\ov{h}(X))\neq X$.
+\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix}
+\label{theo:tmps:mix}
+On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+\[
+p(e) \left\{
+\begin{array}{ll}
+= \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
+= \frac{1}{2\mathsf{N}} \textrm{ sinon.}
+\end{array}
+\right.
+\]
+La chaîne de Markov associée converge vers la distribution uniforme et
-\begin{theorem} \label{prop:stop}
-Si $\ov{h}$ est bijective et anti involutive
-$\ov{h}(\ov{h}(X))\neq X$, alors
-$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
-\end{theorem}
+\[
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2).
+\]
+\end{restatable}
-Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
-On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement
-l'algorithme~\ref{CI Algorithm}. En effet dans la section présente,
-la probabilité de rester dans une configuration donnée
-est fixée à $\frac{1}{2}+\frac{1}{2n}$.
-Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$.
-Cette version, qui reste davantage sur place que l'algorithme original,
-a été introduite pour simplifier le calcul de la borne sup
-du temps d'arrêt.
Sans entrer dans les détails de la preuve, on remarque aussi
-que le calcul de cette borne impose uniquement que
+que le calcul de ce majorant impose uniquement que
pour chaque n{\oe}ud du $\mathsf{N}$-cube
un arc entrant et un arc sortant sont supprimés.
Le fait qu'on enlève un cycle hamiltonien et que ce dernier
soit équilibré n'est pas pris en compte.
-En intégrant cette contrainte, la borne supérieure pourrait être réduite.
+En intégrant cette contrainte, ce majorant pourrait être ré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 é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
$E[\ts]$ pour un $\mathsf{N}$ donné tandis que la courbe est une représentation de
la fonction $x \mapsto 2x\ln(2x+8)$.
On constate que l'approximation de $E[\ts]$ est largement inférieure
-à la borne quadratique donnée au théorème~\ref{prop:stop} et que la conjecture
+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{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 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é.
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$).
\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}
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
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)
-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.
\section{Conclusion}
-Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir
+Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir
de codes de Gray équilibrés. Une méthode complètement automatique de
construction de ce type de codes a été présentée étendant les méthodes
existantes.
Dans le cas des itérations unaires,
l'algorithme qui en découle a un temps de mélange qui a
-une borne sup quadratique de convergence vers la distribution uniforme.
+un majorant quadratique de convergence vers la distribution uniforme.
Pratiquement, ce temps de mélange se rapproche de $N\ln N$.
Les expérimentations au travers de la batterie de test de NIST ont montré
que toutes les propriétés statistiques sont obtenues pour
