A LARGE DEVIATIONS APPROACH TO ERROR EXPONENTS IN SOURCE-CODING AND HYPOTHESIS-TESTING

The usual approach to finding the error exponents in binary hypothesis testing and in source coding for finite Markov chains involves combinatorial “type-counting” arguments. The purpose of this correspondence is to point out that the basic results can be proved fairly easily if one uses a Sanov theorem for the distribution of types. Such a theorem comes easily from large deviations theory. A caveat is that this technique only identifies the error exponent up to terms of order o(n) in the exponent, whereas the combinatorial arguments give an estimate up to terms of order O(log n) in the exponent. © 1990 IEEE