Remarques sur l'ergodicité des algorithmes de recuit simulé sur un graphe

We consider the simulated annealing algorithm associated to a potential U on a graph (M, q) (reversible or satisfying the Hajek's weak reversibility condition), whose temperature at time t [greater-or-equal, slanted] 0 is given by k ln-1 (1 + t), with k> c(M, U) the critical constant for the ergodicity in law of the process. Let (respectively ) the connected component of the set [x [set membership, variant] M U(x) <minM U + k] (respectively {x [set membership, variant] M U(x) [less-than-or-equals, slant] minM U + k}) which contains all the global minima. We will see that is the recurrent set and that the occupation times of points in (or of points x0 in such that U(x0) = k) satisfy a strong law of large numbers. Furthermore, if the graph is a reversible tree and if , we shall study the behaviour in law and a.s. of the fluctuations around these laws of large numbers (central limit theorem and law of the iterated logarithm).Résumé On considère l'algorithme de recuit simulé associé à un potentiel U sur un graphe (M, q) (réversible ou satisfaisant la condition de réversibilité faible de Hajek), dont la décroissance de la température est en k ln-1 (1 + t), avec k> c(M, U) la constante critique assurant l'ergodicité en loi de ce processus. Soit (respectivement ) la composante connexe de l'ensemble [x [set membership, variant]M U(x) < minM U + k] (respectivement {x [set membership, variant] M U(x) [less-than-or-equals, slant] minM U + k}) qui contient l'ensemble des minima globaux du potentiel U. On verra que est l'ensemble des points récurrents et que les temps d'occupation des points de (ou des points tels que U(x0) = k) satisfont une loi forte des grands nombres. Dans le cas où le graphe est un arbre réversible et où , on étudiera également le comportement en loi et p.s. des fluctuations autour de ces lois des grands nombres (théoréme de la limite centrale et loi du logarithme itéré).