1

Improved Bounds on Lossless Source Coding
and Guessing Moments via Rényi Measures
Igal Sason

Sergio Verdú

arXiv:1801.01265v2 [] 29 Jan 2018

Abstract
This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on
a finite set when side information may be available. These moments quantify the number of guesses required for correctly
identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi
conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is
significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP
error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal
guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths
for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability
function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant
generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that
allow decoding errors.

Keywords
Cumulant generating function, guessing moments, lossless source coding, M -ary hypothesis testing, Rényi entropy,
Rényi divergence, Arimoto-Rényi conditional entropy, smooth Rényi entropy.

I.

I NTRODUCTION

A. Prior work
The problem of guessing discrete random variables has found a variety of applications in information theory,
coding theory, cryptography, and searching and sorting algorithms. The central object of interest is the distribution
I. Sason is with the Andrew and Erna Viterbi Faculty of Electrical Engineering, Technion–Israel Institute of Technology, Haifa 32000,
Israel (e-mail: sason@ee.technion.ac.il).
S. Verdú is with the Department of Electrical Engineering, Princeton University, Princeton, New Jersey 08544, USA (e-mail:
verdu@princeton.edu).
This work has been supported by the Israeli Science Foundation (ISF) under Grant 12/12, by ARO-MURI contract number W911NF15-1-0479 and in part by the Center for Science of Information, an NSF Science and Technology Center under Grant CCF-0939370.

January 30, 2018

DRAFT

2

of the number of guesses required to identify a realization of a random variable X , taking values on a finite
or countably infinite set X = {1, . . . , |X |}, by asking questions of the form “Is X equal to x?”. A guessing
function is a one-to-one function g : X → X , which can be viewed as a permutation of the elements of X in

the order in which they are guessed. We can envision a generic algorithm that outputs g −1 (1); a supervisor
checks whether X = g −1 (1), if so then the algorithm halts; otherwise, the algorithm outputs g −1 (2) and the
process repeats until the value of X is guessed correctly. Therefore, the number of guesses is g(x) when the
true outcome is x ∈ X .
Lower and upper bounds on the minimal expected number of required guesses for correctly identifying the
realization of X , expressed as a function of the Shannon entropy H(X), have been respectively derived by
Massey [31] and by McEliece and Yu [32]. More generally, given a probability mass function PX on X , it is
of interest to minimize the generalized guessing moment
E[g ρ (X)] =

X

PX (x)g ρ (x),

ρ > 0.

(1)

x∈X

For an arbitrary positive ρ, the ρ-th moment of the number of guesses is minimized by selecting the guessing
function to be a ranking function gX , for which gX (x) = k if PX (x) is the k -th largest mass. Upper and lower
bounds on the ρ-th moment of ranking functions, expressed in terms of the Rényi entropy Hα (X) of order
α=

1
1+ρ ,

were derived by Arikan [1], followed by a refined upper bound by Boztaş [6]. Although if |X | is

small, it is straightforward to evaluate numerically the guessing moments, the benefit of bounds expressed in
terms of Rényi entropies is particularly relevant when dealing with a random vector X n = (X1 , . . . , Xn ) whose
letters belong to a finite alphabet A; computing all the probabilities of the mass function PX n over the set
An , and then sorting them in decreasing order for the calculation of the ρ-th moment of the optimal guessing

function for the elements of An has exponential complexity in n. Therefore, it becomes infeasible even for
moderate values of n. In contrast, regardless of the value of n, bounds on guessing moments which depend on
the Rényi entropy are readily computable if for example {Xi }ni=1 are independent; in which case, the Rényi
entropy of the vector is equal to the sum of the Rényi entropies of its components (hence, the exponential
complexity is reduced to linear complexity in n; furthermore, in the i.i.d. case, the complexity in calculating
the Rényi entropy of X n is independent of n). Arikan’s bounds are asymptotically tight for random vectors of
length n as n → ∞, so another benefit of these bounds is that they provide the correct exponential growth rate
of the guessing moments for sufficiently large n. In [1], Arikan generalized his bounds to allow side information,
leading to asymptotically tight bounds which are expressed in terms of the Arimoto-Rényi conditional entropy
[4].
The guessing problem has been studied in the information-theoretic literature in various contexts, which
include: guessing subject to distortion [2], joint source-channel coding and guessing with application to sequential
January 30, 2018

DRAFT

3

decoding [3], guessing with a prior access to a malicious oracle [11], a large deviations approach to guessing
and source compression ([15], [22], [48]), guessing with limited memory [23], guesswork exponents for Markov
sources [30], guessing in secrecy problems ([40], [52]), and guessing under source uncertainty [47].
For uniquely-decodable lossless source coding, Campbell ([13], [14]) proposed the normalized cumulant
generating function of the codeword lengths as a generalization to the frequently used design criterion of the
normalized average code length. Campbell’s motivation in [13] was to control the contribution of the longer
codewords via a free parameter in the cumulant generating function: if the value of this parameter tends to zero,
then the resulting design criterion becomes the normalized average code length while by increasing the value
of the free parameter, the penalty for longer codewords is more severe, and the resulting code optimization
yields a reduction in the fluctuations of the codeword lengths. In [13], Campbell obtained asymptotically tight
upper and lower bounds on the minimum normalized cumulant generating function for discrete memoryless
stationary sources with finite alphabet. These bounds, expressed in terms of the Rényi entropy, imply that for
sufficiently long source sequences, it is possible to make the normalized cumulant generating function of the
codeword lengths approach the Rényi entropy as closely as desired by a proper fixed-to-variable uniquelydecodable source code; moreover, a converse result in [13] shows that there is no uniquely-decodable source
code for which the normalized cumulant generating function of its codeword lengths lies below the Rényi
entropy. Campbell’s result generalizes Shannon’s fundamental result in [43] for the average codeword lengths
of lossless compression codes, expressed in terms of the Shannon entropy. In addition, this type of bounds was
studied in the context of various coding problems, including guessing (see, e.g., [1], [2], [3], [7], [8], [9], [16],
[17], [22], [28], [33], [34], [35], [47], [51]).
Kontoyiannis and Verdú [26] studied the behavior of the best achievable rate and other fundamental limits
in variable-rate lossless source compression without prefix constraints. In the non-asymptotic regime, the fundamental limits of fixed-to-variable lossless compression with and without prefix constraints were shown to be
tightly coupled. They derived in [26] non-asymptotic upper and lower bounds on the distribution of codeword
lengths, along with a rigorous proof of the Gaussian approximation put forward by Strassen [46] for memoryless
sources. An alternative approach was followed by Courtade and Verdú in [16], where they derived non-asymptotic
bounds for the normalized cumulant generating function of the codeword lengths for optimal variable-length
lossless codes without prefix constraints; these bounds are used in [16] to obtain simple proofs of the asymptotic
normality and the reliability function of memoryless sources allowing countably infinite alphabets.
In [27], Kostina et al. studied the fundamental limits of the minimum average length of lossless and lossy
variable-length compression, allowing a nonzero error probability ε ∈ [0, 1) for almost lossless compression.
The bounds in [27] were used to obtain a Gaussian approximation on the speed of convergence of the minimum
average length, which was shown to be quite accurate for all but small blocklengths. In [24], Koga and Yamamoto
January 30, 2018

DRAFT

4

followed an information-spectrum approach to obtain asymptotic properties of the codeword lengths for prefix
fixed-to-variable source codes, allowing decoding errors. This work was refined in the non-asymptotic setting
by Kuzuoka [28], which bounds the cumulant generating function of the codeword lengths via the use of the
smooth Rényi entropy.
B. Organization of the paper
Section II defines the Rényi information measures, and summarizes those properties used in this paper.
Section III derives upper and lower bounds on the minimal guessing moments of a random variable taking a
finite number of values where side information on its value may be available. These bounds improve earlier
results by Arikan [1] and Boztaş [6] in the non-asymptotic regime. Section III also derives tight lower and upper
bounds which establish relationships between the MAP error probability in M -ary hypothesis testing, and the
moments of the optimal guessing function for correctly identifying X when side information Y is available. The
bounds on the guessing moments are applied in Section IV to optimal variable-length lossless data compression.
We derive improved bounds on the normalized cumulant generating function of the codeword lengths for fixed-tovariable optimal codes, and on the non-asymptotic reliability function of discrete memoryless sources, tightening
earlier results by Courtade and Verdú [16]. Following up the aforementioned work by Kuzuoka [28], Section V
relies on techniques in Sections III and IV in order to derive improved lower bounds on the cumulant generating
function of the codeword lengths for fixed-to-variable source coding allowing errors via the use of the smooth
Rényi entropy ([12], [25], [36], [37]). The bounds in Section V are derived for source codes allowing a given
maximal or average error probability.
II.

P RELIMINARIES

The information measures used in this paper apply to discrete random variables.
Definition 1: [38] Let X be a discrete random variable taking values on a finite or countably infinite set X ,
and let PX be its probability mass function. The Rényi entropy of order α ∈ (0, 1) ∪ (1, ∞) is given by1
X
1
Hα (X) = Hα (PX ) =
log
PXα (x).
1−α

(2)

x∈X

By its continuous extension,

H0 (X) = log {x ∈ X : PX (x) > 0} ,

(3)

H1 (X) = H(X),

(4)

H∞ (X) = log

1

1
pmax

(5)

Unless explicitly stated, the logarithm base can be chosen by the reader, with exp indicating the inverse function of log.

January 30, 2018

DRAFT

5

where H(X) is the entropy of X , and
pmax = max PX (x).
x∈X

(6)

All definitions in this section extend in a natural way to random vectors.
Lemma 1: [38] Let X n = (X1 , . . . , Xn ) be an n-dimensional random vector with independent components.
Then, for all α ∈ [0, ∞],
n

Hα (X ) =

n
X

Hα (Xi ).

(7)

i=1

Note however that in contrast to the Shannon entropy, Hα (X n ) may exceed the right side of (7) when α 6= 1
and {Xi } are dependent.
Definition 2: [38] Given probability mass functions P and Q on a finite or countably infinite set X , the Rényi
divergence of order α > 0 is defined as follows:
•

If α ∈ (0, 1) ∪ (1, ∞), then
Dα (P kQ) =

•

X
1
log
P α (x) Q1−α (x).
α−1

(8)

x∈X

By the continuous extension of Dα (P kQ), the Rényi divergences of orders 0, 1, and ∞ are defined as

D0 (P kQ) = − log Q {x ∈ X : P (x) > 0} ,
D1 (P kQ) = D(P kQ),
D∞ (P kQ) = log sup
x∈X

P (x)
,
Q(x)

(9)
(10)
(11)

where D(P kQ) denotes the relative entropy.
Properties of the Rényi divergence were studied in [5], [19], [41, Section 8] and [45]. The Rényi divergence of
negative orders is defined by extending (8) to α ∈ (−∞, 0) [19, Section 5].
Lemma 2: [19, Section 5] The following properties are satisfied by the Rényi divergence:
•

For all α 6= 0, Dα (P kQ) = 0 if and only if P = Q.

•

Dα (P kQ) ∈ [0, ∞] for α ∈ [0, ∞], and Dα (P kQ) ∈ [−∞, 0] for α ∈ [−∞, 0) (with the continuous

extension where D−∞ (P kQ) , lim Dα (P kQ) [19, (81)]).
α→−∞

Definition 3: For all α ∈ (0, 1) ∪ (1, ∞), the binary Rényi divergence of order α, denoted by dα (pkq) for
(p, q) ∈ [0, 1]2 , is defined as Dα ([p 1 − p]k[q 1 − q]). It is the continuous extension to [0, 1]2 of


1
dα (pkq) =
log pα q 1−α + (1 − p)α (1 − q)1−α .
α−1

(12)

Definition 4: [4] Let PXY be defined on X × Y , where X is a discrete random variable. The Arimoto-Rényi

conditional entropy of order α ∈ [0, ∞] of X given Y is defined as follows:
January 30, 2018

DRAFT

6

•

If α ∈ (0, 1) ∪ (1, ∞), then
Hα (X|Y ) =



α
log E 
1−α

X

α
PX|Y

x∈X

!1
α
(x|Y ) 



X
α
1−α
=
log
PY (y) exp
Hα (X|Y = y) ,
1−α
α

(13)

(14)

y∈Y

where (14) applies if Y is a discrete random variable.
•

By its continuous extension, the Arimoto-Rényi conditional entropy of orders 0, 1, and ∞ are defined as
H0 (X|Y ) = sup H0 (X | Y = y),

(15)

H1 (X|Y ) = H(X|Y ),

(16)

y∈Y

H∞ (X|Y ) = log

1
h
i.
E max PX|Y (x|Y )

(17)

x∈X

Properties of the Arimoto-Rényi conditional entropy were studied in [20], [39] and [42].
As in [42, Section 4], we find several useful results satisfied by the Arimoto-Rényi conditional entropy of
negative orders.
Another Rényi information measure used in this paper is the smooth Rényi entropy, introduced by Renner
and Wolf [37] (after a different definition in [36]).
Definition 5: [37] Let X be a discrete random variable taking values on X , and let PX denote the probability
mass function of X . Let α ∈ (0, 1) ∪ (1, ∞) and ε ∈ [0, 1). The ε-smooth Rényi entropy of order α is given by
Hα(ε) (X) =

1
1−α

min

µ∈B (ε) (PX )

log

X

µα (x)

(18)

x∈X

where B (ε) (PX ) is the following subset of sub-probability measures defined on X :
(
)
X
(ε)
B (PX ) , µ : X → [0, 1] :
µ(x) ≥ 1 − ε, µ(x) ≤ PX (x), ∀x ∈ X .

(19)

x∈X

The ε-smooth Rényi entropy becomes the Rényi entropy when ε = 0, i.e.,
Hα(0) (X) = Hα (X)

(20)

for all α ∈ (0, 1) ∪ (1, ∞).
(ε)

Properties of Hα (X) were studied in [25] and [37].
Lemma 3: [25, Theorem 1] Let X be a random variable taking values on a finite set X = {x1 , . . . , xM },
whose elements are ordered such that
PX (x1 ) ≥ PX (x2 ) ≥ . . . ≥ PX (xM ),

(21)

and let ε ∈ [0, 1). Then,
January 30, 2018

DRAFT

7

a) For α ∈ (0, 1), the minimum in the right side of (18) is achieved by µ1 ∈ B (ε) (PX ) given by


PX (xi ),
i = 1, . . . , Jε − 1





JX
ε −1

PX (xj ),
i = Jε
µ1 (xi ) = 1 − ε −


j=1





0,
i = J + 1, . . . , M

(22)

ε

with

(

Jε = min 1 ≤ j ≤ M :

j
X
i=1

)

PX (xi ) ≥ 1 − ε .

(23)

b) For α > 1, the minimum in the right side of (18) is achieved by µ2 ∈ B (ε) (PX ) given by


β,
i = 1, . . . , Kβ
µ2 (xi ) =

PX (xi ),
i = Kβ + 1, . . . , M

(24)

where β ∈ (0, 1) and Kβ ∈ {1, . . . , M } are jointly selected such that
M
X
i=1

µ2 (xi ) = 1 − ε,

(25)


Kβ = max 1 ≤ j ≤ M : PX (xj ) ≥ β .

(26)

