annexePreuveDistribution.tex

   1
   2 Considérons le lemme technique suivant:
   3 \begin{lemma}\label{lem:stoc}
   4 Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\textsc{giu}(f)$, et  $M$  la matrice
   5 $2^n\times 2^n$  définie par
   6 $M = \frac{1}{n}\check{M}$.
   7 Alors $M$ est une matrice stochastique régulière si et seulement si
   8 $\textsc{giu}(f)$ est fortement connexe.
   9 \end{lemma}
  10
  11 \begin{Proof}
  12 On remarque tout d'abord que $M$
  13 est une matrice stochastique par construction.
  14 Supposons $M$ régulière.
  15 Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
  16 1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
  17 Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
  18 dans $\textsc{giu}(f)$ et puisque ce nombre est positif, alors
  19 $\textsc{giu}(f)$ est fortement connexe.
  20
  21 Réciproquement si $\textsc{giu}(f)$
  22 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.
  23 Il existe donc
  24 $k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.
  25 Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que
  26 $\check{M}_{ij}^{l\times  k_{ij}}>0$,
  27 on peut conclure que, si
  28 $k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
  29 $\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$.
  30 Ainsi, $\check{M}$ et donc $M$ sont régulières.
  31 \end{Proof}
  32
  33 Ces résultats permettent formuler et de prouver le théorème suivant:
  34
  35 \begin{theorem}
  36   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son
  37   graphe d'itérations , $\check{M}$ sa matrice d'adjacence
  38   et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
  39   Si $\textsc{giu}(f)$ est fortement connexe, alors
  40   la sortie du générateur de nombres pseudo aléatoires détaillé par
  41   l'algorithme~\ref{CI Algorithm} suit une loi qui
  42   tend vers la distribution uniforme si
  43   et seulement si  $M$ est une matrice doublement stochastique.
  44 \end{theorem}
  45
  46 \begin{Proof}
  47   $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc})
  48   qui a un unique vecteur de probabilités stationnaire
  49   (Théorème \ref{th}).
  50   Soit $\pi$  défini par
  51   $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
  52   On a  $\pi M = \pi$ si et seulement si
  53   la somme des valeurs de chaque colonne de $M$  est 1,
  54   \textit{i.e.} si et seulement si
  55   $M$ est  doublement  stochastique.
  56 \end{Proof}
  57