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 ρ*.

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