Ergodicity in Parametric Nonstationary Markov Chains: An Application to Simulated Annealing Methods

A nonstationary Markov chain is weakly ergodic if the dependence of 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 probabilistic analyses of general search methods for combinatorial optimization problems (simulated annealing).