Lossless compression with moderate error probability

For the problem of lossless compression of a memoryless source, we give a detailed, precise characterization of the best achievable error probability, in the 'moderate error probability' regime. This is the asymptotic setting where the probability of error decays to zero while at the same time the rate converges to the entropy at a speed no faster than 1/√N. These results combine some of the essential benefits of earlier analyses in terms of error exponents and of Gaussian approximation. Analogous results for the problem of hypothesis testing are also established. © 2013 IEEE