talk/condunif.tex

   1  \begin{theorem}[Uniformité de la sortie~\cite{bcgr11:ip}]
   2   Soit $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$, $\textsc{giu}(f)$ son
   3   graphe d'itérations , $\check{M}$ sa matrice d'adjacence.
   4   Si $\textsc{giu}(f)$ est fortement connexe, alors
   5   la sortie du générateur de nombres pseudo-aléatoires suit une loi qui
   6   tend vers la distribution uniforme ssi  $\dfrac{1}{\mathsf{N}} \check{M}$ est  doublement stochastique.
   7 \end{theorem}
   8
   9
  10 \begin{minipage}[b]{0.45\textwidth}
  11 \begin{block}{}
  12   \begin{minipage}[b]{0.15\textwidth}
  13     \includegraphics[height=3cm]{../images/g.pdf}
  14   \end{minipage}
  15   \begin{minipage}[b]{0.80\textwidth}
  16     \begin{itemize}
  17     \item $g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2})$
  18     \item $M_g = \dfrac{1}{2}\left(
  19         \begin{array}{c}
  20           1  0  1  0 \\
  21           1  0  0  1 \\
  22           1  0  0  1 \\
  23           0  1  1  0
  24         \end{array}
  25       \right)$
  26     \item $\pi_g=(\frac{4}{10}, \frac{1}{10},\frac{3}{10},\frac{2}{10})$
  27     \end{itemize}
  28   \end{minipage}
  29 \end{block}
  30 \end{minipage}
  31 \quad
  32 \begin{minipage}[b]{0.50\textwidth}
  33   \begin{block}{}
  34   \begin{minipage}[b]{0.15\textwidth}
  35     \includegraphics[height=3cm]{../images/h.pdf}
  36   \end{minipage}
  37   \begin{minipage}[b]{0.82\textwidth}
  38     \vspace{-2em}
  39   \begin{itemize}
  40   \item $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$
  41   \item $M_h = \dfrac{1}{2}\left(
  42       \begin{array}{c}
  43         1  0  1  0 \\
  44         0  1  0  1 \\
  45         1  0  0  1 \\
  46         0  1  1  0
  47
  48       \end{array}
  49     \right)
  50     $
  51   \item $\pi_h=(\frac{1}{2}, \frac{1}{2},\frac{1}{2},\frac{1}{2})$
  52   \end{itemize}
  53 \end{minipage}
  54 \end{block}
  55 \end{minipage}
  56