typos

[rairo15.git] / exp.tex

Cette section présente une application directe de la théorie développée ci-avant
à la génération de nombres pseudo-aléatoires. On présente tout d'abord le générateur
basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), 
puis comment intégrer la contrainte de \gls{distributionuniforme} (cf. glossaire) 
de la sortie 
dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}). 


\subsection{Générateur de nombres pseudo-aléatoires basé sur le chaos}
\label{sub:prng:algo}

On peut penser à construire un générateur de nombres pseudo-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.

\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 + \textit{Random}(b+1)$\;
%$k\leftarrow b + \textit{XORshift}(b+1)$\;
\For{$i=0,\dots,k-1$}
{
$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
%$s\leftarrow{\textit{XORshift}(n)}$\;
$x\leftarrow{F_f(s,x)}$\;
}
return $x$\;
%\end{scriptsize}
\caption{Algorithme de génération de nombres pseudo-aléatoires 
à l'aide de la fonction chaotique $G_f$.}
\label{CI Algorithm}
\end{algorithm}


Celui-ci prend  en entrée: une  fonction $f$; un  entier $b$, qui assure  que le
nombre  d'itérations est compris  entre $b+1  $ et  $2b+1$ et  une configuration
initiale $x^0$.   Il retourne  une nouvelle configuration  $x$.  En  interne, il
exploite    la   fonction \linebreak    $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
\mathcal{P}(\{1,\ldots   n\})$   qui   donne   l'ensemble   dont   la   fonction
caractéristique  serait  représentée par  le  nombre  donné  en argument  et  un
algorithme de génération de nombres pseudo-aléatoires \textit{Random}$(l)$.  Cet
algorithme est utilisé  dans notre générateur pour construire  la longueur de la
stratégie ainsi  que les éléments  qui la composent.  Pratiquement,  il retourne
des    entiers   dans    $\llbracket    1   ;    l    \rrbracket$   selon    une
\gls{distributionuniforme} %(cf. glossaire)
et utilise \textit{XORshift} qui est
une classe de  générateurs de nombres pseudo-aléatoires très  rapides conçus par
George Marsaglia~\cite{Marsaglia98}.

% L'algorithme \textit{XORshift} exploite itérativement
% la fonction \og \gls{xor}\fg{} $\oplus$ (cf. glossaire) 
% sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).

L'algorithme \textit{XORshift} 
exploite itérativement l'opérateur $\oplus$  
sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire)
.
Cet opérateur, défini dans $\Bool^{n}$, 
applique la fonction \og  \gls{xor} \fg{} (cf. glossaire) 
aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}).
Une instance de cette classe est donnée dans l'algorithme~\ref{XORshift} détaillé
ci-dessous.

\begin{algorithm}[h]
%\SetLine
\KwIn{la configuration interne $z$ (un mot de 32-bit)}
\KwOut{$y$ (un mot de 32-bits)}
$z\leftarrow{z\oplus{(z\ll13)}}$\;
$z\leftarrow{z\oplus{(z\gg17)}}$\;
$z\leftarrow{z\oplus{(z\ll5)}}$\;
$y\leftarrow{z}$\;
return $y$\;
\medskip
\caption{Une boucle de l'algorithme de \textit{XORshift}.}
\label{XORshift}
\end{algorithm}

Il reste à instancier une fonction $f$ dans 
l'algorithme~\ref{CI Algorithm}. 
%en adéquation avec  l'approche développée 
%en section~\ref{sec:sccg}.
La section suivante montre comment l'uniformité de la distribution
contraint cette instanciation.

\subsection{Un générateur à sortie uniformément distribuée}
\label{sub:prng:unif}

Une matrice \emph{stochastique} est une matrice carrée
dont tous les éléments sont positifs ou nuls et dont
la somme de chaque ligne
vaut 1. 
Une matrice est \emph{doublement stochastique} si elle est stochastique et que la somme de chaque colonne est 1.
Enfin, une matrice stochastique de taille $n \times n$ est \emph{régulière} 
si  la propriété suivante est établie:
$$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$

On énonce enfin le théorème suivant liant les 
\glspl{vecteurDeProbabilite} (cf. glossaire) 
et les \glspl{chaineDeMarkov}  (cf. glossaire)
:

 
\begin{Theo}\label{th}
  Si $M$ est une matrice stochastique régulière, alors $M$ 
  possède un unique vecteur stationnaire de probabilités  $\pi$
  ($\pi.M = \pi$).
  De plus, si $\pi^0$ est un \gls{vecteurDeProbabilite} 
 et si on définit 
  la suite $(\pi^{k})^{k \in  \Nats}$ par 
  $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
  alors la \gls{chaineDeMarkov} $\pi^k$
  converge vers $\pi$ lorsque $k$ tend vers l'infini.
\end{Theo}


Montrons sur un exemple jouet à deux éléments 
que ce théorème permet de vérifier si la sortie d'un générateur de 
nombres pseudo-aléatoires est uniformément distribuée ou non.
Soit alors $g$ et $h$ deux fonctions  de $\Bool^2$
définies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $
et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
% Leurs graphes d'interactions donnés en figures \ref{fig:g:inter} et \ref{fig:h:inter}
% vérifient les hypothèses du théorème~\ref{th:Adrien}. 
Leurs graphes d'itérations
sont  fortement connexes, ce que l'on a pu déjà vérifier aux figures
\ref{fig:g:iter} et \ref{fig:h:iter}.
\textit{A priori}, ces deux fonctions pourraient être intégrées
dans un générateur de nombres pseudo-aléatoires. Montrons que ce n'est pas le cas pour $g$ et 
que cela l'est pour $h$.

Comme le générateur \textit{Random} possède une sortie uniformément 
distribuée,  la  stratégie est uniforme sur $\llbracket 1, 2^2 \rrbracket$,
et donc, 
pour tout sommet de $\Gamma(g)$ et de  $\Gamma(h)$,
chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant 
de ce sommet, une probabilité $1/4$ d'être celui qui sera traversé.
En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov.
Il est facile de vérifier que la \gls{matriceDeTransitions} (cf. glossaire)
d'un tel processus 
est $M_g   = \frac{1}{4} \check{M}_g$, 
où $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire)
donnée en figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. 

