We define a notion of
order of recurrencefor the states and transitions of a general class of time-inhomogeneous Markov chains with transition probabilities proportional to powers of a small vanishing parameter. These orders are shown to satisfy a balance equationacross every edge cut in the associated graph. The resulting order balance equations allow computation of the orders of recurrence of the states, and thereby the determination of the asymptotic behavior of the Markov chain.
The method of
optimization by simulated annealingis a special case of such Markov processes, and can therefore be treated by means of these balance equations. In particular, in this special situation we show that there holds a detailed balanceof order of recurrence across every edgein the graph. Moreover, the sum of the order of recurrence of a state and its cost is shown to be a constant in each connected set of recurrent states. By this approach, we determine the necessary and sufficient condition on the rate of cooling to guarantee that a minimum of the optimization problem is hit with probability one. Moreover, the rates of convergence of the probabilities can be deduced from the orders of recurrence.