Efficient compression of monotone and m-modal distributions
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh · 2014
We consider universal compression of n samples drawn independently according to a monotone or m-modal distribution over k elements. We show that for all these distributions, the per-sample redundancy diminishes to 0 if k = exp(o(n/log n)) and is at least a constant if k = exp(Ω(n)).