We formalize the tail redundancy of a collection ${\mathcal{ P}}$ of distributions over a countably infinite alphabet, and show that this fundamental quantity characterizes the asymptotic per-symbol minimax redundancy of universally compressing sequences generated i.i.d. from ${\mathcal{ P}}$ . Contrary to the worst case formulations of universal compression, finite single letter minimax (average case) redundancy of ${\mathcal{ P}}$ does not automatically imply that the expected minimax redundancy of describing length- $n$ strings sampled i.i.d. from ${\mathcal{ P}}$ grows sublinearly with $n$ . Instead, we prove that universal compression of length- $n$ i.i.d. 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 i.i.d. strings is equal to the tail redundancy.
