2018/09/19 by Hosseini, Maryam, Santhanam, Narayana
#68P30 #94A15 #E.4 #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1809.07005
We formalize the tail redundancy of a collection of distributions over a countably infinite alphabet, and show that this fundamental quantity characterizes the asymptotic per-symbol redundancy of universally compressing sequences generated iid from a collection \mathcal P of distributions over a countably infinite alphabet. Contrary to the worst case formulations of universal compression, finite single letter (average case) redundancy of \mathcal P does not automatically imply that the expected redundancy of describing length-n strings sampled iid from \mathcal P grows sublinearly with n. Instead, we prove that universal compression of length-n \iid sequences from \mathcal P is characterized by how well the tails of distributions in \mathcal P can be universally described, showing that the asymptotic per-symbol redundancy of iid strings is equal to the tail redundancy.