14Secrypt.tex

   1 On  a vu  dans  le chapitre précédent  que  pour avoir
   2 un  générateur à  sortie
   3 uniforme, il est nécessaire que  la matrice d'adjacence du graphe d'itération du
   4 système  soit doublement stochastique.   Nous présentons  dans cette  partie une
   5 méthode permettant de générer de telles matrices.
   6
   7 Les approches théoriques basées sur la programmation logique par contraintes sur
   8 domaines  finis ne  sont pas  envisageables en  pratique dès  que la  taille des
   9 matrices considérées devient suffisamment grande.
  10
  11 Une approche plus pragmatique consiste  à supprimer un cycle hamiltonien dans le
  12 graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
  13 arête sortante et une arête entrante.
  14
  15
  16 % This aim of this section is to show
  17 % that finding DSSC matrices from a hypercube
  18 % is a typical finite domain satisfaction
  19 % problem, classically denoted as
  20 % Constraint Logic Programming on Finite Domains (CLPFD).
  21 % This part is addressed in the first section. Next, we analyse the first
  22 % results to provide a generation of DSSC matrices with small mixing times.
  23
  24 \section{Programmation logique par contraintes sur des domaines finis}
  25 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments.
  26 Pour éviter d'avoir à gérer des fractions, on peut considérer que
  27 les matrices (d'incidence) à générer ont des lignes et des colonnes dont les
  28 sommes valent ${\mathsf{N}}$ à chaque fois.
  29 On cherche ainsi toutes les matrices $M$ de taille  $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que
  30
  31 \begin{enumerate}
  32 \item $M_{ij}$ vaut 0 si $j$ n'est pas un voisin de $i$, \textit{i.e.},
  33   il n'y a pas d'arc de $i$ à $j$ dans le graphe $\textsc{giu}(f)$;
  34
  35 \item $0 \le M_{ii} \le {\mathsf{N}}$: le nombre de boucles autour de chaque
  36 configuration $i$ est inférieur à ${\mathsf{N}}$;
  37
  38 \item pour $j \neq i$,  $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$
  39 si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
  40 \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}$:
  41 la matrice est stochastique à droite;
  42 \item pour chaque indice de colonne $j$,
  43   $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$:
  44   la matrice est stochastique à gauche;
  45 \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;
  46 \end{enumerate}
  47 Ce problème s'exprime sur des domaines finis entiers avec des opérateurs
  48 arithmétiques simples (sommes et produits). il pourrait théoriquement être
  49 traité par des démarches de programmation logique par contrainte
  50 sur des domaines finis (comme en PROLOG).
  51 L'algorithme donné en Figure~\ref{fig:prolog}
  52 est en effet le c{\oe}ur du programme PROLOG
  53 qui pourrait être utilisé pour instancier toutes les solutions,
  54 ici pour  $\mathsf{N} = 2$. Dans ce code,
  55 \verb+mmult(+$X,Y,R$\verb+)+ et
  56 \verb+summ(+$X,Y,R$\verb+)+
  57 valent True si et seulement si $R$
  58 est le produit matriciel  (ou la somme matricielle)
  59 entre  $X$ and $Y$ respectivement.
  60 il n'est pas difficile d'adapter ce code à n'importe quelle valeur
  61 entière naturelle  $\mathsf{N}$.
  62
  63 \begin{figure}[ht]
  64 \begin{scriptsize}
  65 \lstset{language=prolog}
  66 \begin{lstlisting}
  67 bistoc(X):-
  68   M=[[M0_0, M0_1, 0, M0_3], [M1_0, M1_1, 0, M1_3],
  69      [M2_0, 0, M2_2, M2_3], [0, M3_1, M3_2, M3_3]],
  70   [M0_0, M1_1, M2_2, M3_3] ins 0..2,
  71   [M0_1, M0_3, M1_0, M1_3, M2_0, M2_3, M3_1, M3_2]
  72      ins 0..1,
  73   M0_0+ M0_1+ M0_2 #=2, M1_0+ M1_1+ M1_3 #=2,
  74   M2_0+ M2_2+ M2_3 #=2, M3_1+ M3_2+ M3_3 #=2,
  75   M0_0+ M1_0+ M2_0 #=2, M0_1+ M1_1+ M3_1 #=2,
  76   M0_2+ M2_2+ M3_2 #=2, M1_3+ M2_3+ M3_3 #=2,
  77   mmult(M,M,M2),
  78   mmult(M,M2,M3),
  79   mmult(M,M3,M4),
  80   summ(M,M2,S2),
  81   summ(S2,M3,S3),
  82   summ(S3,M4,S4),
  83   allpositive(S4).
  84 \end{lstlisting}
  85 \end{scriptsize}
  86 \caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog}
  87 \end{figure}
  88
  89 Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux
  90 fonctions  $f$ et $g$ si leur graphes
  91 respectifs  $\textsf{giu}(f)$ et $\textsf{giu}(g)$
  92 sont isomorphes.
  93 C'est évidemment une relation d'équivalence.
  94
  95
  96
  97 \subsection{Analyse de l'approche}
  98 Exécutée sur un ordinateur personnelle, PROLOG trouve
  99 en moins d'une seconde les
 100 49 solutions pour  $n=2$,
 101 dont 2 seulement ne sont pas équivalentes,
 102 en moins d'une minute les 27642 solutions dont seulement 111 ne
 103 sont pas équivalentes pour $n=3$.
 104 Cependant, l'approche ne permet pas d'engendrer toutes les solutions
 105 pour $n=4$.
 106 Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut
 107 pas être retenue pour $n$ de grande taille, même
 108 en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
 109
 110 Cependant, pour des valeurs de $n$ petites, nous avons
 111 comparé les fonctions non équivalentes selon leur proportion
 112 à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
 113
 114
 115
 116
 117 \begin{xpl}
 118 Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes
 119 qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$.
 120 \begin{table}[ht]
 121 \begin{small}
 122 $$
 123 \begin{array}{|l|l|l|}
 124 \hline
 125 \textrm{Name} & \textrm{Image} & \textrm{MT}\\
 126 \hline
 127 f^a &  (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3})  &  16   \\
 128 \hline
 129 f^*  &  (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
 130 \overline{x_1}\overline{x_3} + x_1x_2)  &  17   \\
 131 \hline
 132 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}, &  \\
 133 & \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  26   \\
 134 \hline
 135 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}, & \\
 136 & \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  29   \\
 137 \hline
 138 f^d  &  (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3})  &  30   \\
 139 \hline
 140 % [3, 4, 7, 0, 1, 6, 5, 2], #16
 141 % [3, 4, 7, 0, 2, 6, 5, 1], #17
 142 % [3, 6, 7, 5, 2, 0, 1, 4], #26
 143 % [3, 4, 7, 5, 2, 6, 1, 0], #29
 144 % [3, 2, 5, 6, 7, 0, 1, 4]] #30
 145 \end{array}
 146 $$
 147 \end{small}
 148 \caption{Les 5 fonctions booléennes $n=3$ aux temps de mélange les plus faibles.}\label{table:mixing:3}
 149 \end{table}
 150 \end{xpl}
 151
 152 Une analyse syntaxique de ces fonctions ne permet pas, à priori,
 153 de déduire des règles permettant de construire de nouvelles
 154 fonction dont le temps de mélange serait faible.
 155 Cependant, le graphe $\textsc{giu}(f^*)$
 156 (donné à la Figure~\ref{fig:iteration:f*})
 157 est le $3$-cube dans lequel le cycle
 158 $000,100,101,001,011,111,110,010,000$
 159 a été enlevé. Dans cette figure, le le graphe $\textsc{giu}(f)$ est
 160 en continu tandis que le cycle est en pointillés.
 161 Ce cycle qui visite chaque n{\oe}ud exactement une fois est un
 162 \emph{cycle hamiltonien}.
 163 La matrice de Markov correspondante est donnée à
 164 la figure~\ref{fig:markov:f*}.
 165 On s'intéresse  par la suite à la génération de ce genre de cycles.
 166
 167
 168
 169
 170
 171 \begin{figure}[ht]
 172   \begin{center}
 173     \subfigure[Graphe $\textsc{giu}(f^*)$.
 174     \label{fig:iteration:f*}]{
 175       \begin{minipage}{0.55\linewidth}
 176         \centering
 177         \includegraphics[width=\columnwidth]{images/iter_f0d}%
 178       \end{minipage}
 179     }%
 180     \subfigure[Matrice de Markov associée à $\textsc{giu}(f^*)$
 181     \label{fig:markov:f*}]{%
 182       \begin{minipage}{0.35\linewidth}
 183         \begin{scriptsize}
 184           \begin{center}
 185             $ \dfrac{1}{4} \left(
 186               \begin{array}{cccccccc}
 187                 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
 188
 189                 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
 190
 191                 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
 192
 193                 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
 194
 195                 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
 196
 197                 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
 198
 199                 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
 200
 201                 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
 202
 203               \end{array}            \right) $
 204           \end{center}
 205         \end{scriptsize}
 206       \end{minipage}
 207     }%
 208     \caption{Représentations de $f^*(x_1,x_2,x_3)=
 209       (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
 210       \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
 211   \end{center}
 212 \end{figure}
 213
 214
 215
 216
 217 \section{Graphes
 218   $\textsc{giu}(f)$
 219   $\textsc{gig}(f)$
 220   fortement connexes et doublement stochastiques}
 221 % Secrypt 14
 222
 223
 224
 225
 226 \subsection{Suppression des cycles hamiltoniens}
 227 \label{sec:hamiltonian}
 228
 229 Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
 230 suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
 231 stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
 232 équilibrés.
 233
 234 \subsubsection{Aspects théoriques}
 235 \label{sub:removing:theory}
 236
 237 Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
 238 hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
 239 connexité du graphe d'itérations.
 240
 241 \begin{theorem}\label{th:supprCH}
 242   La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
 243   $n$-cube, produit une matrice doublement stochastique.
 244 \end{theorem}
 245 \begin{Proof}
 246
 247 Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
 248 Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
 249 une arête entrante $(o,v)$ et une arête sortante $(v,e)$
 250 est ainsi enlevée.
 251 Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes
 252 pour le rendre complet. La matrice de Markov $M$ correspondante est
 253 remplie de $\frac{1}{2^n}$ et est doublement stochastique.
 254 Comme on enlève exactement une arête sortante $(v,e)$
 255 à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans
 256 $C_2$ les $2^{n-1}$ arêtes issues de $v$ et
 257 relatives aux parties de $\{1,\ldots,n\}$ qui
 258 contiennent $e$. Cela revient à annuler
 259 dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter
 260 $1/2$ à l'élément $M_{vv}$.
 261 La matrice $M$ reste stochastique.
 262 On effectue un raisonnement similaire pour les arêtes entrantes:
 263 comme on enlève exactement une arête entrante $(o,v)$ pour chaque
 264 n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement
 265 $2^{n-1}$ arêtes menant à $v$ qui sont enlevées.
 266 Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et
 267 $M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
 268 $M$ est donc doublement stochastique.
 269 \end{Proof}
 270
 271
 272
 273 \begin{theorem}\label{th:grapheFC}
 274   Le  graphe d'itérations  issu du  $n$-cube,  auquel un  cycle hamiltonien  est
 275   enlevé, est fortement connexe.
 276 \end{theorem}
 277
 278
 279 \begin{Proof}
 280 On considère les deux $n$-cubes $C_1$ et $C_2$ définis
 281 dans la preuve du théorème~\ref{th:supprCH}.
 282 Dans $C_1$ on considère le cycle inverse $r$ du cycle
 283 hamiltonien $c$.
 284 Aucun arc n'appartient à la fois  à $r$ et à $c$:
 285 en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
 286 Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.
 287 Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds.
 288 Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles
 289 depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui
 290 étend le précédent graphe est ainsi fortement connexe.
 291
 292 \end{Proof}
 293
 294
 295
 296 Les preuves, relativement directes, sont  laissées en exercices au lecteur.  Par
 297 contre, ce qui  est moins aisé est la génération de  cycles hamiltoniens dans le
 298 $n$-cube,  ce qui  revient à  trouver des  \emph{codes de  Gray  cycliques}.  On
 299 rappelle que  les codes de  Gray sont des  séquences de mots binaires  de taille
 300 fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit. Un
 301 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 302 différent que par un seul bit.
 303
 304 \subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés}
 305 \label{sub:gray}
 306
 307 La borne  inférieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
 308     \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnée  dans~\cite{Feder2009NTB},
 309 indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
 310 cette  difficulté,  nous  nous   restreignons  aux  codes  induisant  un  graphe
 311 d'itérations $\textsf{giu}(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des
 312 nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
 313 $i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
 314 total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
 315 \emph{équilibrés}.
 316
 317 Un code de Gray équilibré peut être défini de la façon suivante :
 318
 319 \begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
 320   Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
 321   $n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
 322   $s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
 323   $w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{NT}_n : \{1,\dots,  n\} \rightarrow
 324   \{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
 325     de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
 326   le nombre d'occurrences de $i$ dans $S$.
 327
 328   Le      code       $L$      est      \textbf{équilibré}       si      $\forall
 329   i,j\in\{1,...,n\},~|\textit{NT}_n(i)  -  \textit{NT}_n(j)|  \le  2$.   Il  est
 330   \textbf{totalement             équilibré}             si             $\forall
 331   i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
 332 \end{Def}
 333
 334 On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
 335 équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De
 336 plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{NT}_n(i)$  est  pair
 337 $\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
 338 différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec
 339 $\textit{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
 340 $\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
 341 vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
 342
 343 \begin{xpl}
 344   Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au
 345   cycle hamiltonien enlevé de $f^*$.  Sa séquence des transitions est \linebreak
 346   $S=3,1,3,2,3,1,3,2$  et  les nombres  de  transitions sont  $\textit{TC}_3(1)=
 347   \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré.
 348
 349   Si l'on  considère maintenant $L^4=$ 0000,  0010, 0110, 1110, 1111,  0111, 0011,
 350   0001,  0101, 0100,  1100, 1101,  1001,  1011, 1010,  1000,  un  code de  Gray
 351   cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4,
 352   on constate que  $\forall
 353   i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que
 354   ce code est totalement équilibré.
 355 \end{xpl}
 356
 357 \subsection{Génération de codes de Gray équilibrés par induction}
 358 \label{sec:induction}
 359
 360 Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
 361 algorithme inductif  pour générer  des codes  de Gray équilibrés  de $n$  bits à
 362 partir   de  codes   de  $n-2$   bits.   Cependant,   leur  méthode   n'est  pas
 363 constructive. En effet, elle effectue  des manipulations sur un partitionnement du
 364 code de Gray  initial de $n-2$ bits pour  obtenir un code de Gray  sur $n$ bits,
 365 mais le  résultat n'est pas  systématiquement équilibré. Il est  donc nécessaire
 366 d'évaluer les résultats obtenus à  partir de tous les partitionnements réalisables
 367 en suivant les  contraintes spécifiées.  Or, le nombre  de possibilités augmente
 368 exponentiellement (voir~\cite{Mons14} pour  l'évaluation détaillée), ce qui rend
 369 déraisonnable    tout   parcours    exhaustif.    Une    amélioration   proposée
 370 dans~\cite{Mons14} permet  de réduire le nombre  de partitionnements considérés,
 371 mais l'ordre  de grandeur  reste similaire. On  constate donc clairement  ici la
 372 nécessité de trouver  des algorithmes de génération de  codes de Gray équilibrés
 373 plus  efficaces.  Ce  problème  représente  une des  voies  que nous  souhaitons
 374 explorer dans la suite de nos travaux.
 375
 376 Le   tableau~\ref{table:nbFunc}  donne  le   nombre  de   fonctions  différentes
 377 compatibles avec les codes de  Gray équilibrés générés par l'approche précédente
 378 selon le nombre  de bits. Il donne  donc la taille de la  classe des générateurs
 379 pouvant être produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basées
 380 sur des sous-ensembles des partitionnements possibles.
 381
 382 \begin{table}[ht]
 383   \begin{center}
 384     \begin{tabular}{|l|c|c|c|c|c|}
 385       \hline
 386       $n$              & 4 & 5 & 6    & 7      & 8      \\
 387       \hline
 388       nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
 389       \hline
 390     \end{tabular}
 391   \end{center}
 392 \caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc}
 393 \end{table}
 394
 395
 396 Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse
 397 un générateur les embarquant converge vers la distribution uniforme.
 398 C'est l'objectif de la section suivante.
 399
 400 \section{Quantifier l'écart par rapport à la distribution uniforme}
 401 On considère ici une fonction construite comme à la section précédente.
 402 On s'intéresse ici à étudier de manière théorique les
 403 itérations définies à l'équation~(\ref{eq:asyn}) pour une
 404 stratégie donnée.
 405 Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un
 406 graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la
 407 stratégie.
 408 On remarque que ce graphe d'itération est toujours un sous graphe
 409 du   ${\mathsf{N}}$-cube augmenté des
 410 boucles sur chaque sommet, \textit{i.e.}, les arcs
 411 $(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$.
 412 Ainsi, le travail ci dessous répond à la question de
 413 définir la longueur du chemin minimum dans ce graphe pour
 414 obtenir une distribution uniforme.
 415 Ceci se base sur la théorie des chaînes de Markov.
 416 Pour une référence
 417 générale à ce sujet on pourra se référer
 418 au livre~\cite{LevinPeresWilmer2006},
 419 particulièrement au chapitre sur les temps d'arrêt.
 420
 421
 422
 423
 424 \begin{xpl}
 425 On considère par exemple le graphe $\textsc{giu}(f)$ donné à la
 426 \textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de
 427 probabilités $p$ définie sur l'ensemble des arcs comme suit:
 428 $$
 429 p(e) \left\{
 430 \begin{array}{ll}
 431 = \frac{2}{3} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
 432 = \frac{1}{6} \textrm{ sinon.}
 433 \end{array}
 434 \right.
 435 $$
 436 La matrice $P$ de la chaîne de Markov associée à  $f^*$
 437 est
 438 \[
 439 P=\dfrac{1}{6} \left(
 440 \begin{array}{llllllll}
 441 4&1&1&0&0&0&0&0 \\
 442 1&4&0&0&0&1&0&0 \\
 443 0&0&4&1&0&0&1&0 \\
 444 0&1&1&4&0&0&0&0 \\
 445 1&0&0&0&4&0&1&0 \\
 446 0&0&0&0&1&4&0&1 \\
 447 0&0&0&0&1&0&4&1 \\
 448 0&0&0&1&0&1&0&4
 449 \end{array}
 450 \right)
 451 \]
 452 \end{xpl}
 453
 454
 455
 456
 457 Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur
 458 $\Bool^{\mathsf{N}}$.
 459 La distance de \og totale variation\fg{} entre  $\pi$ et $\mu$
 460 est notée  $\tv{\pi-\mu}$ et est définie par
 461 $$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$
 462 On sait que
 463 $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
 464 De plus, si
 465 $\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a
 466 $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
 467
 468 Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$.
 469 $P(X,\cdot)$ est la distribution induite par la  $X^{\textrm{ème}}$ colonne
 470 de  $P$.
 471 Si la chaîne de  Markov induite par
 472 $P$ a une  distribution stationnaire $\pi$, on définit alors
 473 $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$
 474
 475 et
 476
 477 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 478
 479 Un résultat classique est
 480
 481 $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
 482
 483
 484
 485
 486 Soit $(X_t)_{t\in \mathbb{N}}$ une suite de  variables aléatoires de
 487 $\Bool^{\mathsf{N}}$.
 488 une variable aléatoire $\tau$ dans $\mathbb{N}$ est un
 489 \emph{temps d'arrêt} pour la suite
 490 $(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
 491 (\Bool^{\mathsf{N}})^{t+1}$ tel que
 492 $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
 493 En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs
 494 de
 495 $(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$.
 496
 497
 498 Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et
 499 $f(X_{t-1},Z_t)$  une représentation fonctionnelle de celle-ci.
 500 Un \emph{temps d'arrêt aléatoire} pour la chaîne de
 501 Markov  est un temps d'arrêt pour
 502 $(Z_t)_{t\in\mathbb{N}}$.
 503 Si la chaîne de Markov  est irréductible et a $\pi$
 504 comme distribution stationnaire, alors un
 505 \emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
 506 (qui peut dépendre de la configuration initiale $X$),
 507 tel que la distribution de $X_\tau$ est $\pi$:
 508 $$\P_X(X_\tau=Y)=\pi(Y).$$
 509
 510
 511 Un temps d'arrêt  $\tau$ est qualifié de  \emph{fort} si  $X_{\tau}$
 512 est indépendant de  $\tau$.  On a les deux théorèmes suivants, dont les
 513 démonstrations sont données en annexes~\ref{anx:generateur}.
 514
 515
 516 \begin{theorem}
 517 Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
 518 \P_X(\tau > t)$.
 519 \end{theorem}
 520
 521 \begin{theorem} \label{prop:stop}
 522 If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
 523 $\ov{h}(\ov{h}(X))\neq X$, alors
 524 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
 525 \end{theorem}
 526
 527 Sans entrer dans les détails de la preuve, on remarque que le calcul
 528 de cette borne ne tient pas en compte le fait qu'on préfère enlever des
 529 chemins hamiltoniens équilibrés.
 530 En intégrant cette contrainte, la borne supérieure pourrait être réduite.
 531
 532 \section{Et les itérations généralisées?}
 533 Le chaptire précédent a présenté un algorithme de
 534 PRNG construit à partir d'itérations unaires.
 535 On pourrait penser que cet algorithme est peu efficace puisqu'il
 536 dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à
 537 chaque itération qu'un seul élément de $[n]$.
 538 On pourrait penser à un algorithme basé sur les itérations généralisées,
 539 c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque
 540 itération.
 541 C'est l'algorithme~\ref{CI Algorithm:prng:g}.
 542
 543 \begin{algorithm}[h]
 544 %\begin{scriptsize}
 545 \KwIn{une fonction $f$, un nombre d'itérations $b$,
 546 une configuration initiale $x^0$ ($n$ bits)}
 547 \KwOut{une configuration $x$ ($n$ bits)}
 548 $x\leftarrow x^0$\;
 549 $k\leftarrow b $\;
 550 \For{$i=1,\dots,k$}
 551 {
 552 $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
 553 $x\leftarrow{F_{f_g}(s,x)}$\;
 554 }
 555 return $x$\;
 556 %\end{scriptsize}
 557 \caption{PRNG basé sur les itérations généralisées.}
 558 \label{CI Algorithm:prng:g}
 559 \end{algorithm}
 560
 561 Par rapport à l'algorithme~\ref{CI Algorithm} seule
 562 la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est différente.
 563 Dans celle-ci la fonction  $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
 564 \mathcal{P}(\{1,\ldots   n\})$   retourne  l'ensemble   dont   la   fonction
 565 caractéristique  serait  représentée par  le  nombre  donné  en argument.
 566 Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
 567 On remarque aussi que l'argument de la fonction  $\textit{Random}$
 568 passe de $n$ à $2^n$.
 569
 570