Universal Source Coding for Monotonic and Fast Decaying Monotonic Distributions
Universal Source Coding for Monotonic and Fast Decaying Monotonic Distributions
We study universal compression of sequences generated by monotonic distributions. We show that for a monotonic distribution over an alphabet of size k, each probability parameter costs essentially 0.5log(n/k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) bits, where n is the coded sequence length, as long as k=o(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/3</sup> ). Otherwise, …