Remark 1: The sub-probability measures µ1 , µ2 ∈ B (ε) (PX ) in Lemma 3 are independent of α for α ∈ (0, 1)
or α > 1, respectively.
Lemma 4: Under the assumption in Lemma 3, the following inequalities hold for ε ∈ (0, 1):
a) If α ∈ (0, 1)
1
1
1
log
≤ Hα(ε) (X) ≤
log
α−1
1−ε
α−1



1
1−ε



+ log



1
µ1 (xJε )



(27)

with Jε as defined in (23).
b) If α > 1
1
1
1
log
≤ Hα(ε) (X) ≤
log
α−1
1−ε
α−1



1
1−ε



+ log



1
min{Pmin , β}



(28)

where Pmin denotes the minimal non-zero mass of PX , and β is defined in (24)–(26).
Proof: From (22) and (24), it follows that for all x ∈ X
µ1 (x) ≤ µα1 (x) ≤ µ1 (x) µα−1
(xJε ),
1

α ∈ (0, 1),

α−1
µ2 (x) min{Pmin
, β α−1 } ≤ µα2 (x) ≤ µ2 (x),

α > 1.

(29)
(30)

The bounds in (27) and (28) can be verified from Definition 5, (22), (25), (29) and (30).
Remark 2: The left inequality in (27) can be obtained from [37, Lemma 2].
January 30, 2018

DRAFT

8

The following result readily follows from Lemma 4.
Corollary 1: Under the assumption in Lemma 3, for ε ∈ (0, 1),
lim Hα(ε) (X) = −∞,

(31)

lim Hα(ε) (X) = +∞.

(32)

α↑1

α↓1

Remark 3: In contrast to Hα (X) which is non-negative, continuous and monotonically non-increasing in α
(ε)

when X takes values on a finite set, Corollary 1 shows that these properties do not fully extend to Hα (X) with
(ε)

ε ∈ (0, 1). Bearing in mind the discontinuity shown in Corollary 1, Hα (X) is monotonically non-increasing

on both α ∈ (0, 1) and α ∈ (1, ∞) [37, Lemma 1].
III.

I MPROVED B OUNDS ON G UESSING M OMENTS

This section provides improved upper and lower bounds on the guessing moments of a discrete random
variable. The upper bounds in this section correspond to the case where the guessing function is a ranking
function.

A. Key result
Theorem 1: Given a discrete random variable X taking values on a set X , a function g : X → (0, ∞), and
a scalar ρ 6= 0, then
1)

"
#
X
1
sup
H β (X) − log
g −β (x)
β+ρ
β
β∈(−ρ,+∞)\{0}
x∈X

1
≤ log E[g ρ (X)]
ρ
"
#
X
1
−β
≤
inf
H β (X) − log
g (x) .
β+ρ
β∈(−∞,−ρ)\{0} β

(33)
(34)

x∈X

2) For τ ∈ R, define the probability mass function

g −τ (x)
Qτ (x) = P −τ
,
g (a)

x ∈ X,

(35)

a∈X

provided that the sum in the right side of (35) is finite. The following results hold:
a) If PX = Qρ and X is a finite set, then
1
1
log E[g ρ (X)] = − log
ρ
ρ

January 30, 2018

!
1 X −ρ
g (x) .
|X |

(36)

x∈X

DRAFT

9

b) If PX = Qν with ν > 0 and ν 6= ρ, then the supremum in the left side of (33) is attained at β = ν − ρ,
and the inequality in (33) is an identity. Conversely, if (33) is an identity and the supremum is attained
at β ∗ ∈ (−ρ, +∞) \ {0}, then PX = Qρ+β ∗ .
c) If PX = Qν with ν < 0 and ν 6= ρ, then the infimum in the right side of (34) is attained at β = ν − ρ,
and the inequality in (34) is an identity. Conversely, if (34) is an identity and the infimum is attained at
β ∗ ∈ (−∞, −ρ) \ {0}, then PX = Qρ+β ∗ .

Proof: It is instructive to prove a weaker result first where instead of optimizing with respect to β , we
simply take β = 1 in the upper/lower bound.
Let α 6= 0, and let Rα be the scaled probability mass function defined by
1

P α (x)
Rα (x) = P X 1
,
PXα (a)

x ∈ X.

(37)

a∈X

Then,
1
D1+ρ (R1+ρ kQ1 ) = log
ρ

X

!

PX (x)g ρ (x)

x∈X

1
= log E[g ρ (X)] + log
ρ

+ log

X

x∈X

1
g(x)

!

X

x∈X

1
g(x)

−H

1
1+ρ

!

1+ρ
−
log
ρ

(X)

X

x∈X

1
1+ρ

!

PX (x)

(38)

(39)

where (38) follows from (8), (35) and (37); (39) is due to (2). Since D1+ρ (R1+ρ kQ1 ) ≥ 0 for ρ > −1 (see
Lemma 2), the non-negativity of the right side of (39) implies that
#
"
X
1
1
−β
ρ
g (x)
log E[g (X)] ≥
H β (X) − log
β+ρ
ρ
β

(40)

the non-positivity of the right side of (39) implies that
"
#
X
1
1
log E[g ρ (X)] ≤
H β (X) − log
g −β (x)
β+ρ
ρ
β

(41)

x∈X

holds for β = 1 and ρ ∈ (−1, 0) ∪ (0, ∞); furthermore, since D1+ρ (R1+ρ kQ1 ) ≤ 0 for ρ < −1 (see Lemma 2),

x∈X

holds for β = 1 and ρ ∈ (−∞, −1).

We proceed to show (40) and (41) for the range of β specified in (33) and (34) respectively. Consider next
ρ 6= 0 and β 6= 0. Let ρe , βρ .

To prove (33):

i) If β ∈ (−ρ, 0) with ρ ∈ (0, ∞), then ρe ∈ (−∞, −1). Since 1 ∈ (−∞, −ρe), (40) follows from the specialized
version of (41) with β ← 1 and (ρ, g) ← (ρe, g β ).

ii) If β ∈ (0, ∞) with ρ ∈ (0, ∞), then ρe ∈ (0, ∞); and if β ∈ (−ρ, ∞) with ρ ∈ (−∞, 0), then ρe ∈ (−1, 0).
In both cases, 1 ∈ (−ρe, ∞) and, consequently, (40) follows from its specialized version with β ← 1 and
(ρ, g) ← (ρe, g β ).

January 30, 2018

DRAFT

10

To prove (34):
iii) If β ∈ (−∞, −ρ) with ρ ∈ (0, ∞), then ρe ∈ (−1, 0); and if β ∈ (−∞, 0) with ρ ∈ (−∞, 0), then
ρe ∈ (0, ∞). In both cases 1 ∈ (−ρe, ∞), and therefore (41) follows from the specialized version of (40)

with β ← 1 and (ρ, g) ← (ρe, g β ).

iv) If β ∈ (0, −ρ) with ρ ∈ (−∞, 0), then ρe ∈ (−∞, −1); this yields (41) from its specialized version with
β ← 1 and (ρ, g) ← (ρe, g β ).

To prove Item 2):
•
•

Suppose the set X is finite. By letting τ = ν in (35), the identity in (36) follows easily.

∗

Suppose that PX = Qν with ν > 0 and ν 6= ρ. Let β ∗ = ν − ρ and let (ρ, g) ← ( βρ∗ , g β ), which yields
Q1 ← Qβ ∗ (see (35)), R1+ρ ← Rν/β ∗ , and

1
1+ρ

←

β∗
β ∗ +ρ .

Then, from (38)–(39),
!
X 1
β∗
Dν/β ∗ (Rν/β ∗ kQβ ∗ ) =
log E[g ρ (X)] + log
− H ∗β∗ (X).
β +ρ
ρ
g β ∗ (x)

(42)

x∈X

Since by assumption PX = Qν , it is easy to verify from (35) and (37) that Rν/β ∗ = Qβ ∗ . Hence, both
sides of (42) are equal to zero, which therefore implies that the supremum in the left side of (33) is
attained at β = β ∗ ∈ (−ρ, +∞) \ {0}, and the inequality in (33) is an identity. This proves the first part
of Item 2b). To prove its second part, assume that (33) is an identity and the supremum is attained at β ∗

in the range of β specified in (33). This implies that the right side of (42) is equal to zero, and so is its
left side. In view of Lemma 2, since ν = 0, it follows that Rν/β ∗ = Qβ ∗ which then gives that PX = Qν .
•

The proof of Item 2c) is analogous to the proof of Item 2b).

Remark 4: Theorem 1 can be proved in the following alternative way: For β 6= 0, let
α=

ρ+β
.
β

(43)

It can be verified from (8), (35) and (37) that
β
Dα (Rα kQβ ) = log E[g ρ (X)] + log
ρ

X

x∈X

!

g −β (x)

−H

β
β+ρ

(X),

(44)

and then, in view of Lemma 2, the following cases are considered for the free parameter β :
i) If β ∈ (−ρ, ∞) and β > 0, then α > 0 and Dα (Rα kQβ ) ≥ 0; hence, the right side of (44) is non-negative,
and dividing it by β gives (40);
ii) If β ∈ (−ρ, ∞) and β < 0, then α < 0, and therefore Dα (Rα kQβ ) ≤ 0; since the right side of (44) is
non-positive, dividing it by β gives (40);
iii) If β ∈ (−∞, −ρ) and β < 0, then α > 0 and Dα (Rα kQβ ) ≥ 0; hence, the right side of (44) is non-negative,
and dividing it by β gives (41);
January 30, 2018

DRAFT

11

iv) If β ∈ (−∞, −ρ) and β > 0, then α < 0, and therefore Dα (Rα kQβ ) ≤ 0; since the right side of (44) is
non-positive, dividing it by β gives (41).
This gives the lower and upper bounds in (33) and (34), respectively, after an optimization of the right sides of
(40) and (41) over the free parameter β ∈ (−ρ, ∞) \ {0} and β ∈ (−∞, −ρ) \ {0}, respectively. Item 2) can be
proved in a similar way to our earlier proof by relying on (43), (44), and Lemma 2; note that in view of (35),
(37) and (43), if β = ν − ρ, then Rα = Qβ if and only if PX = Qν .
Remark 5: For ρ > 0, the supremum over β in the right side of (33) involves negative orders of the Rényi
entropy whenever β ∈ (−ρ, 0). As shown in Example 1, the optimal value of β ∈ (−ρ, ∞)\{0} can be negative;
furthermore, for every such β , Theorem 1 asserts the existence of a probability mass function for which (33) is
achieved with equality. Allowing Rényi entropy of negative orders in Theorem 1 is therefore beneficial.
The particularization of Item 1) in Theorem 1 to β = 1 yields the following, generally looser, bound:
Corollary 2: [16, Lemma 2] Let X and g be as in Theorem 1, and ρ ∈ (−1, 0) ∪ (0, ∞). Then,
X 1


1
log E g ρ (X) ≥ H 1 (X) − log
.
1+ρ
ρ
g(x)

(45)

x∈X

Remark 6: The proof of Corollary 2, which serves as a first step in proving Theorem 1, differs from its proof

in [16, Lemma 2] (see also [1, Theorem 1] for a specialized version where ρ > 0). The proofs in [1] and [16]
rely on the reverse Hölder inequality, whereas the proof here is based on the Rényi divergence.
B. Lower bounds
Theorem 1 is applied in this section to derive lower bounds on guessing moments with or without side
information, improving the bounds in [1].
Theorem 2: Let X be a random variable taking values on the finite set X = {1, . . . , M }, and let g : X → X
be an arbitrary guessing function. Then, for every ρ 6= 0,

with

i


1
1h
H β (X) − log uM (β)
log E g ρ (X) ≥
sup
β+ρ
ρ
β∈(−ρ,∞)\{0} β

uM (β) =

January 30, 2018


5
1


−
log
M
+
γ
+

e

2M
6(10M 2 + 1)











(M + 1)1−β
(M + 1)−β

min ζ(β) −
−
, uM (1)


β−1
2



1−β
1 h



1
+
M + 21
−


1
−
β









M 1−β − 1 1 



+ 2 1 + M −β
1−β

i

3 1−β
2

(46)

β = 1,

β > 1,

(47)
|β| < 1,
β ≤ −1
DRAFT

where γ ≈ 0.5772 is the Euler-Mascheroni constant, and ζ(β) =

∞
P

n=1

12
1
nβ

is the Riemann zeta function for β > 1.

Proof: Since g : X → X is a one-to-one function with X = {1, . . . , M },
X

x∈X

g

−β

M
X
1
(x) =
.
iβ

(48)

i=1

In view of (33), we derive (46) by proving that
M
X
1
≤ uM (β),
iβ
i=1

M
X
1
≥ uM (β),
iβ
i=1

β ≥ 0,

(49a)

β≤0

(49b)

where uM (β) is given in (47). Note that the restriction β > −ρ in (46) is due to (33). The proof of (49a) and
(49b) is deferred to Appendix A.
Remark 7: Specializing Theorem 2 to β = 1 and using uM (1) ≤ 1 + loge M for M ≥ 2, we obtain



1
log E g ρ (X) ≥ H 1 (X) − log 1 + loge M
1+ρ
ρ

(50)

for ρ ∈ (−1, ∞). This bound was obtained in the range ρ > 0 by Arikan [1, (1)].
The following remark justifies the utility of Theorem 2.


Remark 8: Since Theorem 1 also applies to guessing functions, it gives a lower bound on ρ1 log E g ρ (X)
M
P
1
where uM (β) in (46)–(47) is replaced by the finite sum
j β for β ∈ (−ρ, ∞) \ {0}. While numerical evidence
j=1

shows that it is slightly better than the bound in Theorem 2 for large M , the latter bound is much easier to
compute if M is large.

The following simple example illustrates the improvement afforded by the lower bound in Theorem 2, as
well as the sub-optimality of β = 1.
Example 1: Let X be geometrically distributed restricted to {1, . . . , M } with the probability mass function
PX (k) =
24
25

(1 − a) ak−1
,
1 − aM

k ∈ {1, . . . , M }

(51)

and M = 128. Since PX is monotonically decreasing on {1, . . . , M }, the optimal guessing
 6

function is gX (i) = i for i ∈ {1, . . . , M }. Figure 1 compares 61 loge E gX
(X) with its lower bounds in (46)

where a =

and (50). The numerical results exemplify the sub-optimality of β = 1 in the right side of (46). Not only is the

improvement over the lower bound in [1, (1)] significant, but the improved lower bound is very close to the
actual value of the sixth guessing moment. Furthermore, the improved lower bound is attained at β = −2.85,
thereby showing the benefit of allowing negative orders in the definition of Rényi entropy.
Remark 9: Massey [31] obtained a lower bound on the expected value of the minimal number of guesses for
correctly guessing the value of a discrete random variable X which does not necessarily take a finite number

January 30, 2018

DRAFT

13

4

⇥ 6
⇤
1
loge E gX
(X)
6

3

2

1

0
6
Fig. 1.

Comparison of

1
6

4

2

0 1 2

4

6

8


 6
(X) = 4.084 for the random variable X in Example 1 with its lower bounds. The lower bound
loge E gX

in (50) is equal to 2.953, while Theorem 2 improves this lower bound to 4.078 (attained at β = −2.85).

of values:
H(X) ≤ E[g(X)] h



1
E[g(X)]



≤ log E[g(X)] + log e,

(52)
(53)

