Large deviations for a class of nonhomogeneous Markov chains

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 → P is irregular. Results in the intermediate regime apply to geometrically fast running optimizations, and to some issues in glassy physics.