REMARKS ON ERGODICITY OF SIMULATED ANNEALING ALGORITHMS ON A GRAPH

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 than or equal to 0 is given by kln(-1)(1 + t), with k > c(M, U) the critical constant for the ergodicity in law of the process. Let ($) over tilde M (respectively ($) over cap M) the connected component of the set {x is an element of M\U(x) < min(M) U + k} (respectively {x is an element of M\U(x)less than or equal to min(M) U + k}) which contains all the global minima. We will see that ($) over cap M is the recurrent set and that the occupation times of points in ($) over tilde M (or of points x(0) in ($) over cap M such that U(x(0))=k) satisfy a strong law of large numbers. Furthermore, if the graph is a reversible tree and if ($) over cap M = ($) over tilde M, 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).