]> AND Private Git Repository - hdrcouchot.git/blob - talk/heam.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
la veille
[hdrcouchot.git] / 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}