Large deviations of a class of non-homogeneous Markov chains

Abstract

<p>Let Sigma = 1, 2, ..., r be a finite set of points. Let Pn = pn( i, j) : i, j [is in] Sigma be an r x r stochastic matrix for n ≥ 1, and p be a distribution on Sigma. Let now Pp= Pp({Pn }) be the (non-homogeneous) Markov measure on the sequence space Sinfinity with Borel sets B(Sinfinity) corresponding to initial distribution p and transition kernels Pn.;We now describe the class of non-homogeneous process focused upon in the article. These are the Markov chains where the transition kernels are asymptotically close to a fixed stochastic matrix. Let p be a distribution and P be a stochastic matrix on Sigma. Define the collection A=A p,P by A={Pp ({Pn}) :lim n→infinityPn =P}. The collection A can be thought of as perturbations of the stationary Markov chain run with P, and is a natural class in which to explore how "non-homogeneity" enters into the large deviation picture.;Let now f : Sigma → Rd be a d ≥ 1 dimensional function. Let also Pp({P n})[is in]A(p, P) be a "perturbed" non-homogeneous Markov measure. In terms of the coordinate process, define the additive sums Zn = Zn(f) for n ≥ 1 by Zn=1n i=1nf(Xi). The goal of this paper is to understand the large deviation behavior of the induced distributions of Zn : n ≥ 1 with respect to Pp({P n}) . An immediate question which comes to mind asks whether these large deviations differ from the deviations with respect to the stationary chain run with P. The general answer found in our work is "yes" and "no," and as might be suspected depends on the rate of convergence Pn → P and the structure of the limit matrix P.;More specifically, when P is an irreducible matrix, it turns out that the large deviation of behavior of Zn under Pp({P n}) is exactly that under the stationary chain associated with P no matter the rate of convergence of Pn to P. Therefore, perhaps the most interesting case is when the target matrix P is reducible. In this situation, the large deviations of Zn depend both on the type of reducibilities of P and the convergence rate of Pn to P, and fall roughly into three distinct categories. Namely, when the convergence speed is "very" fast, the large deviation behavior is the same as for the stationary Markov chain run under P; when the speed is "slow," one obtains a "trivial" large deviation behavior; and finally when the speed is "intermediate," a non-trivial behavior is found which differs from stationarity. Moreover, these behaviors are characterized in terms of an explicit rate function which illustrates that among all paths which lead to a deviation those which minimize certain "routing" and "resting" costs are selected.</p>