where h is the binary entropy function, and (52) is achieved with equality if and only if X is geometrically distributed. The idea behind (52) is that H(X) = H(g(X)) (since X and g(X) are in one-to-one correspondence),
and the entropy of the positive integer-valued random variable g(X) with a given value of its expectation is
maximized when X is geometrically distributed, which gives the right side of (52). Note that (52) provides
an implicit lower bound on E[g(X)] as a function of the Shannon entropy H(X), whereas (53) gives a looser
though explicit lower bound.
Massey’s bound (52) can be generalized to obtain a lower bound on the ρ-th moment of the guessing function
as a function of Hα (X) for arbitrary α, ρ > 0. To this end, we first rely on the basic equality
Hα (X) = Hα (g(X))

(54)

since g is a one-to-one function, and then we seek the distribution of the random variable Z = g(X), taking
values on {1, . . . , M } with possibly M = ∞, which maximizes Hα (Z) under the equality constraint
E[Z ρ ] = θ

(55)

for fixed θ > 1. The problem of maximizing the Rényi entropy under general equality constraints was studied by
Bunte and Lapidoth (see [10, Theorem II.1]) in the setting of continuous random variables. In the discrete setting,
January 30, 2018

DRAFT

14

a similar proof which relies on the non-negativity of Sundaresan’s divergence [47] provides the maximizing
distribution of the Rényi entropy Hα (Z) for a fixed value of E[Z ρ ]:

1

c (1 + λnρ ) α−1 1{1 ≤ n ≤ M },
α ∈ (0, 1), λ > −M −ρ
PZ (n) =
1

c (1 + λnρ ) α−1
1{n ∈ T },
α>1

(56)

where T , Tλ,ρ = {1, . . . , M } ∩ {n : 1 + λnρ ≥ 0}, and λ ∈ R is set to satisfy (55) with the normalizing
constant c in (56). Hence, we get from (54) and (56) that
Hα (X) ≤ Hα (Z)

(57)

with equality for the maximizing distribution PZ in (56) which is selected to satisfy (55). An analogous way to
view this problem is to minimize E[g ρ (X)] for a given value of Hα (X). This leads to an extension of Massey’s
bound in (52) which, however, does not lend itself to a closed-form generalized bound and its computation is
rather involved (especially, for α > 1). The lower bound in Theorem 2, on the other hand, can be calculated
more easily.

C. Upper bounds
The average number of guesses is minimized by taking the guessing function to be the ranking function gX ,
for which gX (x) = k if PX (x) is the k -th largest mass [31]. Although the tie breaking affects the choice of gX ,
the distribution of gX (X) does not depend on how ties are resolved. Not only does this strategy minimize the
average number of guesses, but it also minimizes the ρ-th moment of the number of guesses for every ρ > 0.
Theorem 3: [1, Proposition 4] Let X be a discrete random variable taking values on a set X , and let gX be
the ranking function according to PX . Then, for all ρ > 0,

ρ
E[gX
(X)] ≤ exp ρH
The following result tightens Theorem 3.

1
1+ρ


(X) .

(58)

Theorem 4: Under the assumptions in Theorem 3, for all ρ ≥ 0,


i


1 h
ρ
exp ρH 1 (X) − 1 + exp (ρ − 1)+ H 1 (X)
E[gX
(X)] ≤
1+ρ
ρ
1+ρ

(59)

where (x)+ , max{x, 0} for x ∈ R.

Proof: From [6, Lemma 2], if ρ ≥ 0, then
 1+ρ


1+ρ 
E gX
(X) − E gX (X) − 1
≤

January 30, 2018

X

x∈X

1
1+ρ

!1+ρ

PX (x)


= exp ρH

1
1+ρ


(X) .

(60)

DRAFT

15

At this point we deviate from the analysis in [6]. For ρ ≥ 1, let r : [1, ∞) → R and v : [0, ∞) → R be given by
r(u) =

u1+ρ − (u − 1)1+ρ − 1
− (u − 1)ρ ,
1+ρ

v(u) = uρ ,

u≥1

u ≥ 0.

(61)
(62)

Expressing the derivative of (61) with the aid of (62) implies that, for all u ≥ 1,
r0 (u) = v(u) − v(u − 1) − v 0 (u − 1) ≥ 0,

(63)

where the inequality is due to the convexity of v(·) in (0, ∞). Since r(1) = 0, it follows that r(·) is non-negative
in [1, ∞). Invoking the result in (60), along with E[r(gX (X))] ≥ 0, implies that for ρ ≥ 1


i

ρ 
1 h
exp ρH 1 (X) − 1 .
E gX (X) − 1
≤
1+ρ
1+ρ

(64)

A replacement of ρ by ρ − 1 in (60) gives that for ρ ≥ 1



 ρ


ρ 
E gX
(X) − E gX (X) − 1
≤ exp (ρ − 1) H 1 (X) .

(65)

ρ

Hence, for ρ ≥ 1, adding (64) and (65) yields


i


1 h
ρ
exp ρH 1 (X) − 1 + exp (ρ − 1)H 1 (X) .
E[gX
(X)] ≤
1+ρ
ρ
1+ρ

(66)

This proves (59) for ρ ≥ 1. We next consider the case where ρ ∈ (0, 1). Lemma 8 in Appendix B yields
uρ ≤

and therefore, for ρ ∈ (0, 1),

 ρ

E gX
(X) ≤

u1+ρ − (u − 1)1+ρ + ρ
,
1+ρ

u ≥ 1,

i
h
1+ρ i
1  h 1+ρ
ρ
E gX (X) − E gX (X) − 1
+
.
1+ρ
1+ρ

(67)

(68)

Combining (60) and (68) gives (59) for ρ ∈ (0, 1). The case ρ = 0, for which (59) holds with equality, is trivial.
Remark 10: Bound (59) strictly (unless X is deterministic) improves the bound in (58). This holds for
ρ ∈ (0, 1) since H

(X) ≥ 0; for ρ ∈ [1, ∞), the difference between the bounds in (58) and (59) is equal to

  1 h


i


1
1
1
exp ρ H (X) −
exp ρH (X) − 1 + exp (ρ − 1)H (X)
1+ρ
1+ρ
ρ
1+ρ
!1+ρ
!ρ
1
X
X 1
ρ
1
PX1+ρ (x)
−
PXρ (x) +
=
1+ρ
1+ρ
x∈X
x∈X
!1+ρ
!ρ
1
1
X
X
ρ
1
≥
PX1+ρ (x)
−
PX1+ρ (x) +
(69)
1+ρ
1+ρ
x∈X
x∈X
!
1
X
=s
PX1+ρ (x)
(70)
1
1+ρ

x∈X

January 30, 2018

DRAFT

16

1

1

where (69) holds since PXρ (x) ≤ PX1+ρ (x), and (70) holds with s : [1, ∞) → R given by


ρu
1
ρ
s(u) = u
−1 +
, u ≥ 1.
1+ρ
1+ρ
In (70), note that

P

x∈X

1

PX1+ρ (x) ≥

P

(71)

PX (x) = 1. The right side of (70) is non-negative since s(1) = 0, and

x∈X

s0 (u) = ρ(u − 1)uρ−1 > 0

(72)

for all u > 1. This shows that the bound in (59) is at least as tight as the bound in (58) with a strict improvement
unless X is deterministic.
In the range ρ ∈ [0, 2], we can tighten (59) according to the following result.
Theorem 5: Under the assumptions in Theorem 3,
a) For ρ ∈ [0, 1]


 ρ − (1 − ρ)(2ρ − 1)(1 − p )
1
max
exp ρH 1 (X) +
.
1+ρ
1+ρ
1+ρ

(73)

 1
 ρ2 − ρ − 1


1
exp ρH 1 (X) + exp (ρ − 1)H 1 (X) +
.
1+ρ
ρ
1+ρ
ρ
ρ(1 + ρ)

(74)

ρ
E[gX
(X)] ≤

b) For ρ ∈ [1, 2]
ρ
E[gX
(X)] ≤

Furthermore, both (73) and (74) hold with equality if X is deterministic.
Proof: See Appendix B.

Remark 11: Particularizing (74) to ρ = 1 and ρ = 2, we recover the bounds on the first and second moments
in [6, Theorem 3]. Furthermore, the bounds in (73) and (74) provide a continuous transition at ρ = 1.
Theorem 6: Under the assumptions in Theorem 3, for ρ ≥ 2,
ρ
E[gX
(X)]

≤1+

where {cj (ρ)} is given by

cj (ρ) =















bρc
X
j=0

h

cj (ρ) exp (ρ − j) H

1
1+ρ

j=0

1
2

j=1

ρ . . . (ρ − j + 2)





2j






 ρ . . . (ρ − j + 2)
2j−1 (ρ − j + 1)

1
1+ρ−j


i
(X) − 1 ,

(75)

(76)
j ∈ {2, . . . , bρc − 1}
j = bρc

and bxc denotes the largest integer that is smaller than or equal to x.
Proof: See Appendix C.

January 30, 2018

DRAFT

17

Remark 12: In contrast to [6, Theorem 3], the results in Theorems 5 and 6 provide an explicit upper bound
ρ
on E[gX
(X)] for ρ ∈ (0, ∞) as a function of Rényi entropies of X . Note also that the upper bounds in (74)

and (75) coincide at ρ = 2.
Remark 13: Numerical evidence shows that none of the bounds in (59) and (75) supersedes the other for
ρ > 2 (as it is next illustrated in Examples 2 and 3). Since (74) and (75) coincide at ρ = 2, Theorem 5-b)

implies that the bound in (75) is tighter than (59) for this value of ρ.
Example 2: Let X ∈ {1, . . . , 32} have the probability distribution in (51) with a = 0.9 and M = 32. Table I
compares

1
3

