talk/heam.tex

   1
   2 \begin{theorem}[Temps de mixage sans chemin hamiltonien~\cite{ccgh16}]
   3 On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de
   4 probabilités $p$ définie sur l'ensemble des arcs comme suit:
   5 \[
   6 p(e) \left\{
   7 \begin{array}{ll}
   8 = \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
   9 = \frac{1}{2\mathsf{N}} \textrm{ sinon.}
  10 \end{array}
  11 \right.
  12 \]
  13
  14 La chaîne de Markov associée converge vers la distribution uniforme et
  15
  16 \[
  17  \, t_{\rm mix}(\varepsilon)
  18 \leq \lceil\log_2(\varepsilon^{-1})\rceil
  19 4(8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1))
  20 \]
  21
  22 \end{theorem}
  23 \begin{itemize}
  24 \item Remarques sur la preuve:
  25 \begin{itemize}
  26 \item Itérations paresseuses $\not \equiv$ algorithme.
  27 \item Hypothèse très faible: suppressions d'un arc entrant et d'un arc sortant
  28 par n{\oe}ud.
  29 \item Pratiquement:
  30 $
  31 4(8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1))
  32 \leadsto
  33 4(2\mathsf{N}\ln(2\mathsf{N}+8)).
  34 $
  35
  36 \end{itemize}
  37 \end{itemize}