  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.5 \log (n/k^3)$ bits,
where $n$ is the coded sequence length, as long as $k = o(n^{1/3})$. Otherwise,
for $k = O(n)$, the total average sequence redundancy is $O(n^{1/3+\epsilon})$
bits overall. We then show that there exists a sub-class of monotonic
distributions over infinite alphabets for which redundancy of
$O(n^{1/3+\epsilon})$ bits overall is still achievable. This class contains
fast decaying distributions, including many distributions over the integers and
geometric distributions. For some slower decays, including other distributions
over the integers, redundancy of $o(n)$ bits overall is achievable, where a
method to compute specific redundancy rates for such distributions is derived.
The results are specifically true for finite entropy monotonic distributions.
Finally, we study individual sequence redundancy behavior assuming a sequence
is governed by a monotonic distribution. We show that for sequences whose
empirical distributions are monotonic, individual redundancy bounds similar to
those in the average case can be obtained. However, even if the monotonicity in
the empirical distribution is violated, diminishing per symbol individual
sequence redundancies with respect to the monotonic maximum likelihood
description length may still be achievable.