3 (X)] to its various lower and upper bounds. Notice that in this example, the upper bound
loge E[gX

in (75) improves the bound in (59).
TABLE I.

C OMPARISON OF

(50)

Theorem 2

lower bound

lower bound

1.864

2.593

1
3

1
3

3
loge E[gX
(X)] AND BOUNDS IN E XAMPLE 2.

3 (X)]
loge E[gX

(75)

(59)

(58)

exact value

upper bound

upper bound

upper bound

2.609

2.920

2.939

3.360

Example 3: Let X ∈ {1, . . . , 16} have the probability distribution in (51) with a = 0.9 and M = 16. Table II
compares

1
20

20 (X)] to its various lower and upper bounds. Note that in Table II, the lower bound in
loge E[gX

TABLE II.

C OMPARISON OF

(50)

Theorem 2

lower bound

lower bound

1.439

2.602

1
20

1
20

20
(X)] AND BOUNDS IN E XAMPLE 3.
loge E[gX

20 (X)]
loge E[gX

(75)

(59)

(58)

exact value

upper bound

upper bound

upper bound

2.606

2.662

2.657

2.767

(50) is quite weaker than the lower bound in Theorem 2, which shows an excellent match with its exact value.
In contrast to Example 2, Example 3 shows that the upper bound (75) may be weaker than (59).

D. Improved bounds on guessing moments with side information
This subsection extends the lower and upper bounds in Sections III-B and III-C to allow side information Y
for guessing the value of X . These bounds tighten the results in [1, Theorem 1] and [1, Proposition 4] for all
ρ > 0.

January 30, 2018

DRAFT

18

Theorem 7: Let X and Y be discrete random variables taking values on the sets X = {1, . . . , M } and Y ,
respectively. For all y ∈ Y , let g(·|y) be a guessing function of X given that Y = y . Then, for ρ ∈ (0, ∞),
i


1
1h
log E g ρ (X|Y ) ≥
sup
H β (X|Y ) − log uM (β)
(77)
β+ρ
ρ
β∈(−ρ,0)∪(0,∞) β
with uM (·) as defined in (47).
Proof:
E[g ρ (X|Y )] =

X

PY (y) E[g ρ (X|y)]

(78)

y∈Y

!
i
ρh
≥
PY (y) exp
sup
H β (X|Y = y) − log uM (β)
β+ρ
β∈(−ρ,0)∪(0,∞) β
y∈Y
 h
i
X
ρ
≥
sup
PY (y) exp
H β (X|Y = y) − log uM (β)
β+ρ
β
β∈(−ρ,0)∪(0,∞) y∈Y
 h
i
ρ
=
sup
exp
H β (X|Y ) − log uM (β)
β+ρ
β
β∈(−ρ,0)∪(0,∞)
X

(79)
(80)
(81)

where (79) follows from (46) with the conditional guessing function g(·|Y = y) : X → X where |X | = M ;
(81) follows from (14) with α =

β
ρ+β .

Remark 14: Similarly to Remark 7, the loosening of the result in Theorem 7 by replacing the supremum
over β ∈ (−ρ, 0) ∪ (0, ∞) in the right side of (77) with the value β = 1 and further using the inequality
uM (1) ≤ 1 + loge M for M ≥ 2 (see (47)) yields Arikan’s result in [1, (2)]. As explained in [1], Theorem 7 can

be used to obtain an improved non-asymptotic lower bound on the moments of the number of computational
steps used to decode tree codes by an arbitrary sequential decoder.
Theorem 8: Let X and Y be discrete random variables taking values on sets X and Y , respectively. For all
y ∈ Y , let gX|Y (·|y) be a ranking function of X given that Y = y . Then, for ρ ∈ (0, ∞),


i


1 h
ρ
E[gX|Y
(X|Y )] ≤
exp ρH 1 (X|Y ) − 1 + exp (ρ − 1)+ H 1 (X|Y ) .
1+ρ
ρ
1+ρ

(82)

For ρ ∈ (0, 1), (82) can be tightened to
ρ
E[gX|Y
(X|Y )] ≤

with


 ρ − (1 − ρ)(2ρ − 1)(1 − p∗ )
1
exp ρH 1 (X|Y ) +
1+ρ
1+ρ
1+ρ
p∗ , sup max pX|Y (x|y).
y∈Y x∈X

(83)

(84)

For ρ ∈ [1, 2], (82) can be tightened to
ρ
E[gX|Y
(X|Y )] ≤

January 30, 2018


 1

 ρ2 − ρ − 1
1
exp ρH 1 (X|Y ) + exp (ρ − 1)H 1 (X|Y ) +
.
1+ρ
ρ
1+ρ
ρ
ρ(1 + ρ)

(85)

DRAFT

19

Moreover, for ρ ≥ 2,
ρ
E[gX|Y
(X|Y )] ≤ 1 +

bρc
X
j=0

h

cj (ρ) exp (ρ − j) H

1
1+ρ−j


i
(X|Y ) − 1 ,

(86)

with {cj (ρ)} defined in (76).
Proof: From Theorem 4 and (78), for all ρ ∈ [1, ∞),
ρ
(X|Y )]
E[gX|Y






X
1 X
PY (y) exp ρH 1 (X | Y = y) − 1 +
≤
PY (y) exp (ρ − 1) H 1 (X | Y = y)
1+ρ
ρ
1+ρ
y∈Y

=

(87)

y∈Y


i



1 h
exp ρH 1 (X|Y ) − 1 + exp (ρ − 1) H 1 (X|Y )
1+ρ
ρ
1+ρ

where (87) follows from (59), and (88) follows from (14) with α =

1
1+ρ

and α =

1
ρ.

(88)

The proof of (82) for

ρ ∈ (0, 1) is similar.

Extending (73), (74) and (75) to (83), (85) and (86), respectively, relies on (14) and it is similar to the
extension of the result in Theorem 4 to (82).
Remark 15: The bound in (82) improves the result in [1, Proposition 4] since the superiority of the bound
in Theorem 4 over the result in Theorem 3 is preserved after the averaging in (78).
Remark 16: Following Remark 13, neither of the bounds in (82) and (86) supersedes the other for ρ ≥ 2.
Since (85) and (86) coincide for ρ = 2, it follows from Theorem 8 that the upper bound in (86) is tighter than
(82) for this value of ρ. Note that both bounds are tight if X , conditioned on Y , is deterministic, for which
ρ
they are equal to E[gX|Y
(X|Y )] = 1. Finally, note that the transition from (83) to (85) is continuous at ρ = 1.

E. Relationship between guessing moments and minimum probability of error
Let X and Y be discrete random variables,2 taking values on the sets X and Y respectively. The minimum
probability of error of X given Y , denoted by εX|Y , is achieved by the maximum-a-posteriori (MAP) decision
rule. Hence,
εX|Y =

X

y∈Y



PY (y) 1 − max PX|Y (x|y) .
x∈X

(89)

ρ
In contrast, the moments of the ranking function E[gX|Y
(X|Y )] quantify the number of guesses required for

correctly identifying the unknown object X on the basis of Y . It is therefore natural to establish relationships
between both quantities. First note that by definition,
1 − εX|Y = P[gX|Y (X|Y ) = 1].
2

(90)

The assumption that Y is a discrete random variable can be easily dispensed with.

January 30, 2018

DRAFT

20

In [42], we derived lower and upper bounds on εX|Y as a function of Hα (X|Y ) for an arbitrary order α.
In this section, Theorems 7–8 provide lower and upper bounds on guessing moments of a ranking function
gX|Y (X|Y ) as a function of Arimoto-Rényi conditional entropies. As a natural continuation to these studies,
ρ
we derive tight lower and upper bounds on E[gX|Y
(X|Y )] as a function of εX|Y .

Theorem 9: Let X and Y be discrete random variables taking values on sets X = {1, . . . , M } and Y ,
respectively. Then, for ρ > 0,
ρ
fρ (εX|Y ) ≤ E[gX|Y
(X|Y )]


M
X
≤ 1 +  M1−1
j ρ − 1 εX|Y

(91)
(92)

j=2

where the function fρ : [0, 1) → [0, ∞) is given by
fρ (u) = (1 − u)




1
ku =
.
1−u

ku
X
j=1

j ρ + [1 − (1 − u)ku ](ku + 1)ρ ,

u ∈ [0, 1)

(93)
(94)

Furthermore, the lower and upper bounds in (91) and (92) are tight:
•

•

Let pmax (y) = maxPX|Y (x|y) for y ∈ Y . The lower bound is attained if and only if pmax (y) = pmax is
x∈X
k
j
1
masses equal to pmax , and an additional
fixed for all y ∈ Y , and conditioned on Y = y , X has pmax
j
k
1
1
mass equal to 1 − pmax pmax whenever pmax is not an integer.
The upper bound is attained if and only if regardless of y ∈ Y , conditioned on Y = y , X is equiprobable
among its M − 1 conditionally least likely values on X .


Proof: For y ∈ Y and i ∈ {1, . . . , M }, let xi (y) ∈ X satisfy gX|Y xi (y)|y = i. By the definition of

gX|Y (·|·) on X × Y , it follows that

For ρ ∈ (0, ∞),




PX|Y x1 (y)|y ≥ PX|Y x2 (y)|y ≥ . . . ≥ PX|Y xM (y)|y .

ρ
E[gX|Y
(X|Y )] =

X

y∈Y

=

X

y∈Y

ρ
PY (y) E[gX|Y
(X|y)]

(

(96)

PY (y) max PX|Y (x|y) +
x∈X

= 1 − εX|Y +
≤ 1 − εX|Y
January 30, 2018

(95)

X

y∈Y

M
X

iρ PX|Y xi (y)|y

i=2

(

PY (y)

M
X

ρ

i PX|Y xi (y)|y

i=2

1 X
+
M −1
y∈Y

(

PY (y)

M
X
i=2

ρ

i

!



)

M
X
i=2



!)

(97)

(98)

PX|Y xi (y)|y



!)

(99)

DRAFT

21



 X
M
1 X
= 1 − εX|Y +
PY (y) 1 − max PX|Y (x|y)
iρ
x∈X
M −1
i=2
y∈Y
!
M
1 X ρ
i − 1 εX|Y
=1+
M −1

(100)

(101)

i=2

where (97) and (100) follow from (95); (98) and (101) follow from (89); (99) follows from Lemma 12 (see
Appendix D), for which we take the strictly monotonically increasing function f to be given by
f (i) = (i + 1)ρ ,

i = 1, . . . , M − 1,

(102)


and qi ← PX|Y xi+1 (y)|y . This proves the upper bound in (92). A necessary and sufficient condition for

attaining the upper bound in (92) follows from Lemma 12 and due to the strict monotonicity of the function
in (102) for ρ > 0. Hence, it follows that (99) is satisfied with equality if and only if, for every y ∈ Y ,

qi (y) , PX|Y xi+1 (y)|y is fixed for all i ∈ {1, . . . , M − 1}; due to (95), this is equivalent to the requirement

that regardless of y ∈ Y , conditioned on Y = y , the M − 1 least probable values of X are equiprobable.
To show (91), we write the conditional moment of the ranking function as
(
)
M
X
X

ρ
ρ
PY (y)
i PX|Y xi (y)|y ,
E[gX|Y (X|Y )] =
y∈Y

(103)

i=1

and we denote the conditional error probability given the observation Y = y by εX|Y (y) = 1 − pmax (y). Note
from (95) that x1 (y) is a mode of PX|Y (·|y), and we have

PX|Y x1 (y)|y = pmax (y) = 1 − εX|Y (y).

The inner sum in the right side of (103) is minimized, for a given value of εX|Y (y), by



1


1 − εX|Y (y)
i = 1, . . . ,


1 − εX|Y (y)








1
1
PX|Y (xi (y)|y) = 1 − (1 − ε
i=
+1
X|Y (y))


1 − εX|Y (y)
1 − εX|Y (y)





0
otherwise.

(104)

(105)

In order to show it, note that according to (95), any perturbation of PX|Y (·|y) in (105) necessarily shifts mass

from xi (y) to xj (y) with j > i; since {k ρ }k≥1 is positive and monotonically increasing in k for ρ > 0, this
can only increase the inner sum in the right side of (103).
From the minimizing conditional distribution in (105), for a given value of εX|Y (y), and (93)–(94)
M
X
i=1

January 30, 2018



iρ PX|Y xi (y)|y ≥ fρ εX|Y (y) .

(106)

DRAFT

22

Due to the convexity of fρ : [0, 1) → [0, ∞) in (93)–(94) for ρ > 0 (see Lemma 13 in Appendix D), and since
X
εX|Y =
PY (y)εX|Y (y),
(107)
y∈Y

the lower bound in (91) follows from (103), (106) and Jensen’s inequality. This also yields the necessary and

sufficient condition for the attainability of the bound in (91), as it specified in the statement of the theorem
(note that, from (104), pmax (y) is fixed for all y ∈ Y if and only if εX|Y (y) is so).
Remark 17: The lower and upper bounds in (91) and (92) coincide in each of the extreme cases εX|Y = 0
and εX|Y = 1 −

1
M.

The former and latter values refer, respectively, to the following cases:

•

X is a deterministic function of Y ,

•

X and Y are independent, and X is equiprobable.

Example 4: Let X and Y be random variables which take values

10 1




1 10
1 

PXY (x, y) (x,y)∈X 2 =

52  1 1

1 1

It follows from (108) that PY (y) =

1
4

on X = {1, 2, 3, 4}, and let

1 1


1 1 
.

10 1 

1 10

(108)

for all y ∈ X , and we can select the conditional ranking function of X

given Y to satisfy gX|Y (x|1) = x for all x ∈ X (since 1 is the most likely value of X given Y = 1, and 2,3,4
are conditionally equiprobable given Y = 1); moreover, symmetry in (108) yields
ρ
E[gX|Y
(X|Y )] =

1
13

(10 + 2ρ + 3ρ + 4ρ ) .

The result in (109) coincides with the upper bound in (92) since, regardless of y , PX|Y (x|y) =

(109)
1
13

for the

|X | − 1 = 3 least probable values of X given Y = y . This can be verified directly since it follows from (89)

and (108) that εX|Y =

3
13 ,

and then the upper bound in (92) (with M = 4) is equal to the right side of (109).

ρ
In the next example, we illustrate the locus of attainable values of (εX|Y , loge E[gX|Y
(X|Y )]) for a fixed M .

 P

M
1
1
ρ
;
The extreme cases identified in Remark 17 correspond to the points (0, 0) and 1 − M , loge M j=1 j

in these extreme cases, there is a one-to-one correspondence between the two quantities.

Example 5: Let X be a random variable taking values on X with |X | = M ≥ 2. Letting ρ = 1 in (91)–(94)
yields
1+

1
2 (1



1
+ εX|Y )
1 − εX|Y



−

1
2 (1



1
− εX|Y )
1 − εX|Y

2

≤ E[gX|Y (X|Y )] ≤ 1 + 12 M εX|Y

(110)

where both upper and lower bounds on the expected number of guesses in (110) are attainable for any value of
εX|Y ∈ [0, 1 −

1
M ].

The plots in Figure 2 illustrate the tight bounds in (110) for a fixed M .

In view of Theorems 2 and 9, the next result provides an explicit lower bound on εX|Y as a function of
Hα (X|Y ) for any non-zero α < 1.
January 30, 2018

DRAFT

23

1.5

⇥
⇤
loge EloggX|Y
E[g (X|Y
X|Y)] )

3

⇥
⇤
E[gX|Y(X|Y
(X|Y)] )
loge ElogegX|Y

2.5

1

X|Y

2

e

1.5

0.5

1

0.5

0

0

0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.8

1

"X|Y
X|Y

X|Y
"X|Y

Fig. 2.

0.6

Example 5: locus of attainable values of (εX|Y , loge E[gX|Y (X|Y )]). The random variable X takes M = 8 (left plot) or

M = 64 (right plot) possible values.

Theorem 10: Let X and Y be discrete random variables taking values on sets X = {1, . . . , M } and Y ,
respectively. Then, for all α ∈ (−∞, 0) ∪ (0, 1),



h

i





αρ

 exp α1 − 1 Hα (X|Y ) − log uM 1−α

− 1
εX|Y ≥ sup
M

ρ>0 


1 P ρ


j −1


M −1

(111)

j=2

with uM (·) as defined in (47).

Proof: Combining (77) and (92) yields, for every ρ > 0 and β ∈ (−ρ, 0) ∪ (0, ∞),
 h
i
exp βρ H β (X|Y ) − log uM (β) − 1
β+ρ
εX|Y ≥
.
M
1 P ρ
j −1
M −1

(112)

j=2

Fix α ∈ (−∞, 0) ∪ (0, 1), and let the above free parameters β and ρ satisfy ρ =

1
α


− 1 β (note that α cannot

be zero or larger than 1, as otherwise β ∈
/ (−ρ, 0) ∪ (0, ∞)). Supremizing the right side of (112) over ρ > 0
yields (111).
In [42], we derived the following lower bounds on εX|Y as a function of Hα (X|Y ):
1) A generalization of Fano’s inequality in [42, Theorem 3] holds for α > 0, and it is given by
Hα (X|Y ) ≤ log M − dα εX|Y k1 −

with dα (·k·) as defined in (12).
January 30, 2018

1
M



(113)

DRAFT

24

2) An explicit lower bound in [42, Theorem 6] holds for α < 0, and it is given by

i
1−αh
εX|Y ≥ exp
Hα (X|Y ) − log(M − 1) .
α

(114)

Example 6 includes numerical comparisons of the lower bounds on εX|Y in (111), (113) and (114).
Remark 18: Shannon’s inequality [44] (see also [50]) gives an explicit lower bound on εX|Y as a function

of H(X|Y ) when M is finite:
εX|Y ≥

1
H(X|Y )
,
6 log M + log log M − log H(X|Y )

(115)

and the right side of (115) does not depend on the base of the logarithm. The bound in (111) becomes trivial


αρ
in the limit where α ↑ 1 since, for any fixed ρ > 0, (47) implies that uM 1−α
→ 1, and therefore the lower
bound on εX|Y tends to zero in this case. Nevertheless, numerical experimentation shows that the convergence
of this bound in (111) to zero is only affected by values of α very close to 1, as it is illustrated in Example 6
with a comparison to Shannon’s lower bound in (115).
Example 6: Let X and Y be random variables taking values on X = {1, 2, 3, 4}, and let


9 3 4 9






9 9 3 4 
1 

.
PXY (x, y) (x,y)∈X 2 =

100 
 4 9 9 3 


3 4 9 9

It can be verified from (89) that εX|Y =
TABLE III.

16
25

(116)

= 0.640. Table III shows a slight advantage of the lower bound

E XAMPLE 6: L OWER BOUNDS ON εX|Y .

α

(111)

(113)

(114)

−1

0.463

–

0.447

− 12

0.475

–

0.355

− 14

0.482

–

0.206

1
5

0.494

0.523

–

1
2

0.502

0.530

–

4
5

0.510

0.536

–

in (113) over (111) for α ∈ (0, 1), and a superiority of the lower bound in (111) over (114) for some negative
values of α.
In view of Remark 18, the lower bound in (111) for α close to 1 is compared with Shannon’s lower bound
in (115). For α = 0.99, the lower bound in (111) is equal to 0.515 (note that it is slightly looser than (113),
which is equal to 0.540); on the other hand, the lower bound in (115) is equal to 0.146.
January 30, 2018

DRAFT

25

Theorem 9 establishes relationships between the ρ-th moment of the optimal guessing function, for fixed ρ > 0,
and the MAP error probability. This characterizes the exact locus of their attainable values, as it is shown in
Figure 2 for ρ = 1. A natural question is whether the MAP error probability can be uniquely determined on the
basis of the knowledge of these ρ-th moments for all ρ > 0. The following result answers this question in the
affirmative, also suggesting an easy way to determine the MAP error probability on the basis of the knowledge
of these ρ-th moments at an arbitrarily small right neighborhood of ρ = 0.
Theorem 11: Let X and Y be discrete random variables taking values on sets X = {1, . . . , M } and Y ,
respectively. For an integer k ≥ 0, let zk be given by
zk =

