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 ⩾ 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 M̃ (respectively M̂) the connected component of the set [x ∈ M | U(x) <minM U + k] (respectively {x ∈ M | U(x) ⩽ minM U + k}) which contains all the global minima. We will see that M̂ is the recurrent set and that the occupation times of points in M̃ (or of points x0 in M̂ such that U(x0) = k) satisfy a strong law of large numbers. Furthermore, if the graph is a reversible tree and if M̂ = 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). é sidè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 M̃ (respectivement M̂) la composante connexe de lʹensemble [x ∈M | U(x) < minM U + k] (respectivement {x ∈ M | U(x) ⩽ minM U + k}) qui contient lʹensemble des minima globaux du potentiel U. On verra que M̂ est lʹensemble des points récurrents et que les temps dʹoccupation des points de M̃ (ou des points x0 ∈ M̂ 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ù M̂ = M̃, 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é).