Large deviations, hypotheses testing, and source coding for finite Markov chains

Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\{Xₙ\} n ≥ 1</tex> be a finite Markov chain with transition probability matrix of strictly positive entries. A large deviation theorem is proved for the empirical transition count matrix and is used to get asymptotically optimal critical regions for testing simple hypotheses about the transition matrix. As a corollary, the error exponent in the source coding theorem for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\{Xₙ\}</tex> is obtained. These results generalize the corresponding results for the independent and identically distributed case.