Universal Quadratic Lower Bounds on Error Exponents (UL-BEE)
Cheng Chang and Anant Sahai
We consider the problem of block-size selection to achieve a desired probability of error for universal source coding with and without decoder side information. Previously, this question was studied in  for rates in the vicinity of entropy for known distributions using central-limit-theorem techniques. We are interested in all rates for unknown distributions and use error-exponent techniques. By adapting a technique of Gallager from the exercises of , we derive a universal lower bound to the source-coding error exponent that depends only on the alphabet size and is quadratic in the gap to entropy. Then the block-size selection problem can be solved as a natural. These results all agree with the previous central limit result in order. This shows that the large deviation principal can be used in the vicinity of a central limit if used properly.
- D. Baron, M. A. Khojastepour, and R. G. Baraniuk, "Redundancy Rates of Slepian-Wolf Coding," 42nd Allerton Conference, 2004.
- R. G. Gallager, Information Theory and Reliable Communication, John Wiley, New York, NY, 1971.