On the problem of exit from cycles for simulated annealing processes--a backward equation approach

For a simulated annealing process Xt on S with transition rates qij(t)=pijexp(.(U(i,j))/T(t)) where i,j.S and T(t).0 in a suitable way, we study the exit distribution Pt,i(X.=a) and mean exit time Et,i(.) of Xt from a cycle c as t... A cycle is a particular subset of S whose precise definition will be given in Section 1. Here . is the exit time of the process from c containing i and a is an arbitrary state not in c. We consider the differential (backward) equation of Pt,i(X.=a) and Et,i(.) and show that limt..Pt,i(X.=a)/exp(.U(c,a).T(t)) and \lim_{t\to\infty E_{t,i}(\tau)/\exp(V(c)/T(t)) exist and are independent of i.c. The constant (U(c,a)) is usually referred to as the cost from c to a and V(c),(.U(c,a)) is the minimal cost coming out of c. We also obtain estimates of |Pt,i(X.=a).Pt,j(X.=a)| and |Et,i(.)| for i.j as t... As an application, we shall show that similar results hold for the family of Markov processes with transition rates q.ij=pijexp(.U(i,j)/.) where .>0 is small.