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
section~\ref{sec:mixing}.
L'extension du travail aux itérations généralisées est présentée à la
section~\ref{sec:prng:gray:general}.
-Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans
-ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}.
-Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
+Finalement, des instances de PRNGs engendrés selon les méthodes détaillées dans
+ce chapitre sont présentées en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
à~\cite{chgw+14:oip}.
+La section~\ref{sec:mixing} est publiée dans~\cite{ccgh16}.
% This aim of this section is to show
configuration $i$ est inférieur à ${\mathsf{N}}$;
\item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$
-si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
+si et seulement si $M_{ij}$ vaut 1 (et 0 sinon);
\item pour chaque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à droite;
\item pour chaque indice de colonne $j$,
$1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à gauche;
-\item 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}
$\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}
principalement de prouver que si $\mathsf{N}$ est une puissance de 2,
le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et
que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits
-si $S_{\mathsf{N}-2}$ l'est aussi..
+si $S_{\mathsf{N}-2}$ l'est aussi.
Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement
un code de Gray (totalement) équilibré.
Cette section montre que ceci est vrai en rappelant tout d'abord
L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé
comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré.
-La théorème suivante montre que c'est possible et sa preuve,
-donnée en annexes~\ref{anx:generateur}, explique comment le faire.
+Le théorème suivant montre que c'est possible et sa preuve,
+donnée en annexe~\ref{anx:generateur}, explique comment le faire.
\begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre}
\label{prop:balanced}
Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par
$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$.
-il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
-de l'algorithme de \emph{Robinson-Cohn} extension telle que
-le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$
-sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$
+Il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
+de l'algorithme de \emph{Robinson-Cohn} telle que
+les nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$
+valent tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$
pour chaque $i$, $1 \le i \le \mathsf{N}$.
\end{restatable}
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.
\]
\end{xpl}
-On remarque que dans cette marche on reste sur place avec une probabilité
-
-
+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{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)$.
+\[
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le
+x
+\leq \lceil\log_2(\varepsilon^{-1})
+(32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1))
+\]
\end{restatable}
-Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
-On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement
-l'algorithme~\ref{CI Algorithm}. En effet dans la section présente,
-la probabilité de rester dans une configuration donnée
-est fixée à $\frac{1}{2}+\frac{1}{2n}$.
-Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$.
-Cette version, qui reste davantage sur place que l'algorithme original,
-a été introduite pour simplifier le calcul d'un majorant
-du temps d'arrêt.
Sans entrer dans les détails de la preuve, on remarque aussi
un arc entrant et un arc sortant sont supprimés.
Le fait qu'on enlève un cycle hamiltonien et que ce dernier
soit équilibré n'est pas pris en compte.
-En intégrant cette contrainte, ce majorant pourrait être réduite.
+En intégrant cette contrainte, ce majorant pourrait être réduit.
En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube.
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
-à le majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture
+au majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture
donnée au paragraphe précédent est sensée.
}
\Return{$\textit{nbit}$}\;
%\end{scriptsize}
-\caption{Pseudo Code pour évaluer le temps d'arrêt}
+\caption{Pseudo-code pour évaluer le temps d'arrêt}
\label{algo:stop}
\end{algorithm}
définie par
$M = \dfrac{1}{2^n} \check{M}$.
Si $\textsc{gig}(f)$ est fortement connexe, alors
- la sortie du générateur de nombres pseudo aléatoires détaillé par
+ la sortie du générateur de nombres pseudo-aléatoires détaillé par
l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui
tend vers la distribution uniforme si
et seulement si $M$ est une matrice doublement stochastique.
\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$).
Cela s'explique assez simplement. Depuis une configuration initiale, le nombre
de configurations qu'on ne peut pas atteindre en une itération est de:
\begin{itemize}
-\item $2^n-n$ en unaire. Ceci représente un rapport de
- $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$
+\item $2^n-n-1$ en unaire. Ceci représente un rapport de
+ $\dfrac{2^n-n-1}{2^n} = 1-\dfrac{n-1}{2^n}$
de toutes les configurations; plus $n$ est grand,
plus ce nombre est proche de $1$, et plus grand devient le nombre
d'itérations nécessaires pour atteinte une déviation faible;
\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.
