On the convergence rate of annealing processes. (English) Zbl 0665.60090

Let \(X_ t\) be an inhomogeneous Markov process defined on \(S=\{0,1,...,N\}\) with transition rate \[ Q_{ij}=P(i,j)\exp [-(u(j)- u(i))^ t/T(t)]\quad for\quad j\neq i,\quad and\quad =-\sum_{k\neq i}Q_{ik}(t)\quad for\quad j=i, \] where T(t) is the temperature and u(i) is the energy level at i. The paper investigates the rate of convergence of \(P(X_ t=i)\) and shows that \[ \lim_{t\to \infty}P(X(t)=i)/\exp (-u(i)/T(t)) \] exists and is positive for each \(i\in S\) under certain conditions on T(t). These limits are independent of the initial distribution of \(X_ 0\) and can be obtained through solving systems of linear equations.
Reviewer: L.Lakatos


60J99 Markov processes
60J27 Continuous-time Markov processes on discrete state spaces
15B51 Stochastic matrices
15A18 Eigenvalues, singular values, and eigenvectors
90B40 Search theory
Full Text: DOI