Abstract

A nonstationary Markov chain is weakly ergodic if the dependence on the state distribution on the starting state vanishes as time tends to infinity. A chain is strongly ergodic if it is weakly ergodic and converges in distribution. In this paper we show that the two ergodicity concepts are equivalent for finite chains under rather general (and widely verifiable) conditions. We discuss applications to probabalistic analyses of general search methods for combinatorial optimization problems (simulated annealing).

Authors
Shoshana Anily and Awi Federgruen
Format
Journal Article
Publication Date
Journal
Operations Research

Full Citation

Anily, Shoshana and Awi Federgruen
. “Ergodicity in parametric nonstationary Markov chains: An application to simulated annealing methods.”
Operations Research
vol.
35
, (January 01, 1987):
867
-
874
.