dk
ρ
(X|Y )]
E[gX|Y
dρk

ρ=0

.

(117)

Then,

εX|Y = 1 −

1
cM

z0

1

···

1

z1
..
.

loge 2
..
.

···
..
.

loge M
..
.

−1
zM −1 logM
2 ···
e

with

cM



log 2,


 e
M
= Y


loge k


k=2

(118)

−1
logM
M
e

M = 2,

Y

loge

2≤i<j≤M

j 
i

(119)
,

M ≥ 3.

Proof: Let xi (y) ∈ X be the element that satisfies (95) for i ∈ {1, . . . , M } and y ∈ Y , and consider the
ranking function gX|Y that satisfies
gX|Y (xi (y)|y) = i

for all i and y as above. Then,
ρ
E[gX|Y
(X|Y

)] =

X

y∈Y

=

X

y∈Y

(

PY (y)

X

)

ρ
PX|Y (x|y) gX|Y
(x|y)

x∈X

(

PY (y)

M
X

(120)

PX|Y (xi (y)|y) iρ

i=1

)

(121)

(122)

where (121) and (122) follow from (96) and (120), respectively. Swapping the order of summation in (122)
yields



M  X

X
ρ
E[gX|Y
(X|Y )] =
iρ
PX,Y (xi (y), y)


i=1

=

(123)

y∈Y

M
−1
X

(i + 1)ρ ui

(124)

i=0

January 30, 2018

DRAFT

26

where ui is the inner sum in the right side of (123) with i replaced by i + 1. Taking the k -th derivative of (124)
at ρ = 0, and recalling (117) yields

M
−1
X



ui ,



i=0
zk =
M
−1


X

ui logke (i + 1),



k = 0,

(125)
k ∈ {1, . . . , M − 1},

i=1

which gives the set of M linear equations

1
1
···


 0
loge 2
···

..
..

 0
.
.

−1
0 logM
2 ···
e



1
loge M
..
.
−1
logM
M
e











u0
u1
..
.
uM −1



 
 
 
=
 
 
 

z0
z1
..
.
zM −1










(126)

with the M unknown variables u> = (u0 , . . . , uM −1 ). The equations in (126) are linearly independent since
by Lemma 14 in Appendix D
1

1

···

1

0

loge 2
..
.

···
..
.

loge M
..
.

0

−1
0 logM
2 ···
e

= cM 6= 0

(127)

−1
logM
M
e

with cM as defined in (119), so u0 in (126) is uniquely determined. We have
εX|Y = 1 −

X

PX,Y (x1 (y), y)

(128)

y∈Y

= 1 − u0

(129)

where (128) follows from (89) and since, by definition, x1 (y) is a mode of PX|Y (·|y) for all y ∈ Y ; (129)
holds by the definition of u0 as the inner sum in the right side of (123) with i = 1. Finally, (118) follows from
(126)–(129) and Cramer’s rule.
Remark 19: Theorem 11 can be, alternatively, first proved without side information. Then, by replacing PX
by PX|Y (·|y), (128)–(129) hold for εX|Y =y ; finally, it holds by averaging in view of the linearity of u in z.
IV.

N ON -A SYMPTOTIC B OUNDS FOR O PTIMAL F IXED - TO -VARIABLE L OSSLESS C OMPRESSION

This section applies the improved bounds on guessing moments in Section III to analyze non-prefix one-to-one
binary optimal codes, which do not satisfy Kraft’s inequality. These codes are one-shot codes that assign distinct
codewords to source symbols; their average length, which is smaller than the Shannon entropy of the source, is
analyzed in [18, Section 7] and [49]. Preliminary material is introduced in Section IV-A, improved bounds on
January 30, 2018

DRAFT

27

the distribution of optimal codeword lengths are derived in Section IV-B, and improved non-asymptotic bounds
for fixed-to-variable codes are derived in Section IV-C.

A. Basic setup, notation and preliminaries
Definition 6: A variable-length lossless compression binary code for a discrete set X is an injective mapping:
f : X → {0, 1}∗ = {∅, 0, 1, 00, 01, 10, 11, 000, . . .}

(130)

where f (x) is the codeword which is assigned to x ∈ X ; the length of this codeword is denoted by `(f (x))

where ` : {0, 1}∗ → {0, 1, 2, . . .} with the convention that `(∅) = 0.

Definition 7: [51] A variable-length lossless source code is compact whenever it contains a codeword only
if all shorter codewords also belong to the code.
Definition 8: [51] Given a probability mass function PX on X , a variable-length lossless source code is
PX -efficient if for all (a, b) ∈ X 2 ,
`(f (a)) < `(f (b)) =⇒ PX (a) ≥ PX (b).

(131)

Definition 9: [51] Given a probability mass function PX on X , a variable-length lossless source code is
PX -optimal if it is both compact and PX -efficient.
∗ : X → {0, 1}∗ be a P -optimal variableThe optimality in Definition 9 is justified in Proposition 1. Let fX
X

length lossless source code. If |X | < ∞, then
a) ∅ is assigned to the most likely element in X .
b) All the 2` binary strings of length ` are assigned to the 2` -th through (2`+1 − 1)-th most likely elements
with ` ∈ {1, . . . , blog2 (1 + |X |)c − 1}. For example, 0 and 1 (or 1 and 0) are assigned, respectively, to the
second and third most likely elements in X .
c) If log2 (1 + |X |) is not an integer, then codewords of length blog2 (1 + |X |)c are assigned to each of the
remaining 1 + |X | − 2blog2 (1+|X |)c elements in X .

As long as |X | > 1, there is more than one PX -optimal code since compactness and PX -efficiency are
preserved by swapping codewords of the same length (and, if |X | = 2, then the second most likely element can
∗ (x)) for some x ∈ X
be either assigned 0 or 1). In the presence of ties among probabilities, the value of `(fX
∗ . The following result provides several relevant properties of optimal codes.
may depend on the choice of fX

Proposition 1: ([26], [51]) Fix a probability mass function PX on a finite set X . The following results hold

∗ : X → {0, 1}∗ :
for PX -optimal codes fX

∗ (X)) is invariant to the actual choice of f ∗ , and it only depends on P .
a) The distribution of `(fX
X
X

January 30, 2018

DRAFT

28

b) For every lossless data compression code f , and for all r ≥ 0,




 ∗


P ` f (X) ≤ r ≤ P ` fX
(X) ≤ r .

c)

(132)

Furthermore, the inequality in (132) is strict for some r ≥ 0 if f is not PX -optimal.
X

x∈X

∗

2−`(fX (x)) ≤ log2 (1 + |X |)

(133)

with equality if and only if |X | + 1 is a positive integral power of 2. Furthermore, all compact codes for X
P −`(f (x))
achieve the same value of
2
, which is larger than that achieved by a non-compact code.
x∈X

Definition 10: The cumulant generating function of the codeword lengths of PX -optimal binary codes is
given by


∗
Λ∗ (ρ) , log E 2ρ `(fX (X)) ,

ρ ∈ R.

(134)

Remark 20: (134) is actually a scaled cumulant generating function. The cumulant generating function of a
random variable X is given by


ΛX (ρ) = loge E eρX ,

ρ∈R

(135)

whereas, following Campbell [13], it is more natural to study the function given by

Note, however, that (135) and (136) satisfy



e X (ρ) = log E 2ρX .
Λ

e X (ρ) = ΛX (ρ loge 2) log e,
Λ

(136)

(137)

which implies that they can be obtained from each other by proper linear scalings of the axes.
As mentioned in the introduction, the cumulant generating function of the codeword lengths provides an
important design criterion. In particular, it yields the average length via the equality
Λ∗ (ρ)
∗
= E[`(fX
(X))].
ρ→0
ρ
lim

(138)

Theorem 12: [16, Theorem 1] If ρ ∈ (−∞, −1], then
H∞ (X) − log log2 (1 + |X |) ≤ −Λ∗ (ρ) ≤ H∞ (X),

and, if ρ ∈ (−1, 0) ∪ (0, ∞), then
H

January 30, 2018

1
1+ρ

(X) − log log2 (1 + |X |) ≤

Λ∗ (ρ)
≤ H 1 (X).
1+ρ
ρ

(139)

(140)

DRAFT

29

By invoking the Chernoff bound and using Theorem 12, the following result holds.
Theorem 13: [16, Theorem 2] For all H(X) < R < log |X |
n
o
1
1 (X)
log
≥
sup
ρR
−
ρH
∗ (X)) ≥ R]
1+ρ
P[`(fX
ρ>0
= D(Xα kX)

(141)
(142)

where α ∈ (0, 1) is a function of R chosen so that R = H(Xα ), and Xα has the scaled probability mass
function
P α (x)
PXα (x) = P X α
,
PX (a)

x ∈ X.

(143)

a∈X

B. Improved bounds on the distribution of the optimal code lengths
We derive bounds on the cumulant generating function and the complementary cumulative distribution of
optimal lengths for lossless compression of a random variable X which takes values on a finite set X . These
bounds improve those in Theorems 12 and 13, and in Section IV-C we use them to derive non-asymptotic
bounds for optimal fixed-to-variable lossless codes.
We start by generalizing [16, Lemma 1] from β = 1 to arbitrary β ∈ R.
Lemma 5: For an optimal binary code, and for all β ∈ R

1 − sm
β

∆
m

,
(2
−
1)s
+

β
X
∗
1
−
s
β
−β `(fX (x))
2
=


x∈X
m + 2∆ − 1,

β 6= 1

(144)

β=1

, t(β, |X |)

(145)

sβ = 21−β ,


m = log2 (1 + |X |) ,

(146)

where

(147)

∆ = log2 (1 + |X |) − m ∈ [0, 1).

(148)

Proof: From Definition 9, there are 2` elements of X which are assigned codewords of length ` with

` ∈ {0, 1, . . . , m − 1}, and |X | − 2m + 1 elements which are assigned codewords of length m. Hence, for β ∈ R,

X

x∈X

January 30, 2018

∗

2−β `(fX (x)) = (|X | − 2m + 1) 2−βm +

m−1
X

2` 2−β` .

(149)

`=0

DRAFT

30

In view of (147) and (148), for β = 1, (144) follows from (149). If β 6= 1, then from (146)–(149)
X

x∈X



1 − 2(1−β)m
∗
2−β `(fX (x)) = (1 + |X |)2−m − 1 2(1−β)m +
1 − 21−β
= (2∆ − 1)sm
β +

1 − sm
β
1 − sβ

.

(150)
(151)

Lemma 6: Let X be a random variable taking values on a finite set X , and let ρ 6= 0. Then, for an optimal
binary code,
i
 ρ `(f ∗ (X)) 
1
1h
X
β
log E 2
≥
sup
H (X) − log t(β, |X |) ,
β+ρ
ρ
β∈(−ρ,∞)\{0} β

(152)

where t(·) is defined in (145).

∗

Proof: Let g : X → {1, 2, 4, 8, . . .} be defined by g(x) = 2`(fX (x)) for all x ∈ X . The result in (152)
follows by combining (33) and Lemma 5.
Lemma 7: Let X be a random variable taking values on a finite set X , and let gX be a ranking function of
X . Then, for every optimal binary code and for all ρ > 0,



∗
ρ
ρ
2−ρ E[gX
(X)] < E 2ρ `(fX (X)) ≤ E[gX
(X)].

(153)

Proof: Let xk be the k -th most probable outcome of X under a given tie-breaking rule. For an optimal
∗ (x )) = blog kc
compression code, the length of the assigned codeword of the element xk ∈ X satisfies `(fX
k
2

([26, (15)]). Hence, for ρ > 0,
 X

∗
PX (xk ) 2ρ blog2 kc
E 2ρ `(fX (X)) =

(154)

k

≤

X

PX (xk ) k ρ

(155)

k

 ρ

= E gX
(X) .

(156)

This proves the right side of (153). To show the left side of (153), note that
blog2 kc > log2 k − 1

(157)

which implies from (154), (156) and (157) that for ρ > 0

 X
∗
E 2ρ `(fX (X)) >
PX (xk ) 2ρ (log2 k−1)

(158)

k

 ρ

= 2−ρ E gX
(X) .

January 30, 2018

(159)

DRAFT

31

Theorem 14: Let X be a random variable taking values on a finite set X . Then, for every optimal binary
code, the cumulant generating function in (134) satisfies
i
1h
sup
H β (X) − log t(β, |X |)
β+ρ
β∈(−ρ,∞)\{0} β
≤

Λ∗ (ρ)
ρ

(160)



i


1 h
1
+
≤ H 1 (X) + log
1 − exp −ρH 1 (X) + exp (ρ − 1) H 1 (X) − ρH 1 (X) ,
1+ρ
1+ρ
ρ
1+ρ
ρ
1+ρ

(161)

for all ρ > 0, where t(·) is given in (145). Moreover, (160) also holds for ρ < 0.

Proof: The lower bound in the left side of (160) is Lemma 6, and the upper bound in the right side of
(161) follows from Theorem 4 and Lemma 7.
Remark 21: For ρ ∈ (−1, 0) ∪ (0, ∞), loosening the bound in the left side of (160) by the sub-optimal choice
of β = 1 and invoking t(1, |X |) ≤ log2 (1 + |X |) (in view of Lemma 5, and since 2x − 1 ≤ x for x ∈ [0, 1])
recovers the lower bound in (140).
Remark 22: In view of (70), the second term in the right side of (161) is non-positive for all ρ ≥ 1; due to
the non-negativity of the Rényi entropy, this also holds for ρ ∈ (0, 1). Hence, for ρ > 0, the upper bound in
(161) improves the bound in the right side of (140).
The Chernoff bound and (161) readily yield the following lower bound.
Theorem 15: Under the assumptions in Theorem 14, for R < log |X |,
!


i

1
1 h
 ∗
 ≥ sup ρR − ρH 1 (X) − log
log
1 − exp −ρH 1 (X)
1+ρ
1+ρ
1+ρ
P `(fX (X)) > R
ρ>0


+
1
1
+ exp (ρ − 1) H (X) − ρH (X)
. (162)
ρ

1+ρ

Remark 23: The bound in (162) is strictly tighter than the right side in (142) unless X is deterministic. To

show this, note that in view of Remark 22 and (141)–(142), the bound in (162) cannot be looser than the right
side in (142). Moreover, since the function ρR − ρH

1
1+ρ

(X) is concave in ρ > 0, its local (and hence global)

maximum is achieved at ρ∗ > 0; from the proof of [16, Theorem 2], this value of ρ∗ satisfies
α=

1
,
1 + ρ∗

ρ∗ R − ρ∗ H

1
1+ρ∗

H(Xα ) = R,

(163)

(X) = D(Xα kX)

(164)

where Xα has the scaled probability mass function in (143). Hence, by replacing the supremum over ρ > 0

January 30, 2018

DRAFT

32

with the value at ρ = ρ∗ , (164) yields the following loosened bound:
!


i
1 h
1
∗
 ∗
 ≥ D(Xα kX) − log
1
log
1
−
exp
−ρ
H
(X)
1+ρ∗
1 + ρ∗
P `(fX (X)) > R

+ exp (ρ∗ − 1)+ H 1∗ (X) − ρ∗ H
ρ


1
(X) .
∗

(165)

1+ρ

Hence, it is enough to prove that (165) is strictly tighter than (142). This follows from the strict inequality in
(70) whenever X is non-deterministic, thus implying that, for all ρ > 0,


1
X
ρ
PX1+ρ (x) = exp 1+ρ
H 1 (X) > 1.

(166)

1+ρ

x∈X

C. Non-asymptotic bounds for fixed-to-variable lossless source codes
We consider the fixed-to-variable-length lossless compression in Definition 9 where the object to be compressed xn = (x1 , . . . , xn ) ∈ An is a string of length n (n is known to both encoder and decoder), whose
n
Q
letters are drawn from a finite alphabet X according to the probability mass function PX n (xn ) =
PX (xi )
i=1

for all xn ∈ An . We consider the following non-asymptotic measures for optimal fixed-to-variable lossless

compression:
•

•

The cumulant generating function of the codeword lengths is given by
h
i
1
∗
n
Λn (ρ) := log E 2ρ `(fX n (X )) , ρ ∈ R.
n

(167)

The non-asymptotic version of the source reliability function is given by
!
1
1

 .
En (R) = log
∗ (X n )) ≥ R
n
P n1 `(fX
n

(168)

∗ : An → {0, 1}∗
Theorem 16: Consider a memoryless and stationary source of finite alphabet X , and let fX
n

be an optimal compression code. Then, the following bounds hold:
a) For all ρ > 0


ρ
1
n
sup
H β (X) − log t(β, |A| )
β+ρ
n
β∈(−ρ,∞)\{0} β
≤ Λn (ρ)
≤ ρH

1
1+ρ

(169)
(X) +




i
1 h
1
log
1 − exp −nρH 1 (X)
1+ρ
n
1+ρ
 h
i
+
1
1
+ exp n (ρ − 1) H (X) − ρH (X)
ρ

where t(·) is as defined in (145).

January 30, 2018

(170)

1+ρ

DRAFT

33

b) For R < log |X |


En (R) ≥ sup ρR − ρH

1
1+ρ

ρ>0


i

1
1 h
(X) − log
1 − exp −nρH 1 (X)
1+ρ
n
1+ρ
 h
i
+
.
+ exp n (ρ − 1) H 1 (X) − ρH 1 (X)
ρ

(171)

1+ρ

Proof: Items a) and b) follow, respectively, from Theorems 14 and 15 with |X | replaced by |A|n , and since
Hα (X n ) = nHα (X) holds for i.i.d. random variables and for all α > 0 (see Lemma 1).

