Quasi-Statically Cooled Markov Chains
Authors:
- 1 January 1994
- journal article
- research article
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 8 (1) , 1-19
Abstract
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 ρ*.Keywords
This publication has 15 references indexed in Scilit:
- Simulated Annealing Type Markov Chains and Their Order Balance EquationsSIAM Journal on Control and Optimization, 1989
- A Limit Theorem for a Class of Inhomogeneous Markov ProcessesThe Annals of Probability, 1989
- A proof of the Markov chain tree theoremStatistics & Probability Letters, 1989
- Cooling Schedules for Optimal AnnealingMathematics of Operations Research, 1988
- Balance of Recurrece Order in Time-Inhomogenous Markov Chains with Application to Simulated AnnealingProbability in the Engineering and Informational Sciences, 1988
- Simulated annealing methods with general acceptance probabilitiesJournal of Applied Probability, 1987
- Estimating a probability using finite memoryIEEE Transactions on Information Theory, 1986
- Convergence and finite-time behavior of simulated annealingAdvances in Applied Probability, 1986
- Optimization by Simulated AnnealingScience, 1983
- Studies in irreversible thermodynamics IV. diagrammatic representation of steady state fluxes for unimolecular systemsJournal of Theoretical Biology, 1966