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

Let\{X_{n}\} n \geq 1be 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\{X_{n}\}is obtained. These results generalize the corresponding results for the independent and identically distributed case.