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

Let 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 is obtained. These results generalize the corresponding results for the independent and identically distributed case.