arête sortante et une arête entrante.
-This aim of this section is to show
-that finding DSSC matrices from a hypercube
-is a typical finite domain satisfaction
-problem, classically denoted as
-Constraint Logic Programming on Finite Domains (CLPFD).
-This part is addressed in the first section. Next, we analyse the first
-results to provide a generation of DSSC matrices with small mixing times.
+% This aim of this section is to show
+% that finding DSSC matrices from a hypercube
+% is a typical finite domain satisfaction
+% problem, classically denoted as
+% Constraint Logic Programming on Finite Domains (CLPFD).
+% This part is addressed in the first section. Next, we analyse the first
+% results to provide a generation of DSSC matrices with small mixing times.
\section{Programmation logique par contraintes sur des domaines finis}
Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments.
-Pour éviter d'avoir à gérér des fractions, on peut considérer que
+Pour éviter d'avoir à gérer des fractions, on peut considérer que
les matrices (d'incidence) à générer ont des lignes et des colonnes dont les
sommes valent ${\mathsf{N}}$ à chaque fois.
On cherche ainsi toutes les matrices $M$ de taille $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que
\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)
-\item pour chque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
+\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 chque indice de colonne $j$,
+\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;
\end{enumerate}
Ce problème s'exprime sur des domaines finis entiers avec des opérateurs
-arithmétiques simples (sommes et poduits). il pourrait théoriquement être
-traité par desdémarches de programation logique par contrainte
+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}
est en effet le c{\oe}ur du programme PROLOG
allpositive(S4).
\end{lstlisting}
\end{scriptsize}
-\caption{Prolog Problem to Find DSSC Matrix when $n=2$}\label{fig:prolog}
+\caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog}
\end{figure}
-Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux
+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)$
sont isomorphes.
pour $n=4$.
Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut
pas être retenue pour $n$ de grande taille, même
-en s'appuyant sur l'éfficience de l'algorithme de backtrack natif de PROLOG.
+en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
Cependant, pour des valeurs de $n$ petites, nous avons
-comparé les fonctions non équivalantes selon leur proportion
+comparé les fonctions non équivalentes selon leur proportion
à 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é.
+a été enlevé. Dans cette figure, le 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 matrice de Markov correspondante est donnée à
\label{fig:iteration:f*}]{
\begin{minipage}{0.55\linewidth}
\centering
- \includegraphics[width=\columnwidth]{images/iter_f0c}%
+ \includegraphics[width=\columnwidth]{images/iter_f0d}%
\end{minipage}
}%
\subfigure[Matrice de Markov associée à $\textsc{giu}(f^*)$
sur des sous-ensembles des partitionnements possibles.
\begin{table}[ht]
- %\begin{center}
+ \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 \\
+ nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
\hline
\end{tabular}
- %\end{center}
-\caption{Nombre de générateurs selon le nombre de bits.}\label{table:nbFunc}
+ \end{center}
+\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc}
\end{table}
+Ces fonctions étant générée, 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}
-%15 Rairo
\ No newline at end of file
+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}
+
+\begin{theorem} \label{prop:stop}
+If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+$\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 que le calcul
+de cette borne ne tient pas en compte 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.
+
+\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}.
+
+\begin{algorithm}[h]
+%\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$.
+
+Dans ce qui suit, on va étudier cet algorithme comparativement à
+l'algorithme~\ref{CI Algorithm}.
+
