talk/markov.tex~

   1 \begin{block}{Iteration Graph}
   2 The {\emph{iteration graph}} $\Gamma(f)$:
   3 directed graph s. t.
   4 \begin{itemize}
   5 \item the set of vertices: $\Bool^n$
   6 \item the set of edges: $(x,F_f(i,x)) \in \Gamma(f)$, $x\in\Bool^n$,
   7 $i\in \llbracket1;n\rrbracket$
   8 \end{itemize}
   9 \end{block}
  10
  11 \begin{block}{Markov Matrix}
  12 Matrix $M$:
  13 \[
  14 \begin{array}{l}
  15 M_{ij} = \frac{1}{n} \textrm{ if $i \neq j$ and $(i,j) \in  \Gamma(f)$} \\
  16 M_{ij} = 0 \textrm{ if $i \neq j$ and $(i,j) \not \in  \Gamma(f)$} \\
  17 M_{ii} = 1 - \sum\limits_{j=1, j\neq i}^n M_{ij}
  18 \end{array}
  19 \]
  20 \end{block}
  21
  22 \begin{exampleblock}{$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2})$, $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
  23 \vspace{-1em}
  24 \begin{figure}%[t]
  25     \subfloat[$\Gamma(g)$, $M_g$]{
  26       \begin{minipage}{0.11\textwidth}
  27           \includegraphics[scale=0.4]{g.pdf}
  28       \end{minipage}
  29       \begin{minipage}{0.25\textwidth}
  30           $\dfrac{1}{2}\left(
  31             \begin{array}{c}
  32               1  0  1  0 \\
  33               1  0  0  1 \\
  34               1  0  0  1 \\
  35               0  1  1  0
  36             \end{array}
  37           \right)$
  38         \end{minipage}
  39       }
  40     \subfloat[$\Gamma(h)$, $M_h$]{
  41       \begin{minipage}{0.10\textwidth}
  42           \includegraphics[scale=0.4]{h.pdf}
  43       \end{minipage}
  44       \begin{minipage}{0.25\textwidth}
  45         $\dfrac{1}{2}\left(
  46           \begin{array}{c}
  47             1  0  1  0 \\
  48             0  1  0  1 \\
  49             1  0  0  1 \\
  50             0  1  1  0
  51           \end{array}
  52         \right)
  53         $
  54       \end{minipage}
  55     }
  56 \end{figure}
  57 \end{exampleblock}