Quasi-Statically Cooled Markov Chains Academic Article uri icon


  • We consider time-inhomogeneous Markov chains on a finite state-space, whose transition probabilitiespij(t) = cij(t)Vij are proportional to powers of a vanishing small parameter (t). We determine the precise relationship between this chain and the corresponding time-homogeneous chains pij= cij(t)vij, as 0. Let {} be the steady-state distribution of this time-homogeneous chain. We characterize the orders {} in = (). We show that if (t) 0 slowly enough, then the timewise occupation measures := sup { q > 0 | Prob(x(t) = i) = + }, called the recurrence orders, satisfy i j = j i. Moreover, : = { | = minj} is the set of ground states of the time-homogeneous chain, then x(t) . in an appropriate sense, whenever (t) is cooled slowly. We also show that there exists a critical * such that x(t) if and only if = + . We characterize this critical rate as * = max.min min max. Finally, we provide a graph algorithm for determining the orders [i] [i] and the critical rate *.

published proceedings

  • Probability in the Engineering and Informational Sciences

author list (cited authors)

  • Desai, M., Kumar, S., & Kumar, P. R.

citation count

  • 3

complete list of authors

  • Desai, Madhav||Kumar, Sunil||Kumar, PR

publication date

  • January 1994