exp.tex

   1 X section présente une application directe de la théorie développée ci-avant
   2 à la génération de nombres pseudo-aléatoires. On présente tout d'abord le générateur
   3 basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}),
   4 puis comment intégrer la contrainte de \gls{distributionuniforme} (cf. glossaire)
   5 de la sortie
   6 dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}).
   7
   8
   9 \subsection{Générateur de nombres pseudo-aléatoires basé sur le chaos}
  10 \label{sub:prng:algo}
  11
  12 On peut penser à construire un générateur de nombres pseudo-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
  13
  14 \begin{algorithm}[h]
  15 %\begin{scriptsize}
  16 \KwIn{une fonction $f$, un nombre d'itérations $b$,
  17 une configuration initiale $x^0$ ($n$ bits)}
  18 \KwOut{une configuration $x$ ($n$ bits)}
  19 $x\leftarrow x^0$\;
  20 $k\leftarrow b + \textit{Random}(b+1)$\;
  21 %$k\leftarrow b + \textit{XORshift}(b+1)$\;
  22 \For{$i=0,\dots,k-1$}
  23 {
  24 $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
  25 %$s\leftarrow{\textit{XORshift}(n)}$\;
  26 $x\leftarrow{F_f(s,x)}$\;
  27 }
  28 return $x$\;
  29 %\end{scriptsize}
  30 \caption{Algorithme de génération de nombres pseudo-aléatoires
  31 à l'aide de la fonction chaotique $G_f$.}
  32 \label{CI Algorithm}
  33 \end{algorithm}
  34
  35
  36 Celui-ci prend  en entrée: une  fonction $f$; un  entier $b$, qui assure  que le
  37 nombre  d'itérations est compris  entre $b+1  $ et  $2b+1$ et  une configuration
  38 initiale $x^0$.   Il retourne  une nouvelle configuration  $x$.  En  interne, il
  39 exploite    la   fonction \linebreak    $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
  40 \mathcal{P}(\{1,\ldots   n\})$   qui   donne   l'ensemble   dont   la   fonction
  41 caractéristique  serait  représentée par  le  nombre  donné  en argument  et  un
  42 algorithme de génération de nombres pseudo-aléatoires \textit{Random}$(l)$.  Cet
  43 algorithme est utilisé  dans notre générateur pour construire  la longueur de la
  44 stratégie ainsi  que les éléments  qui la composent.  Pratiquement,  il retourne
  45 des    entiers   dans    $\llbracket    1   ;    l    \rrbracket$   selon    une
  46 \gls{distributionuniforme} %(cf. glossaire)
  47 et utilise \textit{XORshift} qui est
  48 une classe de  générateurs de nombres pseudo-aléatoires très  rapides conçus par
  49 George Marsaglia~\cite{Marsaglia98}.
  50
  51 % L'algorithme \textit{XORshift} exploite itérativement
  52 % la fonction \og \gls{xor}\fg{} $\oplus$ (cf. glossaire)
  53 % sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).
  54
  55 L'algorithme \textit{XORshift}
  56 exploite itérativement l'opérateur $\oplus$
  57 sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire)
  58 .
  59 Cet opérateur, défini dans $\Bool^{n}$,
  60 applique la fonction \og  \gls{xor} \fg{} (cf. glossaire)
  61 aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}).
  62 Une instance de cette classe est donnée dans l'algorithme~\ref{XORshift} détaillé
  63 ci-dessous.
  64
  65 \begin{algorithm}[h]
  66 %\SetLine
  67 \KwIn{la configuration interne $z$ (un mot de 32-bit)}
  68 \KwOut{$y$ (un mot de 32-bits)}
  69 $z\leftarrow{z\oplus{(z\ll13)}}$\;
  70 $z\leftarrow{z\oplus{(z\gg17)}}$\;
  71 $z\leftarrow{z\oplus{(z\ll5)}}$\;
  72 $y\leftarrow{z}$\;
  73 return $y$\;
  74 \medskip
  75 \caption{Une boucle de l'algorithme de \textit{XORshift}.}
  76 \label{XORshift}
  77 \end{algorithm}
  78
  79 Il reste à instancier une fonction $f$ dans
  80 l'algorithme~\ref{CI Algorithm}.
  81 %en adéquation avec  l'approche développée
  82 %en section~\ref{sec:sccg}.
  83 La section suivante montre comment l'uniformité de la distribution
  84 contraint cette instanciation.
  85
  86 \subsection{Un générateur à sortie uniformément distribuée}
  87 \label{sub:prng:unif}
  88
  89 Une matrice \emph{stochastique} est une matrice carrée
  90 dont tous les éléments sont positifs ou nuls et dont
  91 la somme de chaque ligne
  92 vaut 1.
  93 Une matrice est \emph{doublement stochastique} si elle est stochastique et que la somme de chaque colonne est 1.
  94 Enfin, une matrice stochastique de taille $n \times n$ est \emph{régulière}
  95 si  la propriété suivante est établie:
  96 $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
  97
  98 On énonce enfin le théorème suivant liant les
  99 \glspl{vecteurDeProbabilite} (cf. glossaire)
 100 et les \glspl{chaineDeMarkov}  (cf. glossaire)
 101 :
 102
 103
 104 \begin{Theo}\label{th}
 105   Si $M$ est une matrice stochastique régulière, alors $M$
 106   possède un unique vecteur stationnaire de probabilités  $\pi$
 107   ($\pi.M = \pi$).
 108   De plus, si $\pi^0$ est un \gls{vecteurDeProbabilite}
 109  et si on définit
 110   la suite $(\pi^{k})^{k \in  \Nats}$ par
 111   $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$
 112   alors la \gls{chaineDeMarkov} $\pi^k$
 113   converge vers $\pi$ lorsque $k$ tend vers l'infini.
 114 \end{Theo}
 115
 116
 117 Montrons sur un exemple jouet à deux éléments
 118 que ce théorème permet de vérifier si la sortie d'un générateur de
 119 nombres pseudo-aléatoires est uniformément distribuée ou non.
 120 Soit alors $g$ et $h$ deux fonctions  de $\Bool^2$
 121 définies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $
 122 et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
 123 % Leurs graphes d'interactions donnés en figures \ref{fig:g:inter} et \ref{fig:h:inter}
 124 % vérifient les hypothèses du théorème~\ref{th:Adrien}.
 125 Leurs graphes d'itérations
 126 sont  fortement connexes, ce que l'on a pu déjà vérifier aux figures
 127 \ref{fig:g:iter} et \ref{fig:h:iter}.
 128 \textit{A priori}, ces deux fonctions pourraient être intégrées
 129 dans un générateur de nombres pseudo-aléatoires. Montrons que ce n'est pas le cas pour $g$ et
 130 que cela l'est pour $h$.
 131
 132 Comme le générateur \textit{Random} possède une sortie uniformément
 133 distribuée,  la  stratégie est uniforme sur $\llbracket 1, 2^2 \rrbracket$,
 134 et donc,
 135 pour tout sommet de $\Gamma(g)$ et de  $\Gamma(h)$,
 136 chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant
 137 de ce sommet, une probabilité $1/4$ d'être celui qui sera traversé.
 138 En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov.
 139 Il est facile de vérifier que la \gls{matriceDeTransitions} (cf. glossaire)
 140 d'un tel processus
 141 est $M_g   = \frac{1}{4} \check{M}_g$,
 142 où $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire)
 143 donnée en figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$.
 144
 145 \begin{figure}[ht]
 146   \begin{center}
 147     \subfloat[$\check{M}_g $]{
 148       \begin{minipage}{0.25\textwidth}
 149         \begin{center}
 150           % \vspace{-3cm}
 151           $\left(
 152             \begin{array}{cccc}
 153               2 & 0 & 2 & 0 \\
 154               1 & 1 & 1 & 1 \\
 155               1 & 1 & 1 & 1 \\
 156               1 & 1 & 1 & 1
 157             \end{array}
 158           \right)
 159           $
 160         \end{center}
 161       \end{minipage}
 162       \label{fig:g:incidence}
 163     }
 164     \subfloat[$\check{M}_h $]{
 165       \begin{minipage}{0.25\textwidth}
 166         \begin{center}
 167           $\left(
 168             \begin{array}{cccc}
 169               2 & 0 & 2 & 0 \\
 170               0 & 2 & 0 & 2 \\
 171               1 & 1 & 1 & 1 \\
 172               1 & 1 & 1 & 1
 173             \end{array}
 174           \right)
 175           $
 176         \end{center}
 177       \end{minipage}
 178       \label{fig:h:incidence}
 179     }
 180   \end{center}
 181   \caption{Graphe des fonctions candidates avec $n=2$.}
 182   \label{fig:xplgraph}
 183 \end{figure}
 184
 185 Les deux matrices $M_g$ et $M_h$ sont  stochastiques. Pour
 186 montrer qu'elles sont régulières il suffit de constater qu'aucun élément de
 187 $M^2_g$ ni de  $M^2_h$ n'est nul.
 188 De plus, les vecteurs de probabilités
 189 $\pi_g=(\frac{1}{3}, \frac{1}{6},\frac{1}{3},\frac{1}{6})$ et
 190 $\pi_h=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$
 191 vérifient $\pi_g M_g = \pi_g$ et
 192 $\pi_h M_h = \pi_h$.
 193 Alors d'après le théorème~\ref{th},
 194 pour n'importe quel vecteur initial de probabilités $\pi^0$, on a
 195 $\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et
 196 $\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$.
 197 Ainsi, la chaîne de Markov associée à $h$ tend vers une
 198 distribution uniforme, contrairement à celle associée à $g$.
 199 On en déduit que $g$ ne devrait pas être itérée dans
 200 un générateur de nombres pseudo-aléatoires.
 201 Au contraire,
 202 $h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm},
 203 pour peu que le nombre $b$ d'itérations entre deux mesures successives
 204 de valeurs  soit suffisamment grand de sorte que
 205 le vecteur d'état de la chaîne de Markov
 206 ait une distribution suffisamment proche de la distribution uniforme.
 207
 208
 209 Considérons le lemme technique suivant:
 210 \begin{Lemma}\label{lem:stoc}
 211 Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et  $M$  la matrice
 212 $2^n\times 2^n$  définie par
 213 $M = \frac{1}{n}\check{M}$.
 214 Alors $M$ est une matrice stochastique régulière si et seulement si
 215 $\Gamma(f)$ est fortement connexe.
 216 \end{Lemma}
 217
 218 \begin{Proof}
 219 On remarque tout d'abord que $M$
 220 est une matrice stochastique par construction.
 221 Supposons $M$ régulière.
 222 Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
 223 1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
 224 Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
 225 dans $\Gamma(f)$ et puisque ce nombre est positif, alors
 226 $\Gamma(f)$ est fortement connexe.
 227
 228 Réciproquement si $\Gamma(f)$
 229 est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
 230 Il existe donc
 231 $k_{ij} \in \llbracket 1,  2^n \rrbracket$ tel que $\check{M}_{ij}^{k_{ij}}>0$.
 232 Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que
 233 $\check{M}_{ij}^{l\times  k_{ij}}>0$,
 234 on peut conclure que, si
 235 $k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
 236 $\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$.
 237 Ainsi, $\check{M}$ et donc $M$ sont régulières.
 238 \end{Proof}
 239
 240 Ces résultats permettent de formuler et de prouver le théorème suivant:
 241
 242 \begin{Theo}
 243   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son
 244   graphe d'itérations, $\check{M}$ sa matrice d'adjacence
 245   et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
 246   Si $\Gamma(f)$ est fortement connexe, alors
 247   la sortie du générateur de nombres pseudo-aléatoires détaillé par
 248   l'algorithme~\ref{CI Algorithm} suit une loi qui
 249   tend vers la distribution uniforme si
 250   et seulement si  $M$ est une matrice doublement stochastique.
 251 \end{Theo}
 252 \begin{Proof}
 253   $M$ est une matrice stochastique régulière (lemme~\ref{lem:stoc})
 254   qui a un unique vecteur de probabilités stationnaire
 255   (théorème \ref{th}).
 256   Soit $\pi$  défini par
 257   $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
 258   On a  $\pi M = \pi$ si et seulement si
 259   la somme des valeurs de chaque colonne de $M$  est 1,
 260   \textit{i.e.} si et seulement si
 261   $M$ est  doublement  stochastique.
 262 \end{Proof}
 263
 264 %%% Local Variables:
 265 %%% mode: latex
 266 %%% TeX-master: "main"
 267 %%% End: