LARGE-TIME BEHAVIOR OF PERTURBED DIFFUSION MARKOV-PROCESSES WITH APPLICATIONS TO THE 2ND EIGENVALUE PROBLEM FOR FOKKER-PLANCK OPERATORS AND SIMULATED ANNEALING

We study the large-time behavior and rate of convergence to the invariant measures of the processes d Xε(t)=b(X)ε(t)) d t + εσ(Xε(t)) d B(t). A crucial constant Λ appears naturally in our study. Heuristically, when the time is of the order exp(Λ - α)/ε2, the transition density has a good lower bound and when the process has run for about exp(Λ - α)/ε2, it is very close to the invariant measure. Let Lε=(ε2/2)Λ - ∇U · ∇ be a second-order differential operator on ℝd. Under suitable conditions, Lz has the discrete spectrum {Mathematical expression} Let U be a function from ℝd to [0,∞) with suitable conditions. A nonhomogeneous Markov process Y(·) governed by {Mathematical expression} with Y(0)=x is used to search for a global minimum of U. Let S={x|U(x)=minyU(y)}. There exists a critical constant d* such that for c > d*, Y(t) uniformly converges to S in probability over x in a compact set. The above statement fails for c <d*. For c > Λ, Y(t) converges weakly to a probability measure which does not depend on the starting point x and concentrates on S. The techniques can also be used to study discrete simulated annealing. © 1990 Kluwer Academic Publishers.