# title
Balance of Recurrece Order in Time-Inhomogenous Markov Chains with Application to Simulated Annealing

# abstract
<jats:p>We define a notion of <jats:italic>order of recurrence</jats:italic> for 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 <jats:italic>balance equation</jats:italic> across 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.</jats:p><jats:p>The method of <jats:italic>optimization by simulated annealing</jats:italic> is 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 <jats:italic>detailed balance</jats:italic> of order of recurrence across <jats:italic>every edge</jats:italic> in 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 <jats:italic>probability one</jats:italic>. Moreover, the rates of convergence of the probabilities can be deduced from the orders of recurrence.</jats:p>

# publicationVenue.label
Probability in the Engineering and Informational Sciences

# publicationOutlet
Probability in the Engineering and Informational Sciences