REMARKS ON ERGODICITY OF SIMULATED ANNEAL ING ALGORITHMS ON A GRAPH

We consider the simulated annealing algorithm associated to a potentia l U on a graph (M,q) (reversible or satisfying the Hajek's weak revers ibility 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 constan t for the ergodicity in law of the process. Let ($) over tilde M (resp ectively ($) over cap M) the connected component of the set {x is an e lement 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 n umbers. 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 limi t theorem and law of the iterated logarithm).