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