Universal Source Coding for Monotonic and Fast Decaying Monotonic
  Distributions
Universal Source Coding for Monotonic and Fast Decaying
Monotonic Distributions∗
Gil I. Shamir
Department of Electrical and Computer Engineering
University of Utah
Salt Lake City, UT 84112, U.S.A
e-mail: gshamir@ece.utah.edu.
Abstract
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/k3) bits, where n is the coded sequence length, as long as k = o(n1/3).
Otherwise, for k = O(n), the total average sequence redundancy is O(n1/3+ε) bits overall. We
then show that there exists a sub-class of monotonic distributions over infinite alphabets for
which redundancy of O(n1/3+ε) 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.
Index Terms: monotonic distributions, universal compression, average redundancy, indi-
vidual redundancy, large alphabets, patterns.
∗Supported by NSF Grant CCF-0347969. Part of the material in this manuscript was accepted for presentation
in the IEEE International Symposium on Information Theory, Nice, France, June, 2007.
http://arxiv.org/abs/0704.0838v1
1 Introduction
The classical setting of the universal lossless compression problem [5], [8], [9] assumes that a se-
quence xn of length n that was generated by a source θ is to be compressed without knowledge
of the particular θ that generated xn but with knowledge of the class Λ of all possible sources θ.
The average performance of any given code, that assigns a length function L(·), is judged on the
basis of the redundancy function Rn (L,θ), which is defined as the difference between the expected
code length of L (·) with respect to (w.r.t.) the given source probability mass function Pθ and the
nth-order entropy of Pθ normalized by the length n of the uncoded sequence. A class of sources
is said to be universally compressible in some worst sense if the redundancy function diminishes
for this worst setting. Another approach to universal coding [29] considers the individual sequence
redundancy R̂n (L, x
n), defined as the normalized difference between the code length obtained by
L(·) for xn and the negative logarithm of the maximum likelihood (ML) probability of the sequence
xn, where the ML probability is within the class Λ. We thereafter refer to this negative logarithm as
the ML description length of xn. The individual sequence redundancy is defined for each sequence
that can be generated by a source θ in the given class Λ.
Classical literature on universal compression [5], [8], [9], [23], [29] considered compression of
sequences generated by sources over finite alphabets. In fact, it was shown by Kieffer [15] (see also
[13]) that there are no universal codes (in the sense of diminishing redundancy) for sources over
infinite alphabets. Later work (see, e.g., [21], [25]), however, bounded the achievable redundancies
for identically and independently distributed (i.i.d.) sequences generated by sources over large and
infinite alphabets. Specifically, while it was shown that the redundancy does not decay if the
alphabet size is of the same order of magnitude as the sequence length n or greater, it was also
shown that the redundancy does decay for alphabets of size o(n). 1
While there is no universal code for infinite alphabets, recent work [20] demonstrated that if
one considers the pattern of a sequence instead of the sequence itself, universal codes do exist in
the sense of diminishing redundancy. A pattern of a sequence, first considered, to the best of our
knowledge, in [1], is a sequence of indices, where the index ψi at time i represents the order of first
occurrence of letter xi in the sequence x
n. Further study of universal compression of patterns [20],
[21], [26], [28] provided various lower and upper bounds to various forms of redundancy in universal
1For two functions f(n) and g(n), f(n) = o(g(n)) if ∀c,∃n0, such that, ∀n > n0, f(n) < cg(n); f(n) = O(g(n))
if ∃c, n0, such that, ∀n > n0, 0 ≤ f(n) ≤ cg(n); f(n) = Θ(g(n)) if ∃c1, c2, n0, such that, ∀n > n0, c1g(n) ≤ f(n) ≤
c2g(n).
compression of patterns. Another related study is that of compression of data, where the order of
the occurring data symbols is not important, but their types and empirical counts are [30]-[31].
This paper considers universal compression of data sequences generated by distributions that
are known a-priori to be monotonic. Hence, the order of probabilities of the source symbols is
known in advance to both encoder and decoder and can be utilized as side information to improve
universal compression performance. Monotonic distributions are common for distributions over
the integers, including the geometric distribution and others. Such distributions do occur in image
compression problems (see, e.g., [18], [19]), and in other applications that compress residual signals.
A specific application one can consider for the results in this paper is compression of the list of
last or first names in a given city of a given population. One can usually find some monotonicity
for such a distribution in the given population, which both encoder and decoder may be aware of
a-priori . For example, the last name “Smith” can be expected to be much more common than
the last name “Shannon”. Another example is the compression of a sequence of observations of
different species, where one has prior knowledge which species are more common, and which are
rare. Finally, one can consider compressing data for which side information given to the decoder
through a different channel gives the monotonicity order.
Unlike compression of patterns, Foster, Stine, and Wyner, showed in [10] that there are no
universal block codes in the standard sense for the complete class of monotonic distributions. The
main reason is that there exist such distributions, for which much of the statistical weight lies in
symbols that have very low probability, and most of which will not occur in a given sequence.
Thus, in practice, even though one has the prior knowledge of the monotonicity of the distribution,
this monotonicity is not necessarily retained in an observed sequence. Therefore, actual coding
can be very similar to compressing with infinite alphabets, and the additional prior knowledge
of the monotonicity is not very helpful in reducing redundancy. Despite that, Foster, Stine, and
Wyner demonstrated codes that obtained universal per-symbol redundancy of o(1) as long as the
source entropy is fixed (i.e., neither increasing with n nor infinite). However, instead of considering
redundancy in the standard sense, the study of monotonic distributions resorted to studying relative
redundancy , which bounds the ratio between average assigned code length and the source entropy.
This approach dates back to work by Elias [7], Rissanen [22], and Ryabko [24].
The work in [10] studied coding sequences (or blocks) generated by i.i.d. monotonic distributions,
and designed codes for which the relative block redundancy could be (upper) bounded. Unlike that
work, the focus in [7], [22], and [24] was on designing codes that minimize the redundancy or
relative redundancy for a single symbol generated by a monotonic distribution. Specifically, in
[22], minimax codes, which minimize the relative redundancy for the worst possible monotonic
distribution over a given alphabet size, were derived. In [24], it was shown that redundancy of
O(log log k), where k is the alphabet size, can be obtained with minimax per-symbol codes. Very
recent work [16] considered per-symbol codes that minimize an average redundancy over the class
of monotonic distributions for a given alphabet size. Unlike [10], all these papers study per-symbol
codes. Therefore, the codes designed always pay non-diminishing per-symbol redundancy.
A different line of work on monotonic distributions considered optimizing codes for a known
monotonic distribution but with unknown parameters (see [18], [19] for design of codes for two-sided
geometric distributions). In this line of work, the class of sources is very limited and consists of
only the unknown parameters of a known distribution.
In this paper, we consider a general class of monotonic distributions that is not restricted
to a specific type. We study standard block redundancy for coding sequences generated by i.i.d.
monotonic distributions, i.e., a setting similar to the work in [10]. We do, however, restrict ourselves
to smaller subsets of the complete class of monotonic distributions. First, we consider monotonic
distributions over alphabets of size k, where k is either small w.r.t. n, or of O(n). Then, we extend
the analysis to show that under minimal restrictions of the monotonic distribution class, there exist
universal codes in the standard sense, i.e., with diminishing per-symbol redundancy. In fact, not
only do universal codes exist, but under mild restrictions, they achieve the same redundancy as
obtained for alphabets of size O(n). The restrictions on this subclass imply that some types of fast
decaying monotonic distributions are included in it, and therefore, sequences generated by these
distributions (without prior knowledge of either the distribution or of its parameters) can still be
compressed universally in the class of monotonic distributions.
The main contributions of this paper are the development of codes and derivation of their
upper bounds on the redundancies for coding i.i.d. sequences generated by monotonic distributions.
Specifically, the paper gives complete characterization of the redundancy in coding with monotonic
distributions over “small” alphabets (k = o(n1/3)) and “large” alphabets (k = O(n)). Then, it
shows that these redundancy bounds carry over (in first order) to fast decaying distributions. Next,
a code that achieves good redundancy rates for even slower decaying monotonic distributions is
derived, and is used to study achievable redundancy rates for such distributions. Lower bounds are
also presented to complete the characterization, and are shown to meet the upper bounds in the first
three cases (small alphabets, large alphabets, and fast decaying distributions). The lower bounds
turn out to result from lower bounds obtained for coding patterns. The relationship to patterns is
demonstrated in the proofs of those lower bounds. Finally, individual sequences are considered. It is
shown that under mild conditions, there exist universal codes w.r.t. the monotonic ML description
length for sequences that contain the O(n) more likely symbols, even if their empirical distributions
are not monotonic.
The outline of this paper is as follows. Section 2 describes the notation and basic definitions.
Then, in section 3, lower bounds on the redundancy for monotonic distributions are derived. Next,
in Section 4, we propose codes and upper bound their redundancy for coding monotonic distribu-
tions over small and large alphabets. These bounds are then extended to fast decaying monotonic
distributions in Section 5. Finally, in Section 6, we consider individual sequence redundancy.
2 Notation and Definitions
Let xn
= (x1, x2, . . . , xn) denote a sequence of n symbols over the alphabet Σ of size k, where k
can go to infinity. Without loss of generality, we assume that Σ = {1, 2, . . . , k}, i.e., it is the set of
positive integers from 1 to k. The sequence xn is generated by an i.i.d. distribution of some source,
determined by the parameter vector θ
= (θ1, θ2, . . . , θk), where θi is the probability of X taking
value i. The components of θ are non-negative and sum to 1. The distributions we consider in
this paper are monotonic. Therefore, θ1 ≥ θ2 ≥ . . . ≥ θk. The class of all monotonic distributions
will be denoted by M. The class of monotonic distributions over an alphabet of size k is denoted
by Mk. It is assumed that prior to coding xn both encoder and decoder know that θ ∈ M or
θ ∈ Mk, and also know the order of the probabilities in θ. In the more restrictive setting, k is
known in advance and it is known that θ ∈ Mk. We do not restrict ourselves to this setting. In
general, boldface letters will denote vectors, whose components will be denoted by their indices in
the vector. Capital letters will denote random variables. We will denote an estimator by the hat
sign. In particular, θ̂ will denote the ML estimator of θ which is obtained from xn.
The probability of xn generated by θ is given by Pθ (x
= Pr (xn | Θ = θ). The average
per-symbol2 nth-order redundancy obtained by a code that assigns length function L(·) for θ is
Rn (L,θ)
EθL [X
n]−Hθ [X] , (1)
where Eθ denotes expectation w.r.t. θ, and Hθ [X] is the (per-symbol) entropy (rate) of the source
2In this paper, redundancy is defined per-symbol (normalized by the sequence length n). However, when we refer
to redundancy in overall bits, we address the block redundancy cost for a sequence.
(Hθ [X
n] is the nth-order sequence entropy of θ, and for i.i.d. sources, Hθ [X
n] = nHθ [X]). With
entropy coding techniques, assigning a universal probability Q (xn) is identical to designing a uni-
versal code for coding xn where, up to negligible integer length constraints that will be ignored,
the negative logarithm to the base of 2 of the assigned probability is considered as the code length.
The individual sequence redundancy (see, e.g., [29]) of a code with length function L (·) per
sequence xn is
R̂n (L, x
{L (xn) + log PML (xn)} , (2)
where the logarithm function is taken to the base of 2, here and elsewhere, and PML (x
n) is the
probability of xn given by the ML estimator θ̂Λ ∈ Λ of the governing parameter vector Θ. The
negative logarithm of this probability is, up to integer length constraints, the shortest possible
code length assigned to xn in Λ. It will be referred to as the ML description length of xn in Λ.
In the general case, one considers the i.i.d. ML. However, since we only consider θ ∈ M, i.e.,
restrict the sequence to one governed by a monotonic distribution, we define θ̂M ∈ M as the
monotonic ML estimator. Its associated shortest code length will be referred to as the monotonic
ML description length. The estimator θ̂M may differ from the i.i.d. ML θ̂, in particular, if the
empirical distribution of xn is not monotonic. The individual sequence redundancy in M is thus
defined w.r.t. the monotonic ML description length, which is the negative logarithm of PML (x
xn | Θ = θ̂M ∈ M
The average minimax redundancy of some class Λ is defined as
R+n (Λ)
= min
Rn (L,θ) . (3)
Similarly, the individual minimax redundancy is that of the best code L (·) for the worst sequence
R̂+n (Λ)
= min
{L (xn) + logPθ (xn)} . (4)
The maximin redundancy of Λ is
R−n (Λ)
= sup
w (dθ)Rn (L,θ) , (5)
where w(·) is a prior on Λ. In [5], it was shown that R+n (Λ) ≥ R−n (Λ). Later, however, [6], [11],
[24] the two were shown to be essentially equal.
3 Lower Bounds
Lower bounds on various forms of the redundancy for the class of monotonic distributions can be
obtained with slight modifications of the proofs for the lower bounds on the redundancy of coding
patterns in [14], [20], [21], and [26]. The bounds are presented in the following three theorems. For
the sake of completeness, the main steps of the proofs of the first two theorems are presented in
appendices, and the proof of the third theorem is presented below. The reader is referred to [14],
[20], [21], [25] and [26] for more details.
Theorem 1 Fix an arbitrarily small ε > 0, and let n → ∞. Then, the nth-order average max-
imin and minimax universal coding redundancies for i.i.d. sequences generated by a monotonic
distribution with alphabet size k are lower bounded by
R−n (Mk) ≥
log n
+ k−1
log πe
log k
, for k ≤
πn1−ε
)1/3 · (1.5 log e) · n(1−ε)/3
, for k >
πn1−ε
)1/3 . (6)
Theorem 2 Fix an arbitrarily small ε > 0, and let n→ ∞. Then, the nth-order average universal
coding redundancy for coding i.i.d. sequences generated by monotonic distributions with alphabet
size k is lower bounded by
Rn (L,θ) ≥
log n
− k−1
log 8π
log k
, for k ≤ 1
1.5 log e
2π1/3
· n(1−ε)/3
, for k > 1
)1/3 (7)
for every code L(·) and almost every i.i.d. source θ ∈ Mk, except for a set of sources Aε (n) whose
relative volume in Mk goes to 0 as n→ ∞.
Theorems 1 and 2 give lower bounds on redundancies of coding over monotonic distributions
for the class Mk. However, the bounds are more general, and the second region applies to the
whole class of monotonic distributions M. As in the case of patterns [20], [26], the bounds in
(6)-(7) show that each parameter costs at least 0.5 log(n/k3) bits for small alphabets, and the total
universality cost is at least Θ(n1/3−ε) bits overall for larger alphabets. Unlike the currently known
results on patterns, however, we show in Section 4 that for k = O(n) these bounds are achievable
for monotonic distributions. The proofs of Theorems 1 and 2 are presented in Appendix A and in
Appendix B, respectively.
Theorem 3 Let n → ∞. Then, the nth-order individual minimax redundancy for i.i.d. sequences
with maximal letter k w.r.t. the monotonic ML description length with alphabet size k is lower
bounded by
R̂+n (Mk) ≥
log n
log e
23/12
log k
, for k ≤ e5/18
(2π)1/3
· n1/3
e5/18
(2π)1/3
(log e) · n1/3
, for n > k > e
(2π)1/3
· n1/3
(log e) · n1/3
, for k ≥ n.
Theorem 3 lower bounds the individual minimax redundancy for coding a sequence believed
to have an empirical monotonic distribution. The alphabet size is determined by the maximal
letter that occurs in the sequence, i.e., k = max {x1, x2, . . . , xn}. (If k is unknown, one can use
Elias’ code for the integers [7] using O(log k) bits to describe k. However this is not reflected in
the lower bound.) The ML probability estimate is taken over the class of monotonic distributions,
i.e., the empirical probability (standard ML) estimate θ̂ is not θ̂M in case θ̂ does not satisfy the
monotonicity that defines the class M. While the average case maximin and minimax bounds
of Theorem 1 also apply to R̂+n (Mk), the bounds of Theorem 3 are tighter for the individual
redundancy and are obtained using individual sequence redundancy techniques.
Proof of Theorem 3: Using Shtarkov’s normalized maximum likelihood (NML) approach [29],
one can assign probability
Q (xn)
yn Pθ̂M
maxθ′∈M Pθ′ (x
yn maxθ′∈M Pθ′ (y
to sequence xn. This approach minimizes the individual minimax redundancy, giving individual
redundancy of
R̂n (Q,x
maxθ′∈M Pθ′ (x
Q (xn)
Pθ′ (y
to every xn, specifically achieving the individual minimax redundancy.
It is now left to bound the logarithm of the sum in (10). For the first two regions, we follow
the approach used in Theorem 2 in [21] for bounding the redundancy for standard compression
of i.i.d. sequences over large alphabets, but adjust it to monotonic distributions. Alternatively,
one can derive the same bounds following the approach used for bounding the individual minimax
redundancy of patterns in proving Theorem 12 in [20]. Let nℓx
= (nx(1), nx(2), . . . , nx(ℓ)) denote
the occurrence counts of the first ℓ letters of the alphabet Σ in xn. For ℓ = k,
i=1 nx(i) = n.
Now, following (10),
nR̂+n (Mk)
≥ log
yn:θ̂(yn)∈M
≥ log
ny(1), . . . , ny(ℓ)
ny(i)
)ny(i)
≥ log
ny(1), . . . , ny(k)
ny(i)
)ny(i)
≥ log
ek/12 · (2π)k/2
nx(i)
≥ log
k − 1
ek/12
≥ k − 1
+ k log
e23/12√
−O (log k) (11)
where (a) follows from including only sequences yn that have a monotonic empirical (i.i.d. ML)
distribution in Shtarkov’s sum. Inequality (b) follows from partitioning the sequences yn into types
as done in [21], first by the number of occurring symbols ℓ, and then by the empirical distribution.
Unlike standard i.i.d. distributions though, monotonicity implies that only the first ℓ symbols in Σ
occur, and thus the choice of ℓ out of k in the proof in [21] is replaced by 1. Like in coding patterns,
we also divide by ℓ! because each type with ℓ occurring symbols can be ordered in at most ℓ! ways,
where only some retain the monotonicity. (Note that this step is the reason that step (b) produces
an inequality, because more than one of the orderings may be monotonic if equal occurrence counts
occur.) Except the division by ℓ!, the remaining steps follow those in [21]. Retaining only the term
ℓ = k yields inequality (c). Inequality (d) follows from Stirling’s bound
2πm ·
≤ m! ≤
2πm ·
· exp
. (12)
Then, (e) follows from the relation between arithmetic and geometric means, and from expressing
the number of types as the number of ordered partitions of n into k parts
k − 1
. Finally, (f)
follows from applying (12) again and by lower bounding
k − 1
The first region in (8) results directly from (11). The behavior is similar to patterns as shown
in [1] for this region. As mentioned in [20], to obtain the second region, the bound is maximized
by retaining ℓ̂ =
n1/3e5/18
/(2π)1/3 instead of k in step (c) of (11), for every k ≥ ℓ̂. The bounds
obtained are equal to those obtained for patterns because the first step (a) in (11) discards all
the sequences whose contributions to Shtarkov’s sum are different between patterns and monotonic
distributions. A similar step is effectively done deriving the bounds for patterns. The difference
is that in the case of patterns, components of Shtarkov’s sum are reduced, but all are retained
in the sum, while here, we omit components from the sum, corresponding to sequences with non-
monotonic i.i.d. ML estimates. The analysis in [20] that also attains the second region of the
bound in (8) is still valid here. It differs from the steps taken above by lower bounding a pattern
probability by a larger probability than the ML i.i.d. probability corresponding to the pattern. The
bound used in the derivation of Theorem 12 in [20] adds a multiplicative factor to each pattern
probability which equals the number of sequences with the same pattern and an equal i.i.d. ML
probability. However, this similar effect is included in Shtarkov’s sum for monotonic distributions
since all these sequences do have a corresponding i.i.d. ML estimate which is monotonic, and are
thus not omitted by step (a) of the derivation.
The analysis in [14] yields the third region of the bound in (8), since, for k ≥ n,
R̂+n (Mk) =
Ψ(yn)
1.5n1/3 log e
log n
, (13)
where Ψ(yn) is the pattern of the sequence yn. Inequality (a) holds because each pattern cor-
responds to at least one sequence whose ML probability parameter estimates are ordered, i.e.,
θ̂i ≥ θ̂i+1,∀i, where the most probable index represents i = 1, the second most probable index
i = 2, and so on. Note that the sum element on the right hand side is for a probability of a
sequence, not a pattern, but the sum is over all patterns. The left hand side also includes sequences
for which the probabilities are unordered. Furthermore, exchanging the letters that correspond
to two indices with the same occurrence count will not violate monotonicity. Thus the inequality
follows. Step (b) in (13) is taken from [14], where the sum on the left hand side was shown to
equal the right hand side. This was true when summing over all patterns with up to n indices, thus
requiring k ≥ n. Note that this requirement does not mean that n distinct symbols must occur
in xn, only that the maximal symbol in xn is n or greater. This concludes the proof of Theorem 3. �
4 Upper Bounds for Small and Large Alphabets
In this section, we demonstrate codes that asymptotically achieve the lower bounds for θ ∈ Mk
and k = O(n). We begin with a theorem that shows the achievable redundancies, and devote the
remainder of the section to describing the codes and deriving upper bounds on their redundancies.
The theorem is stated assuming no initial knowledge of k. The proof first considers the setting
where k is known, and then shows how the same bounds are achieved even when k is unknown in
advance, but as long as it satisfies the conditions.
Theorem 4 Fix an arbitrarily small ε > 0, and let n → ∞. Then, there exist a code with length
function L∗ (·) that achieves redundancy
Rn (L
∗,θ) ≤
(1 + ε) k−1
n(logn)2
, for k ≤ n1/3,
(1 + ε) (log n)
log k
n1/3−ε
, for n1/3 < k = o(n),
(1 + ε) 2
(log n)
2 n1/3
, for n1/3 < k = O(n),
for i.i.d. sequences generated by any source θ ∈ Mk.
Slightly tighter bounds are possible in the first and second regions and between them. The
bounds presented, however, are inclusive for each of the regions. Note that the third region con-
tains the second, but if k = o(n), a tighter bound is possible in the second region. The code
designed to code a sequence xn is a two part code [23] that quantizes a distribution that minimizes
the cost, and uses it to code xn. The total redundancy cost consists of the cost of describing the
quantized distribution and the quantization cost. The second is bounded through the quantized
true distribution of the sequence, which cannot result in lower cost than that of the chosen dis-
tribution (which minimizes the cost). In order to achieve the low costs of the lower bound, the
probability parameters are quantized non-uniformly, where the smaller the probability the finer the
quantization. This approach was used in [25] and [26] to obtain upper bounds on the redundancy
for coding over large alphabets and for coding patterns, respectively. The method used in [25] and
[26], however, is insufficient here, because it still results in too many quantization points due to the
polynomial growth in quantization spacing. Here, we use an exponential growth as the parameters
increase. This general idea was used in [28] to improve an upper bound on the redundancy of
coding patterns. Here, however, we improve on the method presented in [28]. Another key step in
the proof here is the fact that since both encoder and decoder know the order of the probabilities
a-priori , this order need not be coded. It is sufficient to encode the quantized probabilities of the
monotonic distribution, and the decoder can identify which probability is associated with which
symbol using the monotonicity of the distribution.
Proof of Theorem 4: We start with k ≤ n1/3 assuming k is known. Let β = 1/(log n) be a
parameter (note, that we can choose other values). Partition the probability space into J1 = ⌈1/β⌉
intervals,
n(j−1)β
, 1 ≤ j ≤ J1. (15)
Note that I1 = [1/n, 2/n), I2 = [2/n, 4/n), . . . , Ij = [2
j−1/n, 2j/n). Let kj = |θi ∈ Ij| denote the
number of probabilities in θ that are in interval Ij. In interval j, take a grid of points with spacing
. (16)
Note that to complete all points in an interval, the spacing between two points at the boundary of an
interval may be smaller. There are ⌈log n⌉ intervals. Ignoring negligible integer length constraints
(here and elsewhere), in each interval, the number of points is bounded by
|Ij | ≤
, ∀j : j = 1, 2, . . . , J1, (17)
where | · | denotes the cardinality of a set. Let the grid
τ = (τ1, τ2, . . .) =
, . . . ,
, . . .
be a vector that takes all the points from all intervals, with cardinality
= |τ | ≤ 1
⌈log n⌉ . (19)
Now, let ϕ = (ϕ1, ϕ2, . . . , ϕk) be a monotonic probability vector, such that
ϕi = 1, ϕ1 ≥
ϕ2 ≥ · · · ≥ ϕk ≥ 0, and also the smaller k−1 components of ϕ are either 0 or from τ , i.e., ϕi ∈ (τ ∪
{0}), i = 2, 3, . . . , k. One can code xn using a two part code, assuming the distribution governing
xn is given by the parameter ϕ. The code length required (up to integer length constraints) is
L (xn|ϕ) = log k + LR(ϕ)− log Pϕ (xn) , (20)
where log k bits are needed to describe how many letter probabilities are greater than 0 in ϕ, and
LR(ϕ) is the number of bits required to describe the quantized points of ϕ.
The vector ϕ can be described by a code as follows. Let k̂ϕ be the number of nonzero letter
probabilities hypothesized by ϕ. Let bi denote the index of ϕi in τ , i.e., ϕi = τbi . Then, we
will use the following differential code. For ϕ
we need at most 1 + log b
+ 2 log(1 + log b
bits to code its index in τ using Elias’ coding for the integers [7]. For ϕi−1, we need at most
1 + log(bi−1 − bi + 1) + 2 log[1 + log(bi−1 − bi + 1)] bits to code the index displacement from the
index of the previous parameter, where an additional 1 is added to the difference in case the two
parameters share the same index. Summing up all components of ϕ, and taking b
k̂ϕ+1
LR(ϕ) ≤ k̂ϕ − 1 +
log (bi − bi+1 + 1) + 2
log [1 + log (bi − bi+1 + 1)]
≤ (k − 1) + (k − 1) log B1 + k − 1
+ 2(k − 1) log log B1 + k − 1
+ o(k)
= (1 + ε)
k − 1
n (log n)
. (21)
Inequality (a) is obtained by applying Jensen’s inequality once on the first sum, twice on the second
sum utilizing the monotonicity of the logarithm function, and by bounding k̂ϕ by k and absorbing
low order terms in the resulting o(k) term. Then, low order terms are absorbed in ε, and (19) is
used to obtain (b).
To code xn, we choose ϕ which minimizes the expression in (20) over all ϕ, i.e.,
L∗ (xn) = min
L (xn|ϕ) △= L (xn|ϕ̂) . (22)
The pointwise redundancy for xn is given by
nRn (L
∗, xn) = L∗ (xn) + log Pθ (x
n) = log k + L∗R (ϕ̂) + log
Pθ (x
Pϕ̂ (x
. (23)
Note that the pointwise redundancy differs from the individual one, since it is defined w.r.t. the
true probability of xn.
To bound the third term of (23), let θ′ be a quantized still monotonic version of θ onto τ , i.e.,
θ′i ∈ (τ ∪ {0}), i = 2, 3, . . . , k, where if θi > 0 ⇔ θ′i > 0 as well. Define the quantization error,
δi = θi − θ′i. (24)
The quantization is performed from the smallest parameter θk to the largest, where monotonicity
is retained, as well as minimal absolute quantization error. This implies that θi will be quantized
to one of the two nearest grid points (one smaller and one greater than it). It also guarantees that
|δ1| ≤ ∆
, where j2 is the index of the interval in which θ2 is contained, i.e., θ2 ∈ Ij2 . Now, since
θ′ is included in the minimization of (22), we have, for every xn,
L∗ (xn) ≤ L
xn|θ′
, (25)
and also
nRn (L
∗, xn) ≤ log k + LR
+ log
Pθ (x
Pθ′ (x
. (26)
Averaging over all possible xn, the average redundancy is bounded by
nRn (L
∗,θ) = log k + EθL
R (ϕ̂) + Eθ log
Pθ (X
Pϕ̂ (X
≤ log k + EθLR
′)+ Eθ log
Pθ (X
Pθ′ (X
. (27)
The second term of (27) is bounded with the bound of (21), and we proceed with the third term.
Eθ log
Pθ (X
Pθ′ (X
θi log
θ′i + δi
≤ n(log e)
θ′i + δi
= n(log e)
≤ k log e+ 2(log e)k
kj · njβ
≤ 5(log e)k. (28)
Equality (a) is since the argument in the logarithm is fixed, thus expectation is performed only on
the number of occurrences of letter i for each letter. Representing θi = θ
i + δi yields equation (b).
We use ln(1+x) ≤ x to obtain (c). Equality (d) is obtained since all the quantization displacements
must sum to 0. The first term of inequality (e) is obtained under a worst case assumption that
θi ≪ 1/n for i ≥ 2. Thus it is quantized to θ′i = 1/n, and the bound |δi| ≤ 1/n is used. The
second term is obtained by separating the terms into their intervals. In interval j, the bounds
θ′i ≥ n(j−1)β/n, and |δi| ≤
knjβ/n1.5 are used, and also nβ = 2. Inequality (f) is obtained since
j ≤ 2n. (29)
Inequality (29) is obtained since k1 ≤ n, k2 ≤ (n− k1)/2, k3 ≤ (n− k1)/4− k2/2, and so on, until
kJ1 ≤
2J1−1
2J1−ℓ
j ≤ 2n. (30)
The reason for these relations are the lower limits of the J1 intervals that restrict the number
of parameters inside the interval. The restriction is done in order of intervals, so that the used
probabilities are subtracted, leading to the series of equations.
Plugging the bounds of (21) and (28) into (27), we obtain,
nRn (L
∗,θ) ≤ log k + (1 + ε) k − 1
n (log n)
+ 5(log e)k
1 + ε′
) k − 1
n (log n)
, (31)
where we absorb low order terms in ε′. Replacing ε′ by ε normalizing the redundancy per symbol
by n, the bound of the first region of (14) is proved.
We now consider the larger values of k, i.e., n1/3 < k = O(n). The idea of the proof is the
same. However, we need to partition the probability space to different intervals, the spacing within
an interval must be optimized, and the parameters’ description cost must be bounded differently,
because now there are more parameters quantized than points in the quantization grid. Define the
jth interval as
n(j−1)β
, 1 ≤ j ≤ J2, (32)
where J2 = ⌈2/β⌉ = ⌈2 log n⌉. Again, let kj = |θi ∈ Ij| denote the number of probabilities in θ that
are in interval Ij. It could be possible to use the intervals as defined in (15), but this would not
guarantee bounded redundancy in the rate we require if there are very small probabilities θi ≪ 1/n.
Therefore, the interval definition in (15) can be used for larger alphabets only if the probabilities
of the symbols are known to be bounded. Define the spacing in interval j as
, (33)
where α is a parameter to be optimized. Similarly to (17), the interval cardinality here is
|Ij| ≤ 0.5 · nα, ∀j : j = 1, 2, . . . , J2, (34)
In a similar manner to the definition of τ in (18), we define
η = (η1, η2, . . .) =
, . . . ,
, . . .
. (35)
The cardinality of η is
= |η| ≤ 0.5 · nα ⌈2 log n⌉ ≤ nα ⌈log n⌉ . (36)
We now perform the encoding similarly to the small k case, where we allow quantization to
nonzero values to the components of ϕ up to i = n2. (This is more than needed but is possible
since η1 = 1/n
2.) Encoding is performed similarly to the small k case. Thus, similarly to (27), we
nRn (L
∗,θ) ≤ 2 log n+ EθLR
′)+ Eθ log
Pθ (X
Pθ′ (X
, (37)
where the first term is due to allowing up to k̂ = n2. Since usually in this region k ≥ B2 (except
the low end), the description of vectors ϕ and θ′ is done by coding the cardinality of |ϕi = ηj | and
|θ′i = ηj |, respectively, i.e., for each grid point the code describes how many letters have probability
quantized to this point. This idea resembles coding profiles of patterns, as done in [20]. However,
unlike the method in [20], here, many probability parameters of symbols with different occurrences
are mapped to the same grid point by quantization. The number of parameters mapped to a grid
point of η is coded using Elias’ representation of the integers. Hence, in a similar manner to (21),
1 + log
|θ′i = ηj |+ 1
+ 2 log
1 + log
|θ′i = ηj |+ 1
≤ B2 +B2 log
k +B2
+ 2B2 log log
k +B2
+ o (B2)
(1 + ε)(log n)
log k
nα, for nα < k = o(n),
(1 + ε)(1 − α) (log n)2 nα, for nα < k = O(n).
The additional 1 term in the logarithm in (a) is for 0 occurrences, (b) is obtained similarly to step
(a) of (21), absorbing all low order terms in the last term. To obtain (c), we first assume, for the
first region, that knε ≫ B2 (an assumption that must be later validated with the choice of α).
Then, low order terms are absorbed in ε. The extra nε factor is unnecessary if k ≫ B2. The second
region is obtained by upper bounding k without this factor. It is possible to separate the first
region into two regions, eliminate this factor in the lower region, and obtain a more complicated,
yet tighter, expression in the upper region, where k ∼ Θ(n1/3).
Now, similarly to (28), we obtain
Eθ log
Pθ (X
Pθ′ (X
≤ n(log e)
≤ O(1) +
2 log e
n1+2α
≤ 4(log e)n1−2α +O(1). (39)
The first term of inequality (a) is obtained under the assumption that k = O(n), θ′i ≥ 1/n2, and
|δi| ≤ 1/n2. For the second term |δi| ≤ njβ/n2+α, and θ′i ≥ n(j−1)β/n2. Inequality (b) is obtained
in a similar manner to inequality (f) of (28), where the sum is shown similarly to be 2n2.
Summing up the contributions of (38) and (39) in (37), it is clear that α = 1/3 minimizes
the total cost (to first order). This choice of α also satisfies the assumption of step (c) in (38).
Using α = 1/3, absorbing all low order terms in ε and normalizing by n, we obtain the remaining
two regions of the bound in (14). It should be noted that the proof here would give a bound of
O(n1/3+ε) up to k = O(n4/3). If the intervals in (15) were used for bounded distributions, the
coefficients of the last two regions will be reduced by a factor of 2. Additional manipulations on
the grid η may reduce the coefficients more (see, e.g., [28]).
The proof up to this point assumes that k is known in advance. This is important for the code
resulting in the bound for the first region because the quantization grid depends on k. Specifically,
if in building the grid, k is underestimated, the description cost of ϕ increases. If k is overestimated,
the quantization cost will increase. Also, if the code of the second region is used for a smaller k, a
larger bound than necessary results. To solve this, the optimization that chooses L∗ (xn) is done
over all possible values of k (greater than or equal to the maximal symbol occurring in xn), i.e.,
every greater k in the first region, and the construction of the code for the other regions. For every
k in the first region, a different construction is done, using the appropriate k to determine the
spacing in each interval. The value of k yielding the shortest code word is then used, and O(log n)
additional bits are used at the prefix of the code to inform the decoder which k is used. The analysis
continues as before. This does not change the redundancy to first order, giving all three regions of
the bound in (14), even if k is unknown in advance. This concludes the proof of Theorem 4. �
5 Upper Bounds for Fast Decaying Distributions
This section shows that with some mild conditions on the source distribution, the same redundancy
upper bounds achieved for finite monotonic distributions can be achieved even if the monotonic
distribution is over an infinite alphabet. The key observation that allows this is that a distribution
that decays fast enough will result in only a small number of occurrences of unlikely letters in a
sequence. These letters may very likely be out of order, but since there are very few of them, they
can be handled without increasing the asymptotic behavior of the coding cost. More precisely, fast
decaying monotonic distributions can be viewed as if they have some effective bounded alphabet
size, where occurrences of symbols outside this limited alphabet are rare. We present two theorems
and a corollary that show how one can upper bound the redundancy obtained when coding with
some unknown distribution. The first theorem provides a slightly stronger bound (with smaller
coefficient) even for k = O(n), where the smaller coefficient is attained by improved bounding,
that more uniformly weights the quantization cost for minimal probabilities. In the weaker version
of the results presented here, if the distribution decays slower and there are more low probability
symbols, the redundancy order does increase due to the penalty of identifying these symbols in
a sequence. However, we show, consistently with the results in [10], that as long as the entropy
of the source is finite, a universal code, in the sense of diminishing redundancy per symbol, does
exist. We begin with stating the two theorems and the corollary, then the proofs are presented.
The section is concluded with three examples of typical monotonic distributions over the integers,
to which the bounds are applied.
5.1 Upper Bounds
We begin with some notation. Fix an arbitrary small ε > 0, and let n→ ∞. Define m △= mρ
as the effective alphabet size, where ρ > ε. (Note that ρ = (logm)/(log n).) Let
Rn(m)
log n
, for m = o
ρ+ ε− 1
(log n)
n1/3, otherwise.
Theorem 5 I. Fix an arbitrarily small ε > 0, and let n → ∞. Let xn be generated by an i.i.d.
monotonic distribution θ ∈ M. If there exists m∗, such that,
nθi log i = o [Rn (m∗)] , (41)
then, there exists a code with length function L∗(·), such that
Rn (L
∗,θ) ≤ (1 + ε)
Rn (m∗) (42)
for the monotonic distribution θ.
II. If there exists m∗ for which ρ∗ = o
n1/3/(log n)
, such that,
θi log i = o(1), (43)
then, there exists a universal code with length function L∗(·), such that
Rn (L
∗,θ) = o(1). (44)
Theorem 5 implies that if a monotonic distribution decays fast enough, its effective alphabet
size does not exceed O(nρ), and, as long as ρ is fixed, bounds of the same order as those obtained for
finite alphabets are achievable. Specifically, very fast decaying distributions, although over infinite
alphabets, may even behave like monotonic distributions with o
symbols. The condition in
(41) merely means that the cost that a code would obtain in order to code very rare symbols, that
are larger than the effective alphabet size, is negligible w.r.t. the total cost obtained from other,
more likely, symbols. Note that for m = n, the bound is tighter than that of the third region
of Theorem 4, and a constant of 5/9 replaces 2/3. The second part of the theorem states that if
the decay is slow, but the cost of coding rare symbols is still diminishing per symbol, a universal
code still exists for such distributions. However, in this case the redundancy will be dominated by
coding the rare (out of order) symbols. This result leads to the following corollary:
Corollary 1 As n → ∞, sequences generated by monotonic distributions with Hθ(X) = O(1) are
universally compressible in the average sense.
Corollary 1 shows that sequences generated by finite entropy monotonic distributions can be com-
pressed in the average with diminishing per symbol redundancy. This result is consistent with the
results shown in [10].
While Theorem 5 bounds the redundancy decay rate with two extremes, a more general theorem
can be used to provide some best redundancy decay rate that a code can be designed to adapt to
for some unknown monotonic distribution that governs the data. As the examples at the end of
this section show, the next theorem is very useful for slower decaying distributions.
Theorem 6 Fix an arbitrarily small ε > 0, and let n → ∞. Let xn be generated by an i.i.d.
monotonic distribution θ ∈ M. Then, there exists a code with length function L∗(·), that achieves
redundancy
nRn (L
∗,θ) ≤ (1 + ε) ·
α,ρ:ρ≥α+ε
· (ρ+ 2α) (ρ− α) (log n)2nα + 5(log e)n1−2α +
θi log i
for coding sequences generated by the source θ.
We continue with proving the two theorems and the corollary.
Proof : The idea of the proof of both theorems is to separate the more likely symbols from the
unlikely ones. First, the code determines the point of separation m = nρ. (Note that ρ can be
greater than 1.) Then, all symbols i ≤ m are considered likely and are quantized in a similar
manner as in the codes for smaller alphabets. Unlike bounded alphabets, though, a more robust
grid is used here to allow larger values of m. Coding of occurrences of these symbols uses the
quantized probabilities. The unlikely symbols are coded hierarchically. They are first merged into
a single symbol, and then are coded within this symbol, where the full cost of conveying to the
decoder which rare symbols occur in the sequence is required. Thus, they are presented giving
their actual value. As long as the decay is fast enough, the average cost of conveying these symbols
becomes negligible w.r.t. the cost of coding the likely symbols. If the decay is slower, but still fast
enough, as the case described in condition (43), the coding cost of the rare symbols dominates the
redundancy, but still diminishing redundancy can be achieved. In order to determine the best value
of m for a given sequence, all values are tried and the one yielding the shortest description is used
for coding the specific sequence xn.
Let m ≥ 2 determine the number of likely symbols in the alphabet. For a given m, define
θi, (46)
as the total probability of the remaining symbols. Given θ, m and Sm, a probability
P (xn|m,Sm,θ)
nx(i)
· Snx(x>m)m ·
nx(i)
nx(x > m)
)nx(i)
, (47)
can be computed for xn, where nx(i) is the occurrence count of symbol i in x
n, and nx(x > m)
is the count of all symbols greater than m in xn. This probability mass function clusters all large
symbols (with small probabilities) greater than m into one symbol. Then, it uses the ML estimate
of each of the large symbols to distinguish among them in the clustered symbol.
For every m, we can define a quantization grid ξm for the first m probability parameters of
θ. The idea is similar to that used for all probability parameters in the proof of Theorem 4. If
m = o(n1/3), we use ξm = τm, where τm is the grid defined in (18) where m replaces k. Otherwise,
we can use the definition of η in (35). However, to obtain tighter bounds for large m, we define a
different grid for the larger values of m following similar steps to those in (32)-(36). First, define
the jth interval as
n(j−1)β
nρ+2α
nρ+2α
, 1 ≤ j ≤ Jρ, (48)
where ρ = (logm)/(log n) as defined above, α is a parameter, and β = 1/(log n) as before. Within
the jth interval, we define the spacing in the grid by
nρ+3α
. (49)
As in (34),
|Ij | ≤ 0.5 · nα, ∀j : j = 1, 2, . . . , Jρ, (50)
and the total number of intervals is
Jρ = ⌈(ρ+ 2α) log n⌉ . (51)
Similarly to (35), ξm is defined as
ξm = (ξ1, ξ2, . . .) =
nρ+2α
nρ+2α
nρ+3α
, . . . ,
nρ+2α
nρ+2α
nρ+3α
, . . .
. (52)
The cardinality of ξm is thus
= |ξm| ≤ 0.5 · nα ⌈(ρ+ 2α) log n⌉ . (53)
An mth order quantized version θ′m of θ is obtained by quantizing θi, i = 2, 3, . . . ,m onto ξm,
such that θ′i ∈ ξm for these values of i. Then, the remaining cluster probability Sm is quantized into
S′m ∈ [1/n, 2/n, . . . , 1]. The parameter θ′1 is constrained by the quantization of the other parameters.
Quantization is performed in a similar manner as before, to minimize the accumulating cost and
retain monotonicity.
Now, for any m ≥ 2, let ϕm be any monotonic probability vector of cardinality m whose last
m− 1 components are quantized into ξm, and let σm ∈ [1/n, 2/n, . . . , 1] be a quantized estimate of
the total probability of the remaining symbols, such that
i=1 ϕi,m+σm = 1, where ϕi,m is the ith
component of ϕm. If m, σm and ϕm are known, a given x
n can be coded using P (xn|m,σm,ϕm)
as defined in (47), where σm replaces Sm, and the m components of ϕm replace the first m com-
ponents of θ. However, in the universal setting, none of these parameter are known in advance.
Furthermore, neither the symbols greater than m nor their conditional ML probabilities are known
in advance. Therefore, the total cost of coding xn using these parameters requires universality costs
for describing them. The cost of universally coding xn assigning probability P (xn|m,σm,ϕm) to it
thus requires the following five components: 1) m should be described using Elias’ representation
with at most 1+ ρ log n+2 log(1+ ρ log n) bits. 2) The value of σm in its quantization grid should
be coded using log n bits. 3) The m components of ϕm require LR (ϕm) (which is bounded below)
bits. 4) The number cx(x > m) of distinct letters in x
n greater than m is coded using log n bits.
5) Each letter i > m in xn is coded. Elias’ coding for the integers using 1 + log i+ 2 log(1 + log i)
bits can be used, but to simplify the derivation we can also use the code, also presented in [7], that
uses no more than 1 + 2 log i bits to describe i. In addition, at most log n bits are required for
describing nx(i) in x
n. For n→ ∞, m≫ 1, and ε > 0 arbitrarily small, this yields a total cost of
L (xn|m,σm,ϕm) ≤ − log P (xn|m,σm,ϕm) + LR (ϕm) + [(1 + ε)ρ+ cx(x > m) + 2] log n
+cx(x > m) + 2
i>m,i∈xn
log i, (54)
where we assume m is large enough to bound the cost of describing m by (1 + ε)ρ log n.
The description cost of ϕm for m = o(n
1/3) is bounded by
LR (ϕm) ≤ (1 + ε)
using (21), where m replaces k. The (log n)2 factor in (21) can be absorbed in ε since we limit m
to o(n1/3), unlike the derivation in (21). For larger values of m, we describe symbol probabilities of
ϕm in the grid ξm in a similar manner to the description of O(n) symbol probabilities in the grid
η. Similarly to (38), we thus have
LR(ϕm) ≤ Bρ +Bρ log
nρ +Bρ
+ 2Bρ log log
nρ +Bρ
+ o (Bρ)
≤ (1 + ε)
(ρ+ 2α) (ρ+ ε− α) (log n)2nα (56)
where to obtain inequality (a), we first multiply nρ by nε in the numerator of the argument of the
logarithm. This is only necessary for ρ→ α to guarantee that nρ+ε ≫ Bρ. Substituting the bound
on Bρ from (53), absorbing low order terms in the leading ε, yields the bound.
A sequence xn can now be coded using the universal parameters that minimize the length of
the sequence description, i.e.,
L∗ (xn)
= min
σm′∈[
,...,1]
ϕm′ :ϕi∈ξm′ ,i≥2
xn|m′, σm′ ,ϕm′
xn|m,S′m,θ′m
, (57)
where θ′m and S
m are the true source parameters quantized as described above, and the inequality
holds for every m. Note that the maximization on m′ should be performed only up to the maximal
symbol the occurs in xn.
Following (54)-(57), up to negligible integer length constraints, the average redundancy using
L∗(·) is bounded, for every m ≥ 2, by
nRn (L
∗,θ) = Eθ [L
∗ (Xn) + log Pθ (X
Xn | m,S′m,θ′m
+ logPθ (X
≤ Eθ log
Pθ (X
Xn | m,S′m,θ′m
) + LR
Pθ (i ∈ Xn) log i
+(1 + ε) [EθCx (X > m) + ρ+ 2] log n (58)
where (a) follows from (57), and (b) follows from averaging on (54) with σm = S
m, and ϕm = θ
where the average on cx(x > m) is absorbed in the leading ε.
Expressing Pθ (x
n) as
Pθ (x
nx(i)
 · Snx(x>m)m ·
)nx(i)
, (59)
and defining δS
= Sm − S′m, the first term of (58) is bounded, for the upper region of m, by
Eθ log
Pθ (X
Xn | m,S′m,θ′m
) ≤ Eθ
Nx(i) log
θ′i,m
+Nx (X > m) log
Nx(i) log
θi/Sm
Nx(i)/Nx(X > m)
≤ n ·
θi log
θ′i,m
+ nSm log
≤ n(log e)
θ′i,m
≤ (log e) ·
n · nρ
nρ+2α
+ 2(log e)n1−ρ−4α ·
jβ + log e
≤ 5(log e)n1−2α + log e, (60)
where (a) is since for the third term, the conditional ML probability used for coding is greater than
the actual conditional probability assigned to all letters greater than m for every xn. Hence, the
third term is bounded by 0. For the other terms expectation is performed. Inequality (b) is obtained
similarly to (28) where quantization includes the first m components of θ and the parameter Sm.
Then, inequality (c) follows the same reasoning as step (a) of (39). The first term bounds the worst
case in which all nρ symbols are quantized to 1/nρ+2α with |δi| ≤ 1/nρ+2α. The second term is
obtained where θ′i,m ≥ n(j−1)β/nρ+2α and |δi| ≤ njβ/nρ+3α for θi ∈ Ij , and kj = |θi ∈ Ij| as before.
The last term is since S′m ≥ 1/n and |δS | ≤ 1/n. Finally, (d) is obtained similarly to step (b) of
(39), where as in (29),
jβ ≤ 2nρ+2α. For m = o(n1/3), the same initial steps up to step (b) in
(60) are applied, and then the remaining steps in (28) are applied to the left sum with m replacing
k, yielding a total quantization cost of 5(log e)m+ log e.
To bound the third and fourth terms of (58), we realize that
Pθ (i ∈ Xn) = 1− (1− θi)n ≤ nθi. (61)
Similarly,
EθCx(X > m) =
Pθ (i ∈ Xn) ≤ nSm. (62)
Combining the dominant terms of the third and fourth terms of (58), we have
Pθ (i ∈ Xn) log i+ (1 + ε)EθCx(X > m) log n
Pθ (i ∈ Xn) [2 log i+ (1 + ε) log n]
1 + ε
Pθ (i ∈ Xn) log i
1 + ε
θi log i (63)
where (a) is because EθCx(X > m) =
i>m Pθ (i ∈ Xn), (b) is because for i > m = nρ, log i >
ρ log n, and (c) follows from (61). Given ρ > ε for an arbitrary fixed ε > 0, the resulting coefficient
above is upper bounded by some constant κ.
Summing up the contributions of the terms of (58) from (28), (55), and (63), absorbing low
order terms in a leading ε′, we obtain that for m = o(n1/3),
nRn (L
∗,θ) ≤
1 + ε′
) m− 1
θi log i. (64)
For the second region, substituting α = 1/3, and summing up the contributions of (60), (56), and
(63) to (58), absorbing low order terms in ε′, we obtain
nRn (L
∗,θ) ≤ (1 + ε′)
ρ+ ε′ −
(log n)
n1/3 + κn
θi log i. (65)
Since (64)-(65) hold for every m > nε, there exists m∗ for which the minimal bound is obtained.
To bound the redundancy, we choose this m∗. Now, if the condition in (41) holds, then the second
term in (64) and (65) is negligible w.r.t. the first term. Absorbing it in a leading ε, normalizing by
n, yields the upper bound of (42), and concludes the proof of the Part I of Theorem 5.
For Part II of Theorem 5, we consider the bound of the second region in (65). If there exists
ρ∗ = o
n1/3/(log n)
for which the condition in (43) holds, then both terms of (65) are of o(n),
yielding a total redundancy per symbol of o(1). The proof of Theorem 5 is concluded. �
To prove Corollary 1, we use Wyner’s inequality [32], which implies that for a finite entropy
monotonic distribution,
θi log i = Eθ [logX] ≤ Hθ [X] . (66)
Since the sum on the left hand side of (66) is finite if Hθ[X] is finite, there must exist some n0 such
θi log i = o(1). Let n > n0, then for m
∗ = n and ρ∗ = 1, condition (43) is satisfied.
Therefore, (44) holds, and the proof of Corollary 1 is concluded. �
We now consider only the upper region in (58) with parameters α and ρ taking any valid value.
(The code leading to the bound of the upper region can be applied even if the actual effective
alphabet size is in the lower region.) We can sum up the contributions of (60), (56), and (63) to
(58), absorbing low order terms in ε. Equation (56) is valid without the middle ε term as long as
ρ ≥ α + ε. Since, in the upper region of m, i ≥ m is large enough, Elias’ code for the integers
can be used costing (1 + ε) log i to code i, with ε > 0 which can be made arbitrarily small. Hence,
the leading coefficient of the bound in (63) can be replaced by (1 + ε)(1 + 1/ρ). This yields the
expression bounding the redundancy in (45). This expression applies to every valid choice of α and
ρ, including the choice that minimizes the expression. Thus the proof of Theorem 6 is concluded. �
5.2 Examples
We demonstrate the use of the bounds of Theorems 5 and 6 with three typical distributions over
the integers. We specifically show that the redundancy rate of O
n1/3+ε
bits overall is achievable
when coding many of the typical monotonic distributions, and, in fact, for many distributions
faster convergence rates are achievable with the codes provided in proving the theorems above.
The assumption that very few unlikely symbols are likely to appear in a sequence generated by a
monotonic distribution, which is reflected in the conditions in (41) and (43), is very realistic even
in practical examples. Specifically, in the phone book example, there may be many rare names, but
only very few of them may occur in a certain city, and the more common names constitute most of
any possible phone book sequence.
5.2.1 Fast Decaying Distributions Over the Integers
Consider the monotonic distributions over the integers of the form,
, i = 1, 2, . . . , (67)
where γ > 0, and a is a normalization coefficient that guarantees that the probabilities over all
integers sum to 1. It is easy to show by approximating summation by integration that for some
m→ ∞,
Sm ≤ (1 + ε)
θi log i ≤ (1 + ε)
a logm
. (69)
For m = nρ and fixed ρ, the sum in (41) is thus O
n1−ργ log n
, which is o
n1/3(log n)2
for every
ρ ≥ 2/(3γ). Specifically, as long as γ ≤ 2 (slow decay), the minimal value of ρ required to guarantee
negligibility of the sum in (41) is greater than 1/3. Using Theorem 5, this implies that for γ ≤ 2,
the second (upper) region of the upper bound in (42) holds with the minimal choice of ρ∗ = 2/(3γ).
Plugging in this value in the second region of (40) (i.e., in (42)) yields the upper bound shown below
for this region. For γ > 2, 2/(3γ) < 1/3. Hence, (41) holds for m∗ = o
. This means that for
the distribution in (67) with γ > 2, the effective alphabet size is o
, and thus the achievable
redundancy is in the first region of the bound of (42). Thus, even though the distribution is over
an infinite alphabet, its compressibility behavior is similar to a distribution over a relatively small
alphabet. To find the exact redundancy rate, we balance between the contributions of (55) and
(63) in (58). As long as 1 − ργ < ρ, condition (41) holds, and the contribution of small letters
in (63) is negligible w.r.t. the other terms of the redundancy. Equality, implying ρ∗ = 1/(1 + γ),
achieves the minimal redundancy rate. Thus, for γ > 2,
nRn (L
≤ (1 + ε)
a(2ρ∗ + 1)
∗γ log n+
(1− 3ρ∗) log n
= (1 + ε)
1+γ log n (70)
where the first term in (a) follows from the bounds in (63) and (69), with m = nρ
, and the second
term from that in (55), and (b) follows from ρ∗ = 1/(1 + γ). Note that for a fixed ρ∗, the factor 3
in the first term can be reduced to 2 with Elias’ coding for the integers. The results described are
summarized in the following corollary:
Corollary 2 Let θ ∈ M be defined in (67). Then, there exists a universal code with length function
L∗(·) that has only prior knowledge that θ ∈ M, that can achieve universal coding redundancy
Rn (L
∗,θ) ≤
(1 + ε) 1
1 + 1
+ ε− 1
n1/3(logn)2
, for γ ≤ 2,
(1 + ε)
1+γ logn
, for γ > 2.
Corollary 2 gives the redundancy rates for all distributions defined in (67). For example, if γ = 1,
the redundancy is O
n1/3(log n)2
bits overall with coefficient 2/9. For γ = 3, O(n1/4 log n) bits
are required. For faster decays (greater γ) even smaller redundancy rates are achievable.
5.2.2 Geometric Distributions
Geometric distributions given by
θi = p (1− p)i−1 ; i = 1, 2, . . . , (72)
where 0 < p < 1, decay even faster than the distribution over the integers in (67). Thus their
effective alphabet sizes are even smaller. This implies that a universal code can have even smaller
redundancy than that presented in Corollary 2 when coding sequences generated by a geometric
distribution (even if this is unknown in advance, and the only prior knowledge is that θ ∈ M).
Choosing m = ℓ · log n, the contribution of low probability symbols in (63) to (58) can be upper
bounded by
θi (log i+ log n)
≤ 2n(1− p)m log n+O (n(1− p)m logm)
= 2n1+ℓ log(1−p)(log n) +O
n1+ℓ log(1−p) log log n
where (a) follows from computing Sm using geometric series, and bounding the second term, and
(b) follows from substituting m = ℓ log n and representing (1 − p)ℓ logn as nℓ log(1−p). As long as
ℓ ≥ 1/(− log(1− p)), the expression in (73) is O(log n), thus negligible w.r.t. the redundancy upper
bound of (42) with m∗ = ℓ∗ log n = (log n)/(− log(1 − p)). Substituting this m∗ in (42), we obtain
the following corollary:
Corollary 3 Let θ ∈ M be a geometric distribution defined in (72). Then, there exists a universal
code with length function L∗(·) that has only prior knowledge that θ ∈ M, that can achieve universal
coding redundancy
Rn (L
∗,θ) ≤ 1 + ε
−2 log(1− p)
· (log n)
. (74)
Corollary 3 shows that if θ parameterizes a geometric distribution, sequences governed by θ can be
coded with average universal coding redundancy of O
(log n)2
bits. Their effective alphabet size
is O(log n), implying that larger symbols are very unlikely to occur. For example, for p = 0.5, the
effective alphabet size is log n, and 0.5(log n)2 bits are required for a universal code. For p = 0.75,
the effective alphabet size is (log n)/2, and (log n)2/4 bits are required by a universal code.
5.2.3 Slow Decaying Distributions Over the Integers
Up to now, we considered fast decaying distributions, which all achieved the O(n1/3+ε/n) redun-
dancy rate. We now consider a slowly decaying monotonic distribution over the integers, given
i (log i)
, i = 2, 3, . . . , (75)
where γ > 0 and a is a normalizing factor (see, e.g., [12], [27]). This distribution has finite
entropy only if γ > 0 (but is a valid infinite entropy distribution for γ > −1). Unlike the previous
distributions, we need to use Theorem 6 to bound the redundancy for coding sequences generated
by this distribution. Approximating the sum with an integral, the order of the third term of (45)
θi log i = O
(logm)γ
. (76)
In order to minimize the redundancy bound of (45), we define ρ = nℓ. For the minimum rate, all
terms of (45) must be balanced. To achieve that, we must have
α+ 2ℓ = 1− 2α = 1− γℓ. (77)
The solution is α = γ/(4 + 3γ), and ℓ = 2/(4 + 3γ). Substituting these values in the expression of
(45), with ρ = nℓ, results in the first term in (45) dominating, and yields the following corollary:
Corollary 4 Let θ ∈ M be defined in (75) with γ > 0. Then, there exists a universal code with
length function L∗(·) that has only prior knowledge that θ ∈ M, that can achieve universal coding
redundancy
Rn (L
∗,θ) ≤ (1 + ε)
3γ+4 (log n)2
. (78)
Due to the slow decay rate of the distribution in (75), the effective alphabet size is much greater
here. For γ = 1, for example, it is nn
. This implies that very large symbols are likely to appear
in xn. As γ increases though, the effective alphabet size decreases, and as γ → ∞, m → n. The
redundancy rate increases due to the slow decay. For γ ≥ 1, it is O
n5/7(log n)2/n
. As γ → ∞,
since the distribution tends to decay faster, the redundancy rate tends to the finite alphabet rate
n1/3(log n)2/n
. However, as the decay rate is slower γ → 0, a non-diminishing redundancy
rate is approached. Note that the proof of Theorem 6 does not limit the distribution to a finite
entropy one. Therefore, the bound of (78) applies, in fact, also to −1 < γ ≤ 0. However, for γ ≤ 0,
the per-symbol redundancy is no long diminishing.
6 Individual Sequences
In this section, we first show that individual sequences whose empirical distributions obey the
monotonicity constraints can be universally compressed as well as the average case. We then
study compression of sequences whose empirical distributions may diverge from monotonic. We
demonstrate that under mild conditions, similar in nature to those of Theorems 5 and 6, redundancy
that diminishes (slower than in the average case) w.r.t. the monotonic ML description length can
be obtained. However, these results are only useful when the monotonic ML description length
diverges only slightly from the (standard) ML description length of a sequence, i.e., the empirical
distribution of a sequence only mildly violates monotonicity. Otherwise, the penalty of using an
incorrect monotone model overwhelms the redundancy gain. We begin with sequences that obey
the monotonicity constraints.
Theorem 7 Fix an arbitrarily small ε > 0, and let n→ ∞. Let xn be a sequence for which θ̂ ∈ M,
i.e., θ̂1 ≥ θ̂2 ≥ . . .. Let k = k̂ be the number of letters occurring in xn. Then, there exists a code
L∗ (·) that achieves individual sequence redundancy w.r.t. θ̂M = θ̂ for xn which is upper bounded
R̂n (L
∗, xn) ≤
(1 + ε) k−1
n(logn)
, for k ≤ n1/3,
(1 + ε) (log n)
log k
n1/3−ε
, for n1/3 < k = o(n),
(1 + ε) 1
(log n)
2 n1/3
, for n1/3 < k = O(n).
Note that by the monotonicity constraint, the number of symbols k̂ occurring in xn also equals to
the maximal symbol in xn. Since, in the individual sequence case, this maximal symbol defines the
class considered and also to be consistent with Theorem 3, we use k to characterize the alphabet
size of a given sequence. (The maximal symbol in the individual sequence case is equivalent to the
alphabet size in the average case.) Finally, since θ̂ is monotonic, θ̂M = θ̂.
Proof of Theorem 7: The result in Theorem 7 follows directly from the proof of Theorem 4.
Both regions of the proof apply here, where instead of quantizing θ to θ′, we quantize θ̂ to θ̂
similar manner, and do not need to average over all sequences. In fact, instead of using any general
ϕ̂ to code xn, we can use θ̂
without any additional optimizations, where log n bits describe k. The
description costs of θ̂
are almost the same as those of θ′. The factor 2 reduction in the last region
is because it is sufficient here to replace n2 by n in the denominators of (32). This is because for
every occurring symbol θ̂′i ≥ 1/n and δi ≤ 1/n, thus the first term of step (a) in (39) holds with
the new grid, and B2 in (36) reduces by a factor of 2. The quantization costs bounded in (28) and
(39) are thus bounded similarly, where θ̂ replaces θ and θ̂
replaces θ′. This results in the bounds
in (79) and concludes the proof of Theorem 7. �
If one a-priori knows that xn is likely to have been generated by a monotonic distribution,
the case considered in Theorem 7 is with high probability the typical one. However, a typical
sequence can also be one for which θ̂ 6∈ M, where θ̂ mildly violates the monotonicity. In the pure
individual sequence setting (where no underlying distribution is assumed but some monotonicity
assumption is reasonable for the empirical distribution of xn), one can still observe sequences that
have empirical distributions that are either monotonic or slightly diverge from monotonic. Coding
for this more general case can apply the methods described in Section 5 to the individual sequence
case. If the divergence from monotonicity is small, one may still achieve bounds of the same order
of those presented in Theorem 7 with additional negligible cost of relaying which symbols are out
of order. The next theorem, however, provides a general upper bound in the form of the bounds
of Theorems 5 and 6 for the individual sequence redundancy w.r.t. the monotonic ML description
length, as defined in (10). We begin, again, with some notation.
Recall the definition of an effective alphabet size m
= nρ (where ρ = (logm)/(log n).)
Now, use this definition for a specific individual sequence xn. Let
R̂n(m)
log n
, m ≤ n1/3,
m log n
, n1/3 < m = o (
minα<ρ
ρ+1+α
(ρ− α) (log n)2 nα + 3(log e)n1−α
, otherwise.
Theorem 8 Fix an arbitrarily small ε > 0, and let n→ ∞. Then, there exists a code with length
function L∗(·), that achieves individual sequence redundancy w.r.t. the monotonic ML description
length of xn (as defined in (10)) bounded by
R̂n (L
∗, xn) ≤ 1 + ε
R̂n (nρ) +
i>nρ,i∈xn
log i
for every xn.
Theorem 8 shows that if one can find a relatively small effective alphabet of the symbols that
occur in xn, and the symbols outside this alphabet are small enough, xn can be described with
diminishing per-symbol redundancy w.r.t. its monotonic ML description length. This implies that
as long as the occurring symbols are not too large, there exist a universal code w.r.t. a monotonic
ML distribution for any such sequence xn. This is unlike standard individual sequence compression
w.r.t. the i.i.d. ML description length. Specifically, if the effective alphabet size is O(n), and
only a small number of symbols which are only polynomial in n occur, the universality cost is
n(log n)2) bits overall, which gives diminishing per-symbol redundancy of O((log n)2/
This redundancy is much better than what can be achieved in standard compression. The penalty,
of course, is when the empirical distribution of an individual sequence diverges significantly away
from a monotonic one. While the monotonic redundancy can be made diminishing under mild
conditions, there is a non-diminishing divergence cost by using the monotonic ML description
length instead of the ML description length in that case. This implies that one should compress
a sequence as generated by a monotonic distribution only if the total description length required
to code xn as such is shorter than the total description length required to code xn with standard
methods. As shown in the proof of Theorem 8, one prefix bit can inform the decoder which type
of description is used.
Theorem 8 shows that as long as the effective alphabet size is polynomial in n, α = 0.5 optimizes
the third region of the upper bound, thus yielding the rate shown above, unless very large symbols
occur in xn. For small effective alphabets (the first region), there is no redundancy gain in using
the monotonic ML description length over the ML description length. The reason, again, is that
the bound is obtained for cases where the actual empirical distribution of a sequence may not be
monotonic. One can still use an i.i.d. ML estimate w.r.t. only the effective alphabet, if the additional
cost of symbols outside this alphabet is negligible, to better code such sequences. Theorem 8 also
shows that if a very large symbol, such as i = an; a > 1, occurs in xn, xn cannot be universally
compressed even w.r.t. its monotonic ML description length. This is because it is impossible to
avoid the cost of (1+ε) log i = (1+ε)n log a bits to describe this symbol to the decoder. The bound
above and its proof below give a very powerful method to individually compress sequences that
have an almost monotonic empirical distribution but may have some limited disorder, for which
the monotonic ML description length diverges only negligibly from the ML description length.
Proof of Theorem 8: The proof follows the same steps as the proof of Theorems 5 and 6. Each
value of m is tested and the best one is chosen, where the same coding costs described in the
mentioned proof are computed for each m. In addition, one can test the cost of coding xn using the
description lengths for both θ̂ and θ̂M. Then, one bit can be used to relay which ML estimator is
used. If θ̂ is used, the codes for coding individual sequences over large alphabets in either [21] or [25]
can be used. In the first region in (81), the bound in [25] is obtained since log P
(xn) ≥ log P
for every xn. This bound yields smaller redundancy for this region than that obtained using θ̂M
if θ̂M 6= θ̂. It implies that for small alphabets, if xn does not have an empirical monotonic
distribution, it is better coded, even in terms of universal coding redundancy, using standard
universal compression methods without taking advantage of a monotonicity assumption.
For the other two regions, we start with a lemma.
Lemma 6.1 Let θ̂M =
θ̂1,M, θ̂2,M, . . . , θ̂k,M
be the monotonic ML estimator of θ from xn, i.e.,
θ̂1,M ≥ θ̂2,M ≥ · · · ≥ θ̂k,M, where k = max {x1, x2, . . . , xn}. Then,
θ̂k,M ≥
. (82)
Lemma 6.1 provides a lower bound on the minimal nonzero probability component of the monotonic
ML estimator. This bound helps in designing the grid of points used to quantize the monotonic
ML distribution of xn, while maintaining bounded quantization costs. The proof of Lemma 6.1 is
in Appendix C.
For m in the second region, we cannot use the grid in (18). The reason is that, here, the
quantization cost is affected by both θ̂ and θ̂M. This is unlike the average case, where the av-
erage respective vectors merge. To limit the quantization cost for very small probabilities, using
Lemma 6.1, the minimal grid point must be 1/n2 or smaller. To make the quantization cost neg-
ligible w.r.t. the cost of describing the quantized ML, the ratio ∆j/ϕi,M between the spacing in
interval j, and a quantized version ϕi,M of θ̂i,M in the jth interval, must be O(m/n). Hence, using
the same methodology of the proof of Theorems 5 and 6, we define the jth interval for an effective
alphabet m = nρ = o (
n) as
Îj =
n(j−1)β
, 1 ≤ j ≤ Ĵρ. (83)
The spacing in the jth interval is
. (84)
This gives a total of
B̂ρ ≤
log n (85)
quantization points. Using the same methodology as in (21), this yields a representation cost of
LR (ϕm) ≤ (1 + ε)m log
where ϕm is the quantized version of θ̂M in which only the firstm components of θ̂M are considered.
Using the quantization with the grid defined in (83)-(86) in a code similar to the one used in the
proof of Theorems 5 and 6, the individual quantization cost is given by
P (xn|m,S′m,ϕm)
θ̂i log
θ̂i,M
+ log e
≤ n(log e)
+ log e
≤ (log e) · n
·mn+ (log e) · n · mn
+ log e
= 3m(log e) + log e. (87)
where (a) follows the same steps as in (60), (b) follows from ln(1+x) ≤ x, and then x ≤ |x|, where
= θ̂i,M − ϕi,m, and (c) follows from Lemma 6.1 and the definition of Îj in (83) (for the worst
case first term, |δi| ≤ 1/n2 and ϕi,m ≥ 1/(mn)), from (84) and (83) (the second term), and since
θ̂i = 1. The only additional non-negligible cost of coding sequences using a code as defined in
the proof of Theorems 5 and 6 for a given m is the cost of coding all symbols i > m that occur in
xn. Using a similar derivation to (54), with Elias’ asymptotic code for the integers, this yields an
additional cost of (1 + ε) (1 + 1/ρ)
i>nρ,i∈xn log i code bits. Combining all costs, absorbing low
order terms in ε, and normalizing by n, yields the second region of the bound in (81). Note that
this bound also applies to the first region, but in that region, a tighter bound is obtained by using a
code that uses the standard i.i.d. ML estimator θ̂. This is because very fine quantization is needed
to offset the cost of mismatch between θ̂ and θ̂M. This quantization requires higher description
costs than the description of a quantized type of a sequence when using standard compression.
(This is not the case when θ̂ obeys the monotonicity, as in Theorem 7. Even if θ̂ does not obey
monotonicity in the upper regions of the bound, this is not the case.)
For the last region of the bound, we follow the same steps above as was done for the upper
region of the bound in Theorem 5 with a parameter α. The intervals are chosen, again, to guarantee
bounded quantization costs. Hence,
Îj =
n(j−1)β
nρ+1+α
nρ+1+α
, 1 ≤ j ≤ Ĵρ. (88)
The spacing in the jth interval is
nρ+1+2α
. (89)
This gives a total of
B̂ρ ≤ 0.5nα ⌈(ρ+ 1 + α) log n⌉ (90)
quantization points. Using the same methodology as in (56), this yields a representation cost of
LR (ϕm) ≤ (1 + ε)
ρ+ 1 + α
(ρ+ ε− α) (log n)2nα. (91)
Similarly to (87),
P (xn|m,S′m,ϕm)
≤ (log e)
nρ+1+α
+ (log e)2n1−α + log e = 3(log e)n1−α + log e (92)
where (a) follows from similar steps to (a)-(c) of (87). Using Lemma 6.1, ϕi,m ≥ 1/nρ+1 and
|δi| ≤ 1/nρ+1+α, leading to the first term. Bounding |δi| ≤ njβ/nρ+1+2α and ϕi,m ≥ n(j−1)β/nρ+1+α
leads to the second term. Note that as before, m is used here in place of k, because using an ef-
fective alphabet m, all greater symbols are packed together as one symbol, and the additional cost
to describe them is reflected in an additional term. Adding this additional term with an identical
expression to that in the lower regions, absorbing low order terms in ε, and normalizing by n,
yields the third region of the bound in (81). Since the bound holds for every α and every ρ > α, it
can be optimized to give the values that attain the minimum, concluding the proof of Theorem 8. �
7 Summary and Conclusions
Universal compression of sequences generated by monotonic distributions was studied. We showed
that for finite alphabets, if one has the prior knowledge of the monotonicity of a distribution,
one can reduce the cost of universality. For alphabets of o(n1/3) letters, this cost reduces from
0.5 log(n/k) bits per each unknown probability parameter to 0.5 log(n/k3) bits per each unknown
probability parameter. Otherwise, for alphabets of O(n) letters, one can compress such sources with
overall redundancy of O(n1/3+ε) bits. This is a significant decrease in redundancy from O(k log n)
or O(n) bits overall that can be achieved if no side information is available about the source
distribution. Redundancy of O(n1/3+ε) bits overall can also be achieved for much larger alphabets
including infinite alphabets for fast decaying monotonic distributions. Sequences generated by
slower decaying distributions can also be compressed with diminishing per-symbol redundancy
costs under some mild conditions and specifically if they have finite entropy rates. Examples for
well-known monotonic distributions demonstrated how the diminishing redundancy decay rates
can be computed by applying the bounds that were derived. Finally, the average case results were
extended to individual sequences. Similar convergence rates were shown for sequences that have
empirical monotonic distributions. Furthermore, universal redundancy bounds w.r.t. the monotonic
ML description length of a sequence were also derived for the more general case. Under some mild
conditions, these bounds still exhibit diminishing per-symbol redundancies.
Appendix A – Proof of Theorem 1
The proof follows the same steps used in [25] and [26] to lower bound the maximin redundancies
for large alphabets and patterns, respectively, using the weak version of the redundancy-capacity
theorem [5]. This version ties between the maximin universal coding redundancy and the capacity
of a channel defined by the conditional probability Pθ (x
n). We define a set ΩMk of points θ ∈ Mk.
Then, show that these points are distinguishable by observing Xn, i.e., the probability that Xn
generated by θ ∈ ΩMk appears to have been generated by another point θ
′ ∈ ΩMk diminishes
with n. Then, using Fano’s inequality [3], the number of such distinguishable points is a lower
bound on R−n (Mk). Since R+n (Mk) ≥ R−n (Mk), it is also a lower bound on the average minimax
redundancy. The two regions in (6) result from a threshold phenomenon, where there exists a value
km of k that maximizes the lower bound, and can be applied to all Mk for k ≥ km.
We begin with defining ΩMk . Let ω be a vector of grid components, such that the last k − 1
components θi, i = 2, . . . , k, of θ ∈ ΩMk must satisfy θi ∈ ω. Let ωb be the bth point in ω, and
define ω0 = 0 and
2(j − 1
, b = 1, 2, . . . . (A.1)
Then, for the bth point in ω,
. (A.2)
To count the number of points in ΩMk , let us first consider the standard i.i.d. case, where there
is no monotonicity requirement, and count the number of points in Ω, which is defined similarly,
but without the monotonicity requirement (i.e., ΩMk ⊆ Ω). Let bi be the index of θi in ω, i.e.,
θi = ωbi . Then, from (A.1)-(A.2) and since the components of θ are probabilities,
ωbi =
θi ≤ 1. (A.3)
It follows that for θ ∈ Ω,
b2i ≤ n1−ε. (A.4)
Hence, since the components bi are nonnegative integers,
= |Ω| ≥
n1−ε⌋
n1−ε−b22
· · ·
n1−ε−
i=2 b
n1−ε−x22
· · ·
n1−ε−
i=2 x
dxk · · · dx3dx2
(A.5)
where Vk−1
is the volume of a k − 1 dimensional sphere with radius
, (a) follows
from monotonic decrease of the function in the integrand for all integration arguments, and (b)
follows since its left hand side computes the volume of the positive quadrant of this sphere. Note
that this is a different proof from that used in [25]-[26] for this step. Applying the monotonicity
constraint, all permutations of θ that are not monotonic must be taken out of the grid. Hence,
= |ΩMk | ≥
k! · 2k−1
, (A.6)
where dividing by k! is a worst case assumption, yielding a lower bound and not an equality. This
leads to a lower bound equal to that obtained for patterns in [26] on the number of points in ΩMk .
Specifically, the bound achieves a maximal value for km =
πn1−ε/2
and then decreases to
eventually become smaller than 1. However, for k > km, one can consider a monotonic distribution
for which all components θi; i > km, of θ are zero, and use the bound for km.
Distinguishability of θ ∈ ΩMk is a direct result of distinguishability of θ ∈ Ω, which is shown
in Lemma 3.1 in [25], i.e., there exits an estimator Θ̂g(X
n) ∈ Ω for which the estimate θ̂g satisfies
limn→∞ Pθ
θ̂g 6= θ
= 0 for all θ ∈ Ω. Since this is true for all points in Ω, it is also true
for all points in ΩMk ⊆ Ω, where now, θ̂g ∈ ΩMk . Assuming all points in ΩMk are equally
probable to generate Xn, we can define an average error probability Pe
Θ̂g(X
n) 6= Θ
θ∈ΩMk
θ̂g 6= θ
/MMk . Using the redundancy-capacity theorem,
nR−n [Mk] ≥ C [Mk → Xn]
≥ I[Θ;Xn] = H [Θ]−H [Θ|Xn]
= logMMk −H [Θ|X
≥ (1− Pe) (logMMk)− 1
≥ (1− o(1)) logMMk , (A.7)
where C [Mk → Xn] denotes the capacity of the respective channel and I[Θ;Xn] is the mutual
information induced by the joint distribution Pr (Θ = θ) · Pθ (Xn). Inequality (a) follows from the
definition of capacity, equality (b) from the uniform distribution of Θ in ΩMk , inequality (c) from
Fano’s inequality, and (d) follows since Pe → 0. Lower bounding the expression in (A.6) for the
two regions (obtaining the same bounds as in [26]), then using (A.7), normalizing by n, and ab-
sorbing low order terms in ε, yields the two regions of the bound in (6). The proof of Theorem 1
is concluded. �
Appendix B – Proof of Theorem 2
To prove Theorem 2, we use the random-coding strong version of the redundancy-capacity theorem
[17]. The idea is similar to the weak version used in Appendix A. We assume that grids ΩMk of
points are uniformly distributed over Mk, and one grid is selected randomly. Then, a point in the
selected grid is randomly selected under a uniform prior to generate Xn. Showing distinguishability
within a selected grid, for every possible random choice of ΩMk , implies that a lower bound on the
cardinality of ΩMk for every possible choice is essentially a lower bound on the overall sequence
redundancy for most sources in Mk.
The construction of ΩMk is identical to that used in [26] to construct a grid of sources that
generate patterns. We pack spheres of radius n−0.5(1−ε) in the parameter space defining Mk. The
set ΩMk consists of the center points of the spheres. To cover the space Mk, we randomly select
a random shift of the whole lattice under a uniform distribution. The cardinality of ΩMk is lower
bounded by the relation between the volume of Mk, which equals (as shown in [26]) 1/[(k− 1)!k!],
and the volume of a single sphere, with factoring also of a packing density (see, e.g., [2]). This
yields eq. (55) in [26],
MMk ≥
(k − 1)! · k! · Vk−1
n−0.5(1−ε)
· 2k−1
, (B.1)
where Vk−1
n−0.5(1−ε)
is the volume of a k−1 dimensional sphere with radius n−0.5(1−ε) (see, e.g.,
[2] for computation of this volume).
For distinguishability, it is sufficient to show that there exists an estimator Θ̂g(X
n) ∈ ΩMk
such that limn→∞ PΘ
Θ̂g(X
n) 6= Θ
= 0 for every choice of ΩMk and for every choice of Θ ∈
ΩMk . This is already shown in Lemma 4.1 in [25] for a larger grid Ω of i.i.d. sources, which is
constructed identically to ΩMk over the complete k−1 dimensional probability simplex. Therefore,
by the monotonicity requirement, for every ΩMk , there exists such Ω, such that ΩMk ⊆ Ω. Since
Lemma 4.1 in [25] holds for Ω, it then must also hold for the smaller grid ΩMk . Note that
distinguishability is easier to prove here than for patterns because Θ̂g(X
n) is obtained directly
form Xn and not from its pattern as in [26]. Now, since all the conditions of the strong random-
coding version of the redundancy-capacity theorem hold, taking the logarithm of bound in (B.1),
absorbing low order terms in ε, and normalizing by n, leads to the first region of the bound in (7).
More detailed steps follow those found in [26].
The second region of the bound is handled in a manner related to the second region of the
bound of Theorem 1. However, here, we cannot simply set the probability of all symbols i > km
to zero, because all possible valid sources must be included in one of the grids ΩMk to generate
a complete covering of Mk. As was done in [26], we include sources with θi > 0 for i > km in
the grids ΩMk , but do not include them in the lower bound on the number of grid points. In-
stead, for k > km, we bound the number of points in a km-dimensional cut of Mk for which the
remaining k− km components of θ are very small (and insignificant). This analysis is valid also for
k > n. Distinguishability for k > km is shown for i.i.d. non-monotonically restricted distributions
in the proof of Lemma 6.1 in [26]. As before, it carries over to monotonic distributions, since as
before, for each ΩMk , there exists an unrestricted corresponding Ω, such that ΩMk ⊆ Ω. The
choice of km = 0.5(n
1−ε/π)1/3 gives the maximal bound w.r.t. k. Since, again, all conditions of the
strong version of the redundancy-capacity theorem are satisfied, the second region of the bound is
obtained. Again, more detailed steps can be found in [26]. This concludes the proof of Theorem 2. �
Appendix C – Proof of Lemma 6.1
For cardinality k, we consider the largest component of θ̂M; θ̂1,M, as the constraint component,
i.e., θ̂1,M = 1−
i=2 θ̂i,M. For any given probability parameter ϕ of cardinality k with ϕ1 > 0, we
Pϕ (x
n) = ϕ
nx(1)
1 (1− ϕ1)
n−nx(1) ·
1− ϕ1
)nx(i) △
nx(1)
1 (1− ϕ1)
n−nx(1)
nx(i)
i (C.1)
where we recall that nx(i) is the occurrence count of i in x
n. Therefore, maximization of Pϕ (x
w.r.t. ϕ1 is independent of the maximization over ϑi; i > 1, and is obtained for ϕ1 = θ̂1 = nx(1)/n.
Since for all i > 1, θ̂1,M ≥ θ̂i,M, θ̂1,M can thus only increase from θ̂1 by the monotonicity constraint.
(Note that the monotonicity constraint implies a water filling [3] optimization to achieve θ̂M.)
Hence, θ̂1,M ≥ nx(1)/n.
Now, using the result above, we show that the derivative of lnPϕM (x
n) w.r.t. ϕk,M is positive
for ϕk,M < 1/(kn) and a monotonic ϕM. A component of a parameter vector ϕM, which is
monotonic, can be expressed as
ϕi,M =
ϕ′ℓ, ϕ
ℓ ≥ 0. (C.2)
Hence,
∂ lnPϕM (x
∂ϕk,M
ϕ1,M=θ̂1,M
∂ lnPϕM (x
ϕ1,M=θ̂1,M
nx(i)
− (k − 1)nx(1)
θ̂1,M
knx(k)
− knx(1)
= 0 (C.3)
where (a) follows from ϕk,M being the smallest nonzero component of ϕM, (b) is since by (C.2),
ϕ′k is included in all terms, and
ϕ1,M = 1−
ϕi,M = 1−
(i− 1)ϕ′i − (k − 1)ϕk,M, (C.4)
where the last equality follows from (C.2), (c) follows by omitting all terms of the sum except i = k,
from the assumption that ϕk,M < 1/(nk) ≤ θ̂k/k, and since θ̂1,M ≥ nx(1)/n = θ̂1, and (d) follows
since its left hand side is 0 for the (i.i.d.) ML parameter values. Hence, PϕM (x
n) must increase,
with ϕ1,M taking its optimal value, for all ϕM for which ϕk,M < 1/(nk), and the maximum is thus
achieved for θ̂k,M ≥ 1/(nk). �
References
[1] J. Åberg, Y. M. Shtarkov, and B. J. M. Smeets, “Multialphabet coding with separate alphabet
description,” in Proceedings of Compression and Complexity of Sequences, pp. 56-65, Jun.
1997.
[2] J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, Third
Edition, 1998.
[3] T. M. Cover and J. A. Thomas, Elements of Information Theory , second edition, John Wiley
& Sons, 2006.
[4] I. Csiszar and J. Korner, Information Theory: Coding Theorems for Discrete Memoryless
Systems., Academic Press, New York, 1981.
[5] L. D. Davisson, “Universal noiseless coding,” IEEE Trans. Inform. Theory , vol. IT-19, no. 6,
pp. 783-795, Nov. 1973.
[6] L. D. Davisson, and A. Leon-Garcia, “A source matching approach to finding minimax codes,”
IEEE Trans. Inform. Theory , vol. IT-26, no. 2, pp. 166-174, Mar. 1980.
[7] P. Elias, “Universal codeword sets and representation of the integers,” IEEE Trans. Inform.
Theory , vol. IT-21, no. 2, pp. 194-203, March 1975.
[8] B. M. Fitingof, “Optimal coding in the case of unknown and changing message statistics,”
Probl. Inform. Transm., vol. 2, no. 2, pp. 1-7, 1966.
[9] B. M. Fitingof, “The compression of discrete information,” Probl. Inform. Transm., vol. 3,
no. 3, pp. 22-29, 1967.
[10] D. P. Foster, R. A. Stine, and A. J. Wyner, “Universal codes for finite sequences of integers
drawn from a monotone distribution,” IEEE Trans. Inform. Theory , vol. 48, no. 6, pp. 1713-
1720, June 2002.
[11] R. G. Gallager, “Source coding with side information and universal coding,” unpublished
manuscript, September 1976.
[12] G. M. Gemelos and T. Weissman, “On the entropy rate of pattern processes,” IEEE Trans.
Inform. Theory , vol. 52, no. 9, pp. 3994-4007, Sept. 2006.
[13] L. Györfi, I. Páli, and E. C. van der Meulen, “There is no universal code for an infinite source
alphabet,” IEEE Trans. Inform. Theory , vol. 40, no. 1, pp. 267-271, Jan. 1994.
[14] N. Jevtić, A. Orlitsky, and N. P. Santhanam, “A lower bound on compression of unknown
alphabets,” Theoret. Comput. Sci., vol. 332, no. 1-3, pp. 293-311, 2005.
[15] J. C. Kieffer, “A unified approach to weak universal source coding,” IEEE Trans. Inform.
Theory , vol. IT-24, no. 6, pp. 674-682, Nov. 1978.
[16] M. Khosravifard, H. Saidi, M. Esmaeili, and T. A. Gulliver, “The minimum average code
for finite memoryless monotone sources,” IEEE Trans. Inform. Theory , vol. 52, no. 3, pp.
955-975, Mar. 2007.
[17] N. Merhav and M. Feder, “A strong version of the redundancy-capacity theorem of universal
coding,” IEEE Trans. Inform. Theory , vol. no. 3, 41, pp. 714-722, May 1995.
[18] N. Merhav, G. Seroussi, and M. J. Weinberger, “Optimal prefix codes for sources with two-
sided geometric distributions,” IEEE Trans. Inform. Theory , vol. 46, no. 1, pp. 121-135, Jan.
2000.
[19] N. Merhav, G. Seroussi, and M. J. Weinberger, “Coding of sources with two-sided geometric
distributions and unknown parameters,” IEEE Trans. Inform. Theory , vol. 46, no. 1, pp.
229-236, Jan. 2000.
[20] A. Orlitsky, N. P. Santhanam, and J. Zhang, “Universal compression of memoryless sources
over unknown alphabets,” IEEE Trans. Inform. Theory , vol. 50, no. 7, pp. 1469-1481, July
2004.
[21] A. Orlitsky, and N. P. Santhanam, “Speaking of infinity,” IEEE Trans. Inform. Theory , vol.
50, no. 10, pp. 2215-2230, Oct. 2004.
[22] J. Rissanen, “Minimax codes for finite alphabets,” IEEE Trans. Inform. Theory , vol. IT-24,
no. 3, pp. 389-392, May 1978.
[23] J. Rissanen, “Universal coding, information, prediction, and estimation,” IEEE Trans. In-
form. Theory , vol. IT-30, no. 4, pp. 629-636, Jul. 1984.
[24] B. Ya. Ryabko, “Coding of a source with unknown but ordered probabilities,” Problems of
Information Transmission, vol. 15, no. 2, pp. 134-138, Oct. 1979.
[25] G. I. Shamir, “On the MDL principle for i.i.d. sources with large alphabets,” IEEE Trans.
Inform. Theory , vol. 52, no. 5, pp. 1939-1955, May 2006.
[26] G. I. Shamir, “Universal lossless compression with unknown alphabets - the average case”,
IEEE Trans. Inform. Theory , vol. 52, no. 11, pp. 4915-4944, Nov. 2006.
[27] G. I. Shamir, “Patterns of sequences and their entropy,” submitted to IEEE Trans. Inform.
Theory . Also in Arxiv:cs.IT/0605046 .
[28] G. I. Shamir, “A new redundancy bound for universal lossless compression of unknown alpha-
bets,” in Proceedings of The 38th Annual Conference on Information Sciences and Systems,
Princeton, New-Jersey, U.S.A., pp. 1175-1179, Mar. 17-19, 2004.
[29] Y. M. Shtarkov, “Universal sequential coding of single messages,” Problems of Information
Transmission, 23(3):3-17, Jul.-Sep. 1987.
[30] L. R. Varshney and V. K. Goyal, “Ordered and disordered source coding,” in Information
Theory & Applications Workshop (ITA), San Diego, California, Feb. 6-10, 2006.
[31] L. R. Varshney and V. K. Goyal, “On universal coding of unordered data,” in Information
Theory & Applications Workshop (ITA), San Diego, California, Jan. 29-Feb. 2, 2007.
[32] A. D. Wyner, “An upper bound on the entropy series,” Inform. Contr., vol. 20, pp. 176-181,
1972.
	Introduction
	Notation and Definitions
	Lower Bounds
	Upper Bounds for Small and Large Alphabets
	Upper Bounds for Fast Decaying Distributions
	Upper Bounds
	Examples
	Fast Decaying Distributions Over the Integers
	Geometric Distributions
	Slow Decaying Distributions Over the Integers
	Individual Sequences
	Summary and Conclusions
	–   Proof of Theorem ??
	–   Proof of Theorem ??
	–   Proof of Lemma ??