Remark 24: The non-asymptotic bounds on the cumulant generating function in (169)–(170) recover the
known asymptotic result in [16, (29)] where for all ρ > 0
Λ(ρ) := lim Λn (ρ) = ρH
n→∞

1
1+ρ

(X),

(172)
1
n→∞ n

which, incidentally, coincides with Arikan’s asymptotic fundamental limit for lim
1
n→∞ n

ρ
n
n
log E[gX
n (X )] when X

log t(1, |A|n ) = 0, and selecting β = 1 in the left side of (169) yields

is i.i.d. [1]. To this end, note that lim

lim Λn (ρ) ≥ ρH

n→∞

1
1+ρ

(X).

(173)

Moreover, since Hα (X) is monotonically non-increasing in α,
i


 h
exp n (ρ − 1)+ H 1 (X) − ρH 1 (X) ≤ exp −nH 1 (X)
ρ

1+ρ

(174)

ρ

and, if X is non-deterministic, then (170) and (174) yield

lim Λn (ρ) ≤ ρH

n→∞

1
1+ρ

(X),

(175)

recovering (172) from (173) and (175). Furthermore, (171) and (174) imply that
E(R) := lim En (R)

(176)

n→∞

n
≥ sup ρR − ρH
ρ>0

1
1+ρ

o
(X) .

(177)

Although, as noted in Remark 24, the improvement in the bounds afforded by Theorem 16 washes out
asymptotically, the following example illustrates the improvement in the non-asymptotic regime.
Example 7: Consider a discrete memoryless source which emits a string of n letters from the alphabet
X = {a, b, c} with PX (a) = 47 , PX (b) =

2
7

and PX (c) = 17 .

The bounds on the cumulant generating function in [16, Theorem 1] (see (140)) are given by
ρH

1
1+ρ

(X) −

ρ
n

log log2 (1 + |A|n ) ≤ Λn (ρ) ≤ ρH

1
1+ρ

(X)

(178)

for ρ > 0. Figure 3 compares (178) with the improved bounds in (169)–(170). For n = 10, the upper and
lower bounds are compared to the exact normalized cumulant (see the left plot in Figure 3); this indicates that
the lower bound in (169) can be tight even for small values of n. The match between the upper and lower
January 30, 2018

DRAFT

34

bounds in (169)–(170) improves by increasing n, and the tightening obtained by the lower bound in (169) can
be significant for small values of n.
1.6
1.5

1
ρ

Λ10 (ρ)

1.4
1.3
1.2
1.1
1
0.9
0.01

Fig. 3.

0.1

ρ

1

10

100

Bounds on the normalized cumulant generating function,

Λn (ρ)
ρ

(in bits), of the codeword lengths of optimal lossless compression

of strings of length n emitted from the discrete memoryless source in Example 7. The dashed lines are the bounds in (178), and the
thin solid lines refer to the improved bounds in (169)–(170). The left plot corresponds to n = 10, in which case we can compute the
exact normalized cumulant (thick solid curve). The right plot corresponds to n = 100.

lower
bounds on E (R)(R)
Lower bounds on E 100

0.7
0.6

100

10

lower
bounds
(R)
Lower
bounds on
on EE10
(R)

0.8

0.5
0.4
0.3
0.2

0.25

0.2

0.15

0.1

0.05

0.1
0
1.3

1.35

1.4

1.45

1.5

1.55

0

[bits]
R Rbits

Fig. 4.

1.4

1.45

1.5

1.55

[bits]
R Rbits

Lower bounds on the non-asymptotic reliability function, En (R) (base 2), for the discrete memoryless source in Example 7.

In each plot, the dashed curve refers to the lower bound on En (R) in Theorem 13, and the solid curve refers to the tighter lower bound
in (171). The left and right plots correspond to n = 10 and n = 100, respectively.

Lower bounds on the non-asymptotic source reliability function En (R) are plotted in Figure 4. In this figure,
the lower bound in Theorem 13 is compared to the tighter bound in (171), illustrating the improvement for
small to moderate values of n.
January 30, 2018

DRAFT

35

V.

L OWER B OUNDS FOR VARIABLE -L ENGTH S OURCE C ODING A LLOWING E RRORS

Following a recent study by Kuzuoka [28], this section applies our bounding techniques to derive improved
lower bounds on the cumulant generating function of the codeword lengths for variable-length source coding
allowing errors (which, in contrast to the conventional fixed-to-fixed paradigm, are not necessarily detectable
by the decoder) by means of the smooth Rényi entropy in Definition 5.
In contrast to [28], the bounds in this subsection are derived for source codes without the prefix condition when
either the maximal or average decoding error probabilities are limited not to exceed a given value ε ∈ [0, 1).
Theorem 17: Let X take values on a finite set X , and let f : X → C be an encoder (possibly stochastic) with

a finite codebook C ⊆ {0, 1}∗ , and let ` : C → {0, 1, . . . , } be the length function of the codewords in C . Fix
ε ∈ [0, 1) and ρ > 0.

1) If the average decoding error probability cannot be larger than ε, then


i
h
1
1
(ε)
log E 2ρ `(f (X)) ≥ sup
H β (X) − log t(β, |X |)
ρ
β+ρ
β>0 β

(179)

(ε)

where Hα (X) is the ε-smooth Rényi entropy of order α, and t(·) is given in (145).
2) If the maximal decoding error probability cannot be larger than ε, then also
i
h
i 1
1h
1
1
H β (X) − log t(β, |X |) − log
log E 2ρ `(f (X)) ≥ sup
.
β+ρ
ρ
β
ρ
1
−
ε
β∈(−ρ,0)

(180)

Proof: We first derive (179), and then rely on its proof for the derivation of (180).

1) Let Q : X → C denote a transition probability matrix such that Q(c|x) is the probability that a codeword
c ∈ C is assigned to x ∈ X by the stochastic encoder. Let ψ : C → X be the deterministic decoding function.

The average decoding error probability is given by
Pe = P[X 6= ψ(f (X))]
X
X
=
PX (x)
Q(c|x).
x∈X

(181)
(182)

c: ψ(c)6=x

In order to minimize Pe for a given (stochastic) encoder, the decision relies on a MAP decoder:
ψ(c) ∈ arg max Q(c|x)PX (x),
x∈X

c∈C

(183)

where ties are arbitrarily resolved. Let

γ(x) , Q ψ −1 (x)|x ∈ (0, 1]

(184)

denote the probability that x ∈ X is assigned to a codeword that is decoded into x. Since the average
decoding error probability satisfies Pe ≤ ε, it follows from (182) and (184) that
X
PX (x)γ(x) ≥ 1 − ε.

(185)

x∈X

January 30, 2018

DRAFT

36

For all x ∈ X , let
`ψ (x) ,

min `(c)

(186)

c∈ψ −1 (x)

be the minimal length of the codewords for which the decoder chooses x, and let
µ(x) , PX (x)γ(x),

x ∈ X.

(187)

0 ≤ µ(x) ≤ PX (x),
X
µ(x) ≥ 1 − ε,

x ∈ X,

(188)

From (184), (185) and (187)

(189)

x∈X

which, by (19), yields
µ ∈ B (ε) (PX ).

(190)

For all ρ > 0
i X
h
X
PX (x)
Q(c|x) 2ρ `(c)
E 2ρ `(f (X)) =
x∈X

≥

and, for every x ∈ X ,

X

c∈ψ −1 (x)

X

(191)

c∈C

PX (x)

x∈X

X

Q(c|x) 2ρ `(c) ,

(192)

c∈ψ −1 (x)

Q(c|x) 2ρ `(c) ≥

X

Q(c|x) 2ρ `ψ (x)

(193)

c∈ψ −1 (x)

= γ(x) 2ρ `ψ (x)

where (193) holds due to (186), and (194) follows from (184). Hence, for all ρ > 0,
i X
h
PX (x)γ(x) 2ρ `ψ (x)
E 2ρ `(f (X)) ≥

(194)

(195)

x∈X

=

X

µ(x) 2ρ `ψ (x)

(196)

x∈X

where (195) follows from (191)–(194), and (196) is due to (187). The finite sets {ψ −1 (x)}x∈X are disjoint.

For x ∈ X , let c∗ (x) ∈ ψ −1 (x) be a codeword which achieves the minimum in the right side of (186), i.e.,
`ψ (x) = `(c∗ (x)).

(197)

Since the codewords {c∗ (x)}x∈X are distinct, it follows from (197) and the proof of Lemma 5 that
X

x∈X

January 30, 2018

2−β `ψ (x) ≤ t(β, |X |),

β ≥ 0,

(198)

DRAFT

37

and
X

x∈X

2−β `ψ (x) ≥ t(β, |X |),

β≤0

(199)

since any perturbation of the set of codeword lengths of a PX -optimal code necessarily shifts shorter to
longer codewords. Let
α,

β+ρ
β

(200)

with ρ > 0 and β 6= 0, and define the following probability mass functions on X :
1

µ α (x)
,
R(x) = P 1
µ α (a)

(201)

a∈X

2−β `ψ (x)
S(x) = P −β ` (a) .
ψ
2

(202)

a∈X

Straightforward calculation shows that
X
1
log
Rα (x)S 1−α (x)
Dα (RkS) =
α−1
x∈X
!
X
β
ρ `ψ (x)
+ log
= log
µ(x) 2
ρ
x∈X

(203)
X

2

−β `ψ (x)

x∈X

!

X

β+ρ
−
log
ρ

µ

β
β+ρ

x∈X

!

(x) .

(204)

We now fix β > 0, and we proceed to upper bound each of the three terms in (204): the first term is upper
bounded using (196), the second term is upper bounded by log t(β, |X |) in view of (198), and the third term
satisfies
H

(ε)
β
β+ρ

(X) ≤

X β
β+ρ
log
µ β+ρ (x),
ρ

(205)

x∈X

which holds in view of Definition 5 and (190). Plugging those bounds into the right side of (204), and
recalling that Dα (RkS) ≥ 0 (this follows from Lemma 2, and since α > 0 in (200) for β, ρ > 0), we obtain

h
i 1
1
(ε)
ρ l(f (X))
log E 2
≥
H β (X) − log t(β, |X |) .
(206)
ρ
β
β+ρ

Finally, (179) follows by supremizing (206) over the free parameter β > 0.

2) If the maximal decoding error probability does not exceed ε, then so is the average decoding error probability,
and we can rely on the results in Item 1) of this proof. Fix β ∈ (−ρ, 0). In view of (200), α < 0 and
Dα (RkS) ≤ 0 (Lemma 2). From (204), we get
!
!
X
X
β
β+ρ
ρ `ψ (x)
−β `ψ (x)
log
µ(x) 2
+ log
2
log
−
ρ
ρ
x∈X

x∈X

X

x∈X

µ

β
β+ρ

!

(x)

≤ 0.

(207)

Due to the above assumption on the maximal decoding error probability, (184) implies that for every x ∈ X
γ(x) ∈ [1 − ε, 1],

January 30, 2018

(208)
DRAFT

38

and, consequently, (187) implies that
(1 − ε)PX (x) ≤ µ(x) ≤ PX (x),

Since

β
β+ρ

< 0 and

ρ
β+ρ

x ∈ X.

(209)

> 0, (2) (with negative orders of the Rényi entropy) and (209) yield
H

β
β+ρ

(X) ≤

X β
β+ρ
log
µ β+ρ (x)
ρ

≤H

(210)

x∈X

β
β+ρ

(X) −

β
1
log
.
ρ
1−ε

Consequently, we have
h
i 1
X
1
log E 2ρ l(f (X)) ≥ log
µ(x) 2ρ `ψ (x)
ρ
ρ
x∈X
"
!
!#
X β
X
1 β+ρ
−β
`
(x)
ψ
log
µ β+ρ (x) − log
2
≥
β
ρ
x∈X
x∈X
!
#
"
X β
1 β+ρ
≥
log
µ β+ρ (x) − log t(β, |X |)
β
ρ
x∈X


1
β
1
≥
H β (X) − log
− log t(β, |X |)
β+ρ
β
ρ
1−ε

(211)

(212)

(213)

(214)

(215)

where (212) holds due to (196); (213) follows from (207) and since β < 0; (214) holds due to (199);
finally, (215) follows from (211). Finally, (180) follows by supremizing the right side of (215) over the free
parameter β ∈ (−ρ, 0).
Remark 25: Note that the lower bound in (179) is expressed in terms of the smooth Rényi entropy of orders
α ∈ (0, 1), and the lower bound in (180) is expressed in terms of the conventional Rényi entropy of negative

orders. The calculation of the bound in (179) relies on Lemma 3a).
Remark 26: The combination of letting ε = 0 in (179) and (180) recovers the result in Lemma 6.
Remark 27: If the maximal decoding error probability cannot be larger than ε ∈ (0, 1), then neither of the
bounds in (179) and (180) is superseded by the other, as can be verified by numerical experimentation.
P −`ψ (x)
Remark 28: For prefix codes, Kraft’s inequality gives
2
≤ 1. Replacing t(1, |X |) in the right side
x∈X

of (198) by 1 recovers the result in [28, Theorem 2] from (179):
h
i
1
(ε)
log E 2ρ `(f (X)) ≥ H 1 (X),
ρ
1+ρ

ρ>0

(216)

where the average error probability cannot be larger than ε. An analogous result of (216), for a lower bound on
the normalized cumulant generating function of the codeword lengths without imposing the prefix condition, is

January 30, 2018

DRAFT

39

