correction de quelques typos

[hdrcouchot.git] / 14Secrypt.tex

On  a vu  dans  le chapitre précédent  que  pour avoir
un  générateur à  sortie
uniforme, il est nécessaire que  la matrice d'adjacence du graphe d'itération du
système  soit doublement stochastique.   Nous présentons  dans cette  partie une
méthode permettant de générer de telles matrices.

Les approches théoriques basées sur la programmation logique par contraintes sur
domaines  finis ne  sont pas  envisageables en  pratique dès  que la  taille des
matrices considérées devient suffisamment grande.

Une approche plus pragmatique consiste  à supprimer un cycle hamiltonien dans le
graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
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. 

\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é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 
  
\begin{enumerate}
\item $M_{ij}$ vaut 0 si $j$ n'est pas un voisin de $i$, \textit{i.e.},
  il n'y a pas d'arc de $i$ à $j$ dans le graphe $\textsc{giu}(f)$;

\item $0 \le M_{ii} \le {\mathsf{N}}$: le nombre de boucles autour de chaque 
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)
\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;
\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 
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 
qui pourrait être utilisé pour instancier toutes les solutions,
ici pour  $\mathsf{N} = 2$. Dans ce code, 
\verb+mmult(+$X,Y,R$\verb+)+ et 
\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. 
il n'est pas difficile d'adapter ce code à n'importe quelle valeur 
entière naturelle  $\mathsf{N}$.  

\begin{figure}[ht]
\begin{scriptsize}
\lstset{language=prolog}
\begin{lstlisting}
bistoc(X):-
  M=[[M0_0, M0_1, 0, M0_3], [M1_0, M1_1, 0, M1_3], 
     [M2_0, 0, M2_2, M2_3], [0, M3_1, M3_2, M3_3]],
  [M0_0, M1_1, M2_2, M3_3] ins 0..2,
  [M0_1, M0_3, M1_0, M1_3, M2_0, M2_3, M3_1, M3_2] 
     ins 0..1,
  M0_0+ M0_1+ M0_2 #=2, M1_0+ M1_1+ M1_3 #=2,
  M2_0+ M2_2+ M2_3 #=2, M3_1+ M3_2+ M3_3 #=2,
  M0_0+ M1_0+ M2_0 #=2, M0_1+ M1_1+ M3_1 #=2, 
  M0_2+ M2_2+ M3_2 #=2, M1_3+ M2_3+ M3_3 #=2,
  mmult(M,M,M2),
  mmult(M,M2,M3),
  mmult(M,M3,M4),
  summ(M,M2,S2),
  summ(S2,M3,S3),
  summ(S3,M4,S4),
  allpositive(S4).
\end{lstlisting}
\end{scriptsize}
\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 pour les deux 
fonctions  $f$ et $g$ si leur graphes 
respectifs  $\textsf{giu}(f)$ et $\textsf{giu}(g)$ 
sont isomorphes.
C'est évidemment une relation d'équivalence.



\subsection{Analyse de l'approche}
Exécutée sur un ordinateur personnelle, PROLOG trouve 
en moins d'une seconde les
49 solutions pour  $n=2$, 
dont 2 seulement ne sont pas équivalentes, 
en moins d'une minute les 27642 solutions dont seulement 111 ne 
sont pas équivalentes pour $n=3$.
Cependant, l'approche ne permet pas d'engendrer toutes les solutions 
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'efficience de l'algorithme de backtrack natif de PROLOG.

Cependant, pour des valeurs de $n$ petites, nous avons 
comparé les fonctions non équivalentes selon leur proportion
à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).




\begin{xpl}
Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes 
qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$. 
\begin{table}[ht]
\begin{small}
$$
\begin{array}{|l|l|l|}
\hline
\textrm{Name} & \textrm{Image} & \textrm{MT}\\
\hline
f^a &  (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3})  &  16   \\
\hline
f^*  &  (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)  &  17   \\
\hline
f^b  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, &  \\
& \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  26   \\
\hline
f^c  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, & \\
& \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  29   \\
\hline
f^d  &  (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3})  &  30   \\
\hline
% [3, 4, 7, 0, 1, 6, 5, 2], #16
% [3, 4, 7, 0, 2, 6, 5, 1], #17
% [3, 6, 7, 5, 2, 0, 1, 4], #26 
% [3, 4, 7, 5, 2, 6, 1, 0], #29
% [3, 2, 5, 6, 7, 0, 1, 4]] #30
\end{array}
$$
\end{small}
\caption{Les 5 fonctions booléennes $n=3$ aux temps de mélange les plus faibles.}\label{table:mixing:3}
\end{table}
\end{xpl}

Une analyse syntaxique de ces fonctions ne permet pas, à priori, 
de déduire des règles permettant de construire de nouvelles
fonction 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 
$000,100,101,001,011,111,110,010,000$ 
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 à 
la figure~\ref{fig:markov:f*}.
On s'intéresse  par la suite à la génération de ce genre de cycles.





