Tail redundancy and its characterization of compression of memoryless sources
share
We obtain a single-letter characterization that is both necessary and sufficient for sequences generated from a collection of distributions over a countably infinite alphabet to be (average-case) strongly compressible. Contrary to the worst case formulation of universal compression, finite single letter (average case) redundancy of does not automatically imply that the expected redundancy of describing length-n strings sampled from grows sublinearly with n. Instead, we prove that universal compression of length-n sequences from is characterized by how well the tails of distributions in can be universally described, and we formalize the later as the tail-redundancy of .
READ FULL TEXT