given by
h
i
1
(ε)
log E 2ρ `(f (X)) ≥ H 1 (X) − log t(1, |X |),
ρ
1+ρ

ρ>0

(217)

where t(1, |X |) is given in (145). Since (217) is obtained by replacing the supremization over β > 0 in the
right side of (179) with its value at β = 1, Theorem 17 gives a better bound than (217).



1
log2 E 2ρ (f (X100 ))
ρ

6

1.5

1

0.5

lower bounds on

lower bounds on



1
log2 E 2ρ (f (X1 ))
ρ

2

0

-0.5

-1
0.01

0.1

ρ

1

10

3

2

1

0.1

ρ

1

10

100

1

10

100



1
log2 E 2ρ (f (X100 ))
ρ

8

1.8

1.6

1.4

1.2

lower bounds on



1
log2 E 2ρ (f (X1 ))
ρ
lower bounds on

Fig. 5.

4

0
0.01

100

2

1

0.8

0.6
0.01

5

0.1

ρ

1

Example 8: Lower bounds on

10

1
ρ

100

7

6

5

4

3

2
0.01

0.1

ρ

h
i
log2 E 2ρ `(f (Xn )) with a maximal error probability of ε = 0.01 (upper plots), and the lossless

case: ε = 0 (lower plots). The left and right plots correspond to n = 1 and n = 100, respectively. The upper and lower dashed lines in
each plot refer, respectively, to (216) and (217); the solid lines refer to the combined lower bounds in (179) and (180) (Theorem 17).

Example 8: Let U1 , . . . , Un be i.i.d. random variables taking values in a set of cardinality 4, and having the

January 30, 2018

DRAFT

40

probability mass function
3
10

4
PU1 = [ 10

2
10

1
10 ].

(218)

Let
Xn =

n
X

Ui ,

i=1

n ∈ N.

(219)

The probability mass function PXn is equal to PU1 convolved with itself n−1 times, and Xn takes Mn = 3n+1
values. Assume that a maximal error probability of ε ∈ [0, 1) is allowed in decoding Xn . Figure 5 compares
the lower bound in (216), for binary prefix codes, with the lower bounds in Theorem 17 and (217) for binary
codes without the prefix condition. The upper and lower plots in Figure 5 correspond to ε = 0.01 and ε = 0
(i.e., the lossless case), respectively; the left and right plots correspond, respectively, to n = 1 and n = 100
(note that, by the central limit theorem, Xn is close to Gaussian for large n). The gain of the combined lower
bounds in (179) and (180) (the solid line in each plot) over the bound in (217) (the dashed lower line in the
corresponding plot) is illustrated in Figure 5 by comparing the left and right plots; by increasing the value of
n, the solid line becomes more steep at sufficiently large values of ρ.

A PPENDIX A
C OMPLETION OF THE P ROOF OF T HEOREM 2
We first prove (49a).
•

For β = 1, (49a) holds due to the upper bound on the harmonic sum in [21, Theorem 1];

•

For β > 1
M
∞
X
X
1
1
= ζ(β) −
β
j
jβ
j=1

j=M +1

= ζ(β) −

where ζ(β) =

P∞

1
n=1 nβ

1
2 (M

+ 1)

−β

−

∞
X

1
2

j=M +1



j

−β

+ (j + 1)

−β



(220)

for β > 1 denotes the Riemann zeta function; due to the convexity of fβ (t) = t−β

in (0, ∞), for all j ∈ N,
1
2



 Z
j −β + (j + 1)−β ≥

j+1

t−β dt.

(221)

j

Hence, from (220) and (221), for all β > 1,

Z ∞
M
X
1
−β
1
≤ ζ(β) − 2 (M + 1) −
t−β dt
jβ
M +1

(222)

j=1

= ζ(β) − 12 (M + 1)−β −
January 30, 2018

(M + 1)1−β
β−1

(223)

DRAFT

41

and
M
M
X
X
1
1
≤
≤ uM (1).
β
j
j

(224)

j=1

j=1

Combining (222)–(224) proves (49a) for β > 1.
•

For β > 0, from the convexity of fβ (t) = t−β in (0, ∞), Jensen’s inequality yields
Z j+ 1
2
1
t−β dt ≥ β
1
j
j−

(225)

2

for all j ∈ N, which implies that

Z M+ 1
M
X
2
1
≤1+
t−β dt
β
3
j
2
j=1
h
1−β
1
M + 21
= 1 + 1−β
−

(226)

3 1−β
2

i

.

(227)

This proves (49a) for β ∈ (0, 1). It can be verified numerically that the upper bound in (223) supersedes
the bound (227) for β > 1; for this reason, we ignore the bound in (227) for the derivation of uM (β) for
β > 1.

We next prove (49b).
•

For β ∈ [−1, 0), (49b) follows from the concavity of f (t) = t−β for t > 0; by Jensen’s inequality, we

obtain the opposite inequalities in (225) and (226) for β ∈ [−1, 0).
P
1
1
• For β = −1, M
j=1 j β = 2 M (M + 1).
•

For β ∈ (−∞, −1), due to the convexity of f (t) = t−β for t > 0,
M
X
1
=
jβ

1
2

≥

1
2

=

Z

+

j=1

M
−1
X


j −β + (j + 1)−β + 21 M −β

1
2

j=1

+

M
−1 Z j+1
X
j=1

M

j

t−β dt +

1
2

M 1−β − 1
+
1−β

1
2

1

=

t−β dt + 12 M −β
1 + M −β




1 + M −β .

(228)

(229)

(230)
(231)

Finally, Theorem 2 follows from Theorem 1, (49a) and (49b).
A PPENDIX B

P ROOF OF T HEOREM 5
We first prove (73) by relying on the following result:

January 30, 2018

DRAFT

42

Lemma 8: For ρ ∈ (0, 1) and u ≥ 1
uρ ≤



u1+ρ − (u − 1)1+ρ
ρ
21+ρ − 1
+
1{1 ≤ u < 2} + 2ρ −
1{u ≥ 2}.
1+ρ
1+ρ
1+ρ

(232)

Proof: For ρ ∈ (0, 1), let f1,ρ : [1, ∞) → R and f2,ρ : [1, ∞) → R be given by
ρ
u1+ρ − (u − 1)1+ρ
+
− uρ ,
1+ρ
1+ρ
u1+ρ − (u − 1)1+ρ
21+ρ − 1
f2,ρ (u) =
+ 2ρ −
− uρ .
1+ρ
1+ρ
f1,ρ (u) =

(233)
(234)

For ρ ∈ (0, 1) and u ∈ [1, ∞)
0
0
f1,ρ
(u) = f2,ρ
(u) = uρ − (u − 1)ρ − ρuρ−1

= ρcρ−1 − ρuρ−1 ,

c ∈ (u − 1, u)

> 0,

(235)
(236)
(237)

where (236) holds by the mean value theorem of calculus; moreover, since f1,ρ (1) = f2,ρ (2) = 0,
f1,ρ (u) ≥ 0,

u ∈ [1, ∞),

(238)

f2,ρ (u) ≥ 0,

u ∈ [2, ∞).

(239)

This gives
0 ≤ f1,ρ (u) 1{1 ≤ u < 2} + min{f1,ρ (u), f2,ρ (u)} 1{u ≥ 2}
= f1,ρ (u) 1{1 ≤ u < 2} + f2,ρ (u) 1{u ≥ 2}

(240)
(241)

where (240) follows from (238) and (239), and (241) follows from (233), (234), and since
2ρ −

ρ
(ρ − 1)(2ρ − 1)
21+ρ − 1
−
=
<0
1+ρ
1+ρ
1+ρ

(242)

for ρ ∈ (0, 1). Finally, (232) is equivalent to the non-negativity of the right side of (241).
From Lemma 8, for ρ ∈ (0, 1),
h
1+ρ i
 ρ

1
1+ρ
E gX
(X) ≤
E gX
(X) − gX (X) − 1
1+ρ


ρ P[gX (X) = 1]
21+ρ − 1
ρ
+ 2 −
P[gX (X) ≥ 2]
+
1+ρ
1+ρ


h
1+ρ i ρ pmax
1
21+ρ − 1
1+ρ
ρ
=
E gX (X) − gX (X) − 1
+
+ 2 −
(1 − pmax )
1+ρ
1+ρ
1+ρ


 ρp

1
21+ρ − 1
max
ρ
≤
exp ρH 1 (X) +
+ 2 −
(1 − pmax )
1+ρ
1+ρ
1+ρ
1+ρ

(243)
(244)
(245)

where (243) follows from (232) by substituting u = gX (X), and taking expectations on both sides of the
inequality; (244) holds since P[gX (X) = 1] = pmax (the first guess of X is a mode of PX ); (245) follows from
(60), which is then simplified to (73).
January 30, 2018

DRAFT

43

We next prove (74).
Lemma 9: If ρ ∈ [1, 2] and u ≥ 1, then
uρ ≤

u1+ρ − (u − 1)1+ρ uρ − (u − 1)ρ ρ2 − ρ − 1
+
+
.
1+ρ
ρ
ρ(1 + ρ)

(246)

Proof: For ρ ∈ [1, 2], let f : [1, ∞) → R be given by
fρ (u) =

u1+ρ − (u − 1)1+ρ uρ − (u − 1)ρ
ρ2 − ρ − 1
+
− uρ +
,
1+ρ
ρ
ρ(1 + ρ)

u ∈ [1, ∞).

(247)

For all u ∈ [1, ∞),
fρ0 (u) = uρ − (u − 1)ρ + uρ−1 − (u − 1)ρ−1 − ρuρ−1
≥ 1 + ρ(u − 1)ρ−1 + uρ−1 − (u − 1)ρ−1 − ρuρ−1

= 1 + (ρ − 1) (u − 1)ρ−1 − uρ−1
≥2−ρ≥0

(248)
(249)
(250)
(251)

where (249) follows from the convexity of u 7→ uρ in (0, ∞) for ρ ≥ 1, and (251) holds since
0 ≤ uρ−1 − (u − 1)ρ−1 ≤ 1

(252)

for ρ ∈ [1, 2] and u ∈ [1, ∞). It can be verified that fρ (1) = 0, which implies that fρ (u) ≥ 0 for ρ ∈ [1, 2] and
u ≥ 1.

Replacing x in (246) with gX (X) ≥ 1, and taking expectations on both sides of (246) yield, via (60) and
(65), the result in (74).
If X is deterministic, then Hα (X) = 0 for all α > 0, gX (X) = 1, and pmax = 1, which imply that (73) and
(74) hold with equality (note that

1
1+ρ

+

1
ρ

+

ρ2 −ρ−1
ρ(ρ+1)

= 1 holds for ρ 6= −1, 0).

A PPENDIX C
P ROOF OF T HEOREM 6
Lemma 10: Under the assumptions in Theorem 3, if ρ ≥ 2, then

 ρ
ρ(ρ − 1)
1
ρ
ρ−1
E[gX
(X)] ≤
exp ρH 1 (X) + E[gX
(X)] −
1+ρ
1+ρ
2
2(1 + ρ)

(253)

with equality if X is deterministic.

Proof: If ρ ≥ 2 and u ≥ 1, then
uρ ≤

u1+ρ − (u − 1)1+ρ ρ ρ−1 ρ(ρ − 1)
+ u
−
.
1+ρ
2
2(1 + ρ)

(254)

To prove (254), let ξ : [1, ∞) → R be given by
ξ(u) =

January 30, 2018

u1+ρ − (u − 1)1+ρ
ρ
ρ(ρ − 1)
− uρ + uρ−1 −
1+ρ
2
2(1 + ρ)

(255)

DRAFT

44

for u ≥ 1, and as (62), we denote v(u) = uρ for u ≥ 0. Then, for u ≥ 1,
ξ 0 (u) = uρ − (u − 1)ρ − ρuρ−1 + 12 ρ(ρ − 1)uρ−2

(256)

= v(u) − v(u − 1) − v 0 (u) + 12 v 00 (u).

(257)

By a Taylor series expansion of v(·) around u,
v(u − 1) = v(u) − v 0 (u) + 21 v 00 (u) − 16 v (3) (c)

(258)

for some c ∈ (u − 1, u) ⊆ (0, ∞); since v (3) (c) = ρ(ρ − 1)(ρ − 2)cρ−3 ≥ 0 for ρ ≥ 2, it follows from (257)

that t0 (u) ≥ 0 for all u ≥ 1. It can be verified that t(1) = 0, which implies that t(·) ≥ 0 in [1, ∞); this gives
(254) from (255). By substituting u = gX (X) in (254) and taking expectations on both sides of the inequality,
it follows that for ρ ≥ 2
ρ
E[gX
(X)]

 1+ρ


1+ρ 
E gX
(X) − E gX (X) − 1
ρ
ρ(ρ − 1)
ρ−1
≤
+ E[gX
(X)] −
1+ρ
2
2(1 + ρ)

(259)

which, from (60), yields (253). If X is deterministic, then gX (X) = 1 and Hα (X) = 0 for α > 0, which
implies equality in (253) since

1
1+ρ

+

ρ
2

−

ρ(ρ−1)
2(1+ρ)

= 1 holds for ρ 6= −1.

We proceed to prove Theorem 6. Combining the recursive upper bound in Lemma 10 with Theorem 5-b)
ρ
gives, after some straightforward algebra, an upper bound on E[gX
(X)] for ρ ≥ 2 which is of the form
ρ
E[gX
(X)] ≤

bρc
X
j=0


cj (ρ) exp (ρ − j) H

1
1+ρ−j


(X) + d(ρ),

(260)

where the sequence {cj (ρ)} is given in (76), and d(ρ) is an additive term which only depends on ρ (but it does
not on the distribution of X ). Since the results in Theorem 5-b) and Lemma 10 are satisfied with equalities if
X is deterministic, then it follows that also (260) holds with equality in this special case. For such X , we have
gX (X) = 1 and Hα (X) = 0 for all α > 0, which therefore implies that
d(ρ) = 1 −

bρc
X

cj (ρ).

(261)

j=0

The bound in (75) is obtained by combining (260) and (261).
A PPENDIX D
T ECHNICAL D ETAILS R ELATED TO S ECTION III-E
Lemmas 11–13 are used to derive the bounds on the optimal generalized guessing moment in (91) and (92),
and Lemma 14 refers to the proof of Theorem 11.
Lemma 11: Let ` ∈ N, p1 ≥ p2 ≥ . . . ≥ p` ≥ 0 with
1
j

January 30, 2018

X̀

k=l−j+1

P̀

pi = 1, and let f : {1, . . . , `} → R satisfy

i=1

f (k) ≥ f (` − j),

(262)

DRAFT

45

for all j ∈ {1, . . . , `}. Then,
X̀
i=1

pi f (i) ≤

1 X̀
f (i).
`

(263)

i=1

Furthermore, if the inequality in (262) is strict for all j , then (263) holds with equality if and only if pi =

1
`

for all i ∈ {1, . . . , `}.
Proof: Denote
uj =

`−j
X
i=1


1  X̀
pi f (i) +
j

i=`−j+1



pi  

X̀

i=`−j+1

Its first and last terms are equal to the side of (263):
u1 =

X̀



f (i) ,

j ∈ {1, . . . , `}.

(264)

pi f (i),

(265)

1 X̀
f (i)
`

(266)

i=1

u` =

i=1