\begin{figure}[ht]
  \begin{center}
    \subfigure[Graphe $\textsc{giu}(f^*)$.
    \label{fig:iteration:f*}]{
      \begin{minipage}{0.55\linewidth}
        \centering
        \includegraphics[width=\columnwidth]{images/iter_f0d}%
      \end{minipage}
    }%
    \subfigure[Matrice de Markov associée à $\textsc{giu}(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}




\section{Graphes 
  $\textsc{giu}(f)$ 
  $\textsc{gig}(f)$ 
  fortement connexes et doublement stochastiques}
% Secrypt 14




\subsection{Suppression des cycles hamiltoniens}
\label{sec:hamiltonian}

Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
équilibrés.

\subsubsection{Aspects théoriques}
\label{sub:removing:theory}

Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
connexité du graphe d'itérations.

\begin{theorem}\label{th:supprCH}
  La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
  $n$-cube, produit une matrice doublement stochastique.
\end{theorem}
\begin{Proof}

Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
une arête entrante $(o,v)$ et une arête sortante $(v,e)$ 
est ainsi enlevée.
Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes 
pour le rendre complet. La matrice de Markov $M$ correspondante est
remplie de $\frac{1}{2^n}$ et est doublement stochastique.
Comme on enlève exactement une arête sortante $(v,e)$ 
à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans 
$C_2$ les $2^{n-1}$ arêtes issues de $v$ et 
relatives aux parties de $\{1,\ldots,n\}$ qui
contiennent $e$. Cela revient à annuler 
dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter 
$1/2$ à l'élément $M_{vv}$.
La matrice $M$ reste stochastique.
On effectue un raisonnement similaire pour les arêtes entrantes:
comme on enlève exactement une arête entrante $(o,v)$ pour chaque 
n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement 
$2^{n-1}$ arêtes menant à $v$ qui sont enlevées. 
Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et 
$M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
$M$ est donc doublement stochastique.
\end{Proof}



\begin{theorem}\label{th:grapheFC}
  Le  graphe d'itérations  issu du  $n$-cube,  auquel un  cycle hamiltonien  est
  enlevé, est fortement connexe.
\end{theorem}


\begin{Proof}
On considère les deux $n$-cubes $C_1$ et $C_2$ définis 
dans la preuve du théorème~\ref{th:supprCH}.
Dans $C_1$ on considère le cycle inverse $r$ du cycle
hamiltonien $c$.
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
étend le précédent graphe est ainsi fortement connexe. 

\end{Proof}



Les preuves, relativement directes, sont  laissées en exercices au lecteur.  Par
contre, ce qui  est moins aisé est la génération de  cycles hamiltoniens dans le
$n$-cube,  ce qui  revient à  trouver des  \emph{codes de  Gray  cycliques}.  On
rappelle que  les codes de  Gray sont des  séquences de mots binaires  de taille
fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit. Un
code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
différent que par un seul bit.

\subsection{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
    \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
d'itérations $\textsf{giu}(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des
nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
$i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
\emph{équilibrés}.

Un code de Gray équilibré peut être défini de la façon suivante :

\begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
  Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
  $n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
  $s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
  $w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{NT}_n : \{1,\dots,  n\} \rightarrow
  \{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
    de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
  le nombre d'occurrences de $i$ dans $S$.
  
  Le      code       $L$      est      \textbf{équilibré}       si      $\forall
  i,j\in\{1,...,n\},~|\textit{NT}_n(i)  -  \textit{NT}_n(j)|  \le  2$.   Il  est
  \textbf{totalement             équilibré}             si             $\forall
  i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
\end{Def}

On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De
plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{NT}_n(i)$  est  pair
$\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{NT}_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
vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.

\begin{xpl}
  Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au
  cycle hamiltonien enlevé de $f^*$.  Sa séquence des transitions est \linebreak
  $S=3,1,3,2,3,1,3,2$  et  les nombres  de  transitions sont  $\textit{TC}_3(1)=
  \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré.

  Si l'on  considère maintenant $L^4=$ 0000,  0010, 0110, 1110, 1111,  0111, 0011,
  0001,  0101, 0100,  1100, 1101,  1001,  1011, 1010,  1000,  un  code de  Gray
  cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4, 
  on constate que  $\forall
  i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que 
  ce code est totalement équilibré.
\end{xpl}

\subsection{Génération de codes de Gray équilibrés par induction}
\label{sec:induction}

Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
algorithme inductif  pour générer  des codes  de Gray équilibrés  de $n$  bits à
partir   de  codes   de  $n-2$   bits.   Cependant,   leur  méthode   n'est  pas
constructive. En effet, elle effectue  des manipulations sur un partitionnement du
code de Gray  initial de $n-2$ bits pour  obtenir un code de Gray  sur $n$ bits,
mais le  résultat n'est pas  systématiquement équilibré. Il est  donc nécessaire
d'évaluer les résultats obtenus à  partir de tous les partitionnements réalisables
en suivant les  contraintes spécifiées.  Or, le nombre  de possibilités augmente
exponentiellement (voir~\cite{Mons14} pour  l'évaluation détaillée), ce qui rend
déraisonnable    tout   parcours    exhaustif.    Une    amélioration   proposée
dans~\cite{Mons14} permet  de réduire le nombre  de partitionnements considérés,
mais l'ordre  de grandeur  reste similaire. On  constate donc clairement  ici la
nécessité de trouver  des algorithmes de génération de  codes de Gray équilibrés
plus  efficaces.  Ce  problème  représente  une des  voies  que nous  souhaitons
explorer dans la suite de nos travaux.

Le   tableau~\ref{table:nbFunc}  donne  le   nombre  de   fonctions  différentes
compatibles avec les codes de  Gray équilibrés générés par l'approche précédente
selon le nombre  de bits. Il donne  donc la taille de la  classe des générateurs
pouvant être produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basées
sur des sous-ensembles des partitionnements possibles.

\begin{table}[ht]
  \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 \\
      \hline
    \end{tabular}
  \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} 
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}.