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

@article{citeulike:1584478, abstract = {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).}, author = {Anily, Shoshana and Federgruen, Awi }, citeulike-article-id = {1584478}, comment = {Definitions of weak/strong ergodicity for Markov chains references for early study of ergodicity for nonstationary chains Condition for weakly ergodic non-stationary Markov chain to be strongly ergodic. Modifies the condition for strong ergodicity (sum of differences of eigenvectors converges) to not require explicit form of eigenvectors}, journal = {Operations Research}, number = {6}, pages = {867--874}, posted-at = {2007-08-23 01:05:21}, priority = {2}, title = {Ergodicity in Parametric Nonstationary Markov Chains: An Application to Simulated Annealing Methods}, url = {http://www.jstor.org/stable/171435}, volume = {35}, year = {1987} }

TY - JOUR ID - citeulike:1584478 L3 - citeulike-article-id:1584478 TI - Ergodicity in Parametric Nonstationary Markov Chains: An Application to Simulated Annealing Methods JF - Operations Research VL - 35 IS - 6 SP - 867 EP - 874 N2 - 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). N1 - Definitions of weak/strong ergodicity for Markov chains references for early study of ergodicity for nonstationary chains Condition for weakly ergodic non-stationary Markov chain to be strongly ergodic. Modifies the condition for strong ergodicity (sum of differences of eigenvectors converges) to not require explicit form of eigenvectors AU - Anily, Shoshana AU - Federgruen, Awi PY - 1987/// UR - http://www.jstor.org/stable/171435 ER -