Mathematics – Probability
Scientific paper
2004-04-12
Annals of Applied Probability 2005, Vol. 15, No. 1A, 421-486
Mathematics
Probability
Published at http://dx.doi.org/10.1214/105051604000000990 in the Annals of Applied Probability (http://www.imstat.org/aap/) by
Scientific paper
10.1214/105051604000000990
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\to P is irregular. Results in the intermediate regime apply to geometrically fast running optimizations, and to some issues in glassy physics.
Dietz Zach
Sethuraman Sunder
No associations
LandOfFree
Large deviations for a class of nonhomogeneous Markov chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Large deviations for a class of nonhomogeneous Markov chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large deviations for a class of nonhomogeneous Markov chains will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-608951