2004/04/30 by Zach Dietz, Sunder Sethuraman
Mathematics · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #math.PR #msc:60F10. #msc:60J10
paper · pdf · doi:10.1214/105051604000000990
published as Annals of Applied Probability 2005, Vol. 15, No. 1A, 421-486 · Published at http://dx.doi.org/10.1214/105051604000000990 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
openalex publication_date 2005/02/01 · arxiv created 2005/04/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Large deviation results are given for a class of perturbed nonhomogeneous Markov chains on finite state space which formally includes some stochastic optimization algorithms. Specifically, let Pn be a sequence of transition matrices on a finite state space which converge to a limit transition matrix P. Let Xn be the associated nonhomogeneous Markov chain where Pn controls movement from time n−1 to n. The main statements are a large deviation principle and bounds for additive functionals of the nonhomogeneous process under some regularity conditions. In particular, when P is reducible, three regimes that depend on the decay of certain “connection” Pn probabilities are identified. Roughly, if the decay is too slow, too fast or in an intermediate range, the large deviation behavior is trivial, the same as the time-homogeneous chain run with P or nontrivial and involving the decay rates. Examples of anomalous behaviors are also given when the approach Pn→P is irregular. Results in the intermediate regime apply to geometrically fast running optimizations, and to some issues in glassy physics.