Large Deviation Theorems for Empirical Types of Markov Chains Constrained to Thin Sets

Abstract

Let M denote the distribution of an irreducible Markov chain supported by a finite directed graph y, and let P<inf>n</inf>denote the empirical type of the first n transitions. Csiszar, Cover, and Choi examined the large deviation properties of P<inf>n</inf>and proved conditional limit theorems subject to linear inequality constraints. We consider linear equality constraints and more general constraint sets ∏ with empty interior in the set of stationary distributions on y. Let ∏^∊⊆ ∏ denote the subset of empirical types of cycles, and let (d(∏) = (d(∏^∊) denote the greatest common divisor of the lengths of cycles whose empirical type falls in ∏. We prove under certain hypotheses on ∏ that the probability M{P<inf>n</inf>e ∏} will decrease exponentially fast with a well defined limiting rate as n →∞ along multiples of d(∏). The exponential decay rate is equal to the minimum information divergence rate of empirical types in ∏ relative to the reference measure M. © 1992 IEEE