so, proving that {uj } is monotonically increasing is sufficient to show (263). By its definition in (264),
straightforward calculation shows that for j ∈ {1, . . . , ` − 1}


X̀
X̀
1
j p`−j −
uj+1 − uj =
pi  
j(j + 1)
i=`−j+1

i=`−j+1

≥0



f (i) − jf (` − j)

(267)
(268)

where (268) holds in view of p1 ≥ . . . ≥ p` and (262). Note that (267) and (268) imply that u1 = ul if and
only if uj+1 = uj for all j ∈ {1, . . . , l − 1}. Hence, if the inequality in (262) is strict, then (267) implies that
uj+1 = uj for all j if and only if the monotonic sequence {pi } is fixed, i.e., p1 = p2 = . . . = p` =

1
`

(since,

by assumption, this sequence sums to 1).
Lemma 12: Let l ∈ N, q1 ≥ . . . ≥ q` ≥ 0, and let f : {1, . . . , `} → R be a strictly monotonically increasing
function. Then,
X̀
i=1

qi f (1) ≤

X̀
i=1

1
qi f (i) ≤
`

X̀
i=1

qi

!

X̀
i=1

!

f (i)

(269)

with equality in the left inequality if and only if qi = 0 for all i ∈ {2, . . . , `}, and equality in the right inequality
if and only if q1 = . . . q` .
Proof: Since by assumption f : {1, . . . , `} → R is a strictly monotonically increasing function, the inequality
in (262) is strict for all j ∈ {1, . . . , `−1}. Let {pi } be the normalized version of the non-negative, monotonically

January 30, 2018

DRAFT

decreasing sequence {qi } such that

P̀

46

pi = 1. Hence,

i=1

pi =

qi
,
P̀
qj

i ∈ {1, . . . , `},

(270)

j=1

and p1 ≥ p2 ≥ . . . ≥ p` ≥ 0. Lemma 11 and (270) give
X̀

X̀

qi f (i) =

i=1

pi f (i)

i=1

1
≤
`

X̀

!

f (i)

i=1

X̀

qi

i=1

!

X̀

!

qi

i=1

!

(271)

,

(272)

and, due to Lemma 11, (272) holds with equality if and only if p1 = . . . = p` = 1` ; due to (270), this holds if
and only if q1 = . . . = q` . Moreover, the assumptions on f : {1, . . . , `} → R and {qi } imply that
X̀
i=1

qi f (i) ≥ f (1)

X̀

qi ,

(273)

i=1

where (273) holds with equality if and only if qi = 0 for all i ∈ {2, . . . , `}.
Lemma 13: The function fρ : [0, 1) → [0, ∞) defined in (93)–(94) is convex for all ρ > 0.
Proof: From (94), the value of ku ∈ N is fixed in each interval [1 −

1
1
m , 1 − m+1 )

with m ∈ N. Hence, fρ

in (93) is a linear function in each such interval; its positive slope, denoted by sρ (m), is given by
ρ

sρ (m) = ku (ku + 1) −

By a transition from an interval [1 −

1
m, 1

−

1
m+1 )

ku
X

jρ.

(274)

j=1

to the successive interval [1 −

1
m+1 , 1

−

1
m+2 ),

the value of

the positive integer ku is increased by 1 (see (94)); consequently, it can be verified from (274) that for ρ > 0
sρ (m + 1) > sρ (m),

m ∈ N.

Hence, the slope of the linear function obtained by restricting fρ to the interval [1 −
than its slope in the interval [1 −
interval [1 −

1
m, 1

−

1
m+1 )

1
m, 1

−

1
m+1 ).

(275)
1
m+1 , 1

−

1
m+2 )

is larger

Hence, fρ can be decomposed by linear functions in each

whose slopes are monotonically increasing in m ∈ N. It can be also verified from

(93) that the function fρ is continuous at the endpoints of these intervals, which therefore yields its convexity
S
1
1
on [0, 1) =
[1 − m
, 1 − m+1
).
m∈N

Lemma 14: The identity in (127) holds for every integer M ≥ 2.

January 30, 2018

DRAFT

47

Proof: The result in (127) is trivial for M = 2. Let M ≥ 3, then
1

1

···

1

0

loge 2

loge M

0

log2e 2

···

0

..
.

0

logeM −1 2

···
..
.

log2e M

···

−1
logM
M
e

···

loge 2
log2e 2
..
.

=

..
.

M
Y

loge k

k=2

=

M
Y

!

Y

(276)

−1
logM
M
e

1

···

1

loge 2
..
.

···
..
.

loge M
..
.

−2
logM
2 ···
e

loge k

k=2

log2e M
..
.

···
..
.

−1
logM
2 ···
e

=

loge M

2≤i<j≤M

(277)

−2
logM
M
e

(loge j − loge i)

(278)

where (276) holds by expanding according to the first column; (277) holds by factoring loge k from the (k−1)-th
row for k = 2, . . . , M ; finally, (278) relies on the Vandermonde determinant (e.g., [29, p. 155]).
R EFERENCES
[1]

E. Arikan, “An inequality on guessing and its application to sequential decoding,” IEEE Trans. on Information Theory, vol. 42,
no. 1, pp. 99–105, January 1996.

[2]

E. Arikan and N. Merhav, “Guessing subject to distortion,” IEEE Trans. on Information Theory, vol. 44, no. 3, pp. 1041–1056,
May 1998.

[3]

E. Arikan and N. Merhav, “Joint source-channel coding and guessing with application to sequential decoding,” IEEE Trans. on
Information Theory, vol. 44, no. 5, pp. 1756–1769, September 1998.

[4]

S. Arimoto, “Information measures and capacity of order α for discrete memoryless channels,” in Topics in Information Theory
- 2nd Colloquium, Keszthely, Hungary, 1975, Colloquia Mathematica Societatis Janós Bolyai (I. Csiszár and P. Elias editors),
Amsterdam, the Netherlands: North Holland, vol. 16, pp. 41-52, 1977.

[5]

R. Atar, K. Chowdhary and P. Dupuis, “Robust bounds on risk-sensitive functionals via Rényi divergence,” SIAM/ASA Journal on
Uncertainty Quantification, vol. 3, no. 1, pp. 18–33, January 2015.

[6]

S. Boztaş, “Comments on “An inequality on guessing and its application to sequential decoding”,” IEEE Trans. on Information
Theory, vol. 43, no. 6, pp. 2062–2063, November 1997.

[7]

A. Bracher, E. Hof and A. Lapidoth, “Guessing attacks on distributed-storage systems,” Proceedings of the 2015 IEEE International
Symposium on Information Theory, pp. 1585–1589, Hong-Kong, China, June 2015.

[8]

A. Bracher, A. Lapidoth and C. Pfister, “Distributed task encoding,” Proceedings of the 2017 IEEE International Symposium on
Information Theory, pp. 1993–1997, Aachen, Germany, June 2017.

[9]

C. Bunte and A. Lapidoth, “Encoding tasks and Rényi entropy,” IEEE Trans. on Information Theory, vol. 60, no. 9, pp. 5065–5076,
September 2014.

January 30, 2018

DRAFT

48

[10]

C. Bunte and A. Lapidoth, “Maximizing Rényi entropy rate,” Proceedings of the 2014 IEEE 28-th Convention of Electrical and
Electronics Engineers in Israel, pp. 1–4, December 2014, Eilat, Israel.

[11]

A. Burin and O. Shayevitz, “Reducing guesswork via an unreliable oracle,” March 2017. [Online]. Available at https://arxiv.org/
abs/1703.01672.

[12]

C. Cachin, “Smooth entropy and Rényi entropy,” Lecture Notes in Computer Science, vol. 1233, pp. 193–208, Springer, 1997.

[13]

L. L. Campbell, “A coding theorem and Rényi’s entropy,” Information and Control, vol. 8, no. 4, pp. 423–429, August 1965.

[14]

L. L. Campbell, “Definition of entropy by means of a coding problem,” Probability Theory and Related Fields, vol. 6, no. 2,
pp. 113–118, June 1966.

[15]

M. M. Christiansen and K. R. Duffy, “Guesswork, large deviations, and Shannon entropy,” IEEE Trans. on Information Theory,
vol. 59, no. 2, pp. 796–802, February 2013.

[16]

T. Courtade and S. Verdú, “Cumulant generating function of codeword lengths in optimal lossless compression,” Proceedings of
the 2014 IEEE International Symposium on Information Theory, pp. 2494–2498, Honolulu, Hawaii, USA, July 2014.

[17]

T. Courtade and S. Verdú, “Variable-length lossy compression and channel coding: Non-asymptotic converses via cumulant
generating functions,” Proceedings of the 2014 IEEE International Symposium on Information Theory, pp. 2499–2503, Honolulu,
Hawaii, USA, July 2014.

[18]

M. Drmota and W. Szpankowski, “Redundancy of lossless data compression for known sources by analytic methods,” Foundations
and Trends in Communications and Information Theory, vol. 13, no. 4, pp. 277–417, 2016.

[19]

T. van Erven and P. Harremoës, “Rényi divergence and Kullback-Leibler divergence,” IEEE Trans. on Information Theory, vol. 60,
no. 7, pp. 3797–3820, July 2014.

[20]

S. Fehr and S. Berens, “On the conditional Rényi entropy,” IEEE Trans. on Information Theory, vol. 60, no. 11, pp. 6801–6810,
November 2014.

[21]

B. N. Guo and F. Qi, “Sharp bounds for harmonic numbers,” Applied Mathematics and Computation, vol. 218, no. 3, pp. 991–995,
October 2011.

[22]

M. K. Hanawal and R. Sundaresan, “Guessing revisited: a large deviations approach,” IEEE Trans. on Information Theory, vol. 57,
no. 1, pp. 70–78, January 2011.

[23]

W. Huleihel, S. Salamatian, and M. Médard, “Guessing with limited memory,” Proceedings of the 2017 IEEE International
Symposium on Information Theory, pp. 2258–2262, Aachen, Germany, June 2017.

[24]

H. Koga and H. Yamamoto, “Asymptotic properties on codeword lengths of an optimal FV code for general sources,” IEEE Trans.
on Information Theory, vol. 51, no. 4, pp. 1546–1555, April 2005.

[25]

H. Koga, “Characterization of the smooth Rényi entropy using majorization,” Proceedings of the 2013 IEEE Information Theory
Workshop, pp. 604–608, Seville, Spain, September 2013.

[26]

I. Kontoyiannis and S. Verdú, “Optimal lossless data compression: non-asymptotics and asymptotics,” IEEE Trans. on Information
Theory, vol. 60, no. 2, pp. 777–795, February 2014.

[27]

V. Kostina, Y. Polyanskiy and S. Verdú, “Variable-length compression allowing errors,” IEEE Trans. on Information Theory,
vol. 61, no. 8, pp. 4316–4330, August 2015.

[28]

S. Kuzuoka, “On the smooth Rényi entropy and variable-length source coding allowing errors,” Proceedings of the 2016 IEEE
International Symposium on Information Theory, pp. 745–749, Barcelona, Spain, July 2016.

[29]

S. Lang, Linear Algebra, Springer, Third edition, 1987.

January 30, 2018

DRAFT

49

[30]

D. Malone and W. G. Sullivan, “Guesswork and entropy,” IEEE Trans. on Information Theory, vol. 50, no. 3, pp. 525–526, March
2004.

[31]

J. L. Massey, “Guessing and entropy,” Proceedings of the 1994 IEEE International Symposium on Information Theory, p. 204,
Trondheim, Norway, June 1994.

[32]

R. J. McEliece and Z. Yu, “An inequality on entropy,” Proceedings of the 1995 IEEE International Symposium on Information
Theory, p. 329, Whistler, Canada, September 1995.

[33]

N. Merhav and E. Arikan, “The Shannon cipher system with a guessing wiretapper,” IEEE Trans. on Information Theory, vol. 45,
no. 6, pp. 1860–1866, September 1999.

[34]

N. Merhav, “On optimum strategies for minimizing exponential moments for a given cost function,” Communications in Information
Systems, vol. 11, no. 4, pp. 343–368, 2011.

[35]

N. Merhav, “On empirical cumulant generating functions of code lengths for individual sequences,” IEEE Trans. on Information
Theory, vol. 63, no. 12, pp. 7729–7736, December 2017.

[36]

R. Renner and S. Wolf, “Smooth Rényi entropy and applications,” Proceedings of the 2004 IEEE International Symposium on
Information Theory, p. 232, Chicago, Illinois, USA, July 2004.

[37]

R. Renner and S. Wolf, “Simple and tight bounds for information reconciliation and privacy amplification,” Advances in Cryptology
- ASIACRYPT 2005, Lecture Notes in Computer Science, vol. 3788, pp. 199–216, Springer, 2005.

[38]

A. Rényi, “On measures of entropy and information,” Proceedings of the 4th Berkeley Symposium on Probability Theory and
Mathematical Statistics, pp. 547–561, Berkeley, California, USA, 1961.

[39]

Y. Sakai and K. Iwata, “Sharp bounds on Arimoto’s conditional Rényi entropies between two distinct orders,” Proceedings of the
2017 IEEE International Symposium on Information Theory, pp. 2985–2989, Aachen, Germany, June 2017.

[40]

S. Salamatian, A. Beirami, A. Cohen and M. Médard, “Centralized versus decentralized multi-agent guesswork,” Proceedings of
the 2017 IEEE International Symposium on Information Theory, pp. 2263–2267, Aachen, Germany, June 2017.

[41]

I. Sason and S. Verdú, “f -divergence inequalities,” IEEE Trans. on Information Theory, vol. 62, no. 11, pp. 5973–6006, November
2016.

[42]

I. Sason and S. Verdú, “Arimoto-Rényi conditional entropy and Bayesian M -Ary hypothesis testing,” IEEE Trans. on Information
Theory, vol. 64, no. 1, pp. 4–25, January 2018.

[43]

C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379–423, 623–656,
July-October 1948.

[44]

C. E. Shannon, “Channels with side information at the transmitter,” IBM Journal on Research and Development, vol. 2, no. 4,
pp. 289–293, October 1958.

[45]

O. Shayevitz, “On Rényi measures and hypothesis testing,” Proceedings of the 2011 IEEE International Symposium on Information
Theory, pp. 800–804, Saint Petersburg, Russia, August 2011.

[46]

V. Strassen, “Asymptotische abschäzungen in Shannon’s informations-theorie,” Transactions of the Third Prague Conference on
Information Theory, Statistics, Decision Functions, Random Processes (Liblice, 1962). Prague: Publ. House Czech. Acad. Sci.,
pp. 689–723, 1964.

[47]

R. Sundaresan, “Guessing under source uncertainty,” IEEE Trans. on Information Theory, vol. 53, no. 1, pp. 269–287, January
2007.

[48]

R. Sundaresan, “Guessing based on length functions,” Proceedings of the 2007 IEEE International Symposium on Information
Theory, pp. 716–719, Nice, France, June 2007.

January 30, 2018

DRAFT

50

[49]

W. Szpankowski and S. Verdú, “Minimum expected length of fixed-to-variable lossless compression without prefix constraints,”
IEEE Trans. on Information Theory, vol. 57, no. 7, pp. 4017–4025, July 2011.

[50]

S. Verdú, “Shannon’s inequality,” 2011 Workshop on Information Theory and Applications, San Diego, California, USA, February
2011. [Online]. Available: http://ita.ucsd.edu/workshop/11/files/paper/paper 374.pdf.

[51]

S. Verdú, Information Theory, in preparation.

[52]

Y. Yona and S. Diggavi, “The effect of bias on the guesswork of hash functions,” Proceedings of the 2017 IEEE International
Symposium on Information Theory, pp. 2253–2257, Aachen, Germany, June 2017.

January 30, 2018

DRAFT