\begin{figure}[ht]
  \begin{center}
    \subfloat[$\check{M}_g $]{
      \begin{minipage}{0.25\textwidth}
        \begin{center}
          % \vspace{-3cm}
          $\left( 
            \begin{array}{cccc} 
              2 & 0 & 2 & 0 \\ 
              1 & 1 & 1 & 1 \\ 
              1 & 1 & 1 & 1 \\ 
              1 & 1 & 1 & 1 
            \end{array}
          \right)
          $
        \end{center}
      \end{minipage}
      \label{fig:g:incidence}
    }
    \subfloat[$\check{M}_h $]{
      \begin{minipage}{0.25\textwidth}
        \begin{center}
          $\left( 
            \begin{array}{cccc} 
              2 & 0 & 2 & 0 \\ 
              0 & 2 & 0 & 2 \\ 
              1 & 1 & 1 & 1 \\ 
              1 & 1 & 1 & 1 
            \end{array}
          \right)
          $
        \end{center}
      \end{minipage}
      \label{fig:h:incidence}
    }
  \end{center}
  \caption{Graphe des fonctions candidates avec $n=2$.}
  \label{fig:xplgraph}
\end{figure}

Les deux matrices $M_g$ et $M_h$ sont  stochastiques. Pour
montrer qu'elles sont régulières il suffit de constater qu'aucun élément de 
$M^2_g$ ni de  $M^2_h$ n'est nul.
De plus, les vecteurs de probabilités 
$\pi_g=(\frac{1}{3}, \frac{1}{6},\frac{1}{3},\frac{1}{6})$ et
$\pi_h=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ 
vérifient $\pi_g M_g = \pi_g$ et 
$\pi_h M_h = \pi_h$. 
Alors d'après le théorème~\ref{th}, 
pour n'importe quel vecteur initial de probabilités $\pi^0$, on a 
$\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
$\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 
Ainsi, la chaîne de Markov associée à $h$ tend vers une 
distribution uniforme, contrairement à celle associée à $g$.
On en déduit que $g$ ne devrait pas être itérée dans 
un générateur de nombres pseudo-aléatoires.
Au contraire, 
$h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm}, 
pour peu que le nombre $b$ d'itérations entre deux mesures successives 
de valeurs  soit suffisamment grand de sorte que
le vecteur d'état de la chaîne de Markov
ait une distribution suffisamment proche de la distribution uniforme.


Considérons le lemme technique suivant:
\begin{Lemma}\label{lem:stoc}
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 
$2^n\times 2^n$  définie par
$M = \frac{1}{n}\check{M}$.
Alors $M$ est une matrice stochastique régulière si et seulement si
$\Gamma(f)$ est fortement connexe.
\end{Lemma}

\begin{Proof}  
On remarque tout d'abord que $M$ 
est une matrice stochastique par construction.
Supposons $M$ régulière. 
Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
dans $\Gamma(f)$ et puisque ce nombre est positif, alors 
$\Gamma(f)$ est fortement connexe.

Réciproquement si $\Gamma(f)$ 
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.
Il existe donc 
$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tel que $\check{M}_{ij}^{k_{ij}}>0$.  
Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
on peut conclure que, si 
$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
Ainsi, $\check{M}$ et donc $M$ sont régulières.
\end{Proof}

Ces résultats permettent de formuler et de prouver le théorème suivant:

\begin{Theo}
  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son 
  graphe d'itérations, $\check{M}$ sa matrice d'adjacence
  et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
  Si $\Gamma(f)$ est fortement connexe, alors 
  la sortie du générateur de nombres pseudo-aléatoires détaillé par 
  l'algorithme~\ref{CI Algorithm} suit une loi qui 
  tend vers la distribution uniforme si 
  et seulement si  $M$ est une matrice doublement stochastique.
\end{Theo}
\begin{Proof}
  $M$ est une matrice stochastique régulière (lemme~\ref{lem:stoc}) 
  qui a un unique vecteur de probabilités stationnaire
  (théorème \ref{th}).
  Soit $\pi$  défini par 
  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
  On a  $\pi M = \pi$ si et seulement si
  la somme des valeurs de chaque colonne de $M$  est 1, 
  \textit{i.e.} si et seulement si 
  $M$ est  doublement  stochastique.
\end{Proof}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: