Quasi-Statically Cooled Markov Chains

We consider time--inhomogeneous Markov chains on a finite state--space, whose transition probabilities p ij (t) = c ij ffl(t) V ij are proportional to powers of a vanishing small parameter ffl(t). We determine the precise relationship between this chain, and the corresponding time--homogeneous chains p ij = c ij ffl V ij , as ffl & 0. Let f ffl i g be the steady--state distribution of this time--homogeneous chain. We characterize the orders fj i g in ffl i = \Theta(ffl j i ). We show that if ffl(t) & 0 slowly enough, then the time--wise occupation measures fi i := supfq ? 0 j P 1 t=1 ffl(t) q Prob(x(t) = i) = +1g, called the recurrence orders, satisfy fi i \Gamma fi j = j j \Gamma j i . Moreover, if G := fj i j j i = min j j j g is the set of "ground states" of the time--homogeneous chain, then x(t) ! G, in an appropriate sense, whenever j(t) is "cooled" slowly. We also show that there exists a critical ae such that x(t) ! G if and only if P 1 t=1 ffl(t) ae = +..