Tail redundancy and its characterization of compression of memoryless sources

Abstract

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.