Large deviations for a class of nonhomogeneous Markov chains

DOI10.1214/105051604000000990MaRDI QIDQ1774226zbMATH OpenOpenAlexFDO

Publication date 29 April 2005

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0404230

Large deviations (60F10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: 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 {P_n} be a sequence of transition matrices on a finite state space which converge to a limit transition matrix P. Let {X_n} be the associated nonhomogeneous Markov chain where P_n 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 P_n 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 P_n o P is irregular. Results in the intermediate regime apply to geometrically fast running optimizations, and to some issues in glassy physics.

Recommendations

Cites work

Cited in

(26)

This page was built for publication: Large deviations for a class of nonhomogeneous Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1774226)