1

The Rényi Capacity and Center
Barış Nakiboğlu

arXiv:1608.02424v4 [cs.IT] 16 Mar 2018

Canım halam Fatma Nakiboğlu Aydiç’in anısına adanmıştır.
Dedicated to the memory of my dear aunt Fatma Nakiboğlu Aydiç.
Abstract—The Rényi’s information measures —the Rényi information, mean, capacity, radius, and center— are analyzed
relying on the elementary properties of the Rényi divergence and
power means. The van Erven-Harremoës conjecture is proved for
any positive order and for any set of probability measures on
a given measurable space. A generalization of the van ErvenHarremoës conjecture is established for the constrained variant
of the problem. The finiteness of the order α Rényi capacity is
shown to imply the continuity of the Rényi capacity on (0, α] and
the uniform equicontinuity of the Rényi information, both as a
family of functions of the order indexed by the priors and as a
family of functions of the prior indexed by the orders. The Rényi
capacities and centers of various families of Poisson processes are
derived as examples.

C ONTENTS
I

Introduction
I-A
Radius, Center, and Capacity . . . . . .
I-B
Augustin’s Method and the Rényi Center
I-C
Main Contributions . . . . . . . . . . .
I-D
Notational Conventions . . . . . . . . .

II

Preliminaries
II-A
The Mean Measure . .
II-B
The Rényi Information
II-C
The Rényi Divergence .
II-D
The Rényi Mean . . . .

1
3
4
5
5

.
.
.
.

6
6
8
9
10

III

The Rényi Capacity
III-A
Cα,W as a Function of α . . . . . . . .
III-B
Finiteness Cα,W . . . . . . . . . . . . .

10
11
13

IV

The Rényi Center
IV-A
Minimax Theorems & Rel. Compactness
IV-B
qα,W as a Function of α . . . . . . . .
IV-C
Unions, Cartesian Products, and More .

13
14
16
17

V

Examples
V-A
Probabilities on Discrete Output Spaces
V-B
Shift Invariant Families of Probabilities
V-C
Families of Poisson Point Processes . .

18
18
19
20

VI

Discussion

23

Appendix
A
B
C

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

The Constrained Rényi Capacity . . . .
Transition Probabilities and Cα,W . . .
Deferred Proofs . . . . . . . . . . . . .

24
24
24
25

References
Proofs Omitted From TIT Manuscript . . . . . .

31
34

e-mail:nakib@alum.mit.edu

I. I NTRODUCTION
Information transmission problems are often posed on models with finite sample spaces or on models with specific noise
structures, such as Gaussian or Poisson models. As a result,
certain fundamental observations such as the minimax theorem
for the Shannon capacity in terms of the Kullback-Leibler
divergence or the existence of a unique “capacity achieving
output distribution”, i.e. the existence of a unique Shannon
center, are established either for models with finite sample
spaces or for specific noise structures. In [56], Kemperman
proved these assertions far more generally by interpreting the
channel as a set of probability measures on a given measurable
space.
In a sense, Kemperman tacitly suggests a purely measure
theoretic understanding of the Shannon capacity and center
that is separated from their significance in the information
transmission problems. Even without the generality afforded
by the measure theoretic framework, such an understanding
is appealing because Shannon capacity and center come up in
various information transmission problems, with very different
operational meanings. Consider for example a finite set W of
probability mass functions on a finite output set Y.
•

•

If we interpret W as a discrete channel that is to be used
multiple times, then the Shannon capacity of W is the
largest rate at which one can communicate reliably via
the channel W, [86].
If we interpret W as a collection of sources that is to
be encoded by a lossless variable length source code,
then the Shannon capacity is a lower bound on the worst
redundancy among the members of W, which is off at
most by one for some lossless variable length source
code, [29], [36], [80].

In this paper we propose an analogous measure theoretic
understanding for the Rényi capacity and center. Our interest
in these concepts stems from their operational significance
in the channel coding problem; we elucidate that operational
significance in our concurrent paper [71]. Because of the
generality of the measure theoretic model we adopt in this
paper, we can discuss in [71] the operational significance of
these concepts for a diverse family of channels in a unified
framework. In the current paper our main aim is to present
an analysis starting from measure theoretic first principles
and the elementary properties of the Rényi divergence. We
will first present a brief overview of the Rényi information,
divergence, and mean. Then we proceed with the analysis of
the Rényi capacity and center.
Deriving the technical results employed in [71] is one of
the main aims of the current paper; however, the scope of
our analysis is not restricted to the needs of the particular

analysis we present in [71]. We aim to build a more complete
understanding of Rényi’s information measures that might lead
us to new analysis techniques for the problems we investigate
in [71] or for other information transmission problems involving Rényi’s information measures. Our abstract and general
framework is conducive to this purpose; in addition it allows
us to observe certain phenomena that cannot be observed in
simpler models. For example,1 the Rényi capacity is either
a continuous function of the order on (0, ∞) or a finite and
continuous function of the order on (0, φ] that is infinite on
(φ, ∞) for some φ ∈ [1, ∞). This dichotomy, however, cannot
be observed with models with finite W or finite Y because the
Rényi capacity is bounded if either W or Y is finite.
In [78], Rényi provided an axiomatic characterization of
a family of divergences for pairs of probability mass functions on a given finite sample space; the resulting family
of divergences, parametrized by positive real numbers, are
named after him. The definition of the Rényi divergence has
been extended to pairs of probability measures. Recently, van
Erven and Harremoës provided a comprehensive investigation
of various properties of the Rényi divergence in [31]. For any
α in [0, ∞], the order α Rényi divergence between probability
measures w and q, denoted by Dα (w k q), is zero when w
is equal to q and non-negative when w is not equal to q.
Hence, given a measurable space (Y, Y) we can use the order
α Rényi divergence to measure the spread of any set of
probability measures W relative to any probability measure
q on (Y, Y) as follows:
Sα,W (q) , supw∈W Dα (w k q) .

Rényi information equals to the mutual information. For other
positive real orders, the order α Rényi information can be
described in terms of Gallager’s function introduced in [35]:
Iα (p;W) =

∀α ∈ ℜ+ \ {1}

(3)

where Gallager’s function E0 (ρ, p) is defined for ρ > −1 as
Z X
1+ρ
1
1+ρ
p(w )( dw
E0 (ρ, p) , − ln
ν(dy). (4)
dν )
w

The order α Rényi capacity Cα,W is defined as the supremum
of the order α Rényi information Iα (p;W) over all priors p.
There are at least two other ways to define the Rényi information for which the order one Rényi information is equal
to the mutual information: one by Arimoto [4] and another
one by Augustin [6] and Csiszár [25]. A review of these
three definitions of the Rényi information has recently been
provided by Verdú [103]. Assuming W and Y to be finite sets,
Csiszár showed that the order α Rényi capacity for all three
definitions of the Rényi information are equal to one another
and to the order α Rényi radius, [25, Proposition 1].
The extension of Kemperman’s result [56, Thm. 1] about
the Shannon capacity and center given in Theorem 1, which
we present in the following, is arguably the most important
observation about the Rényi capacity and center. Theorem 1
establishes the equality of Cα,W and Sα,W for any positive
order α and set of probability measures W. Furthermore,
it asserts the existence of a unique order α Rényi center
qα,W whenever Cα,W is finite and characterizes the unique
order α Rényi center in terms of order α Rényi means.
These observations, however, have been reported in various
forms before, at least partially. In [5], Augustin considered
the orders in (0, 1), proved a result equivalent to Theorem 1
for finite W’s and described how this result can be extended to
arbitrary W’s. Later, Augustin established a result, [6, Thm.
26.6′], that implies Theorem 1 for all orders in α in (0, 2).
Csiszár [25, Prop. 1] proved the equality Cα,W = Sα,W for
arbitrary positive order α assuming W and Y are finite sets.
Van Erven and Harremoës [31, (57)] adopted the definition of
the Rényi information proposed by Csiszár [25] and Augustin
[6] and proved Cα,W = Sα,W for all α in [0, ∞], assuming Y
is a finite set [31, Thm. 34].
The equality of capacity to radius and the existence of
a unique center, are phenomena that have been observed
repeatedly in various contexts. In order to clarify the standing
of Theorem 1 among these results, we provide a more comprehensive discussion of the previous work on these fundamental
observations in §I-A.
The current paper and the concurrent paper [71] grew out of
a desire to understand Augustin’s proofs of the sphere packing
bound given in [5] and [6] more intuitively. Augustin’s proofs
are important because, among other things, they are the only
proofs of the sphere packing bound for non-stationary product
channels, even for the case of discrete channels. Concepts of
Rényi capacity, radius, and center provide a way to express
the principal novelty of Augustin’s method in a succinct and
intuitive way. We discuss the novel observation underlying
Augustin’s method and its promise briefly in §I-B.

(1)

Sα,W (q) is called the order α Rényi radius of W relative
to q. By taking the infimum of Sα,W (q) over all probability
measures q on (Y, Y), we get an absolute measure of the
spread of W, called the order α Rényi radius of W,
Sα,W , inf q∈P(Y,Y) supw∈W Dα (w k q) .

E0 (ρ,p)
ρ
ρ= 1−α
α

(2)

Any probability measure q on the measurable space (Y, Y)
satisfying Sα,W (q) = Sα,W , is called an order α Rényi center
of W. The order one Rényi divergence is the Kullback-Leibler
divergence; hence the order one Rényi radius and center are
the Shannon radius and center referred to in [56].
The Shannon capacity, defined as the supremum of the
mutual information, is another measure of the spread of a
set of probability measures on a given measurable space.
In order to have a parametric generalization of the Shannon
capacity, similar to the one provided by the Rényi radius to
the Shannon radius, we need a parametric generalization of
the mutual information. Sibson [93] proposed one such parametric generalization using the Rényi divergence, called the
Rényi information, see Definition 4. For any set of probability
measures W on a given measurable space (Y, Y), probability
mass function p on W, and positive real number α, Iα (p;W)
is the order α Rényi information2 for prior p. The order one
1 This dichotomy is an immediate consequence of Lemma 15, see page 11
for a more detailed discussion.
2 Sibson defines “the information radius of order α” through an infimum
and then derives a closed form expression for it in [93, Thm. 2.2]. We take
that closed form expression as the definition of the order α Rényi information.

2

Similar to Theorem 1, some of the observations that we
discuss in the paper have been reported before either in terms
of Rényi’s information measures [25], [93] or in terms of other
related quantities, such as Gallager’s function, [5], [6], [35],
[37]. But we also have a number of new observations that
have not been reported before. We provide a tally of our most
important contributions in §I-C.
We conclude the current section with a summary of our
notational conventions presented in §I-D. It is worth mentioning that only §I-D is necessary to understand the rest of the
paper; readers may bypass other parts of the current section
depending on their interest and background.
The Rényi entropy [78] is another information measure, that
is intimately related to the information measures discussed
in this paper. The Rényi entropy [7], [76] and its variants
[4], [33], [83], [97] are of interest by themselves [14], [45],
[52], [77]; in addition they have been used to pose projection
problems [61], [62], [63] related to guessing [3], [84], [95] and
various questions about the information transmission problems
[10], [12], [96]. Recently, there has been a revived interest in
the Rényi information measures and their operational significance [11], [15], [16], [17], [27], [34], [90], [99], in general.

of the space. In principle, one can measure the relative and
the absolute spread of the subsets of X using any non-negative
function g on X × X satisfying g(x , x ) = 0 for all x ∈ X and
define a center accordingly. However, neither the existence nor
the uniqueness of such a center is guaranteed.
When X in the above formulation is the space of all
probability measures P(Y, Y) on a measurable space (Y, Y),
one can measure the spread of a subset W of P(Y, Y) using the
Kullback-Leibler divergence. The resulting radius is nothing
but the Shannon radius of W and whenever the Shannon radius
is finite the existence of a unique Shannon center follows
from Kemperman’s result [56, Thm. 1]. The other assertion
of Kemperman’s result [56, Thm. 1] is the equality of the
Shannon radius of W and the Shannon capacity of W, defined
as the supremum of the mutual information I (p;W) over all
probability mass functions p on W. For the case when both W
and Y are finite sets Kemperman’s result was already known at
the time [37, Thm. 4.5.1]; in [56] Kemperman attributes this
special case to Shannon [88]. For the case when Y is a finite
set, first Gallager [36, Thm. A] and then Davisson and LeonGarcia [29, Thm. 3] proved results equivalent to Kemperman’s.
Later, Haussler [49] proved Kemperman’s result assuming Y
is a complete separable metric space, i.e. Polish space, and Y
is the associated Borel σ-algebra.
Theorem 1, which we prove in the following, extends
Kemperman’s result to the Rényi capacity and center of other
orders. The existence of a unique center under the finite
capacity hypothesis and the equality of the capacity and the
radius have been confirmed in other contexts, as well.
1) Radius for f -Divergence: Csiszár [19], [21], Morimoto
[65], and Ali and Silvey [1] defined the f -divergence using
convex functions, satisfying f (1) = 0. The Kullback-Leibler
divergence4 is the f -divergence corresponding to the function
f (x ) = x ln x . For any convex function f satisfying f (1) = 0,
the absolute and relative f -radius are defined in terms of the
corresponding f -divergence as follows:

A. Radius, Center, and Capacity
The concepts of radius and center, as we use them, are
analogous to their counter parts in Euclidean geometry. Let
W be a set of points in n dimensional Euclidean space ℜn
and q be a point in the same space. Then one measure of
the spread of W relative to q is the infimum of the radii of
the q-centered spheres including all points of W, called the
Chebyshev radius of W relative to q:
SW (q) , supw∈W kw − qk2

∀W ⊂ ℜn , q ∈ ℜn .

If we do not require the centers of the spheres to be at a given
point q, we get an absolute measure of the spread of W, called
the Chebyshev radius of W:
SW , inf q∈ℜn supw∈W kw − qk2

Sf ,W (q) , supw∈W Df (w k q) ,

∀W ⊂ ℜn .

Sf ,W , inf q∈P(Y,Y) supw∈W Df (w k q) .

If SW is finite, there exists3 a unique Chebyshev center qW
satisfying SW (qW ) = SW .
For any set of points in a metric space (X , d ), one can
define the Chebyshev radius by replacing ℜn with X and
kw − qk2 with d (w , q) in the definition. However, neither
the existence nor the uniqueness of the Chebyshev center is
a foregone conclusion for such generalizations. Garkavi [39,
Thm. 1] provides a three point set in a Banach space that
does not have a Chebyshev center. In the Hamming space of
length two binary strings, both (0, 0) and (1, 1) are Chebyshev
centers of the set W = {(0, 1), (1, 0)}. See [2, Ch. 15], for a
discussion of these concepts on the inner product spaces.
The Chebyshev radius is, in a sense, special because it is
defined via the distance measure —the metric corresponding
to the norm of the space for normed spaces and the metric of
the space for metric spaces— that is a part of the description

The f -information and the f -capacity are defined in terms of
corresponding f -divergence as follows
If (p;W) , inf q∈P(Y,Y) Df (p⊛Wk p ⊗ q) ,
Cf ,W , supp∈P(W) If (p;W)

where p⊛W is the probability measure whose marginal distribution on the support of p is p and whose conditional
distribution is w and p ⊗ q is the product measure.
The mutual information5 is the f -information corresponding
to f (x ) = x ln x . For W’s that are finite, Csiszár proved the
following two assertions, see [23, Thm. 3.2]:
4 For positive finite orders other than one the Rényi divergence is not
an f -divergence itself; but it can be written in terms of
an f -divergence:
α
−1
1
ln(1+(α−1)Df (w k q)) for f (x ) = xα−1
, as previously
Dα (w k q) = α−1
pointed out in [20, (14)], [21, (1.10)], [22, (6)], [81, (1)], [82, (80)].
5 For positive finite orders other the Rényi information can be written in
terms of an f -information, as a direct consequence of the analogous relation
α
−1
1
ln(1+(α−1)If (p;W)) for f (x ) = xα−1
.
for divergences: Iα (p;W) = α−1

3 The existence follows from the extreme value theorem for lower semicontinuous functions. The uniqueness is a result of the uniform convexity of
finite dimensional Euclidean spaces.

3

Cf ,W = Sf ,W for any f that is strictly convex at 1.
There exists a unique f -center for any f that is strictly
convex, provided that Sf ,W is finite.
For f ’s that are strictly convex, it seems both assertions of
Csiszár [23, Thm. 3.2] can be extended to arbitrary W’s
using the technique employed by Kemperman in [56], as
Kemperman himself suggested. Gushchin and Zhdanov [44]
proved that Cf ,W equals to Sf ,W for any convex function
f and set of probability measures W provided that Y is a
complete separable metric space, i.e. Polish space, and Y is
the associated Borel σ-algebra.
2) Radius in Quantum Information Theory: In this paper,
we assume W to be a set of probability measures on a given
measurable space. This is a generalization of the case when W
is a set of probability mass functions on a given finite set Y,
i.e. the finite sample space case. Another generalization of the
finite sample space case is obtained by assuming W to be a
set of |Y|-by-|Y| positive semidefinite, trace one, Hermitian
matrices. In quantum information theory such matrices are
called the density matrices; they represent the states of a
|Y| dimensional Hilbert space H, [51, §1.2]. The set of
all such states is denoted by S(H). There is a one-to-one
correspondence between the diagonal members of S(H) and
the probability mass functions on Y. As a result statements
about subsets of S(H) can be interpreted as generalizations
of the corresponding statements about sets of probability mass
functions on Y.
The definition of the Kullback-Leibler divergence has been
extended to the members of S(H); it is, however, customarily
called the quantum relative entropy [51, §3.1.1]:

radius in the classical case provided that Y is a finite set.
However, neither Kemperman’s result in [56] nor the weaker
result by Haussler in [49] require Y to be finite. Thus those
results are not subsumed by the quantum Information theoretic
versions of Kemperman’s result presented in [51], [73], [85].
The situation is similar for the quantum Rényi capacity,
radius, and center. All the results on the equality of the
quantum Rényi capacity and radius that we are aware of [27,
Thm. 6], [51, (4.74)], [58, Lemma I.3], [66, Thm. IV.8], [67,
Prop. 4.2], [104, Lemma 14] assume W to be a subset of S(H)
for a finite dimensional Hilbert space H. Hence, to the best
of our knowledge, Theorem 1 is not subsumed by any of the
known results in quantum information theory.

•

•

D (w k q) , Trw (ln w − ln q)

∀w , q ∈ S(H).

B. Augustin’s Method and the Rényi Center
Augustin’s proof of the sphere packing bound in [5] is
one of the first few complete proofs of the sphere packing
bound. Unlike its contemporaries by Shannon, Gallager and
Berlekamp in [87] and by Haroutunian in [46], Augustin’s
proof does not assume either the stationarity of the channel or
the finiteness of the input set because it does not rely on a type
based expurgation (i.e. a fixed composition argument). After
decades, Augustin’s proofs in [5] and [6] are still the only
proofs of the sphere packing bound for non-stationary product
channels, even in the finite input alphabet case. Augustin’s
method has been applied to problems with feedback, as well.
In [6], using a variant of his method, Augustin provides a proof
sketch for the derivation of the sphere packing bound for codes
on discrete stationary product channels with feedback. What
we call the discrete stationary product channels with feedback
are customarily called DMCs with feedback.
Despite their strength and generality, Augustin’s derivations
of the sphere packing bound is scarcely known to date, even
among the specialists working on related problems. In [71],
we derive sphere packing bounds using Augustin’s method
in a way that makes the roles of the Rényi capacity and
center more salient and precise. Our bound for the product
channels is sharper than the corresponding bounds in [5] and
[6]. In [71], we also present a new proof of the sphere packing
bound for the discrete product channels with feedback that
facilitates the ideas of Haroutunian [47] and Sheverdyaev [91],
as well as Augustin [5], [6]. Our new proof for the case with
feedback holds for non-stationary channels satisfying certain
stationarity hypothesis. A more general discussion of the
operational significance of the Rényi capacity and information
in the channel coding problem is presented in [71], as well.
The generality and strength of Augustin’s results compel
one to ask: What is the principle behind Augustin’s proofs of
the sphere packing bound? A succinct answer exists for those
who are already familiar with the concepts of Rényi capacity,
radius and center.7 In our judgment, the novel observation
behind Augustin’s proofs is the following:

(5)

This definition can be interpreted as an extension because for
the diagonal members of S(H), the quantum relative entropy
as defined in (5) is equal to the Kullback-Leibler divergence
between the corresponding probability mass functions. For any
subset W of S(H), the quantum Shannon radius is defined as
inf q∈S(H) supw∈W D (w k q).
The definition of mutual information has been extended as
well, but it is called the transmission information [51, §4.1.1]:
X
I(p;W) ,
p(w )D (w k qp )
∀p ∈ P(W)
(6)
w∈W
P
where qp = w∈W p(w )w . Note that when W includes only
diagonal members of S(H), the above quantity equals to the
mutual information for the prior p on the corresponding set
probability mass functions. The quantum Shannon capacity is
defined as the supremum of I(p;W) over all probability mass
functions p on W with finite support.
The quantum Shannon capacity and radius are equal to one
another for arbitrary W ⊂ S(H) provided that H is a finite
dimensional Hilbert space,6 [51, Thm. 4.1], [73, Thm. 3.5],
[85, (19)]. This implies the equality of Shannon capacity and

limφ→α Sα,W (qφ,W ) = Cα,W .

6 Results

in [73] and [85] were proved with additional assumptions. In
[73], Ohya, Petz, and Watanabe assumed W to be the image of an arbitrary
Hilbert space under the channeling transformation. In [85], Shumacher and
Westmoreland assumed W to be a closed convex set. The existence of a unique
quantum Shannon center is implicit in both [73] and [85].

7 To be precise, Augustin does not work with Rényi’s information measures
either in [5] or in [6]. It is, however, possible to restate his observations
in terms of Rényi ’s information measures. His approach is eloquent and
insightful, irrespective of the terms he chose to employ.

4

In words, by choosing φ close enough to α, the order α
Rényi radius relative to the order φ Rényi center can be made
arbitrarily close to the order α Rényi capacity, which equals
to the order α Rényi radius. This observation seems benign
enough to hold for other parametric families of divergences
and corresponding capacities, radii, and centers. Thus we
believe that Augustin’s method can probably be used to derive
tight outer bounds in other information transmission problems,
as well.

and gave a proof sketch for an equivalent assertion for
orders in (0, 1) in [5].
In Appendix A, we define Cα,W,A as the supremum
of Iα (p;W) over all priors p in A and generalize the
van Erven-Harremoës bound to the convex A case, see
Definition 10 and Lemma 25. Similar to the unconstrained
case, we need to establish the existence of a unique
center qα,W,A for any convex constraint set A with finite
Cα,W,A , first. This is done in Theorem 2.
Van Erven-Harremoës bounds, i.e. Lemmas 19 and 25,
allow simpler and shorter derivations for Lemmas 20, 21,
23, and 26. Arguably the most important application of
the van Erven-Harremoës bound is in the proof of Lemma
20, which establishes the continuity of the Rényi center
in the order, using the continuity of the Rényi capacity
in the order. This continuity result is used to define the
averaged Rényi center —which is a key concept used in
Augustin’s method— rigorously, see [71, p. 19].
(3) Our framework allows us to pose and answer certain
questions that are non-trivial only for infinite W’s, i.e.
infinite subsets of P(Y, Y).
(a) There exists a countable subset W′ of W such that
Cα,W′ = Cα,W for all α in [0, ∞], Lemma 15-(b).
(b) If Cη,W is finite, then for all ǫ > 0 there exists a finite
subset W′ of W such that Cα,W′ > Cα,W − ǫ for all
α in [ǫ, η], Lemma 15-(g).
(c) Cα,clW = Cα,W for all α in (0, ∞] where clW is the
closure of W in the topology of setwise convergence
or a stronger topology on P(Y, Y), Lemma 24-(b).
Previously, Csiszár and Körner have pointed out that
S1,clW = S1,W for finite Y case, [26, Problem 8.10(b)].
(4) Lemma 23, demonstrating an intuitive fact, is new, to the
best of our knowledge: For any α in (0, ∞], W ⊂ P(Y, Y)
satisfying Cα,W < ∞, and ǫ > 0, let Wα,ǫ be the set
of w ’s in W satisfying Dα (w kqα,W ) ≥ Cα,W − ǫ. Then
Cα,Wα,ǫ = Cα,W , qα,Wα,ǫ = qα,W , and all p ∈ P(Wα,ǫ)
satisfies |Cα,W −Iα (p;W)−Dα (qα,p k qα,W )| ≤ ǫ.

C. Main Contributions
(1) If W and Y are finite sets, the continuity of the Rényi information is evident, both as a function of the order and as
a function of the prior. In their proof of the sphere packing
bound [87, p. 101], while proving the continuity of the
Rényi capacity in the order on (0, 1) —for the finite W
and Y case— Shannon, Gallager, and Berlekamp asserted
that the Rényi information is in fact equicontinuous as a
family of functions of the order on (0, 1) indexed by the
priors. We have strengthened their assertion by replacing
the finiteness hypothesis on the sets W and Y with a finiteness hypothesis for the Rényi capacity and by including
orders larger than one. In addition, we have shown that
the Rényi information is uniformly equicontinuous when
considered as a family of functions of the prior indexed
by the orders. In particular, we have shown that8
(a) If Cη,W is finite, then Iα (p;W) as a family of functions
of the prior p indexed by the order α is uniformly
equicontinuous for orders in [0, η], Lemma 16-(e).
(b) If Cη,W is finite, then Iα (p;W) as a family of functions
of the order α indexed by the prior p is uniformly
equicontinuous on any compact subset of (0, η),
Lemma 16-(f).
We believe these uniform equicontinuity results might be
helpful in overcoming technical difficulties in the proofs
of outer bounds, such as the sphere packing bound.
(2) Reflecting on [31, Thm. 37] for countable Y’s at α = ∞,
van Erven and Harremoës conjectured the following:
Conjecture ([31, Conjecture 1]). If Sα,W < ∞ for an α
in (0, ∞] and a W ⊂ P(Y, Y) then there exists a unique
qα,W ∈ P(Y, Y) satisfying Sα,W = supw∈W Dα (w k qα,W ).
Furthermore, for all q ∈ P(Y, Y) we have

D. Notational Conventions
For any set Y, we denote the set of all subsets of Y —
i.e. the power set of Y— by 2 Y and the set of all probability
measures on finite subsets of Y by P(Y). We call each member
p of P(Y) a probability mass function (p.m.f.). We call the
set of all y’s in Y for which p(y) > 0, the support of p and
denote it by supp(p).
We call the pair (Y, Y) a measurable space iff Y is a σalgebra of subsets of Y. On a measurable space (Y, Y), we
denote the set of all finite signed measures by M(Y, Y), the
+
set of all finite measures by M0 (Y, Y), the set of all non-zero
+
finite measures by M (Y, Y), and the set of all probability
measures by P(Y, Y). A countable collection E of subsets of
Y is called a Y-measurable partition of Y iff ∪E∈E = Y, ∅ ∈
/ E,
E ∩ Ẽ = ∅ for all E, Ẽ ∈ E, and E ⊂ Y, [8, Def. 10.8.1].
A measure µ on the measurable space (Y, Y) is absolutely
continuous with respect to another measure ν on (Y, Y), i.e.
µ≺ν, iff µ(E) = 0 for any E ∈ Y such that ν(E) = 0.
Measures µ and ν are equivalent, i.e. µ ∼ ν, iff µ≺ν and

supw∈W Dα (w k q) ≥ Sα,W + Dα (qα,W k q) .
This conjecture is confirmed in Lemma 19 for the first
time.9 Lemma 19 implicitly asserts the existence of a
unique qα,W , which is proved in Theorem 1. This assertion, however, is not entirely new; Augustin proved an
equivalent assertion for orders in (0, 2) in [6, Thm. 26.6′ ]
8 Our definition of the Rényi information, i.e. Definition 4, is restricted
to the set of priors that are probability mass functions on finite subsets
of W. This restriction allows us to define and discuss Rényi information
without qualifying our statements, but it is not necessary. In Appendix B, we
define Rényi information for a broader class of priors using the concept of
transition probability. It seems proofs of Lemmas 16-(e) and 16-(f) work with
appropriate modifications in this more general framework, as well.
9 We were notified in [48] that van Erven and Harremoës had an unpublished
proof establishing their conjecture in [31] under some regularity conditions.

5

ν≺µ. Measures µ and ν are singular, i.e. µ ⊥ ν, iff there
exists an E ∈ Y such that µ(E) = ν(Y \ E) = 0.
+
A subset W of M (Y, Y) is absolutely continuous with
respect to the measure ν, i.e. W≺ν, iff w ≺ν for all w ∈ W.
A σ-finite measure ν is a reference measure for W iff W≺ν.
+
A subset W of M (Y, Y) is uniformly absolutely continuous
with respect to ν, i.e. W≺uni ν, iff for every ǫ > 0 there
exists a δ > 0 such that w (E) < ǫ for all w ∈ W provided
that ν(E) < δ. By [92, p. 366 & Thm. 2], µ≺ν iff {µ}≺uni ν.
Two subsets W and U of P(Y, Y) are singular, i.e. W ⊥ U,
iff there exists an E ∈ Y such that w (E) = 0 for all w ∈ W
and u(Y \ E) = 0 for all u ∈ U.
We denote the Borel σ-algebra for the usual topology of the
real numbers by B(ℜ). We denote the essential supremum of
a Y-measurable, i.e. (Y, B(ℜ))-measurable, function f for the
measure ν on (Y, Y) by ess supν f (y), i.e.

measure which is the infimum of U with respect to the partial
order ≤. The existence of a unique infimum is guaranteed by
[8, Thm. 4.7.5]. We use the symbol ∨ analogously to ∧ but
we represent maxima and suprema with it, rather than minima
and infima.
II. P RELIMINARIES
We commence our discussion by defining the mean measure
and analyzing it, first as a function of the order for a given
prior then as a function of the prior for a given order. After
that we define the Rényi information using the mean measure
and analyze it as a function of the order and the prior
using the analysis of the mean measure. Then we define the
Rényi divergence and review those features of it that will be
needed in our analysis. We conclude the current section by
defining the Rényi mean and deriving an alternative expression
for the Rényi information in terms of the Rényi divergence
using the Rényi mean.

ess supν f , inf{γ : ν({y : f (y) > γ}) = 0}.
We denote the integral of a measurable
functionR f on (Y, Y)
R
with respect to the measure
ν
by
f
ν(dy)
or f (y)ν(dy ).
R
R
We denote the integral by f dy or f (y)dy , as well, if it is
on the real line and with respect to the Lebesgue measure. If
ν is a probability measure, then we also call the integral of f
with respect to ν the expectation of f or the expected value
of f and denote it by Eν [f ] or Eν [f (Y)].
While discussing the continuity of measure valued functions
and functions defined on sets of measures, we use either
the topology of setwise convergence or the total variation
topology. The topology of setwise convergence is the topology
generated by the sets of the form {µ : |µ(E) − t| < ǫ} for
some E ∈ Y, t ∈ ℜ+ , ǫ ∈ ℜ+ , see [8, §4.7(v)] for a more
detailed discussion. The total variation topology is the metric
topology generated by the total variation norm. For any µ in
M(Y, Y) the total variation norm of µ is defined as

A. The Mean Measure
The weighted power means are generalizations of the
weighted arithmetic mean. For any positive real number α
and p.m.f. p on non-negative
real numbers, the order α mean
P
1
for the prior p is ( x p(x )x α ) /α . For any prior p, the
order α weighted mean is a nondecreasing and continuously
differentiable function of α on ℜ+ . Hence we can calculate its
limit as α approaches zero, or infinity, using the L’Hospital’s
rule [79, Thm. 5.13]:
X
1/α Y
limα↓0
p(x )x α
=
x p(x )
x
x
X
1/α
= maxx :p(x )>0 x .
limα↑∞
p(x )x α
x

The order α mean of measures for the prior p is defined
via the pointwise order α mean of their Radon-Nikodym
derivatives for the prior p. In the following, we confine our
discussion to the means of probability measure.

kµk , supE∈Y µ(E) − µ(Y \ E).
As a consequence of the Lebesgue decomposition theorem [30,
5.5.3] and the Radon-Nikodym theorem [30, 5.5.4] we have
Z
dµ
kµk =
∀µ, ν : µ≺ν.
dν ν(dy )

Definition 1. Let p be a p.m.f. on P(Y, Y) and ν be a
reference measure for w ’s in P(Y, Y) with positive p(w ). Then
the order α mean of the Radon-Nikodym derivatives for the
prior p is10
Q

dw p(w)

if α = 0

 w:p(w)>0 dν  1

dµα,p
P
α
α
dw
if α ∈ ℜ+ ν-a.e. (7)
dν , 
w p(w ) dν


if α = ∞
maxw:p(w)>0 dw
dν

Our notation will be overloaded for certain symbols; however, the relations represented by these symbols will be clear
from the context. We denote the product of topologies [30, p.
38], σ-algebras [30, p. 118], and measures [30, Thm. 4.4.4]
by ⊗. We denote the Cartesian product of sets [30, p. 38] by
×. We use |·| to denote the absolute value of real numbers
and the size of sets. For extended real valued functions f and
g on Y, f ≤ g iff f (y) ≤ g(y) for all y ∈ Y. For measures µ
and ν on (Y, Y), µ ≤ ν iff µ(E) ≤ ν(E) for all E ∈ Y.
For x , y ∈ ℜ, x ∧y is the minimum of x and y. For extended
real valued functions f and g on Y, f ∧ g is the pointwise
minimum of f and g. For µ, w ∈ M(Y, Y), µ∧w is the unique
dµ
dw
measure satisfying dµ∧w
dν = dν ∧ dν for any ν satisfying µ≺ν
and w ≺ν. If F is a set of real valued functions, then ∧f ∈F f
is the extended real valued function obtained by taking the
pointwise infimum of f ’s in F. For a U ⊂ M(Y, Y) satisfying
w ≤ u for all u ∈ U for some w ∈ M(Y, Y), ∧u∈U u is the

The order α mean measure for the prior p is defined as
Z
dµα,p
µα,p (E) ,
∀E ∈ Y.
(8)
dν ν(dy )
E

P
In (7) and throughout this section
P sums of the form w
stands for sums of the form
w:p(w)>0 . In (7), w is a
dummy variable used to express the elements of P(Y, Y), i.e.
10 For each w with positive p(w ), dw exists for all y except for a νdν
measure zero set by the Radon-Nikodym theorem [30, 5.5.4]. Since there are
dµα,p
only finite number of w ’s with positive p(w ), dν
exists as a function of
α from [0, ∞] to ℜ≥0 for all y except for a ν-measure zero set.

6

(a) δ α ≤ πα,p ≤ 1 for α ∈ (0, 1] and 1 ≤ πα,p ≤ δ α for
α ∈ [1, ∞) where δ = minw:p(w)>0 p(w ). Furthermore,
Q


p[1] (w|y) p(w)


α=0

w:p(w)>0
p(w)


1/α
P
πα,p (y) =
p[1] (w |y)α p(w )1−α
α ∈ ℜ+ .


w


p (w|y)

α=∞
maxw:p(w)>0 [1]p(w)
( p (w|y)α p(w)1−α
[1]
if p(w ) > 0
πα,p α
p[α] (w |y) =
.
0
else

∀α ∈ [0, ∞] and ∀E ∈ Y.

µα,p (E) = µ
eα,p (E)

This follows from a standard application of the Lebesgue
decomposition theorem and the Radon-Nikodym theorem.
We are interested in the mean measure primarily as a tool
to define and analyze the Rényi information. In [6, §26],
Augustin introduced the mean measure and derived some of
the observations we present in Lemmas 1-4, albeit for different
parameterizations of the order. Augustin, however, did not
define or analyze the Rényi information itself in [6]. Proofs
of Lemmas 1-4 are presented in Appendix D.

(b) πα,p is a smooth function of α on ℜ+ . Furthermore, the
first two derivatives of πα,p are given by
X
p (w|y)
πα,p
d
p[α] (w |y) ln [α]
dα πα,p = α2
p(w) .
w
2 2 d
d2
d
1−α
− α dα πα,p
dα2 πα,p = πα,p dα πα,p


X
p (w|y) 2
π
+ αα,p
.
p[α] (w |y) ln [α]
3
p(w)
w

α

Lemma 1. Let p be a p.m.f. on P(Y, Y).

(c) (πα,p ) is log-convex
and α0 , α1 ∈ ℜ+

1
−α

≤ kµα,p k ≤ |supp(p)| for
(a) µα,p ∼ µ1,p and |supp(p)|
any α ∈ (0, ∞]. Furthermore, kµ1,p k = 1.
(b) µ0,p ≺w for any w ∈ supp(p) and kµ0,p k ≤ 1.

Lemma 2 establishes the density πα,p as a smooth function
µ1,p -a.e. and provides expressions for its first two derivatives.
These derivatives are Y-measurable functions because πα,p
and p[α] are Y-measurable. Then using their µ1,p -integrals we
can define two mappings:
Z
′
(πα,p
)µ1,p (dy)
∀E ∈ Y,
(11)
µ′α,p (E) ,
E
Z
′′
(πα,p
)µ1,p (dy)
∀E ∈ Y.
(12)
µ′′α,p (E) ,

(9)

Note that for any p.m.f. p on P(Y, Y), the order α density
for the prior p is a Y-measurable function from Y to ℜ by the
Radon-Nikodym theorem [30, 5.5.4].
The order α posteriors defined in the following provides us
an alternative way to express πα,p and its derivatives.

E

p[α] (w |y) ,

p(w )
0



dw
dµα,p

α

if p(w ) > 0

.

2

d
d
where
and
are shorthands for dα
πα,p and dα
2 πα,p .
Note that we have not claimed that either of these mappings
is defining a measure for each α. Lemma 3 given in the
following establishes that fact and analyzes the mean measure
µα,p as a function of the order α.
′
πα,p

Definition 3. Let p be a p.m.f. on P(Y, Y) and α be a positive
real number. Then for each y ∈ Y the order α posterior p[α]
is a p.m.f. on P(Y, Y) given by
(

in α on ℜ+ , i.e. for any β ∈ (0, 1)

where αβ = βα1 + (1 − β)α0 . Furthermore, for α1 6= α0
the inequality is strict iff there exist w , w̃ ∈ supp(p) such
p (w|y)
that [1]p(w) > p(p(w̃w̃|y)
) > 0.
(d) If there exists a w such that p[1] (w |y) > p(w ), then
πα,p (y) is bounded, continuous, and monotone increasing
in α on [0, ∞], else πα,p (y) = 1 for all α in [0, ∞].

Definition 2. Let p be a p.m.f. on P(Y, Y) and α be in [0, ∞].
Then the order α density for the prior p is
dµα,p
dµ1,p .

11

(παβ ,p )αβ ≤ (πα1 ,p )βα1 (πα0 ,p )(1−β)α0

The main consequence of Lemma 1 is that µα,p ≺µ1,p for
all α ∈ [0, ∞]. Hence, we can describe and analyze the mean
measures via their Radon-Nikodym derivatives with respect to
the order one mean measure. We build our analysis of the mean
measure as a function of the order around this observation.
dµ
First, we analyze dµα,p
as a function the order α in Lemma
1,p
2; then use the dominated convergence theorem to obtain the
corresponding results for µα,p in Lemma 3.

πα,p ,

1−α

1−α

probability measures on (Y, Y). The probability mass assigned
to each w by p is denoted by p(w ). The reference measure
ν is absent from the symbol for the mean measure because
mean measure does not depend on the choice of the reference
measure: Let µ
eα,p be the mean measure obtained using a
reference measure νe instead of ν; then

′′
πα,p

Lemma 3. For any p.m.f. p on P(Y, Y).
(a) µα,p is a continuous function of α from [0, ∞] with
+
its usual topology to M0 (Y, Y) with the total variation
topology.
(b) µ′α,p is a continuous function of α from (0, ∞) with
+
its usual topology to M0 (Y, Y) with the total variation
d
µα,p = µ′α,p in the sense that
topology. Furthermore, dα

(10)

else

The order α posterior p.m.f. p[α] is a Y-measurable function
for each w . The order one posterior p.m.f. p[1] is also called
the posterior p.m.f., in accordance with the usual terminology.

d
dα µα,p (E) α=φ

= µ′φ,p (E)

∀E ∈ Y, ∀φ ∈ (0, ∞).

11 Both

of the following statements are equivalent to the log-convexity of
(πα,p )α in α: “π 1 ,p is log-convex in ρ” and “For any β ∈ [0, 1] and

Lemma 2. For any p.m.f. p on P(Y, Y) the following statements hold for µ1,p -almost every y.

1+ρ

α0 , α1 ∈ (0, ∞], παβ ,p ≤ (πα0 ,p )1−β (πα1 ,p )β where αβ is αβ = [(1 −
β)(α0 )−1 + β(α1 )−1 ]−1 .”

7

(c) µ′′α,p is a continuous function of α from (0, ∞) with
its usual topology to M(Y, Y) with the total variation
d ′
µα,p = µ′′α,p in the sense that
topology. Furthermore, dα
d ′
dα µα,p (E) α=φ

= µ′′φ,p (E)

Sibson introduced this quantity12 in [93] using works of
Rényi [78] and Csiszár [21], [22].
Note that Iα (p;W) has the same value for all W’s for
which p is in P(W). Hence, in principle, one can use Iα (p)
rather than Iα (p;W) to denote the Rényi information. Although
this unconventional symbol would be more coherent with
the one we use for mean measure, we refrain from using
it for the fear of alienating readers who prefer the customary symbol. Another justification for using the conventional
notation is the effect of the richness of W — as measured
by supp∈P(W) Iα (p;W)— on the continuity of Iα (p;W) as a
function of p, see Lemma 16-(e).
Properties of the Rényi information as a function of the
order for fixed prior and as a function of the prior for fixed
order are presented in Lemmas 5 and 6, respectively. Proofs
of Lemmas 5 and 6 are presented in Appendix E.

∀E ∈ Y, ∀φ ∈ (0, ∞).

α

(d) kµα,p k is a log-convex function of α on (0, ∞) such that
X
p(w ).
limα↓0 kµα,p kα = ess supµ1,p
w:p[1] (w|y)>0

The log-convexity is strict everywhere on (0, ∞), unless
there exists a γ ≥ 1 satisfying µ1,p (A(p, γ)) = 1 for
p (w|y)
A(p, γ) = {y : [1]p(w) = γ, ∀w : p[1] (w |y) > 0}. If
α−1

there exists such a γ, then kµα,p k = γ α .
(e) kµα,p k is a continuous and nondecreasing function of
α from [0, ∞] to [0, |supp(p)|]. If there exist w , w
e in
supp(p) such that w 6= w
e , then kµα,p k is monotone
increasing everywhere on (0, ∞), else kµα,p k = 1 for
all α in [0, ∞].

Lemma 5. For any subset W of P(Y, Y) and p.m.f. p on
W, I∞ (p;W) ≤ ln |supp(p)| and Iα (p;W) is a non-negative
continuously differentiable nondecreasing function of α on ℜ+
such that

Lemma 3 described the properties of the mean measure as
a function of the order for a fixed prior. Lemma 4, given in
the following, describes the properties of the mean measure
as a function of the prior for a fixed order.

I0 (p;W) = limα↓0 Iα (p;W) ,
I∞ (p;W) = limα↑∞ Iα (p;W) ,

′
 α kµα,p k − ln kµα,p k
α−1 kµα,p k
(α−1)2
d
dα Iα (p;W) =  µ′′ (Y)+2kµ′ k−kµ′ k2
1,p
1,p
1,p

Lemma 4. Let (Y, Y) be a measurable space.
(a) If α ∈ [0, 1], then µα,p and kµα,p k are convex functions of
+
p from P(P(Y, Y)) to M0 (Y, Y) and [0, 1], respectively.
(b) If α ∈ [1,∞], then µα,p and kµα,p k are concave functions
+
of p from P(P(Y, Y)) to M (Y, Y) and [1, ∞), respectively.
(c) For any p1 , p2 ∈ P(P(Y, Y)) such that p1 6= p2 , let
p1 ∧p2
1 −p1 ∧p2
, s1 , 2 pkp
, and
s∧ , s1 and s2 be s∧ , 2 2−kp
1 −p2 k
1 −p2 k
p2 −p1 ∧p2
s2 , 2 kp1 −p2 k . Then s∧ , s1 , s2 ∈ P(P(Y, Y)) and
p1 = (1 −

p2 = (1 −
s1 ⊥ s2 .

kp1 −p2 k
)s∧
2
kp1 −p2 k
)s∧
2

+
+

2

α ∈ ℜ+\{1}

. (16)

α=1

Using the definitions of µ′α,p and µ′′α,p , given in (11) and
(12), together with Lemma 2-(b), we get the following two
alternative expressions for the derivative of Iα (p;W) with
respect to the order on ℜ+

h
i
p (w|y)
1

E̟α ln [α]
−Iα (p;W) α 6= 1
(α−1)α
p(w)

d
2 
(17)
p[1] (w|y)
dαIα (p;W)= 1
α=1
2 E̟1 ln p(w) −I1 (p;W)

i
h
p[α] (w|y)πα,p
1

α 6= 1
(α−1)
2 E̟α ln p
[1] (w|y)kµα,p k 

2
(18)
=
p (w|y)

α=1
12 E̟1 ln [1]p(w) −I1 (p;W)

kp1 −p2 k
s1 ,
2
kp1 −p2 k
s2 ,
2

1
α kp1

(15)

If µ1,p (A(p, γ)) = 1 for some γ ≥ 1, then Iα (p;W) = ln γ for
d
Iα (p;W) > 0 for all α ∈ ℜ+ , where
all α ∈ [0, ∞], else dα
p[1] (w|y)
A(p, γ) , {y : p(w) = γ ∀ w with positive p[1] (w |y)}.

(d) If α ∈ (0, 1], then for any p1 , p2 ∈ P(P(Y, Y)) we have
kµα,p1 − µα,p2 k ≤

(14)

− p2 k.

Hence µα,p is a Lipschitz continuous function of p for the
total variation topology for α ∈ (0, 1].
(e) If α ∈ [1, ∞), then for any p1 , p2 ∈ P(P(Y, Y)) we have

where ̟α is a probability measure on Y ⊗ 2 supp(p) whose Y
µ
and whose conditional distribution is p[α]
marginal is kµα,p
α,p k
The continuity and the convexity properties of the Rényi information in the prior follow from the corresponding properties
of the mean measure described in Lemma 4.

1

kµα,p1 −µα,p2 k ≤ ( 12 kp1 −p2 k) α kµα,s1 −µα,s2 k.
B. The Rényi Information
Definition 4. Let W be a subset of P(Y,Y) and p be a p.m.f.
on W. Then the order α Rényi information for the prior p is

1

α=0
ess inf ln P 1{p (w|y

)>0} p(w)

µ1,p
[1]

w


 α ln kµα,p k
α−1 
 α ∈ ℜ+\{1}
Iα (p;W) ,
P
p
(w|y)
[1]


α=1
Eµ1,p
p[1] (w |y) ln p(w)



w


ln kµ∞,p k
α=∞
(13)

12 Sibson called inf
q∈P(Y,Y) Dα (p⊛Wk p ⊗ q) “the information radius
of order α” and proved that it equals to the expression given in Definition 4
in [93, Thm. 2.2]. Our presentation is different: Definition 4 does not refer
to any infimum; equivalence of the alternative definition is established in
Lemma 14. This is similar to the way things are, usually, handled for the
mutual information: the mutual information is defined without any reference
to an infimum [18, (2.28)], later it is shown to be equal to the infimum of
certain Kullback-Leibler divergence [18, Lemma 10.8.1].
Gallager introduced E0 (ρ, p) in [35], prior to Sibson [93]. The Gallager’s
function E0 (ρ, p), defined in (4), is nothing but a scaled version of the
Rényi information, as we have already pointed out in (3).

8

Lemma 6. Let W be a subset of P(Y, Y).

uniquely define probability measures w|G and q|G on (Y, G).
In the following, we denote Dα w|G q|G by DαG (w k q).

(a) If α ∈ [0, 1), then Iα (p;W) is a non-negative quasiconcave function of p on P(W), that is continuous for
the total variation topology on P(W).
(b) If α ∈ [1, ∞], then Iα (p;W) is a non-negative concave
function of p on P(W).

Lemma 9 ([31, Thm. 9]). For any α ∈ [0, ∞], probability
measure w and q on (Y, Y) and sub-σ-algebra G ⊂ Y
Dα (w k q) ≥ DαG (w k q) .

Lemma 10 ([31, Thm. 3, Thm. 31]). For any α ∈ [0, ∞],
probability measure w and q on (Y, Y)

Gallager [35, p. 18] and Csiszár [23, Lemma 3.2] established the continuity of Iα (p;W) in p on P(W), for finite W’s.
For arbitrary W’s, however, Iα (p;W) is continuous only for
orders in (0, 1); for orders in [1, ∞], Iα (p;W) is continuous in
p on P(W) iff supp∈P(W) Iα (p;W) is finite, see Lemma 16-(d).
The finiteness of supp∈P(W) Iα (p;W) also implies the uniform
equicontinuity of the Rényi information, see Lemma 16-(e,f).
The discontinuity of various Shannon information measures
for countably infinite output sets have previously been pointed
out by Ho and Yeung in [53].

Dα (w k q) ≥

1∧α
2 kw

2

− qk .

(20)

For orders in (0, 1], the bound given in (20) is called the
Pinsker’s inequality; it has been proved by Csiszár [21] for
α = 1 case and by Augustin14 [6] and Gilardoni [42] for α ∈
(0, 1) case. Furthermore the constant α/2 is the best possible:
for any γ < α/2 there are probability measures w and q such
that γkw − qk2 > Dα (w k q). Determination of best lower
bound on the Rényi divergence in terms of the total variation
is an interesting and important problem but it is beyond the
scope of the current manuscript.15

C. The Rényi Divergence
Definition 5. Let w and q be two non-zero finite measures
on the measurable space (Y, Y); then the order α Rényi divergence between w and q is



α=0
− ln q dw

dν > 0 


1−α

 1 ln R dwα dq
+
dν  ν(dy) α ∈ ℜ \{1}
(19)
Dα (w k q) , Rα−1  dν
dq
 dw ln dw −ln

ν(dy)
α=1

dν
dν
dν



dq
ln ess supν dw
α=∞
dν / dν

Lemma 11 ( [31, Thm. 12]). For any order α ∈ [0, ∞], the
order α Rényi divergence is convex in its second argument
for probability measures, i.e. for all w , q1 , q2 ∈ P(Y, Y) and
β ∈ (0, 1) we have
Dα (w k qβ ) ≤ βDα (w k q1 ) + (1 − β)Dα (w k q0 )
where qβ = βq1 + (1 − β)q0 .
Lemma 12 ([31, Thm. 13]). For any order α ∈ [0, ∞], the
order α Rényi divergence is quasi-convex in its arguments
jointly for probability measures, i.e. for all w1 , w2 , q1 , q2 in
P(Y, Y) and β ∈ (0, 1) we have

where ν is any measure satisfying w ≺ν and q≺ν.

The Rényi divergence is usually defined for probability
measures; the inclusion of finite measures allows us to express
certain observations, such as Lemma 8 given in the following,
more succinctly.13 Nonetheless, the propositions derived for
the usual definition with probability measures suffice for our
purposes most of the time. We appropriate all the propositions
we need for our analysis, except Lemma 8, from the recent
paper of van Erven and Harremoës [31]. The equivalence of
Definition 5 and the one used by van Erven and Harremoës in
[31] for probability measures follows from [31, Thm. 4-6].

Dα (wβ k qβ ) ≤ Dα (w1 k q1 ) ∨ Dα (w0 k q0 )
where wβ = βw1 + (1 − β)w0 and qβ = βq1 + (1 − β)q0 .
Lemma 13 ([31, Thm 15]). For any order α ∈ (0, ∞],
Dα (w k q) is a lower semicontinuous function of the pair
of probability measures (w , q) in the topology of setwise
convergence.
The preceding lemmas discuss only the aspects of the
Rényi divergence that is useful for our discussion. A more
complete discussion can be found in [31].

Lemma 7 ([31, Thm. 3, Thm. 7]). For all w , q ∈ P(Y, Y),
Dα (w k q) is a nondecreasing and lower semicontinuous function of α on [0,∞] that is continuous on [0, (1 ∨ χw,q )] where
χw,q , sup{α : Dα (w k q) < ∞}.

kw−qk2

(α−1)Dα(wkq )

≤ 1−e α(1−α)
for all
to [6, Lemma 26.5b],
2
w , q ∈ P(Y, Y) and α ∈ [−1, 2]. This implies (20) for α ∈ (0, 1) via the
identity e−x ≥ 1 − x .
15 Kullback [59], [60] proved that D (w k q) ≥ kw − qk2/2 + kw − qk4/36.
1
Hence, Pinsker’s inequality is tight only for kw − qk ≈ 0. Vajda [102]
−qk
2kw −qk
established D1 (w k q) ≥ ln( 2+kw
) − 2+kw
. Vajda’s inequality
2−kw −qk
−qk
is tight not only for kw − qk ≈ 0 but also for kw − qk ≈ 2. Fedotov,
Harremoës, and Topsøe [32] determined the tight lower bound on D1 (w k q)
in terms of kw − qk in a parametric form. Gilardoni [40], [41] proved an
equivalent result for f -divergences for twice differentiable f ’s. Gilardoni’s
result implies tight bounds for Rényi divergences, which are recently derived
in a more explicit form by Sason [81, Proposition 1]. The core observation in
the derivation of tight Vajda’s inequalities is the sufficiency of the probability
measures on binary alphabets. Guntuboyina, Saha, and Schiebinger [43] have
recently generalized this observation considerably and explained how one can
determine tight bounds on an f -divergence when its arguments are constrained
in terms of other f -divergences. Recall that the total variation distance is the
f -divergence for f (x ) = |x − 1|.
14 According

Lemma 8 is evident form the definition of Rényi divergence.
Lemma 8. Let w , q, v be non-zero finite measures on (Y, Y)
and α be an order in [0, ∞].
• If v ≤ q, then Dα (w k q) ≤ Dα (w k v ).
• If q = γv for a γ ∈ ℜ+ , then Dα (w k q) = Dα (w k v )−ln γ.
Let w and q be two probability measures on the measurable
space (Y, Y) and G be a sub-σ-algebra of Y. Then the identities
w|G (E) = w (E) for all E ∈ G and q|G (E) = q(E) for all E ∈ G
13 It is also convenient while studying the concept of the Rényi-Gallager
information and capacity, see [69] and [72].

9

definition is proposed by Augustin in [6, §34] and later by
Csiszár in [25]
X
Iαc (p;W) ,
inf
p(w )Dα (w k q) .
(26)

D. The Rényi Mean
We have defined the Rényi information using a closed form
expression. The original definition of the Rényi information
by Sibson, however, is in terms of an optimization of the
Rényi divergence over a set of probability measures. These
two definitions are equivalent, as it has already been shown
by Sibson [93, Thm. 2.2]. In the following, we establish this
equivalence and briefly discuss an alternative definition of the
Rényi information related to the aforementioned characterization in terms of the Rényi divergence.

q∈P(Y,Y)

Unlike the definition we have adopted, the one given in (26)
does not have an equivalent closed form expression. But for
any finite positive order α, the infimum in (26) has a unique
minimizer, which is a fixed point of an operator defined
using α and p, [69]. These properties were first proved by
Augustin for orders between zero and one in [6]. Thus we
have called the quantity defined in (26), the order α Augustin
information in [72]. We present a more detailed discussion of
the properties of the Augustin information and its relation to
the Rényi information in [69].
Arimoto proposed a third definition for the Rényi information in [4]. Recently Verdú has provided a discussion of the
Rényi entropy and these three definitions of the Rényi information in [103].

Definition 6. Let p be a p.m.f. on P(Y, Y); then the order α
Rényi mean for prior p is

−D1(p[0] kp[1] )
1{ϑp (y )=ϑ̄p } µ1,p

 e
α=0
R −D1(p[0] kp[1] )
(21)
qα,p ,
1{ϑp (y )=ϑ̄p } µ1,p (dy)
e

 µα,p
α ∈ (0,∞]
kµα,p k
P
where ϑp (y) ,
w p(w )1{p[1] (w|y)>0} , ϑ̄p , ess supµ1,p ϑp ,

and p[0] (w |y) ,

p(w)1{p[1] (w|y )>0}
P
.
u p(u)1{p(u|y )>0}

III. T HE R ÉNYI C APACITY

Then the following identity can be confirmed by substitution
using (19): For any α in (0, ∞], p in P(W), and q in P(Y, Y),

Definition 7. Let α be an order in [0, ∞] and W be a subset
of P(Y, Y); then the order α Rényi capacity of W is

Dα (p⊛Wk p ⊗q) = Dα (p⊛Wk p ⊗qα,p )+Dα (qα,p k q) . (22)

Cα,W , supp∈P(W) Iα (p;W) .

This identity was first pointed out by Sibson in [93, p. 153],
then by others [25, (12)] [50, (43)] [74, (38)] [89, Lemma 3]
[103, (52)]. For α = 1 case, it had been used by Topsøe in
[100], even before Sibson [93], and in [101].
On the other hand, one can also confirm by substitution that
Iα (p;W) = Dα (p⊛Wk p ⊗ qα,p ) for all positive values of α.
These two observations lead to the alternative characterization
of the order α Rényi information in terms of the order α
Rényi divergence presented in the following lemma, which is
valid for all non-negative orders.

=

inf Dα (p⊛Wk p ⊗ q)

=

inf Dα (µα,p k q)

q∈P(Y,Y)

q∈P(Y,Y)

(27)

Unlike the order α Rényi information, the order α Rényi capacity is not a quantity that is introduced or discussed by Sibson in [93]. In the spirit of his earlier work on f -divergences
[23], Csiszár introduces it16 in [25].
Using the alternative characterization of the Rényi information given in (24), we get the following expression for the
order α Rényi capacity for all α in [0, ∞]
Cα,W = supp∈P(W) inf q∈P(Y,Y) Dα (p⊛Wk p ⊗ q) .

Lemma 14. Let W be a subset of P(Y, Y), p be a p.m.f. on
W, and α be an order in [0, ∞]; then
Iα (p;W) = Dα (p⊛Wk p ⊗ qα,p )

w

(28)

For finite orders the Rényi capacity does not have a closed
form expression. The supremum given in the definition of the
Rényi capacity need not to be finite, see Examples 6 and 7.
Even when the supremum is finite it might not be achieved by
any prior, i.e. there are W’s for which Iα (p;W) < Cα,W for
all p ∈ P(W), see Examples 2 and 4. When the supremum
is achieved, the optimal prior might not be unique, i.e. there
are W’s for which Iα (p1 ;W) = Iα (p2 ;W) = Cα,W for p1 6= p2
both of which are in P(W), see Example 3. These subtleties,
however, do not constitute a serious impediment for analyzing
the Rényi capacity.
In §III-A, we analyze the Rényi capacity as a function of the
order. In §III-B, we determine necessary and sufficient conditions for the finiteness of the Rényi capacity and investigate
the implications of the finiteness of the Rényi capacity on the
continuity of the mean measure and the Rényi information.

(23)
(24)
α ∈ (0, ∞]\{1} (25)

where p⊛W is the probability measure on 2 supp(p) ⊗ Y whose
marginal distribution on supp(p) is p and whose conditional
distribution is w .
Proof of Lemma 14 is presented in Appendix F. For any
positive order α and prior p, the only probability measure q
satisfying Dα (p⊛Wk p ⊗ q) = Iα (p;W) is qα,p as a result
of (22) and Lemmas 10, 14. In other words, the order α
Rényi mean for prior p is the unique minimizer for the
infimum given in (24) for positive orders α. For α = 0, the
order zero Rényi mean is still a minimizer by Lemma 14 but
it is not necessarily the unique minimizer. Any probability
measure q that is absolutely continuous in the q0,p satisfies
D0 (p⊛Wk p ⊗ q) = I0 (p;W).
The definition of Rényi information we have adopted is
not the only definition of Rényi information. The following

16 In

[35], Gallager introduces a ‘capacity’ using E0 (ρ, p) as follows
(
supp∈P(W) E0 (ρ, p) ρ ∈ ℜ+
.
E0 (ρ, W) ,
inf p∈P(W) E0 (ρ, p) ρ ∈ (−1, 0)

Note that E0 (ρ, W) = ρC

10

1 ,W
1+ρ

by (3).

on (0, φ] by Lemma 15-(a,f), Cα,W is infinite on [φ, ∞] by
the hypothesis, and hence Cα,W is continuous on (0, ∞] by
the pasting lemma [68, Thm. 18.3]. —Example 6 provides a
W for each φ ∈ (1, ∞) such that χW = (0, φ).— Thus unless
χW = (0, φ] for some φ ∈ [1, ∞), Cα,W is continuous on
(0, ∞]. If χW = (0, φ], then Cα,W is bounded and continuous
on (0, φ] and infinite on (φ, ∞]. Hence the Rényi capacity
has a unique discontinuity on (0, ∞], which is at α = φ. —
Example 7 provides a W for each φ ∈ [1, ∞) such that Cα,W
has its unique discontinuity at α = φ.—

A. The Rényi Capacity as a Function of the Order
We are interested in characterizing the behavior of the
Rényi capacity as a function of the order because the operational significance of the Rényi capacity, at least for the
channel coding problem and the sphere packing bound, is not
through its value at a specific order but through its behavior
as a function of the order. Parts (a,c,d,e,f) of Lemma 15
characterize the behavior of the Rényi capacity for an arbitrary
W as a function of the order. When analyzing the behavior of
the Rényi capacity for a specific family of W’s, proofs of some
of our results might be valid only for countable W’s, because
of a construction we use in the proof or because of another
technical constraint. In that hypothetical situation, Lemma 15(b) would enable us to extend our results from countable W’s
to arbitrary W’s. Lemma 15-(g) establishes a similar but, in a
sense, more subtle property for the case of finite W’s rather
than countable ones.17

Proof of Lemma 15.
(a) The pointwise supremum of a family of nondecreasing
(lower semicontinuous) functions is nondecreasing (lower
semicontinuous). Then Cα,W is nondecreasing and lower
semicontinuous in α on [0, ∞] because Cα,W is the
pointwise supremum of the family {Iα (p;W)}p∈P(W) and
Iα (p;W) is nondecreasing and continuous in α for each
p ∈ P(W) by Lemma 5.
(b) The Rényi capacity is a nondecreasing and lower semicontinuous function of the order by part (a). Then

Lemma 15. Let W be a subset of P(Y, Y).
(a) Cα,W is nondecreasing and lower semicontinuous in α on
[0, ∞].
(b) There exists a countable subset W′ of W satisfying
Cα,W′ = Cα,W for all α ∈ [0, ∞].
(c) 1−α
α Cα,W is nonincreasing and continuous in α on (0, 1)
and Cα,W is continuous in α on (0, 1].
(d) (α − 1)Cα,W is convex in α on (1, ∞).
(e) If Cη,W < ∞ for an η ∈ (0, 1), then Cα,W is finite for
all α ∈ [0, 1).
(f) If Cη,W < ∞ for an η ∈ (0, ∞], then Cα,W is nondecreasing and continuous18 in α on (0, η].
(g) If Cη,W < ∞ for an η ∈ (0, ∞], then ∀ǫ > 0, ∃ a finite
subset W′ of W such that Cα,W′ > Cα,W − ǫ for all
α ∈ [ǫ, η].

Cη,W = supα∈(0,η)∩Q Cα,W

∀η ∈ (0, ∞].

Consequently, Cα,W′ = Cα,W for all α in [0, ∞] if
Cα,W′ = Cα,W for all α ∈ Q≥0 . Choose a sequence of
p.m.f.’s {p (α,ı) }ı∈Z+ satisfying Iα p (α,ı) ;W ↑ Cα,W for
each α ∈ Q≥0 . Let W′ be ∪α∈Q≥0 ∪ı∈Z+ supp(p (α,ı) ).
Then Cα,W′ = Cα,W for all α ∈ Q≥0 ; hence for all α
in [0, ∞]. W′ is countable because countable union of
countable sets is countable.
(c) kµα,p k is nondecreasing and continuous in α, by Lemma
3-(e). Furthermore, the definitions of Iα (p;W) and Cα,W
imply
1−α
α Cα,W

The Rényi information Iα (p;W) is continuous in α for any p
in P(W) by Lemma 5, however the Rényi capacity Cα,W is not
necessarily continuous in α. Yet, if the Rényi capacity Cα,W
is not continuous in α on (0, ∞], then it has a very specific
shape as a result of Lemma 15: there exists a φ ∈ [1, ∞) such
that Cα,W is bounded and continuous on (0, φ] and infinite on
(φ, ∞]. In order to see why, first note that if C1/2,W = ∞, then
Cα,W = ∞ for all α in (0, ∞] by Lemma 15-(a,e) and Cα,W is
continuous on (0, ∞]. On the other hand, if C∞,W < ∞, then
Cα,W is continuous on (0, ∞] by Lemma 15-(f). Hence, Cα,W
can fail to be continuous on (0, ∞] only when C1/2,W < ∞
and C∞,W = ∞. Let χW be the set of all orders α for which
Cα,W is finite, i.e.

1
= supp∈P(W) ln kµα,p
k

∀α ∈ (0, 1).

Then 1−α
α Cα,W is nonincreasing and lower semicontinuous in α on (0, 1) because the pointwise supremum
of a family of nonincreasing (lower semicontinuous)
functions is nonincreasing (lower semicontinuous). Thus
1−α
α Cα,W and Cα,W are both continuous from the right
on (0, 1). On the other hand Cα,W and 1−α
α Cα,W are
both continuous from the left on (0, 1) because Cα,W
is nondecreasing and lower semicontinuous on (0, 1) by
part (a). Consequently, Cα,W and 1−α
α Cα,W are both
continuous on (0, 1). Furthermore, Cα,W is continuous
on (0, 1] because Cα,W is nondecreasing and lower
semicontinuous by part (a).
α
(d) kµα,p k is log-convex in α by Lemma 3-(d). On the other
hand, by the definitions of Iα (p;W) and Cα,W we have

χW , {α ∈ ℜ+ : Cα,W < ∞}.
χW is either of the form (0, φ) for a φ ∈ [1, ∞] or of the
form (0, φ] for a φ ∈ [1, ∞) because Cα,W is nondecreasing
by Lemma 15-(a) and finite on (0, 1) by Lemma 15-(e). If
χW = (0, φ) for some φ ∈ [1, ∞], then Cα,W is continuous

(α − 1)Cα,W = supp∈P(W) α ln kµα,p k

∀α ∈ (1, ∞).

Then (α−1)Cα,W is convex in α because the pointwise
supremum of a family of convex functions is convex.
(e) If Cη,W is finite, then so is Cα,W for all α in [0, η]
because Cα,W is nondecreasing in α by part (a). Furthermore, if Cη,W is finite, then so is Cα,W for all α in
[η, 1) because 1−α
α Cα,W is nonincreasing in α on (0, 1)
by part (c).

17 As pointwise statements, i.e. as statements for a given order, Lemma
16-(b,g) follow trivially from the definition of the Rényi capacity. They are
non-trivial only because their assertions hold for all orders for the same W′ .
18 We are unable to establish the continuity of C
α,W at α = 0 for arbitrary
W. For finite W, Sion’s minimax theorem implies the continuity of Cα,W at
α = 0, see Lemma 16-(g).

11

2 2
Recall that x β ln2 x ≤ ( βe
) for all x ∈ [0, 1] and β > 0
2
2 2 ǫ
and ln x ≤ ( ǫe ) x for all x ≥ 1 and ǫ > 0. Thus
h
i
Iα(p;W)−I1(p;W)
2 2
2 2 πβ+ǫ,p β+ǫ
(
.
≤
E
)
+
(
)
(
)
qβ,p
φ−1
βe
ǫe
πβ,p

(f) Cα,W is continuous in α on (0, 1] by part (c). Thus we
only need to prove the claim for the case when η > 1
on [1, η]. We prove the continuity of Cα,W in α first on
(1, η], and then from the right at α = 1. If Cη,W is finite
for an η in (1, ∞), then (α − 1)Cα,W is finite and convex
in α on [1, η] by parts (a) and (d). Then the continuity
of (α − 1)Cα,W , and hence the continuity of Cα,W , in
α on (1, η) follows from [30, Thm. 6.3.3]. On the other
hand Cα,W is continuous from the left because Cα,W is
nondecreasing and lower semicontinuous in α by part (a).
Hence, Cα,W is continuous in α on (1, η].
If C∞,W is finite, then Cη,W is finite for all η ∈ ℜ+
by part (a) and Cα,W is continuous in α on ℜ+ because
the continuity of a function on a collection of open set
implies its continuity on their union, [68, Thm. 18.2].
This implies the continuity of Cα,W on (0, ∞] because
Cα,W is nondecreasing and lower semicontinuous in α
by part (a).
For proving the continuity of Cα,W from the right at
α = 1, we first prove that {Iα (p;W)}p∈P(W) is equicontinuous from the right at α = 1. The definitions of µ′α,p
and Iα (p;W) given in (11) and (13) and Lemma 2-(b)
imply
Iα (p;W) − I1 (p;W) =

Since (πα,p )α is log-convex in α by Lemma 2-(c),
(πβ+ǫ,p )β+ǫ ≤ (πβ,p )β+ǫ−1 π

Then using the fact that kµβ,p k ≥ kµ1,p k = 1 we get
h
i
Iα(p;W)−I1(p;W)
2 2
2 2
≤
(
)
+
(
)
µ
β
.
,p
φ−1
βe
ǫe
1−ǫ

Note that µβ/1 − ǫ,p ≤ µα/1 − ǫ,p because kµα,p k is
nondecreasing in α by Lemma 3-(e). Then using the
definition of Rényi information, β > 1, and φ ∈ (1, α)
we get
Iα (p;W) − I1 (p;W) ≤

Iα (p;W) ≤ I1 (p;W) +

α ln kµα,p k−(α−1)kµ′1,p k
α−1

≤ C1,W +

Cα,Wı ≥ Cα,Wı−1

β,p

On the other hand using the definition µ′′α,p given in (12)
together with Lemma 2-(b) and β > 1 we get,
"
#
X p (w|y)
2kµ′ k
µ′′
[β]
2 p[β] (w|y)
β,p (Y)
− βkµβ,p
ln
kµβ,p k ≤ Eqβ,p
β3
p(w)
β,p k
w

= Eqβ,p

w

p(w )

#

8(α−1) η−1
η Iη(p;W)
ǫ2 e2 e

8(α−1) η−1
η Cη,W .
ǫ2 e2 e

Cα,Wı ≥ Cα,W − 2−ı

µ′′
kµ′β,p k
kµ′β,p k
β,p (Y)
= 2 kµβ,p
k + β kµβ,p k − β kµ k2 . (29)

i
p[1] (w|y) β 2 p[1] (w|y)
ln p(w)πβ,p
p(w)πβ,p

(30)

Hence, Cα,W is continuous from the right at α = 1 if
Cη,W < ∞ for an η > 1.
(g) Let us first consider η ∈ ℜ+ case and construct a
sequence {Wı }ı∈Z+ of finite subset of W, such that
Cα,Wı ↑ Cα,W for all α ∈ (0, η). Choose a p (ı,) in
P(W) such that I2−ı p (ı,) ;W ≥ C2−ı ,W −2−ı for each
ı ∈ Z+ and non-negative integer  not exceeding
2ı η. Let
⌊2ı η⌋
W0 be the empty set and Wı be Wı−1 ∪=0 supp(p (ı,) )
for each ı ∈ Z+ . Then

2

h

.

8(α−1) η−1
η Iη(p;W) .
ǫ2 e2 e

Cα,W ≤ supp∈P(W) I1 (p;W) +

The expression on the right hand side is differentiable in
d
d
φ because dφ
µ′φ,p = µ′′φ,p (Y)
kµφ,p k = µ′φ,p and dφ
by Lemma 3-(b,c). On the other hand, kµφ,p k > 0 for
φ ∈ ℜ+ and kµ1,p k = 1 by Lemma 1-(a). Then the
expression on the right hand side is zero at φ = 1. Hence,
using the mean value theorem [79, 5.10] once again we
can conclude that there exists a β ∈ (1, φ) such that

"w
X

α−1+ǫ
I α (p;W)
α
1−ǫ

Then for any ǫ ∈ (0, η−1
η ) and α ∈ [1, (1 − ǫ)η] we have

kµ′φ,p k
′
Iα (p;W) − I1 (p;W) = ln kµφ,p k + φ kµφ,p
k − µ1,p .

Then using Lemma 2-(a) and (29) we get
"
#
X p (w|y)
Iα(p;W)−I1(p;W)
2 p[β] (w|y)
[β]
≤ Eqβ,p
ln p(w)
φ−1
β2

8(α−1)
ǫ2 e2 e

Then for any ǫ ∈ (0, η−1
η ) the following inequality holds
for all α ∈ [1, (1 − ǫ)η]

for all α in (1, η] and p in P(W). The expression in
the numerator is differentiable in α because kµα,p k is
d
differentiable by Lemma 3-(b). Furthermore, dα
kµα,p k =
′
µα,p by Lemma 3-(b) and the numerator is zero at
α = 1. Then by the mean value theorem [79, 5.10], there
exists a φ ∈ (1, α) such that

Iα(p;W)−I1(p;W)
φ−1

∀ǫ ∈ (0, 1), β > 1.

β
1−ǫ ,p

.

12

∀α ∈ [0, ∞], ı ∈ Z+
ı

⌋
+
∀α ∈ { 20ı , . . . , ⌊η2
2ı }, ı ∈ Z .

Then Cα,Wı ↑ Cα,W for all dyadic rational numbers α
less than η. Therefore Cα,Wı ↑ Cα,W for all α ∈ [0, η]
because the Rényi capacity is nondecreasing and lower
semicontinuous. Since Cη,Wı ≤ Cη,W < ∞, Cα,Wı ’s
and Cα,W are continuous in α on (0, η] by part (f). Then
as a result of Dini’s theorem [30, 2.4.10], {Cα,Wı }ı∈Z+
converges to Cα,W uniformly on [ǫ, η], i.e. for all ε > 0,
there exists ı such that supα∈[ǫ,η] Cα,W − Cα,W < ε
for all  > ı.
For η = ∞ case, let κı be the smallest integer satisfying
C∞,W ≤ Cκı 2−ı ,W + 2−ı for each ı ∈ Z+ . We employ
the construction described above for ’s not exceeding κı
rather than ’s not exceeding ⌊2ı η⌋.

IV. T HE R ÉNYI C ENTER

B. Finiteness of the Rényi Capacity
If W is a finite set, then P(W) is compact for the total
variation topology and various results relying on the compactness can be invoked while analyzing the Rényi information.
For example, if W is finite, then the compactness of P(W)
and Sion’s minimax theorem imply the continuity of the
Rényi capacity in the order on [0, ∞], see Lemma 16-(g).
When W is an infinite set, however, P(W) is not compact.
The finiteness of the Rényi capacity emerges as a shrewd
substitute for the compactness of P(W) that allows us to assert
the continuity of the Rényi information, see Lemma 16-(e,f).
Lemma 16-(a-d) characterize the finiteness of the order α
Rényi capacity in terms of the properties of the order α mean
measure or Rényi information. These equivalent conditions
might be easier to confirm or reject for certain W’s. The
equicontinuity results given in Lemma 16-(e,f) imply that if
γ1 ≤ Iα (p;W) ≤ γ2 for all p ∈ A for some α in (0, η) and
γ1 and γ2 in [0, Cη,W ], then for any ǫ > 0 there exists a
δ > 0 such that γ1 − ǫ ≤ Iφ (s;W) ≤ γ2 + ǫ for all φ in
[α − δ + α + δ] and s in P(W) satisfying inf p∈A kp − sk ≤ δ.
This observation (or its variants, which can be obtained by
employing either Lemma 16-(e) or Lemma 16-(f) on its
own) might be helpful when we are trying to bound the
Rényi information or a related functions uniformly over the
orders and priors through a case by case analysis on a subset
of P(W) or on its neighborhoods.

The primary focus of this section is Theorem 1, given in the
following, and its applications. In §IV-A we prove Theorem
1 and discuss alternative proofs based on Sion’s minimax
theorem. In §IV-B we first prove a lower bound on Sα,W (q),
i.e. the van Erven-Harremoës bound, then we use this bound
to establish the continuity of the Rényi center as a function
of the order. §IV-C is composed of various applications of
Theorem 1 and the van Erven-Harremoës bound.
Theorem 1. For any α ∈ (0, ∞] and W ⊂ P(Y, Y)
Cα,W = supp∈P(W) inf q∈P(Y,Y) Dα (p⊛Wk p ⊗ q)

= inf q∈P(Y,Y) supp∈P(W) Dα (p⊛Wk p ⊗ q)
= inf q∈P(Y,Y) supw∈W Dα (w k q) .

(31)
(32)
(33)

If Cα,W < ∞, then there exists a unique qα,W in P(Y, Y),
called the order α Rényi center, such that
Cα,W = supp∈P(W) Dα (p⊛Wk p ⊗ qα,W )
= supw∈W Dα (w k qα,W ) .

(34)
(35)

Furthermore, for every sequence of priors {pı }ı∈Z+ satisfying
limı→∞ Iα (pı ;W) = Cα,W , the corresponding sequence of
order α Rényi means {qα,pı }ı∈Z+ is a Cauchy sequence for
the total variation metric on P(Y, Y) and qα,W is the unique
limit point of that Cauchy sequence.

Lemma 16. Let W be a subset of P(Y, Y).
(a) For α ∈ (0, 1), Cα,W = ∞ iff there exists a sequence
{pı }ı∈Z+ ⊂ P(W) such that limı→∞ kµα,pı k = 0.
(b) For α ∈ (1, ∞], Cα,W = ∞ iff there exists a sequence
{pı }ı∈Z+ ⊂ P(W) such that limı→∞ kµα,pı k = ∞.
(c) For α ∈ (1, ∞), Cα,W < ∞ iff µα,p is uniformly continuous
in p for the total variation topology.19
(d) For α ∈ [1, ∞], Cα,W < ∞ iff Iα (p;W) is continuous in p
on P(W) for the total variation topology.
(e) For η ∈ ℜ≥0 , if Cη,W < ∞, then {Iα (p;W)}α∈[0,η] is
uniformly equicontinuous,20 in p on P(W).
(f) For η ∈ ℜ+ , if Cη,W < ∞, then {Iα (p;W)}p∈P(W) is
uniformly equicontinuous in α on every compact subset
of (0, η).21
(g) If |W| < ∞, then Cα,W is nondecreasing and continuous
in α on [0, ∞].

Theorem 1 is stated for p’s that are probability mass
functions on W. However, the interpretation of capacity as
the radius implicit in (33) and (35) can be used to extend
the Theorem 1 to the case when p’s are appropriately defined
probability measures, see Appendix B.
For finite orders, neither the Rényi capacity nor the
Rényi center has a closed form expression; this, however, is
not the case for order infinity. The following expressions can
be confirmed using the observation described in (39) by the
interested reader.
_
C∞,W = ln
w ,
(36)
_ w∈W
q∞,W =
w e−C∞,W .
(37)
w∈W

Before presenting the proof and applications of Theorem 1,
let us make a brief digression and discuss what is achieved by
Theorem 1 itself.
Note that the expression in (33) is nothing but the definition
of the α Rényi radius Sα,W . Hence, Theorem 1 establishes
the equality of the order α Rényi capacity and the order α
Rényi radius. We prefer to express the equality of Cα,W and
Sα,W as a minimax equality because unlike the equality of
Cα,W and Sα,W itself, the minimax equality continues to hold
in the constrained variant of the problem, see Theorem 2 of
Appendix A.
Theorem 1 strengthens this minimax equality by asserting the existence of a unique Rényi center that is
achieving the infimum in (32). Recall that we have already established, in Lemma 14, the existence of a unique
Rényi mean qα,p achieving the infimum in (31) for any p
in P(W). The suprema in (31) and (32), however, cannot

Proof of Lemma 16 is deferred to Appendix C. For W’s
with infinite Cα,W , the proof of part (d) establishes the discontinuity at every p in P(W). For order one the discontinuity
of I1 (p;W) was observed by Ho and Yeung [53, Theorem 3]
for a different topology for some W. For the same topology
they established the continuity of I1 (p;W) whenever Y is finite
[53, Corollary 8]. They, however, did not characterize the
conditions for the continuity of I1 (p;W) in their framework.
19 For α ∈ (0, 1], µ
α,p is uniformly continuous in p, even when Cα,W =
∞, because µα,p is Lipschitz continuous on P(P(Y, Y)) by Lemma 4-(d).
20 For α ∈ (0, 1), Lemma 6-(a) has established the continuity of I (p;W)
α
in p without assuming Cα,W to be finite; but the continuity is not uniform.
21 In order to prove the uniform equicontinuity on compact subsets of (0, η),
we prove the following stronger statement: On every compact subset of (0, η),
{Iα (p;W)}p∈P(W) is a family of Lipschitz continuous functions of α with a
common Lipschitz constant, see (119).

13

Lemma 17. For any α in [0, ∞] and finite subset W of
P(Y, Y), ∃e
p ∈ P(W) such that Iα (e
p ;W) = Cα,W . If α is
in (0, ∞], then ∃!qα,W ∈ P(Y, Y) such that,

be replaced by maxima in general. Example 4 provides a
W for which inf q∈P(Y,Y) Dα (p⊛Wk p ⊗ q) < Cα,W and
Dα (p⊛Wk p ⊗ qα,W ) < Cα,W for all p in P(W). Evidently,
this subtlety exists only for infinite W’s; for finite W’s
the compactness of P(W) and the extreme value theorem
guarantees the existence of a p achieving the supremum.
The last assertion of Theorem 1, relating the problem of
determining Rényi capacity to the problem of determining
Rényi center, is important because of its potential in simplifying the problem of determining the Rényi center —defined
as the unique qα,W satisfying (35).
In addition, Theorem 1 provides us a necessary and sufficient condition for a prior p to satisfy Iα (p;W) = Cα,W . That
is important because we do not have a closed form expression
for the order α Rényi capacity, yet occasionally the symmetries
of the elements of W or numerical calculations suggest a prior
p that might satisfy Iα (p;W) = Cα,W .
Iα (p;W) = Cα,W

iff

Sα,W (qα,p ) ≤ Iα (p;W) .

Dα (qα,p k qα,W ) ≤ Cα,W − Iα (p;W)

Proof. (i) ∃e
p ∈ P(W) such that Iα (e
p ;W) = Cα,W : Since
|supp(p)| ≤ |W| for all p ∈ P(W), Cα,W ≤ ln |W|
by Lemma 5. Then Iα (p;W) is continuous on P(W) by
Lemmas 6-(a) and 16-(d). Then there exists a pe achieving
the supremum by the extreme value theorem, [68, 27.4]
because P(W) is compact for finite W.
(ii) If Iα (e
p ;W) = Cα,W for an α ∈ (0, ∞], then
Dα (qα,p k qα,ep ) ≤ Cα,W − Iα (p;W) for all p ∈ P(W):
Let pe ∈ P(W) be such that Iα (e
p ;W) = Cα,W , p be any
e + 1ı p for ı ∈ Z+ .
member of P(W) and pı be pı = ı−1
ı p
For α = ∞ using Lemma 14 we get

(38)

I∞ (pı ;W) = [I∞ (e
p ;W) + D∞ (q∞,ep k q∞,pı )]
∨ [I∞ (p;W) + D∞ (q∞,p k q∞,pı )] .

Then D∞ (q∞,ep k q∞,pı ) = 0 because I∞ (pı ;W) ≤ C∞,W
and I∞ (e
p ;W) = C∞,W . Consequently q∞,ep = q∞,pı and
I∞ (pı ;W) = C∞,W . Thus
I∞ (p;W) + D∞ (q∞,p k q∞,ep ) ≤ C∞,W .
I1 (pı ;W) =

ı−1
ı

[I1 (e
p ;W) + D1 (q1,ep k q1,pı )]

+ 1 [I1 (p;W) + D1 (q1,p k q1,pı )] ,
h ı
(α−1)(Iα(e
p ;W)+Dα(qα,ep kqα,pı ))
1
Iα (pı ;W) = α−1
ln ı−1
ı e

i
+ 1ı e(α−1)(Iα(p;W)+Dα(qα,p kqα,pı )) .

ı→∞

where q ∈ P(Y, Y) is implicit for the latter statement. We
determine the Rényi capacity using (38) in Examples 1, 3, 4
and using (39) in Examples 2, 9 and in Appendix G.
(34) of Theorem 1 and (22) imply that
∀p ∈ P(W).

(42)

For α = 1 and α ∈ ℜ+ \ {1} we have

lim Iα (pı ;W) = Cα,W iff ∃q : Sα,W (q) ≤ lim Iα (pı ;W) (39)

Dα (qα,p k qα,W ) ≤ Cα,W − Iα (p;W)

(41)

Hence, qα,ep = qα,W for all e
p such that Iα (e
p ;W) = Cα,W .

In order to see why (38) holds, note that if Iα (p;W) = Cα,W
then considering the sequence {pı }ı∈Z+ where pı = p we
can conclude that qα,p = qα,W . Then Sα,W (qα,p ) ≤ Iα (p;W)
by (35). On the other hand, if Sα,W (qα,p ) ≤ Iα (p;W) for
some p in P(W), then Iα (p;W) = Cα,W by (33) because
Iα (p;W) ≤ Cα,W and Sα,W ≤ Sα,W (qα,p ) by the definitions
of Rényi capacity and center.
Following a similar reasoning one can show that {pı }ı∈Z+
is optimal iff Sα,W (limı→∞ qα,pı ) ≤ limı→∞ Iα (pı ;W). We
chose the following less explicit characterization over the
aforementioned one in order to avoid ensuring the convergence
of probability measures formally.22
ı→∞

∀p ∈ P(W).

Then using Iα (pı ;W) ≤ Cα,W , Iα (e
p ;W) = Cα,W , and
Dα (qα,ep k qα,pı ) ≥ 0 we get the following identity
Iα (p;W) + Dα (qα,p k qα,pı ) ≤ Cα,W .

Similarly, using Iα (pı ;W) ≤ Cα,W , Iα (e
p ;W) = Cα,W ,
Iα (p;W) ≥ 0, and Dα (qα,p k qα,pı ) ≥ 0 we get
(
(1−α)Cα,W
1
ln ı−e ı−1
α ∈ ℜ+ \{1}
.
Dα (qα,ep k qα,pı ) ≤ α−1
Cα,W
α=1
ı−1

(40)

Consequently, Dα (qα,p k qα,W ) is close to zero whenever
Iα (p;W) is close to Cα,W .
A. Minimax Theorems and the Relative Compactness

Then qα,pı → qα,ep in the total variation topology by
Lemma 10. Thus

We start by proving Theorem 1 for finite W case. In this case
Theorem 1 can be strengthened slightly because the existence
of an optimal prior is guaranteed. The optimal prior, however,
is not necessarily unique, see Example 3. Even then all such
p’s have exactly the same Rényi mean. For finite Y case,
Lemma 17 is well-known, though in a slightly different form,
see [37, Thm. 4.5.1], [26, p. 128] for α = 1 case and [37,
Thm. 5.6.5], [26, p. 172] for α ∈ (0, 1) case. Csiszár’s result
[23, Thm. 3.2] implies Lemma 17 for α’s in ℜ+ .

Dα (qα,p k qα,ep ) ≤ limı→∞ Dα (qα,p k qα,pı )
by Lemma 13. Then
Iα (p;W) + Dα (qα,p k qα,p̃ ) ≤ Cα,W

∀α ∈ ℜ+ . (43)

(iii) If α ∈ (0, ∞], then ∃!qα,W ∈ P(Y, Y) satisfying (41)
such that qα,p = qα,W for all p with Iα (e
p ;W) = Cα,W :
(42), (43) and Lemma 10 implies that

22 We only need C
α,W ≤ Sα,W , but not Cα,W = Sα,W , in order to
deduce Iα (p;W) = Cα,W from Sα,W (qα,p ) ≤ Iα (p;W). The sufficiency
of the conditions given in (38) and (39) for the optimality follows from the
maxmin inequality and the definitions of radius and capacity without invoking
Theorem 1. We need Theorem 1 in order to assert their necessity.

Iα (p;W) +

α∧1
2 kqα,p

2

− qα,p̃ k ≤ Cα,W

Then qα,p̃ = qα,p for any p satisfying Iα (p;W) = Cα,W .

14

qα,pı ∈ P(Y, Y) for all ı ∈ Z+ the limit point qα,W
is in P(Y, Y), by [68, Thm. 2.1.3].
We have established the existence of a unique limit point
for any {pı }ı∈Z+ satisfying limı→∞ Iα (pı ;W) = Cα,W .
However, we have not ruled out the possibility of distinct
limit points for different sequences satisfying the constraint. Let {pı }ı∈Z+ and {p̃ı }ı∈Z+ be two sequences satisfying limı→∞ Iα (pı ;W) = limı→∞ Iα (p̃ı ;W) = Cα,W ,
with limit points qα,W and q̃α,W . Let {p̂ı }ı∈Z+ be
a sequence whose elements for the odd indices are
the elements of {pı }ı∈Z+ and whose elements for
the even indices are the elements of {p̃ı }ı∈Z+ . Then
limı→∞ Iα (p̂ı ;W) = Cα,W ; consequently the sequence
{qα,p̂ı }ı∈Z+ is Cauchy. Thus {qα,p̂ı }ı∈Z+ and all of its
subsequences has the same unique limit point q̂α,W . Then
qα,W = q̂α,W = q̃α,W .
(iii) qα,W satisfies the equality given in (34): For any p in
P(W), let us consider a sequence {pı }ı∈Z+ satisfying
both p1 = p and limı→∞ Iα (pı ;W) = Cα,W . Then p ∈
P(Wı ) for all ı ∈ Z+ . Then using the inequality given
in (41) of Lemma 17 together with (22) we get

When W is not a finite but an arbitrary subset of P(Y, Y),
we cannot invoke the extreme value theorem to establish the
existence an optimal prior p satisfying Iα (p;W) = Cα,W
because P(W) is not compact. Assuming Cα,W to be finite,
Theorem 1 recovers all assertions of Lemma 17, but the
existence of an optimal prior, albeit in a weaker form.
Proof of Theorem 1. For all p ∈ P(W) and q ∈ P(Y, Y), (19)
implies Dα (p⊛Wk p ⊗ q) ≤ maxw∈supp(p) Dα (w k q). Then
considering p’s satisfying p(w ) = 1 for a w in W we get
supw∈W Dα (w k q) = supp∈P(W) Dα (p⊛Wk p ⊗ q)

(44)

for all q ∈ P(Y, Y). Note that (32) implies (33) and (34)
implies (35) because of (44). Furthermore, (31) is nothing but
(28) and expression on the right hand side of (31) is bounded
from above by the expression in (32) as a result of maxmin
inequality. Thus when Cα,W is infinite (32) holds trivially.
When Cα,W is finite the converse of maxmin inequality, and
hence (32), follows from (34). Thus we can assume Cα,W to
be finite and prove the claims about qα,W , in order to prove
the theorem.
(i) If Cα,W < ∞ and limı→∞ Iα (pı ;W) = Cα,W , then
{qα,pı }ı∈Z+ is a Cauchy sequence in P(Y, Y) for the
total variation metric: For any sequence {pı }ı∈Z+ of
members of P(W) satisfying limı→∞ Iα (pı ;W) = Cα,W ,
let {Wı }ı∈Z+ be a nested sequence of finite subsets of
W defined as follows,

Dα (p⊛Wk p ⊗ qα,Wı ) ≤ Cα,Wı

Then for any ı ∈ Z+ , there exists a unique qα,Wı satisfying (41) by Lemma 17. Furthermore, P(W ) ⊂ P(Wı )
for any ı,  ∈ Z+ such that  ≤ ı. In order to bound
qα,p − qα,pı for positive integers  < ı, we use the
triangle inequality for qα,p , qα,pı , and qα,Wı :

Dα (p⊛Wk p ⊗ qα,W ) ≤ Cα,W .
Thus using (24) we get

qα,p −qα,pı ≤ qα,p −qα,Wı +kqα,pı −qα,Wı k. (45)

Iα (p;W) ≤ Dα (p⊛Wk p ⊗ qα,W ) ≤ Cα,W

Let us proceed with bounding qα,p − qα,Wı .
qα,p − qα,Wı

≤

≤

2
α∧1

[Cα,Wı − Iα (p ;Wı)]

≤

2
α∧1

[Cα,W − Iα (p ;W)] .

(b)
(c)

qα,p qα,Wı

∀p ∈ P(W).

Then (34) follows the definition of Cα,W .



2
α∧1 Dα

(46)

Since Wı is a finite set, ∃e
pı ∈ P(Wı ) satisfying
Iα (e
pı ;Wı) = Cα,Wı and qα,epı = qα,Wı by Lemma 17.
Then Iα (e
pı ;Wı) ≥ Iα (pı ;Wı) because pı ∈ P(Wı ) by
construction. Consequently limı→∞ Iα (e
pı ;W) = Cα,W .
We have already established that for such a sequence
qα,epı → qα,W in the total variation topology, and hence
in the topology of setwise convergence. Then the lower
semicontinuity of the Rényi divergence, i.e. Lemma 13,
the identity Cα,Wı ≤ Cα,W , and (46) imply

Wı , ∪ı=1 supp(p ).

2 (a)

∀ı.

Theorem 1 is not just a minimax theorem, the assertions
about the Rényi center are crucial. But those assertions can be
derived separately, if need be. Leaving them aside, we discuss
in the rest of this subsection when (32) can be proved using
Sion’s minimax theorem [57], [94].
Note that P(W) is compact iff W is a finite set and P(Y, Y)
is compact iff Y is a finite set. Consequently, when either W
or Y is finite (32) is an immediate consequence23 of Sion’s
minimax theorem [57], [94]. When W and Y are both infinite
sets, however, neither P(W) nor P(Y, Y) is compact —for the
total variation topology— and we cannot directly apply Sion’s
minimax theorem. Yet, it is possible to recover partial results
using the concept of relative compactness. Recall that a set of
points in a topological space is called relatively compact if it
has a compact closure.

where (a) follows from Lemma 10, (b) follows from
Lemma 17 because pe ∈ P(Wı ), and (c) follows from the
identities Iα (p ;Wı) = Iα (p ;W) and Cα,Wı ≤ Cα,W . We
can obtain a similar bound on kqα,pı − qα,Wı k2 . Then
{qα,pı } is a Cauchy sequence by (45).
(ii) If Cα,W < ∞, then ∃! qα,W in P(Y, Y) satisfying
limı→∞ kqα,W − qα,pı k = 0 for all {pı }ı∈Z+ satisfying
limı→∞ Iα (pı ;W) = Cα,W : Note that M(Y, Y) is a
complete metric space for the total variation metric,
i.e. every Cauchy sequence has a unique limit point in
M(Y, Y), because M(Y, Y) is a Banach space for the total variation topology [8, Thm. 4.6.1]. Then {qα,pı }ı∈Z+
has a unique limit point qα,W in M(Y, Y). Since P(Y, Y)
is a closed set for the total variation topology and

23 Immediate after establishing that D (p⊛Wk p ⊗ q) is upper semiconα
tinuous and quasi-concave in p. The lower semicontinuity and the quasiconvexity of Dα (p⊛Wk p ⊗ q) in q follow from Lemmas 11 and 13.

15

Proof of Lemma 19. As a result of (22) and (23) we have,

First note that as a result of Lemma 14
Iα (p;W) = inf q∈clQα,W Dα (p⊛Wk p ⊗ q)

sup Dα (p̃⊛Wk p̃ ⊗ q) ≥ Dα (p⊛Wk p ⊗ q)

(47)

p̃∈P(W)

for all p’s in P(W) and α’s in ℜ+ where Qα,W is the convex
hull of the set of all order α Rényi means:

= Iα (p;W) + Dα (qα,p k q)

for all p ∈ P(W). Let {pı }ı∈Z+ be a sequence of elements
of P(W) such that limı→∞ Iα (pı ;W) = Cα,W . Then the
sequence {qα,pı }ı∈Z+ is a Cauchy sequence with the unique
limit point qα,W by Theorem 1. Since {qα,pı } → qα,W in total
variation topology, same convergence holds in the topology of
setwise convergence because every open neighborhood in the
latter includes an open neighborhood in the former by the
definitions of these topologies. On the other hand, the order
α Rényi divergence is lower semicontinuous for the topology
of setwise convergence by Lemma 13. Thus we have

Qα,W , ch{qα,p : p ∈ P(W)}.
If Qα,W is relatively compact in the topology of setwise
convergence by Sion’s minimax theorem we have
supp∈P(W) inf q∈clQα,W Dα (p⊛Wk p ⊗ q)

= inf q∈clQα,W supp∈P(W) Dα (p⊛Wk p ⊗ q) .

(48)

We can replace clQα,W by P(Y, Y) in the expression on the
left hand side without changing its value as a result of (47).
However, that operation can decrease the value of the right
hand side because clQα,W ⊂ P(Y, Y). Thus we get,

lim inf [Iα (pı ;W) + Dα (qα,pı k q)] ≥ Cα,W + Dα (qα,W k q) .
ı→∞

Then (49) follows from (44) and (50).

supp∈P(W) inf q∈P(Y,Y) Dα (p⊛Wk p ⊗ q)

The van Erven-Harremoës bound allows us to use the
continuity of Cα,W in α and Pinsker’s inequality to establish
the continuity of qα,W in α for the total variation topology.

≥ inf q∈P(Y,Y) supp∈P(W) Dα (p⊛Wk p ⊗ q) .

The reverse inequality is the max-min inequality, which is
always valid. Thus (32) holds.
A set of finite measures W is relatively compact in the
topology of setwise convergence iff there exists a µ ∈ P(Y, Y)
such that W≺uni µ by a version of the Dunford-Pettis theorem
[8, 4.7.25]. Using de la Vallée Poussin’s characterization of
the uniform integrability [8, Thm. 4.5.9] and monotonicity of
the order α mean measure µα,p in order, i.e. Lemma 3-(b), we
can obtain sufficient conditions for the relative compactness of
Qα,W in the topology of setwise convergence for any α ∈ ℜ+ .
As a result we get the following partial result:

Lemma 20. For any W ⊂ P(Y, Y) and η ∈ (0, ∞] such that
Cη,W < ∞,
Cφ,W − Cα,W ≥ Dα (qα,W k qφ,W )

The continuity of the Rényi center as a function of the order
is important because it allows us to the interpret the Rényi centers as a transition probability from the interval on which the
Rényi capacity is finite to (Y, Y) and apply Augustin’s method,
see [71, §IV-A] for a more detailed discussion.
Proof of Lemma 20. For q = qφ,W , Lemma 19 implies
supw∈W Dα (w k qφ,W ) ≥ Cα,W + Dα (qα,W k qφ,W ) .

B. The Rényi Center as a Function of the Order

(52)

Since Dα (w k qφ,W ) is nondecreasing in α by Lemma 7,

Sα,W is defined as the greatest lower bound of Sα,W (q).
Then Theorem 1 implies, by establishing Cα,W = Sα,W ,

Dφ (w k qφ,W ) ≥ Dα (w k qφ,W ) ∀w ∈ W, φ ∈ [α, η]. (53)
On the other hand by (35) of Theorem 1 we have

∀q ∈ P(Y, Y).

Cφ,W = supw∈W Dφ (w k qφ,W )

Van Erven and Harremoës have conjectured that a better lower
bound on Sα,W (q) should hold, [31, Conjecture 1]. Van Erven
and Harremoës proved their claim for α = ∞ case assuming
Y is countable, [31, Thm. 37]. Lemma 19 establishes the
van Erven-Harremoës bound for any positive order α and
W satisfying Cα,W < ∞, using Theorem 1. A constrained
generalization, i.e. Lemma 25, can be found in Appendix A.

∀φ ∈ (0, η].

(51) follows from (52), (53), and (54).
Using Lemma 10 and (51) we get24
q
2
φ∧1 (Cφ,W − Cα,W ) ≥ kqφ,W − qα,W k.

(54)

(55)

Then, for the total variation topology on P(Y, Y), the continuity of qα,W in α follows from the continuity Cα,W in α on
(0, η], i.e. Lemma 15-(f).

Lemma 19. For any α ∈ (0, ∞], W ⊂ P(Y, Y) satisfying
Cα,W < ∞, and q ∈ P(Y, Y),
supw∈W Dα (w k q) ≥ Cα,W + Dα (qα,W k q) .

(51)

for all α and φ satisfying 0 < α < φ ≤ η. Furthermore, qα,W
is a continuous function of α on (0, η] for the total variation
topology on P(Y, Y).

Lemma 18. Let W be subset of P(Y, Y).
(i) If ∃µ ∈ P(Y, Y) such that W≺uni µ and Sη,W < ∞ for
an η ∈ (0, 1), then (32) holds ∀α ∈ (0, 1).
(ii) If Sη,W < ∞ for an η ∈ [1, ∞], then (32) holds ∀α ∈ (0, η].

Sα,W (q) ≥ Cα,W

(50)

24 For proving a similar continuity result in [6], instead of (51), Augustin
uses the inequality given in the following —which can be proved using (13),
(19), Lemma 3-(b), and Theorem 1: If either α ∈ [φ, η] and φ < 1 or
α ∈ (0, φ] and φ > 1 then

φ
Dφ qα,p k qφ,W ≤ Cφ,W − φ−1
ln kµα,p k
∀p ∈ P(W).

(49)

Lemma 19 quantifies how loose Sα,W (q) —defined in (1)—
is as an upper bound to Cα,W , as surmised by van Erven and
Harremoës in [31].
16

Lemma 21. For any α ∈ (0, ∞] and W ⊂ P(Y, Y) satisfying
W = ∪ı∈T Wı for some Wı ⊂ P(Y, Y) with finite Cα,Wı ’s,
X
supı∈T Cα,Wı ≤ Cα,W ≤ ln
eCα,Wı .
(58)

Lemma 19 established the continuity of the Rényi center in
the order for the total variation topology. We suspect a much
stronger statement is true. In the rest of this subsection, we
motivate, present, and discuss that statement.
For certain W’s the Rényi center is the same probability
measure for all orders for which it exists. For such a W,
Lemma 15-(a,c), imply the following inequality
e

φ−1
φ Cφ,W

qφ,W ≤ e

η−1
η Cη,W

qη,W

ı∈T

Furthermore,
•
•

(56)

•

for any η with finite Cη,W and φ ∈ (0, η].
If there exists a p satisfying Iα (p;W) = Cα,W (or a sequence
{pı }ı∈Z+ satisfying limı→∞ Iα (pı ;W) = Cα,W ) for all α with
finite Cα,W , then (56) holds as a result of Lemma 3-(b). This
condition holds for certain W’s whose Rényi centers do change
with the order as well, see Examples 4 and 9.
In addition there are sets of probability measures satisfying
(56) that do not satisfy any of the hypotheses described
above, see ΛT ,0,b of Example 11. (We have confirmed (56)
numerically for ΛT ,a,b for various values of a and b, as well.)

•

One might think that qα,Wı ⊥ qα,W iff Wı ⊥ W . This,
however, is true only for α’s in [1, ∞]. For α’s in (0, 1), Wı ⊥
W is a sufficient condition for qα,Wı ⊥ qα,W , but it is not
a necessary condition, see Examples 1 and 2. Augustin [6] is
the first one to point out this subtlety andP
to present necessary
and sufficient conditions for Cα,W = ln ı∈T eCα,Wı , to the
best of our knowledge. Bounds given in (58) is well known
[37, p. 535, ex. 5.17]. We use the van Erven-Harremoës bound
in order to characterize the necessary and sufficient
conditions
P
for supı∈T Cα,Wı = Cα,W and Cα,W = ln ı∈T eCα,Wı .
Let T be a finite set. For each t ∈ T, let (Yt , Yt ) be a
measurable space and wt be a probability measure
Q⊗ on (Yt , Yt ).
Then there exists a unique product measure t∈T wt on the
Q⊗
Q×
measurable space ( t∈T Yt , t∈T Yt ) by [30, Thm. 8.2.2].26
Let Wt be a subset of P(Yt , Yt ) for each t ∈ T. Then using
the existence of a unique product measure we can map the
Cartesian
product
Q×
Q⊗ of the sets Wt uniquely to a subset of
P( t∈T Yt , t∈T Yt ), called the product of Wt ’s. Then the
Rényi capacity of the product is equal to the sum of the
Rényi capacities of its components and the Rényi center of
the product, whenever it exists, is equal to the product of
the Rényi centers of its components. Lemma 22 asserts these
observations formally.
Q×
Lemma 22. For anyn finite index set T, if Y = t∈T
o Yt , Y =
Q⊗
Q⊗
w
:
w
∈
W
Y
,
and
W
=
w
:
w
=
for some
t
t
t∈T t
t∈T t
Wt ⊂ P(Yt , Yt ), then
X
Cα,W =
∀α ∈ (0, ∞].
(59)
Cα,Wt

Conjecture 1. For any W ⊂ P(Y, Y) and η ∈ (0, ∞].
satisfying Cη,W < ∞,
µφ,W ≤ µη,W
where µφ,W , e

φ−1
φ Cφ,W

∀φ ∈ (0, η]

(57)

qφ,W for all φ ∈ (0, η].

For any W using the continuity of the Rényi center in the
order, one can prove that there exists a ν in P(Y, Y) such
that {qα,W : Cα,W < ∞}≺ν. However, the continuity of the
Rényi center as a function of the order for the total variation
topology does not imply the continuity of corresponding
dqα,W
as a function of α for νRadon-Nikodym derivative dν
25
almost everywhere. If Conjecture 1 is correct, then it will
dqα,W
imply the continuity of Radon-Nikodym derivative dν
as
a function of α for ν-almost everywhere.
C. The Unions, Cartesian Products, Closures, and More
This subsection is composed of applications of Theorem 1
and Lemma 19. Lemma 21, in the following, bounds from
below and from above the Rényi capacity of a union of sets
in terms of the Rényi capacities of the sets in the union.
Lemma 22 establishes that the Rényi capacity of a Cartesian
product is equal to the sum of the Rényi capacities of its
components. Lemma 23 shows that for any positive ǫ the
order α Rényi capacity of the set of w ’s in W satisfying
Dα (w k qα,W ) ≥ Cα,W − ǫ is equal to Cα,W . Lemma 24
establishes the invariance of Cα,W under the closure and
convexification operations on W and characterizes the relative
compactness of W in terms of its Rényi capacity. Proofs of
these Lemmas are presented in Appendix C.

t∈T

Furthermore, if Cα,W < ∞, then qα,W =

= 1{sin(

1 )≤y≤sin( 1 )+|α−t |}
t −α
t −α

Q⊗

t∈T qα,Wt .

Many information transmission problems are analyzed on
W’s that are products; Lemma 22 is instrumental in the
analysis of certain problems on those W’s. The derivation of
the sphere packing bound presented in [71, §V] is a case in
point. The additivity of the Rényi capacity for products was
first reported by Gallager —in a slightly different form and
for finite W and Y case— in his seminal paper [35, Thm. 5],
see also [37, pp. 149-150, (5.6.59)]. Later, Augustin proved [6,
Lemma 26.7a], which implies Lemma 22, for finite W case
see [5, Lemma 3.6].

25 The continuity in the total variation topology does not imply the
continuity of the corresponding Radon-Nikodym derivative: Let the output
space be the real numbers between −1 and 2, and the Radon-Nikodym
derivative of qα with respect to the Lebesgue measure l be
dqα
dl

Cα,Wı = Cα,W iff Sα,W (qα,Wı ) ≤ Cα,Wı .
Cα,W , then qα,W = qα,Wı .
If Cα,Wı =P
Cα,W = ln ı∈T eCα,Wı and Cα,W is finite iff T is finite
and qα,Wı ⊥ qα,W for all ı 6=  in T.
qα,W for all ı 6=  in T, then
If T is finite
P and qα,Wı ⊥ P
qα,W = ( ∈T eCα,W )−1 ı∈T eCα,Wı qα,Wı .

+ 1{0≤y≤1} (1 − |α − t|)
26 The existence of a unique product measure is guaranteed for any finite
collection of σ-finite measures by [30, Thm. 4.4.4] and for any countable
collection of probability measures by [30, Thm. 8.2.2].

for some t in (0, 1). Evidently limη→α kqα − qη k = 0 for all α ∈ (0, 1).
α
is not continuous in α for any y ∈ (0, 1) at α = t.
But dq
dl

17

Each assertion of Lemma 24 is proved using Theorem 1
together with some other observations. The invariance of Cα,W
under the closure and the convexification operations on W,
presented in Lemma 24-(a,b), follow from the lower semicontinuity and the quasi-convexity of the Rényi divergence in its
first argument. Lemma 24-(c) follows from the monotonicity
of µα,p in α and de la Vallée Poussin’s characterization of the
uniform integrability, i.e. [8, Thm. 4.5.9].
Arguably, the most interesting observation of Lemma 24
is the following: limα↑1 α−1
α Cα,W = 0 iff there exists a
µ in P(Y, Y) satisfying W≺uni µ. This characterization is
important because W is relatively compact, i.e. has a compact
closure, in the topology of setwise convergence iff there exists
a µ in P(Y, Y) satisfying W≺uni µ by [8, Thm. 4.7.25]. Since
the topology of set wise convergence and the weak topology29
have exactly the same family of sets as their compact sets
by [8, Thm. 4.7.25], the uniform absolute continuity also
characterizes the relative compactness in the weak topology.

One curious question is whether or not one can give a class
of priors for which the lower bound given in (40) is not too
loose. Lemma 23 answers this question in the affirmative.
Lemma 23. For any α ∈ (0, ∞], W ⊂ P(Y, Y) with finite
Cα,W , and ǫ ≥ 0, let Wα,ǫ be
Wα,ǫ , {w ∈ W : Dα (w k qα,W ) ≥ Cα,W − ǫ} .

(60)

Then for any ǫ > 0, we have Cα,Wα,ǫ = Cα,W and27
0 ≤ Cα,W − Iα (p;W) − Dα (qα,p k qα,W ) ≤ ǫ

(61)

for all p in P(Wα,ǫ ). Furthermore, if W is a finite set, then
Cα,Wα,0 = Cα,W and (61) holds for ǫ = 0.
The main conclusion of Lemma 23 is the equality
Cα,Wα,ǫ = Cα,W for positive ǫ’s. This is expected for a
general W and evident, even for ǫ = 0 case, for a finite
W because of the existence of an optimal p in P(W) for
finite W’s. One might be tempted to assume the validity of
the assertions for ǫ = 0 case for arbitrary W’s. This, however,
is not true; see Example 4 for a W for which Cα,W > 0
and Cα,Wα,0 = 0. Thus finiteness of W is not a superficial
hypothesis for extending the claims to ǫ = 0 case.
In order to apply certain technical tools, we occasionally
need a given set to be closed, convex, or compact. The
observations presented in Lemma 24, given in the following,
can be helpful in such situations. For example, if we can prove
a statement about Rényi capacity assuming W to be convex,
then we can assert that statement for non-convex W’s using
Lemma 24-(a). Furthermore, in certain situations, calculating
the Rényi capacity might be easier for the convex hull or the
closure of W when compared to W itself, see Example 4.
Lemma 24-(a,b) is helpful in such situations. Note that Lemma
24-(a,b) when considered together with Lemma 21 imply the
equality of the Rényi centers of W, chW, and clW whenever
one of them exists.

V. E XAMPLES
The order α Rényi entropies of a binary random variables,
denoted hα (δ), allow us to write certain expressions succinctly
in some of the examples. For any δ ∈ [0, 1] it is defined as
(
1
α
α
1−α ln(δ + (1 − δ) ) α 6= 1 .
hα (δ) ,
(62)
1
1
δ ln δ + (1 − δ) ln 1−δ α = 1
A. Probabilities on Discrete Output Spaces
For α ≥ 1, qα,W ⊥ qα,U iff W ⊥ U. For α ∈ (0, 1),
W ⊥ U implies qα,W ⊥ qα,U but the converse is not true, i.e.
qα,W ⊥ qα,U can hold even when W and U are nonsingular.
Examples 1 and 2 provide such sets of probability measures.
Example 1. For a δ ∈ (0, 51 ), let W and U be30



1−δ
δ
0 0
0 0 1−δ
1 − δ 0 0 U =
W= δ
0 0
δ
1−δ
δ
δ
1−δ

Lemma 24. Let W be a subset of P(Y, Y).
(a) Cα,chW = Cα,W for all α ∈ (0, ∞] where chW is the
convex hull of W given by chW , {µ1,p : p ∈ P(W)}.
(b) Cα,clW = Cα,W for all α ∈ (0, ∞] where clW is the
closure of W in the topology of setwise convergence or a
stronger topology on P(Y, Y).
(c) If Cη,W < ∞ for an η ≥ 1, then {µα,p : α ∈ [0, η], p ∈ P(W)}
is uniformly absolutely continuous with respect to qη,W
and relatively compact in both the topology of setwise
convergence and the weak topology.
(d) The following four statements are equivalent:28
(i) limα↑1 1−α
α Cα,W = 0.
(ii) ∃µ ∈ P(Y, Y) such that W≺uni µ.
(iii) W has compact closure in the topology of setwise
convergence.
(iv) W has compact closure in the weak topology.

2

2

2

2

δ
1−δ



29 The weak topology on M(Y, Y) is the topology generated by all
continuous linear functions from M(Y, Y) with the total variation topology
to ℜ with its usual topology. Then the weak topology is weaker than the total
variation topology, i.e. the initial topology. On the other hand, the topology of
setwise convergence on M(Y,RY) is the topology generated by the functions
{fE : E ∈ Y} where fE (µ) = E µ(dy) for E in Y and µ in M(Y, Y). Since
fE : M(Y, Y) → ℜ is a continuous linear function for any E ∈ Y, the weak
topology is stronger than the topology of setwise convergence. Nevertheless,
the weak topology and the topology of setwise convergence have exactly the
same class of compact sets, [8, Thm. 4.7.25].
Our use of the term weak topology is consistent with the convention used
in functional analysis, see [8, pp. 281,291]. While discussing the convergence
of measures, however, the term weak topology is commonly used to describe
another topology. If there is a topology on Y and Y is the resulting Baire
σ−algebra [8, p. 12] of the subsets of Y, then one can interpret the space
of measures as a space of linear functionals on the space of continuous and
bounded functions on Y. The weak* topology on the space of measures in
this setting is often called the weak topology [8, Def. 8.1.2]. Although it is
a very important and useful concept in general, the weak topology in this
second sense is not relevant in our discussion because we have not assumed
any topological structure on Y.
30 When W and Y are finite sets and Y = 2 Y , it is customary to describe
W using a matrix. Each row corresponds to an element of W, each column
corresponds to an element of Y and the element on the row w and the column
y is equal to w (y). With a slight abuse of notation we denote the resulting
matrix by W, as well.

27 For α = ∞, (61) is valid for a broader class of p’s in particular for all
P
p’s such that ( w ∈Wα,ǫ p(w )) > 0.
1−α
28 Augustin proves the equivalence of lim
α↑1 α Cα,W = 0 and ∃µ ∈
P(Y, Y) such that W≺uni µ, using Gallager’s inner bound [35, Thm. 1] and
a different characterization of the relative compactness he derives in [6]. Our
proof measure theoretic and self contained.

18

Example 3. For a δ ∈ [0, 1/2], let W be

1/2 − δ
δ
δ
1/2 − δ 1/2 − δ
δ
W=
1/2 − δ 1/2 − δ
 δ
1/2 − δ
δ
δ

The third member of W is not singular with the members
of U; thus W is not singular with U. We show in the
δ
)] where
following that qα,W ⊥ qα,U for all α ∈ (0, f −1 ( 1−δ
1
−1
f
: [0, 4 ] → [0, 1] is the inverse of the bijective decreasing
1
function f (x ) , (21−x − 1) x .
For U and p = [1/2 1/2] we have


Iα (p;U) = ln 2 − hα (δ)
qα,p = 0 0 1/2 1/2

Let pβ be [β/2 β/2 (1 − β)/2 (1 − β)/2] for any β ∈ [0, 1].
Then for all α in ℜ+ and β in [0, 1] we have


Iα (pβ ;W) = ln 2 − hα (2δ)
qα,pβ = 1/4 1/4 1/4 1/4 .

Furthermore, Dα w k qα,pβ = Iα (pβ ;W) for all w in W. Thus
Iα (pβ ;W) = Cα,W and qα,W = qα,pβ for all β in [0, 1] and α
in ℜ+ by (38).

where hα (δ) is defined in (62). On the other hand, both u’s
in U satisfy Dα (uk qα,p ) = ln 2 − hα (δ)
 . Then (38) implies

that Cα,U = ln 2 − hα (δ) and qα,U = 0 0 1/2 1/2 .
For W and pe = [1/2 1/2 0] we have


Iα (e
p ;W) = ln 2 − hα (δ)
qα,ep = 12 12 0 0 .

We have demonstrated in Example 2 that for certain infinite
W’s Iα (p;W) < Cα,W for all p in P(W). Example 4,
given in the following, demonstrates that a stronger assertion
“Dα (w k qα,W ) < Cα,W for all w in W” is true for certain
infinite W’s. Hence, the claims of Lemma 23 about Wα,ǫ
cannot be extended to ǫ = 0 case for infinite W’s, because
for the W given in Example 4 Cα,W > 0 and Wα,0 = ∅.

The first two w ’s in W satisfy Dα (w k qα,ep ) = ln 2− hα (δ).
The third one satisfy Dα (w k qα,ep ) ≤ ln 2−hα (δ) if and only if
δ
α ≤ f −1 ( 1−δ
). Consequently,(38) implies Cα,W = lnδ2−hα (δ)
)].
and qα,W = 1/2 1/2 0 0 for all α ∈ (0, f −1 ( 1−δ

Example 2 provides sets of probability measures that are not
even pairwise disjoint but they have singular Rényi centers for
all orders in (0, 1). Example 2 also demonstrates the possible
absence of an optimal prior for infinite sets of probability
measures.

Example 4. Let us assume γ ∈ (0, 1) and n ∈ Z+ . Let Y be
{0, . . . , n}, Y be 2 Y , U and W be
U = {w δ, :  ∈ {1, . . . , n}, δ ∈ [γ, 1]},

W = {w δ, :  ∈ {1, . . . , n}, δ ∈ (γ, 1]}

Example 2. Let (Y, Y) be (Z, 2 Z ) and let Wı be
Wı = {w ı, :  ∈ Z}.

where w δ, (y) = 1{y=} (1 − δ) + 1{y=0} δ.
Let p ∈ P(U) be p(w δ, ) = n1 1{δ=γ} . Then
h
i
(
α−1
α
α
ln
γ
+
(1
−
γ)n
α ∈ ℜ+ \ {1}
,
Iα (p;U) = α−1
(1 − γ) ln n
α=1
Xn (1−γ)n −1/α 1
γ1{y =0}
{y =}
.
qα,p (y) = γ+(1−γ)n
1−1/α +
γ+(1−γ)n 1−1/α

∀ı ∈ Z

where w ı, (y) = (1{y=ı} + 1{y=} )/2.
For any α in (0, 1) and sequence {pκ }κ∈Z+ ⊂ P(Wı ) of
uniform distributions with strictly increasing support qα,pκ
converges to 1{·=ı} in the total variation topology and
ln 2
. Furthermore, if q(·) = 1{·=ı}
limκ→∞ Iα (pκ ;Wı) = α1−α
α ln 2
ln 2
then Dα (w k q) ≤ 1−α for all w ∈ Wı . Thus Cα,Wı = α1−α
and qα,Wı (·) = 1{·=ı} for all α ∈ (0, 1) by (39).
Note that Wı ’s are not singular with one another, in fact
Wı ∩ W = {w ı, }. Nonetheless, qα,Wı ⊥ qα,W for all α in
(0, 1) whenever ı 6=  and we can use Lemma 21 to calculate
the Rényi capacity of any finite union of Wı ’s. For any finite
set of integers A, let WA be WA = ∪ı∈A Wı ; then
Cα,WA =

α ln 2
1−α

+ ln |A| and qα,WA (y) = |A|

−1


−δ
δ 
.
δ 
1/2 − δ

1/2

=1

Furthermore, one can confirm by substitution that
(
(1+((1/γ )−1)n 1−1/α )1−α
1

ln δα +(1−δ)
α ((1/γ )−1)1−α n 1−1/α
δ,
1−α
Dα w qα,p =
δ ln γδ + (1 − δ) ln (1−δ)n
1−γ

α 6= 1

α=1

.

Then Dα (w k qα,p ) ≤ Iα (p;U) for all w ∈ U and consequently,
Cα,U = Iα (p;U) and qα,U = qα,p by (38).
Since U is the closure of W in the topology of setwise
convergence, Cα,W = Cα,U for all α ∈ ℜ+ by Lemma 24-(b).
Consequently, qα,W = qα,U by Lemma 21 because W ⊂ U.
Then Dα (w k qα,W ) < Cα,W for all w in W and α in ℜ+ .
Hence Iα (p;W) < Cα,W for all p in P(W) and α in ℜ+ by
Lemma 14 and W(α,0) = ∅ for all α in ℜ+ by definition.

1{y∈A} .

Furthermore, for any p ∈ P(WA ) using (22) and (23) we get
Dα (p⊛WA k p ⊗ qα,WA ) = Iα (p;WA) + Dα (qα,p k qα,WA ) .
Recall that Dα (p⊛WA k p ⊗ qα,WA ) ≤ Cα,WA by Theorem 1
and Dα (qα,p k qα,WA ) ≥ 0 by Lemma 10. In addition
• Dα (p⊛WA k p ⊗ qα,WA ) < Cα,WA for any p ∈ P(WA )
satisfying p(w ) > 0 a w such that supp(w ) ⊂ A.
• Dα (qα,p k qα,WA ) > 0 for any p ∈ P(WA ) satisfying
p(w ) > 0 a w such that supp(w ) * A.
Thus Iα (p;WA) < Cα,WA for any p ∈ P(WA ) and finite A.

B. Shift Invariant Families of Probabilities
The shift invariant sets of probability measures on the unit
interval are relatively easy to analyze. Nevertheless, when
considered as a function of the order the Rényi capacities of
these sets form a diverse collection and it is relatively easy to
construct examples and counterexamples for the behavior of
Rényi capacity as function of the order using this family.
First we consider the set of modular shifts of a probability
measure on the unit interval, which is called “channel with
additive noise on the unit circle” by Agustin in [6].

In Example 1 the optimal p satisfying Iα (p;W) = Cα,W
was unique. However, this is not the case in general as
demonstrated by Example 3, given in the following.
19

Example 5. Let Y be [0, 1), Y be B([0, 1)), andR f be a non1
negative Lebesgue measurable function such that 0 f (y)dy =
1. Then W[f ] is the set of all probability measures whose
Radon-Nikodym derivatives with respect to the Lebesgue
measure l is a mod one shift of f :

(63)
W[f ] , w : dw
dl = f ◦ Tx for some x ∈ [0, 1)

Example 7. The existence of the discontinuity is related to the
integrability of f ln f and f α because Cα,W[f ] = Dα (wf kl ).
√
1{0<y <1/e}
• If f (y) = 2
, then C1,W[f ] = ln 2 e and
y(ln 1y )3
Cα,W[f ] = ∞ for all α in (1, ∞].
•

= Cα,W[f ] + ln kqac k

∀w ∈ W .

[f ]

Since qα,W[f ] ≺l , the Radon-Nikodym derivative α,W
dl
exists by the Radon-Nikodym theorem [30, 5.5.4]. Since
W[f ] is invariant under mod one shifts by construction, its
Rényi centers need to be invariant under mods one shift, as
well. Furthermore, l is invariant under mod one shifts. Hence,
dl

=

dqα,W[f ]
dl

◦ Tx

1
)
y

1{0<y <1/e}
R ∞ e−z
dz
z
1− 1
φ

R∞

for a φ in (1, ∞), then

1
1− φ

e−z
z

dz and Cα,W[f ] = ∞

where Tx (y) , y − x − ⌊y − x ⌋.
Note that supw∈W[F] Dα (w k l ) = supf ∈F Dα (wf kl ) because
W[F] = ∪f ∈F W[f ] and Dα (w k l ) = Dα (wf kl ) for all w in W[f ] .
Thus Cα,W[F] ≤ supf ∈F Dα (wf kl ) by Theorem 1. On the other
hand, the reverse inequality follows from (64) and Lemma 21.
Thus, Cα,W[F] = supf ∈F Dα (wf kl ), i.e.

R
1
ln f α (y)dy α ∈ ℜ+ 6= 1
sup α−1




f ∈F R
α=1
. (66)
Cα,W[F] = sup f (y) ln f (y)dy
f ∈F




α=∞
sup ln ess supl f (y)

If kqac k < 1, then supw∈W[f ] Dα (w k qac/kqac k) < Cα,W[f ] .
This, however, is impossible because of Theorem 1. Thus
kqac k = 1, kqs k = 0 and qα,W[f ] ≺l .

dqα,W[f ]

(ln

Example 8. Let F be a familyR of non-negative Lebesgue
measurable functions such that f dy = 1 for all f ∈ F.
Then W[F] is the set of all probability measures whose RadonNikodym derivative is a mod one shift of an f in F:

(65)
W[F] , w : dw
dl = f ◦ Tx for some x ∈ [0, 1), f ∈ F

[f ]

dq

−1
φ

In all of the examples we have considered thus far the
Rényi capacity is not only continuous but also differentiable
in the order. This, however, is not the case in general.

by Theorem 1. On the other hand qα,W[f ] = qs + qac where
qs ⊥ l and qac ≺l , by the Lebesgue
decomposition theorem

[30, 5.5.3]. Then Dα w k qα,W[f ] = Dα (w k qac ) for all w in
W[f ] by (19) because w ≺l for all w in W[f ] . Thus
Dα

y

φ
Cφ,W[f ] = ln(φ−1)
1−φ − φ−1 ln
for all α in (φ, ∞].

where Tx (y) , y − x − ⌊y − x ⌋.
Let us denote the measure whose Radon-Nikodym derivative is f by wf . Note that Dα (w k l ) = Dα (wf kl ) for any w in
W[f ] and α ∈ (0, ∞]. Thus supw∈W[f ] Dα (w k l ) = Dα (wf kl )
for any α ∈ (0, ∞].
If Cα,W[f ] is finite for an α ∈ (0, ∞], then ∃!qα,W[f ] in
P(Y, Y) such that

Dα w k qα,W[f ] ≤ Cα,W[f ]
∀w ∈ W[f ]

(w k qac/kqac k)

If f (y) =

f ∈F

∀x ∈ [0, 1)

1
1
If F = {2y, 2√
y }, then Cα,W[F] is not differentiable at α = 2 .

dqα,W[f ]

needs to be a constant. That constant is one
Thus
dl
because qα,W[f ] is a probability measure. Therefore qα,W[f ] = l
and Cα,W[f ] = Dα (wf kl ) whenever Cα,W[f ] is finite. When it is
infinite so is Dα (wf kl ) by Theorem 1 because Dα (w kl) equals
Dα (wf kl ) for all w in W[f ] . Hence, Cα,W[f ] = Dα (wf kl ), i.e.

R α
1

Rα−1 ln f (y)dy α ∈ ℜ+ 6= 1
Cα,W[f ] =
.
(64)
f (y) ln f (y)dy
α=1


ln ess supl f (y)
α=∞

C. Certain Families of Poisson Point Processes
The following examples demonstrate the generality of our
framework by determining the Rényi capacity of various
families of Poisson point processes with integrable intensity
functions, on real line.31 Some of these families have been
considered before in the context of channel coding problems,
such as the ones in (71) and (73) in the following (see [13],
[28], [55], [105], [106]), others have not been considered
before, such as the ones in (70), (72), and (92).
The Poisson point processes are, sometimes, formulated
and analyzed via the characterization of the interarrival times
without even mentioning the Radon-Nikodym derivatives, see
[38, Ch. 2]. For many applications such an approach turns out
to be sufficient; as a result, the Radon-Nikodym derivatives
of Poisson point processes are not as well-known as one
would expect. Considering this fact, we follow the approach
of Burnashev and Kutoyants in [13] and start our discussion
with a brief refresher on the Radon-Nikodym derivatives of
the Poisson processes.

As a result of Lemma 15, Cα,W is either continuous in α
on (0, ∞] or continuous and bounded on (0, φ] and infinite
on (φ, ∞] for an φ ∈ [1, ∞). The following two examples
are special cases of Example 5 which demonstrate that the
Rényi capacity can become infinite for some orders larger than
one while being continuous on (0, ∞] and the Rényi capacity
can have a discontinuity at any order in [1, ∞).

Example 6. fβ (y) = (1 − β)y −β and β ∈ (0, 1).
 α ln(1−β)−ln(1−αβ)

α ∈ [0, 1) ∪ (1, β −1 )

α−1
β
Cα,W[fβ ] = 1−β + ln(1 − β)
α=1


∞
α ∈ [β −1 , ∞]

31 The analysis we present in the following can be applied to the spatial
Poisson processes defined on appropriately chosen subsets of the Euclidean
space without any major modification. We restrict our analysis to the one
dimensional case, because even the one dimensional case has a structure that
is rich enough to demonstrate the generality of our framework.

Cα,W[fβ ] is continuous on (0, ∞] and monotone increasing and
finite on (0, β −1 ).
20

Definition 8. For any T ∈ ℜ+ and intensity levels a, ̺, b
satisfying 0 ≤ a ≤ ̺ ≤ b ≤ ∞, let ΛT ,a,b,̺ , ΛT ,a,b,≤̺ ,
ΛT ,a,b,≥̺ , and ΛT ,a,b be the set of all Poisson point processes
with [a, b] valued deterministic integrable intensity functions
on (0, T ] with an average equal to ̺, less than or equal to ̺,
greater than or equal to ̺, and in [a, b], respectively:
o
n
RT
ΛT ,a,b,̺ , wf : a ≤ f ≤ b and 0 f (t )dt = T ̺ , (70)
o
n
RT
ΛT ,a,b,≤̺ , wf : a ≤ f ≤ b and 0 f (t )dt ≤ T ̺ , (71)
n
o
RT
ΛT ,a,b,≥̺ , wf : a ≤ f ≤ b and 0 f (t )dt ≥ T ̺ , (72)

For any T ∈ ℜ+ , let XT be the set of all nondecreasing, right-continuous, integer valued functions on (0, T ]. The
sample paths of Poisson point processes are members of XT .
Furthermore, any Poisson point process with deterministic
intensity function f can be represented by a unique probability
measure on the measurable space (Y, Y) for Y = XT when Y
is an appropriately chosen σ−algebra.32
For any sample path y ∈ Y, we denote the th arrival time
by τ (y) and the number of arrivals up to and including time t
by Nt (y). The probability measure associated with a Poisson
process with the intensity function f is denoted by wf . The
probability measure of the Poisson point process with constant
intensity γ is denoted by νγ . If γ = 1, we also use ν to denote
νγ , i.e. ν = ν1 .
For any non-negative integrable function f on (0, T ] the
associated probability measures wf is absolutely continuous
dw
with respect to ν and the Radon-Nikodym derivative dνf is
given by,33 [13, (2.1)], [9, VI.6.T12, p187],
Y
 R
T
dwf
f (τ (y)) e 0 (1−f (t))dt .
(67)
dν (y) =

ΛT ,a,b , {wf : a ≤ f ≤ b} .

The convention proposed in Definition 8 allows us to refer to
various families of Poisson point processes without confusion.
However, explicitly stating the dependence on T , a, and b
is not necessary whenever the values of T , a, and b are
unambiguous. When this is the case we use Λ̺ for ΛT ,a,b,̺ ,
Λ≤̺ for ΛT ,a,b,≤̺ , Λ≥̺ for ΛT ,a,b,≥̺ , and Λ for ΛT ,a,b .
In the following, we first determine the Rényi capacity
and center of ΛT ,a,b,̺ , and then use these expressions to
calculate the Rényi capacity and center of families described
in Definition 8 and in (92).

τ (y)≤T

For any non-negative measurable function g, the following
expression for the expectation34 follows from (67), [13, (2.2)]:

Z Y
RT
g(τ (y)) wf (dy) = e 0 (g(t)−1)f (t)dt . (68)

Example 9. For any T ∈ ℜ+ , a, b ∈ ℜ≥0 such that a ≤ b, and
̺ ∈ [a, b],
( α
α 6= 1
α−1 (ζα,̺ − ̺)T

,
(74)
Cα,Λ̺ =  ̺−a
b−̺
b
a
α=1
b−a b ln ̺ + b−a a ln ̺ T

τ (y)≤T

An immediate consequence of (67) and (68) is the following
expression for the Rényi divergence between wf and wg for
integrable intensity functions f and g and positive real orders:
R  α 1−α

 T f g −f − f + g dt α 6= 1
α−1
0 

. (69)
Dα (wf k wg ) = R T
f

−
f
+
g
dt
α=1
f
ln
g
0

qα,Λ̺ = νζα,̺ ,

̺−a α
ζα,̺ , b−a
b +

34 In [13], Burnashev and Kutoyants express the identities given in (67) and
(68) more succinctly and elegantly, as follows:

e

RT

0 (ln g(t ))y(dt) wf

(y) = e

(dy) = e

b−̺ α
b−a a

.

̺

32 One choice of Y that works is the Borel σ−algebra for the topology
generated by the Skorokhod metric s on XT , denoted by B(XT , s). In
fact, B(XT , s) is rich enough to express the Poisson point processes whose
intensity functions are not deterministic but Markovian, i.e. the intensity at
any t ∈ (0, T ] depends on the previous arrivals. Kabanov’s original work
[55] considers such Poisson
 point processes, as well.
Q
33
τ (y)≤T f (τ (y)) stands for 1 for y’s that do not have any arrivals.
dwf
dν

(75)

1/α

An alternative expression for Cα,Λ̺ is the following:
 b−̺

̺−a
Dα νb k νζα,̺ + b−a
Dα νa k νζα,̺ .
Cα,Λ̺ = b−a

For positive real orders other than one (69) follows from (67)
and (68) by substitution, via the definition of the Rényi divergence. On the other hand, D1 (wf k wg ) = limα↑1 Dα (wf k wg )
because the Rényi divergence is continuous in order on [0, 1]
by Lemma 7. Then the expression for D1 (wf k wg ) follows
from the dominated convergence theorem [8, 2.8.1]α and the ex−x
pression for Dα (wf k wg ) for α ∈ (0, 1) because xα−1
↑ x ln x
as α ↑ 1 for any x ≥ 0.
Let us proceed with defining the set of Poisson point
processes we will be investigating.

Z

(73)

RT

RT
0 (ln f (t ))y(dt)+ 0 (1−f (t ))dt ,

RT

0 (g(t )−1)f (t )dt .

R
R
In the expressions 0T (ln f (t))y(dt ) and 0T (ln g(t))y(dt), the sample path
y is interpreted as a measure that is equal to the sum of Dirac delta functions
located at the arrival times of the sample path y.

21

(76)

(77)

If ̺ is equal to a or b, then Λ has just one element;
consequently Cα,Λ̺ is zero and the only element of Λ̺ is
also the Rényi center. For ̺’s in (a, b), we first determine
̺−a
the Rényi capacity and center assuming that b−a
is a rational
number by giving a sequence of priors {pı } and a probability
measure q satisfying limı→∞ Iα (pı ;Λ̺) = Sα,Λ̺ (q). Then
we determine the Rényi capacity of Λ̺ with irrational ̺−a
b−a
using the continuity of the resulting expression in b and the
monotonicity of Cα,W in W.
̺−a
= nℓ
There exists positive integers ℓ and n such that b−a
̺−a
because b−a is a rational number and b > ̺ > a. Then there
are nℓ length n sequences of a’s and b’s with ℓ b’s and
(n − ℓ) a’s. These sequences will be the building blocks for
f ’s with positive pı (wf ).
For each positive integer ı let us divide the interval (0, T ]

into 2ı n half open intervals of the form ( −1
2ı n T , 2ı n T ] for
ı
 ∈ {1, . . . , 2 n}. Now consider f ’s such that:
• f is {a, b} valued function that is constant in all intervals
T , 2ın T ] for  ∈ {1, . . . , 2ı n}.
of the form ( −1
Pn−1 2ı n
for all  ∈ {1, . . . , 2ı }.
• ℓ=
κ=0 1{f ( n−κ
2ı n T )=b}
For every such f corresponding wf is in Λ̺ . Furthermore, there
(2ı )
are nℓ
distinct f ’s. The prior pı has equal probability mass

Using (78) and (79) for γ = ζα,̺ we can conclude that
limı→∞ Iα (pı ;Λ̺) = Sα,Λ̺ (νζα,̺ ). Then for α’s other than one
̺−a
(74) follows from (39) for values of ̺ making b−a
a rational
̺−a
number. For values of ̺ making b−a a rational number, (74)
for α = 1 case follows from the expression for α 6= 1 case via
L’Hospital’s rule [79, Thm. 5.13] because the Rényi capacity is
a continuous function of the order on (0, 1] by Lemma 15-(c).
̺−a
We now prove that (74) holds for values of ̺ for which b−a
T ,a,b1 ,̺
T ,a,b2 ,̺
is irrational. First note that Λ
⊂Λ
for any T ,
a, ̺, b1 , b2 satisfying b1 ≤ b2 , by the definition of ΛT ,a,b,̺
given in (70). Then Cα,ΛT ,a,b1 ,̺ ≤ Cα,ΛT ,a,b2 ,̺ by definition.
Then (74) holds for the case when ̺−a
b−a is irrational as a result
of the continuity of the expression on the right hand side of
(74) as a function of b for each α ∈ ℜ+ .
For orders other than one (75) follows from Theorem 1
because Sα,Λ̺ (νζα,̺ ) = Cα,Λ̺ by (74) and (79). In order
extend (75) to α = 1 case we invoke the continuity of
Rényi center established Lemma 20.

on all wf ’s with the above described f ’s. Then using (67) we
can calculate the Radon-Nikodym derivative of µα,pı ,
 !1/α

X(nℓ )(2ı ) Qτ (y )≤T fκ (τ (y)) α
dµα,pı

(1−̺)T
.
ı
dν (y) = e
κ=1
(nℓ )(2 )

For the sample paths, i.e. y’s, that do not have more than one

arrival in any of the intervals of the form ( −1
2ı T , 2ı T ], one
can simplify the expression for the Radon-Nikodym derivative
significantly. In particular,
0 (y )
 α
 NT (y )−N
α
α
dµα,pı
(1−̺)T ℓb +(n−ℓ)a
(y)
=
e
∀y ∈ Eı
dν
n

where Nt (y) is the number of arrivals on (0, t ] for the sample
path y and Eı ∈ Y is defined as
n
o
ı
Eı , y : N 2ı T (y) − N −1
(y)
≤
1
∀
∈
{1,
.
.
.
,
2
}
.
ı T
2

Since Eı ⊂ Eı+1 the following holds ∀y ∈ ∪ı∈Z+ Eı
limı→∞

dµα,pı
dν



(y) = e(1−̺)T

ℓb α +(n−ℓ)a α
n

0 (y )
 NT (y )−N
α

Example 10. For any T ∈ ℜ+ , a, b ∈ ℜ≥0 such that a ≤ b,
and ̺ ∈ [a, b],

.

Using the complete independence of the Poisson processes
on disjoint intervals and the probability mass function of the
counting process, [38, Thm. 2.2.10], [9, II.1.(1.9), p. 22], we
can calculate the probability ν(Eı ):
ν(Eı ) =
=

ν−a.e

(y) −−−−→ e(1−̺)T
dµ



ℓb α +(n−ℓ)a α
n

0 (y )
 NT (y )−N
α

=e



ℓb α +(n−ℓ)a α
n

.

NT (y )

1

α

Thus using (13) and the fact that
limı→∞ Iα (pı ;Λ̺) =

α
α−1


−̺ T
̺−a
b−a

=

(ζα,̺ − ̺) T

qα,Λ≥̺ = qα,Λ̺∨̺α

(81)

b−γ
b−a Dα (νa k νs )

+

γ−a
b−a Dα (νb k νs )

(83)

γ

for all w in Λ . Furthermore, the definitions of ζα,γ and ̺α
given in (76) and (82) imply that


Dα νa k νζα,γ ≤ Dα νb k νζα,γ
∀γ ∈ [a, ̺α ].
(84)
Using (83) and (84) together with the alternative expression
for Cα,Λ̺ given in (77) we get

α
Sα,Λ≤̺ (νζα,̺∧̺α ) ≤ b−̺∧̺
b−a Dα νa k νζα,̺∧̺α

α −a
+ ̺∧̺
b−a Dα νb k νζα,̺∧̺α

we get
∀α 6= 1.

qα,Λ≤̺ = qα,Λ̺∧̺α

Dα (w k νs ) ≤

.
ℓ
n

(80)

Since Λ≤̺ is the union of Λγ for γ in [a, ̺], Cα,Λ≤̺ equals
Cα,Λ̺∧̺α iff Sα,Λ≤̺ (qα,Λ̺∧̺α ) ≤ Cα,Λ̺∧̺α by Lemma 21.
On the other hand, when considered together the convexity
α
−x
of xα−1
in x for α 6= 1 case and the convexity of x ln x in x
for α = 1 case (69) implies

α,pı
On the other hand dν
(y) ≤ e(1−̺)T bb N0 (y ) because f (t ) ≤
R (1−̺)T b NT
ν(dy) = e(b−̺)T . Thus the
b. Furthermore e
b N0
dominated convergence theorem [8, 2.8.1] implies that
Z 
0 (y )
 NT (y )−N
α
ℓb α +(n−ℓ)a α
lim kµα,pı k = e(1−̺)T
ν(dy)
n

ı→∞

Cα,Λ≥̺ = Cα,Λ̺∨̺α

where Cα,Λ̺ and qα,Λ̺ are given in (74) and (75) and ̺α is
defined as follows:
( α
1
α
α
1−α + ab −ba
α 1−α ( b αb−a
α 6= 1
α)
α −a α
−a
b
̺α ,
.
(82)
a
b
− b−a
−1 b−a
a
α=1
e b

ı
T
+ 2Tı e− 2ı )(2 )
(e
ı
e−T (1 + 2Tı )(2 ) .

− 2Tı

Then limı→∞ ν(Eı ) = 1 and consequently ν(∪ı∈Z+ Eı ) = 1.
Thus convergence on (∪ı∈Z+ Eı ) implies ν−a.e. convergence:
dµα,pı
dν

Cα,Λ≤̺ = Cα,Λ̺∧̺α

(78)

On the other
R T hand for any γ ∈ ℜ+ and f : (0, T ] → [a, b]
satisfying 0 f (t )dt = T ̺, as a result of (69)
Z Th
i
γ 1−α α
α
Dα (wf k νγ )=
f
(t
)
−
f
(t
)
+
γ
dt
α−1
α−1
0
Z T
i
h
b−f (t) α
γ 1−α f (t)−a α
≤
dt − α̺T
b
+
a
α−1
b−a
b−a
α−1 +γT
0

i
h 1−α 
b−̺ α
̺−a α
α
b + b−a
a − α−1
̺+γ T
= γα−1 b−a

α
= α−1
(79)
(ζα,̺ − ̺)T + Dα νζα,̺ νγ

= Cα,Λ̺∧̺α

Thus Sα,Λ≤̺ (qα,Λ̺∧̺α ) ≤ Cα,Λ̺∧̺α follows from (75). Hence
Cα,Λ≤̺ = Cα,Λ̺∧̺α and qα,Λ≤̺ = qα,Λ̺∧̺α by Lemma 21.
Assertions about Λ≥̺ derived similarly using the following
observations: Λ≥̺ is the union of Λγ for γ in [̺, b] and


Dα νa k νζα,γ ≥ Dα νb k νζα,γ
∀γ ∈ [̺α , b].
(85)
Example 11. For any T ∈ ℜ+ and a, b ∈ ℜ≥0 such that a ≤ b,

where the inequality follows from the convexity of the function
xα
α−1 in x and the Jensen’s inequality.

22

Cα,Λ = Cα,Λ̺α ,

(86)

qα,Λ = qα,Λ̺α ,

(87)

where Cα,Λ̺ , qα,Λ̺ , ̺α are described in (74), (75), (82)
because Λ = Λ≤b . By substitution we get the following more
explicitly expressions:


1
α ab α −ba α
 ( α(b−a)
1−α −
α 6= 1
)
α
α
α
α
b −a
α−1 b −a  T
, (88)
Cα,Λ = 
b
a
−
 e−1 b b−a a b−a − ab ln b T
α=1
b−a
a
qα,Λ = νζα ,
( 1
1
1−α
α 1−α ( b αb−a
−a α )
ζα ,
a
b
e−1 b b−a a − b−a

VI. D ISCUSSION
We have defined and analyzed the order α Rényi capacity
Cα,W and the order α Rényi radius Sα,W for an arbitrary
set of probability measures W on an arbitrary measurable
space. Our most important contributions are the van ErvenHarremoës bound, i.e. Lemma 19, and two uniform equicontinuity results on the Rényi information, i.e. Lemma 16-(e,f). We
have also proved a minimax theorem, i.e. Theorem 1, which
has already been reported by Augustin in an unpublished
manuscript [6] in a different form and for orders between
zero and two. Theorem 1 establishes not only the equality
of Cα,W and Sα,W for any α and W but also the existence
of a unique order α Rényi center whenever Cα,W is finite.
Our analysis lead to certain immediate consequences for two
generalizations: Cα,W,A defined for A ⊂ P(W) and Cα,W
defined for transition probability W . We introduce those
generalizations formally and discuss the implications of our
analysis on them in Appendices A and B.
Results of our analysis, also, encourage one to consider
certain related problems:

(89)

α ∈ ℜ+ \ {1}
.
α=1

(90)

One can also confirm ζα = ζα,̺α using (76) and (82). The
following expression for Cα,Λ is equivalent to (88):
Cα,Λ =

̺α −a
b−a Dα (νb k νζα )

+

b−̺α
b−a Dα (νa k νζα ) .

(91)

In the preceding examples, we have assumed the intensity
functions are bounded above by a constant; we replace this
constant with an integrable function in Example 12 given in
the following. Let us first give a formal definition.
Definition 9. For any T in ℜ+ , a in ℜ≥0 , and Lebesgue
integrable function g on (0, T ] satisfying g ≥ a, ΛT ,a,g(·)
is the set of all Poisson point processes with deterministic
intensity functions f satisfying a ≤ f ≤ g:
ΛT ,a,g(·) , {wf : a ≤ f (t ) ≤ g(t ) ∀t ∈ (0, T ]} .

•

(92)

Example 12. For any T ∈ ℜ+ , a ∈ ℜ≥0 , and g ∈ L1 (l )
satisfying g(t ) ≥ a for all t in (0, T ] we have
R h
i
1
ag α −ga α
 T ( α(g−a)
1−α − α
)
α
α
α
α
g −a
α−1 g −a i dt α 6= 1
0
, (93)
Cα,Λ = R T h
g
a
−
ag

e−1 g g −a a g −a − g−a
α=1
ln ag dt
0
qα,Λ = wζα ,
( 1
1
1−α
α 1−α ( g αg(t)−a
(t)−a α )
ζα (t ) ,
g (t )
a
e−1 [g(t )] g (t )−a a − g (t )−a

(94)

α 6= 1
α=1

.

(95)

If g is a simple function, then we can apply (88) and (89) for
each possible value of g, separately. Then (93) and (94) follow
from Lemma 22 because simple functions can only take finite
number of distinct values.35 On the other hand, there exists a
sequence of simple functions {g (ı) }ı∈Z+ satisfying a ≤ g (ı)
and g (ı) ↑ g for any measurable g. Evidently Cα,ΛT ,a,g (ı) (·) ≤

Cα,ΛT ,a,g (·) because ΛT ,a,g
f satisfies a ≤ f ≤ g, then
1

1

(t)−a
1−α −
α 1−α ( f αf (t)−a
α)

(ı)

(·)

•

⊂ ΛT ,a,g(·) . Furthermore, if

α
α
α af (t)−f (t)a
α−1
f α (t)−a α

1

≤ α 1−α g(t ).

for all t ∈ (0, T ].
Then the integral on the right hand side of (93) equals to
limı→∞ Cα,ΛT ,a,g (ı) (·) by the dominated convergence theorem
[8, 2.8.1]. Hence, it is a lower bound on Cα,ΛT ,a,g (·) . It is, also,
an upper bound on Cα,ΛT ,a,g (·) by (33) because Dα (w k wζα )
is bounded from above by it for all w ∈ ΛT ,a,g(·) . Then (94)
follows from the uniqueness of the Rényi center.

•

35 We are not overlooking the issue of contiguity for the inverse of the
image of g because Example 11 holds as is for Poisson processes defined on
any measurable set of Lebesgue measure T , not just the interval (0, T ].

23

We have not assumed any topological structure on the
output space Y. Although this is a strength because
of the generality of our results, it is also a weakness
because of the obliviousness of our analysis towards the
interactions between Rényi’s information measures and
the topological structure of the output space. In almost
all of the applications Y is a Borel or Baire σ-algebra
of the topological space (Y, τ ); usually there is an even
more specific structure. In all of the examples we have
considered in §V and in most of the applications Y is
the Borel σ-algebra of a complete separable metric space
(Y, d ). Thus one can define metrics other than the total
variation metric on W and P(W) using the metric d and
analyze the behavior of the Rényi’s information measures
on the resulting topologies. Such models have already
been considered in the context of the arbitrarily varying
channels [24], [98] and the typicality [54], [64], [75].
It is easy to confirm that continuity of the order α
Rényi capacity as a function of the order α implies the
continuity of the corresponding f -capacity Cfα ,W as a
α
−1
. The existence of
function of α where fα (x ) = xα−1
similar, but more general, continuity results for richer
classes of f -divergences with appropriate topologies is
expected. What is plausible, but not evident, to us is the
existence of a topology on the set of all convex f ’s that
ensures the continuity of the corresponding f -capacities
in f for all W on the region that f -capacities are finite. In
any event, the interaction of topologies on the space of
convex functions and corresponding f -capacities seems
to be a fertile subject of inquiry.
We used the definition of Rényi information proposed
by Sibson [93]. In (26) we provided the expression for
the alternative definition of Rényi information proposed
by Augustin [6] and Csiszár [25]. We call this quantity
Augustin information. Theorems 1, 2 and many of the
other propositions have their analogues for Augustin
information. We have already reported some of those

in [72]. A more comprehensive study of the Augustin
information and its relation to Rényi information will,
soon, be available [69]. Augustin capacity and center
are of interest to us because they are better suited than
Rényi capacity and center for deriving the sphere packing
bound for memoryless channels, [70], [72]. Concepts
such as A-L information and R-G information, defined
in [72, §§3-A,3-B] to derive the sphere packing bound
for cost constrained memoryless channels, are analyzed
in [69], as well.
We have avoided using information theoretic concepts such
as code, channel, or rate in our discussion because we believe
Rényi’s information measures can and should be defined and
understood on their own as measure theoretic concepts first.
Rényi’s information measures, however, do have operational
meaning in various information transmission problems. We
discuss the case of channel coding problem in [71].

A similar modification is needed for the van ErvenHarremoës bound, i.e. for Lemma 19, as well.
Lemma 25. For any α ∈ (0, ∞], W ⊂ P(Y, Y), convex A
subset of P(W) satisfying Cα,W,A < ∞, and q ∈ P(Y, Y)
Cα,W,A + Dα (qα,W,A k q) ≤ supp∈A Dα (p⊛Wk p ⊗ q) .
Lemma 20 establishing the continuity of the Rényi centers
in the order holds for the constrained Rényi centers. We prove
it using Theorem 2 and Lemma 25 instead of Theorem 1 and
Lemma 19.
Lemma 21 bounding the Rényi capacity of the unions and
Lemma 22 determining the Rényi capacity of the Cartesian
products can be generalized to the constrained case as Lemmas
26 and 27. The proofs in the constrained case are similar to
the proofs for the original lemmas, but replacing P(W)’s with
A’s is not enough on its own. We leave these two proofs to
the reader.
Lemma 26. For any α ∈ (0, ∞], W ⊂ P(Y, Y), and A
satisfying A = ch(∪ı∈T Aı ) for some convex Aı ⊂ P(W)
with finite Cα,W,Aı ’s,
X
supı∈T Cα,W,Aı ≤ Cα,W,A ≤ ln
eCα,W,Aı .

A PPENDIX
A. The Constrained Rényi Capacity
Definition 10. For any α ∈ [0, ∞], W ⊂ P(Y, Y), A ⊂ P(W),
the order α Rényi capacity of W for constraint set A is

ı∈T

Cα,W,P(W) = Cα,W and Cα,W,{p} = Iα (p;W) for any W and
p ∈ P(W). Our analysis has been confined to the A = P(W)
case but some of our proofs are valid for more general A’s.
• Proofs of Lemma 15 and Lemma 16-(a,b,f) are valid as
is for Cα,W,A for any A.
• Proof of Lemma 16-(g) holds for any closed A because
closed subsets of compact sets are compact, [68, 26.2].36
• Proof of Lemma 17 holds for any closed and convex A.
For certain other proof we can replace P(W) with A’s
satisfying appropriate hypothesis to get slightly weaker results.
In particular, the proof of Theorem 1 works as is for convex
A’s and thus the minimax theorem continues to hold for
Cα,W,A . But the alternative expression for Cα,W,A is no
longer (guaranteed to be) equal to the Rényi radius.

Furthermore,
• Cα,W,Aı = Cα,W,A iff supp∈A Dα (p⊛Wk p ⊗ qα,W,Aı ) ≤
Cα,W,Aı
• If Cα,W,Aı = Cα,W,A , then qα,W,A = qα,W,Aı .
P
Cα,W,Aı
and Cα,W,A is finite iff T
• Cα,W,A = ln
ı∈T e
is finite and qα,W,Aı ⊥ qα,W,A for all ı 6=  in T.
• If T is finite and qα,W,Aı ⊥ qα,W,A for all ı 6=  in T, then
P
P
qα,W,A = ( ∈T eCα,W,A )−1 ı∈T eCα,W,Aı qα,W,Aı .
Q×
Lemma 27. For any finite
index set T, if Y =
t∈T
o Yt ,
n
Q⊗
Q⊗
Y =
w : w = t∈T wt : wt ∈ Wt for
t∈T Yt , W =
Q×
some Wt ⊂ P(Yt , Yt ) and A = t∈T At for some convex
At ⊂ P(Wt ), then
X
Cα,W,A =
∀α ∈ (0, ∞].
Cα,Wt ,At

Theorem 2. For any α ∈ (0, ∞], W ⊂ P(Y, Y), and convex
A ⊂ P(W),

B. The Rényi Capacity of Transition Probabilities

Cα,W,A , supp∈A Iα (p;W) .

Cα,W,A = supp∈A inf q∈P(Y,Y) Dα (p⊛Wk p ⊗ q)

= inf q∈P(Y,Y) supp∈A Dα (p⊛Wk p ⊗ q) .

(96)

t∈T

In addition, Cα,W,chAQ
= Cα,W,A . Furthermore, if Cα,W,A is
⊗
finite, then qα,W,A = t∈T qα,Wt ,At = qα,W,chA .

(97)

We have defined the order α Rényi information Iα (p;W) for
any p.m.f. p on a set of probability measures W. We show
in the following —using the concept of transition probability
and the expression for Iα (p;W) given in (24)— that for appropriately chosen σ-algebra W, one can extend the definition
of Iα (p;W) to p’s that are probability measures on (W, W).
Furthermore, we show that if W is countably separated,37 then
Theorem 1 holds for this more general case, see Theorem 3.

(98)

If Cα,W,A < ∞, then there exists a unique qα,W,A in P(Y, Y),
called the order α Rényi center for constraint set A, such that
Cα,W,A = supp∈A Dα (p⊛Wk p ⊗ qα,W,A ) .

(99)

Furthermore, for every sequence of priors {pı }ı∈Z+ ⊂ A
satisfying limı→∞ Iα (pı ;W) = Cα,W,A , the corresponding
sequence of order α Rényi means {qα,pı }ı∈Z+ is a Cauchy
sequence for the total variation metric on P(Y, Y) and qα,W,A
is the unique limit point of that Cauchy sequence.

37 A σ-algebra X on X is countably separated, [8, Def. 6.5.1], if there exists
an at most countable collection sets {Eı } ⊂ X separating the points of X. A
collection {Eı } of subsets of X is said to be separating the points of X, if for
every pair of distinct points z and x in X there exists an Eı which includes
only one of z and x . The Borel σ-algebra of any separable metric space
is countably separated. The Borel σ-algebra of any separable metric space
is also countably generated, i.e. it is the minimum σ-algebra of a countable
collection of sets.

36 We assume P(W) is equipped with the total variation topology. Lemma
16-(g) is valid for any A, not just the closed ones. The proof of that fact,
however, does not follow from the proof of Lemma 16-(g).

24

Definition 11. Let (X, X ) and (Y, Y) be measurable spaces.
Then a function W : X × Y → [0, 1] is called a transition
probability (a stochastic kernel / a Markov kernel) from (X, X )
to (Y, Y) if it satisfies the following two conditions:

On the other hand, for any α ∈ (0, ∞] as a result of
Tonelli-Fubini theorem [30, 4.4.5] and the definition of the
Rényi divergence given in (19) we have
Dα (p⊛W k p ⊗ q) ≤ supx ∈X Dα (W (x |·)k q)
= supw∈W Dα (w k q) .

(i) For all x ∈ X, the function W (x |·) : Y → [0, 1] is a
probability measure on (Y, Y).
(ii) For all E ∈ Y, the function W (·|E) : X → [0, 1] is a
X -measurable function.

Hence,
inf q∈P(Y,Y) supp∈P(X,X ) Dα (p⊛W k p ⊗ q)

By [8, Thm. 10.7.2.], for any transition probability W
and probability measure p on (X, X ) there exists a unique
probability measure p⊛W on (X × Y, X ⊗ Y) satisfying
Z
W (x |Ey )p(dx )
p⊛W (Ex × Ey ) =

≤ inf q∈P(Y,Y) supw∈W Dα (w k q) . (109)

Theorem 1 and the inequalities given in (107), (108), and (109)
imply Cα,W = Cα,W and Theorem 3 for qα,W = qα,W .
Theorem 1 and (108) imply that Cα,W ≤ Cα,W even when
X is not countably separated.

Ex

for all Ex ∈ X and Ey ∈ Y. Now, we can define the order α
Rényi information for p on the transition probability W .

C. Deferred Proofs

Definition 12. For any α ∈ [0, ∞], transition probability
W from (X, X ) to (Y, Y), and p ∈ P(X, X ), the order α
Rényi information for prior p is defined as
Iα (p;W) , inf q∈P(Y,Y) Dα (p⊛W k p ⊗ q) .

The following parametric function allows us to write certain
expressions succinctly in the proofs:
d(x k z ) , x ln xz + (1 − x ) ln 1−x
1−z

(100)

Definition 13. For any α ∈ [0, ∞] and transition probability
W from (X, X ) to (Y, Y), the order α Rényi capacity is
(101)

1

The analysis of the Rényi capacity for an arbitrary transition
probability W is beyond the scope of this paper. However,
if the σ-algebra X is countably separated, then we can use
Theorem 1 to show that Cα,W = Cα,W for a W ⊂ P(Y, Y).

kµα,p1 −µα,p2 k ≤ kp1 −p2 k α 2

1

Cα,W = supp∈P(X,X ) inf q∈P(Y,Y) Dα (p⊛W k p ⊗ q) (102)

α−1
α (Cα,W +ln 2)

for all α in [1, ∞) and p1 , p2 in P(W) Consequently, if
Cα,W is finite, then µα,p is uniformly continuous in p.
We are left with proving that Cα,W = ∞ implies the
absence of uniformly continuity in p for µα,p . For any s
in P(W) let sı be

(104)

where W , {W (x |·) : x ∈ X}. If Cα,W < ∞, then
there exists a unique qα,W in P(Y, Y), called the order α
Rényi center, such that

= supw∈W Dα (w k qα,W ) .

(kµα,s1 k ∨ kµα,s2 k).

kµα,p1 − µα,p2 k ≤ kp1 − p2 k α e

= inf q∈P(Y,Y) supp∈P(X,X ) Dα (p⊛W k p ⊗ q) (103)

Cα,W = supp∈P(X,X ) Dα (p⊛W k p ⊗ qα,W )

α−1
α

for all α in [1, ∞) and p1 , p2 in P(W) where s1 and s2
are members of P(W) determined by the decomposition
given in Lemma 4-(c).
α−1
On the other hand kµα,s k ≤ e α Cα,W for any s in P(W)
by the proof of part (b). Thus

Theorem 3. For any α ∈ (0, ∞] and transition probability W
from (X, X ) to (Y, Y) for a countably separated σ-algebra X

= inf q∈P(Y,Y) supw∈W Dα (w k q)

∀x , z ∈ [0, 1]. (110)

Proof of Lemma 16.
(a) For any α ∈ (0, 1) the definitions of Iα (p;W) and Cα,W
α
imply inf p∈P(W) kµα,p k = e α−1 Cα,W .
α
(b) supp∈P(W) kµα,p k = e α−1 Cα,W for any α ∈ (1, ∞)
and supp∈P(W) kµ∞,p k = eC∞,W by the definitions of
Iα (p;W) and Cα,W .
(c) Let us first prove that if Cα,W < ∞, then µα,p is
uniformly continuous in p. Lemma 4-(e) and the triangle
inequality imply

Definitions 4 and 12 are equivalent because of Lemma 14.
Using the definition of Iα (p;W) we can define the order α
Rényi capacity of a transition probability W .

Cα,W , supp∈P(X,X ) Iα (p;W) .

(108)

sı = (1 − 1ı )s + 1ı pı

(105)

∀ı ∈ Z+

where pı ’s are such that kµα,pı k ≥ ı. The existence of
µα,pı
such pı ’s follows from part (b). Then ı1/α
≤ µα,sı by
α−1
the definition of mean measure. Thus kµα,sı k ≥ ı α
and using the triangle inequality we get

(106)

Proof of Theorem 3. Since X is countably separated, all singletons are in X by [8, Thm. 6.5.7] and P(X) ⊂ P(X, X ).
Consequently, using maxmin inequality we get

kµα,sı − µα,s k ≥ ı

α−1
α

− kµα,s k.

On the other hand, ks − sı k ≤ 2/ı by the triangle
inequality, as well. Thus kµα,p −µα,s k is an unbounded
function of p on every neighborhood of s, i.e. µα,p is not
continuous at p = s.

supp∈P(W) inf q∈P(Y,Y) Dα (p⊛Wk p ⊗ q)

≤ supp∈P(X,X ) inf q∈P(Y,Y) Dα (p⊛W k p ⊗ q)

≤ inf q∈P(Y,Y) supp∈P(X,X ) Dα (p⊛W k p ⊗ q) (107)
25

(d) If Cα,W is infinite, there is a sequence of {pı }ı∈Z+ such
that limı↑∞ Iα (pı ;W) = ∞. Let pβ,ı = (1−β)p +βpı , for
any p. Then the concavity of the order α Rényi information in the prior for α’s in [1, ∞], established in Lemma
6-(b), and the non-negativity of the Rényi information
imply

for all α in (0, η]. Furthermore, given δ and α, g(δ, α, γ)
is nondecreasing in γ. Then using Iα (s1 ;W) ≥ 0,
Iα (s∧ ;W) ≤ Iη (s∧ ;W), and Iη (s∧ ;W) ≤ Cη,W we get
Iα (p1 ;W) ≥ Iα (s∧ ;W)−g(δ, 0, Cη,W )

for all α ∈ (0, η]. On the other hand, p2 = (1 − δ)s∧ + δs2
by the decomposition given in Lemma 4-(c). Then

Iα (pβ,ı ;W) − Iα (p;W) ≥ β(Iα (pı ;W) − Iα (p;W))

1

(1−δ) α µα,s∧ ≤ µα,p2

for all β ∈ (0, 1) and ı ∈ Z+ . On the other hand
kp − pβ,ı k ≤ 2β. Thus Iα (p;W) is not continuous in p,
whenever Cα,W is infinite. The continuity of Iα (p;W) in
p for the case when Cα,W is finite follows from part (e).
(e) We establish the uniform equicontinuity by proving establishing the following bound

as a result of the definition of the mean measure. Thus
e

sup |Iα (p2 ;W)−Iα (p1 ;W)|


C0,W
1
∧ e δ )+ln(1−δ+δeC1,W ) η = 0

ln(1−δ



1−δ+δeCη,W
η ∈ ℜ+\{1}
ln 
 η
1
1 η−1 C
≤
1−η
(1−δ) η +δ η e η η,W




h1 (δ)+δC1,W +ln(1−δ+δeC1,W ) η = 1
(111)

= Iα (s∧ ;W) + f (δ, α, Iα (s2 ;W) − Iα (s∧ ;W))

where the function f (δ, α, γ) is defined for any δ ∈ [0, 1],
α ∈ ℜ+ , and γ ∈ ℜ as follows
(
δγ + h1h(δ)
i α=1.
f (δ, α, γ) ,
α−1
1
1
α
γ
α
α
α
α 6= 1
α−1 ln (1 − δ) + δ e

Similarly for positive orders other than one we have,
h
1
ln (1−δ)e(α−1)[Iα(s∧ ;W)+Dα(qα,s∧ kqα,p1 )]
Iα (p1 ;W) = α−1
i
+δe(α−1)[Iα(s1 ;W)+Dα(qα,s1 kqα,p1 )] . (113)

For any fixed (δ, γ) pair, f (δ, α, γ) is nondecreasing39 in
α. Then for any α in (0, η] we have
Iα (p2 ;W) ≤ Iα (s∧ ;W) + f (δ, η, Iα (s2 ;W) − Iα (s∧ ;W)).

Since the Rényi divergence is non-negative by Lemma 10,
(
(1 − δ)I1 (s∧ ;W) + δI1 (s1 ;W)
α=1
Iα (p1 ;W) ≥ ln[(1−δ)e(α−1)Iα(s∧ ;W) +δe(α−1)Iα(s1 ;W) ]
α 6= 1
α−1

Furthermore, given δ and α, f (δ, α, γ) is nondecreasing
in γ. Then using Iα (s∧ ;W) ≥ 0, Iα (s2 ;W) ≤ Iη (s2 ;W), and
Iη (s2 ;W) ≤ Cη,W we get

≥ Iα (s∧ ;W) − g(δ, α, Iα (s∧ ;W) − Iα (s1 ;W))

Iα (p2 ;W) ≤ Iα (s∧ ;W) + f (δ, η, Cη,W )

where the function g(δ, α, γ) is defined for any δ ∈ [0, 1],
α ∈ ℜ+ , and γ ∈ ℜ as follows
(
δγ
α=1


g(δ, α, γ) ,
.
1
(1−α)γ
ln
(1
−
δ)
+
δe
α
6= 1
1−α

Iα (p2 ;W)−Iα (p1 ;W) ≤ f (δ, η, Cη,W )+g(δ, 0, Cη,W ).
A lower bound on Iα (p2 ;W)−Iα (p1 ;W) can be obtained
using the same arguments with the roles of p1 and p2
reversed. This establishes (111) for η > 0 and α ∈ (0, η].

Iα (p1 ;W) ≥ Iα (s∧ ;W) − g(δ, 0, Iα (s∧ ;W) − Iα (s1 ;W))

39 For any fixed (δ, γ) pair, f (δ, α, γ) is a continuous and differentiable
∂
f (δ, α, γ) ≥ 0. In particular
function of α satisfying ∂α

38 For

any fixed (δ, γ) pair, g(δ, α, γ) is a continuous and differentiable
∂
g(δ, α, γ) ≤ 0. In particular
function of α satisfying ∂α
δe(1−α)γ
(1−δ)+δe(1−α)γ

(115)

for all α in (0, η]. Using (114) and (115) together with
the definition of the Rényi capacity given in (27) we get

Given δ and γ, g(δ, α, γ) is nonincreasing38 in α. Then



(1−α)(Iα(s∧ ;W)−Iα(p2 ;W))−ln(1−δ)
α

for all α’s in ℜ+ . Using the corresponding upper bound
on Dα (qα,s2 k qα,p2 ) together with (112) and (113) we get
the following bound for all positive real orders

(1 − δ)I1 (s∧ ;W)+δI1 (s2 ;W) + h1 (δ) α = 1
1 α−1
Iα(s∧ ;W)
Iα (p2 ;W) ≤ α ln (1−δ) α1 e α−1
α
+δ α e α Iα(s2 ;W)

α 6= 1
α−1

I1 (p1 ;W) = (1 − δ)I1 (s∧ ;W) + (1 − δ)D1 (q1,s∧ k q1,p1 )
+ δI1 (s1 ;W) + δD1 (q1,s1 k q1,p1 ) . (112)

−1
d
(1−α)2

1

(1−δ) α qα,s∧ ≤ qα,p2

=

2k
where δ = kp1 −p
and hα (·) is defined in (62).
2
As a result of the decomposition given Lemma 4-(c) we
can write p1 as p1 = (1 − δ)s∧ + δs1 for some s∧ and
s1 in P(W). Using (19), (22), and (23) we get

=

α−1
α (Iα(s∧ ;W)−Iα(p2 ;W))

by (13) and (21). Applying Lemma 8 we get


1
Dα(qα,s∧ k qα,p2 ) ≤ Dα qα,s∧ k(1−δ) α µα,s∧

α∈[0,η]

∂
g(δ, α, γ)
∂α

(114)


δ .

∂
f (δ, α, γ)
∂α

26

=

1
d
(1−α)2



(1−δ)1/α
(1−δ)1/α +δ 1/α e(1−1/α)γ

1−δ



.

α

Since kµα,p k is a log-convex in α by Lemma 3-(d),

In order to establish (111) for α = 0, recall the definition
of the order zero Rényi information given in (13).

X
s∧ (w )
I0 (p1 ;W) = − ln ess sup (1 − δ)
w:s∧ (w|y)>0
µ1,p1

X
+δ
s1 (w )
w:s1 (w|y)>0


−I0(s∧ ;W)
≥ − ln (1 − δ)e
+δ


= I0 (s∧ ;W) − ln 1 − δ + δeI0(s∧ ;W) .

α

kµα,p k ≤ kµβ,p k

β α−φ
β−φ

kµφ,p k

φ β−α
β−φ

for any φ, α, β satisfying 0 < φ < α < β and p ∈ P(W).
Let us start with η ∈ (0, 1] and ǫ ∈ (0, η2 ] case. Then for
any φ, α, β satisfying 0 < φ < ǫ ≤ α < β ≤ η − ǫ,

Note that I0 (s∧ ;W) ≤ Iη (s∧ ;W) by Lemma 5 and
Iη (s∧ ;W) ≤ Cη,W by definition. Then

I0 (p1 ;W) ≥ I0 (s∧ ;W) − ln 1 − δ + δeCη,W . (116)

Iβ (p;W) − Iα (p;W) =

1
1−α

ln

≤

1
1−α

ln

=
≤

kµα,p kα
kµβ,p k
kµβ,p k

β(1−α)
1−β

β

α−φ
β−φ

kµφ,p k
β(1−α)
k 1−β

kµβ,p
(β−α)(1−φ)
(1−α)(β−φ) (Iβ (p;W)
β−α
ǫ(ǫ−φ) Iβ (p;W) .

1
I0 (p2 ;W) = ess inf ln P
w:p2 (w|y )>0 ((1−δ)s∧ (w)+δs2 (w))
µ1,p2


≤ ess inf µ1,s∧ ln (1−δ) P 1
w:s∧ (w|y )>0 s∧ (w)


1
∧ ess inf µ1,s2 ln δ P
s2 (w)

0 ≤ Iβ (p;W) − Iα (p;W) ≤

1
) ∧ (I0 (s2 ;W) + ln 1δ )
= (I0 (s∧ ;W) + ln 1−δ

Then I0 (s∧ ;W) ≥ 0 and I0 (s2 ;W) ≤ Iη (s2 ;W) ≤ Cη,W imply


Cη,W
1
. (117)
∧ ln e δ
I0 (p2 ;W) ≤ I0 (s∧ ;W) + ln 1−δ

Cη,W
ǫ2 (β

ln

≤

1
α−1

ln

(118)

=

A lower bound on I0 (p2 ;W) − I0 (p1 ;W) can be obtained
using the same arguments with the roles of p1 and p2
reversed. Consequently, (111) holds for η = 0, α = 0
case. In order to establish (111) for η > 0, α = 0 case,
note that


(
1 η−1 C
1
1
1−δ
η ln (1−δ) η +δ η e η η,W
ln 1−δ
≥1
δe−Cη,W
≥
Cη,W
η−1
1−δ
e
ln δ
≤1
δe−Cη,W
i
h
Cη,W
1
∧ ln e δ
≥ ln 1−δ

≤

(α−φ)(β−1)
(α−1)(β−φ) (Iβ (p;W)
(α−φ)
ǫ2 βCβ,W .

Thus using (116) and (117) we get

e

δ



.

|Iα (p;W)−Iφ (p;W)| ≤

− φ|

kµφ,p k
kµβ,p k

φ(α−1)
φ−1

β

α−φ
β−φ

kµφ,p k

kµφ,p k

φ

β−α
β−φ

φ(α−1)
φ−1

− Iφ (p;W))
(121)

If 0 < α − φ < ǫ, then at least one of the three closed
intervals [ǫ, 1 − ǫ], [ 21 , 5η−1
4η ], [1 + ǫ, η − ǫ] includes both α
and φ. When α and φ are in [ǫ, 1−ǫ] we use (120). When
α and φ are in [1 + ǫ, η − ǫ] we use (121). Derivation of
the bound for the second interval takes some effort. Let
us first finish the proof of (119) assuming that the bound
given in (128) holds for the second interval. Then for any
φ, α such that ǫ ≤ φ ≤ α ≤ (φ + ǫ) ∧ (η − ǫ) we have
Iα(p;W)−Iφ(p;W)
α−φ
Cη,W

 ǫ2
2 2Cη,W
e
≤ 4Cη,W + 160η
e2 (η−1)2

ηCη,W
ǫ2

0≤

Thus (111) holds for η > 0, α = 0 case, as well.
(f) In order to establish the uniform equicontinuity we prove
the Lipschitz continuity of {Iα (p;W)}p∈P(W) in α on
compact subsets of (0, η) with a common Lipschitz
constant: If α and φ in [ǫ, η−ǫ] for an ǫ ∈ (0, ǫη ], then
γη
ǫ2 |α

(120)

kµα,p kα

1
α−1

Cη,W

− Iφ (p;W))

− α)

Iα (p;W) − Iφ (p;W) =

I0 (p2 ;W)−I0 (p1 ;W) ≤ ln 1 − δ + δe

1
+ ln 1−δ
∧

β−α
β−φ

for any p in P(W) and β, α satisfying ǫ ≤ α ≤ β ≤ η−ǫ.
(120) establishes (119) for η ∈ (0, 1] and ǫ ∈ (0, η2 ] case.
We proceed with η ∈ (1, ∞) and ǫ ∈ (0, η−1
8η ] case. For
any φ, α, β such that 1 + ǫ ≤ φ < α ≤ β − ǫ and p in
P(W) we have

w:s2 (w|y )>0



φ

The above bound holds for any φ in (0, ǫ). Furthermore,
the Rényi information is a nondecreasing function of the
order by Lemma 5. Then

On the other hand,

Cη,W

.

(119)

ǫ ≤ φ ≤ α ≤ (φ+ǫ)∧(1−ǫ)
1
2

≤ φ ≤ α ≤ (φ+ǫ)∧ 5η−1
4η

1+ǫ ≤ φ ≤ α ≤ (φ+ǫ)∧(η−ǫ)

Thus for any α and φ satisfying ǫ ≤ φ ≤ α ≤ (φ+ǫ)∧(η−ǫ)
and p in P(W) we have
h
i
2Cη,W
ηCη,W + 5e 2e2
.
Iα (p;W) − Iφ (p;W) ≤ α−φ
ǫ2

for all p in P(W) where ǫη and γη are defined as follows
(
η
η ∈ (0, 1]
2
,
ǫη , η−1
η
∈ (1, ∞)
8η
(
Cη,W
η ∈ (0, 1]
.
γη ,
5e2Cη,W
η ∈ (1, ∞)
ηCη,W + 2e2

Note that the preceding bound is linear with a uniform
constant, thus the hypothesis φ ≤ α ≤ φ + ǫ can be
removed without loss of generality. Thus (119) holds for
η ∈ (1, ∞) case for any ǫ ∈ (0, ǫη ], as well.
27

β

4x
Note that x φ ln2 x ≤ e24φ2 1{x ∈[0,1)} + e2 (β−φ)
2 1{x >1}
for all β > φ. Then using Lemma 2-(a) we get the
following bound for all φ in [ 21 , 5η−1
4η ]
2

X
p (w|y)
p[φ] (w |y) φ1 ln [φ]p(w)
w

 

X
p[1] (w|y) φ
p[1] (w|y) 2
=
p(w ) p(w)π
ln
p(w)πφ,p
φ,p
w

 3η−1
−2 X

2η
p[1] (w|y)
−
φ
p(w
)
≤ e24φ2 + e42 3η−1
2η
p(w)πφ,p
w

−2 
 3η−1
2η
π 3η−1 ,p /πφ,p
−
φ
= e24φ2 + e42 3η−1
2η
2η
 3η−1

2 
2η
η
64
π 3η−1 ,p /πφ,p
.
(126)
≤ 16
+
e2
e2
η−1
2η

We are left with establishing the bound given in (128).
For orders other than one, (4) and (16) imply that


kµ′α,p k Iα(p;W)
1
d
.
dα Iα (p;W) = α−1 α kµα,p k −
α
The expression in the brackets is differentiable in α
on ℜ+ because kµα,p k is positive and kµα,p k, µ′α,p ,
and Iα (p;W) are differentiable by Lemma 1-(a), Lemma
3-(b,c), Lemma 5. Furthermore, the expression in the
brackets is equal to zero at α = 1. Then as a result of
the mean value theorem [79, 5.10] for each α ∈ [1/2, 1)
there exists a φ ∈ (α, 1) and such that


αkµ′α,p k
Iα(p;W)
d
d
.
(122)
dα Iα (p;W) = dα
kµα,p k −
α

On the other hand (πα,p )α is log-convex in α by Lemma
2-(c) and πα,p is nondecreasing in α by Lemma 2-(d).
Thus for all φ in [ 21 , 5η−1
4η ] we have

α=φ

Using the expressions for derivatives given in Lemma 2(b) and Lemma 3-(b,c) we get
′
d αkµα,p k
dα kµα,p k

=

αµ′′
α,p (Y)
kµα,p k

= Eqα,p

+
X

kµ′α,p k

−

kµα,p k

p[α] (w|y)
α2
w

h

αkµ′α,p k
kµα,p k2



′
α(1−α)(πα,p
)2
(πα,p )2

+ Eqα,p
 ′ 2 X
π
≤ Eqα,p 4πα,p
2 +
α,p

ln

i

−

p[α] (w|y)
p(w)

2 

αkµ′α,p k
kµα,p k − kµα,p k2

kµ′α,p k

p[α] (w|y)
α2
w



2



ln

p[α] (w|y)
p(w)

2

2 

′
P
απα,p
p (w|y)
Then using w p[α] (w |y) α1 ln [α]
= πα,p
, which
p(w)
follows from Lemma 2-(b), we get
#
"
X p (w|y)  p (w|y) 2
′
2
α
µ
k
k
α,p
[α]
4α +1
d
ln [α]
dα kµα,p k ≤ 4α2 Eqα,p
α2
p(w)

(123)

Since Iα (p;W) is differentiable and nondecreasing in α
= − Iα(p;W)
+
α2

1 d
α dα Iα (p;W)

≥ − Iα(p;W)
α2

2η

 3η−1
2η

≤ (π

η−1

2ηφ
2ηφ−η+1 ,p

)(πφ,p )φ 2ηφ

≤ (πη,p )(πφ,p )

η−1
2η

.

(127)

Using equations (125), (126), and (127) we get

2
kµη,p k
η
32
128
d
dα Iα (p;W) ≤ 4Iη (p;W) + e2 + e2
η−1
kµ1/2,p k
2

128η
= 4Iη (p;W)+ 32
e2 + e2 (η−1)2 e

η−1
η Iη(p;W)+I 1 (p;W)
2

for all α in [ 12 , 5η−1
4η ]. Since Iα (p;W) is nondecreasing in
α by Lemma 5, the definition of Rényi capacity implies

2
η
32
128
d
I
(p;W)
≤
4C
+
+
e2Cα,W
η,W
dα α
e2
e2
η−1

for all α in [ 21 , 5η−1
4η ] and p in P(W). Hence,
i
h
2 2Cη,W
e
(128)
Iα (p;W)−Iφ (p;W) ≤ (α−φ) 4Cη,W + 160η
e2 (η−1)2

w

d Iα(p;W)
dα
α

π 3η−1 ,p

(124)

Using (122), (123), and (124) we can conclude that there
exists a φ ∈ (α, 1) such that
"
#
X p (w|y) h p (w|y)i2
[φ]
d
ln [φ]p(w)
+4Iφ (p;W)
dα Iα (p;W) ≤ 2Eqφ,p
φ2
w

Similarly for all α ∈ (1, ∞) there exists a φ ∈ (1, α) satisfying the same identity. Furthermore, one can confirm
by substitution for the expression given in (17) that
#
"


X
p[1] (w|y) 2
d
1
.
p[1] (w |y) ln p(w)
dα Iα (p;W) α=1 ≤ 2 Eq1,p

for all φ, α in [ 21 , 5η−1
4η ] satisfying φ ≤ α and p in P(W).
(g) For any p ∈ P(W), Iα (p;W) is nondecreasing and
continuous in α on [0, ∞] by Lemma 5. Then Iα (p;W)
is a quasi-convex continuous function of α satisfying
Iα (p;W) = inf η∈(α,∞) Iη (p;W) for any p in P(W). Using
the definition of Cα,W we get
Cα,W = supp∈P(W) inf η∈(α,∞) Iη (p;W)

∀α ∈ ℜ≥0 . (129)

Since Iα (p;W) ≤ ln |W| by Lemma 5, if W is finite, then
Cα,W is finite for all α ∈ ℜ≥0 and Iα (p;W) is continuous
in p on P(W) for all α ∈ ℜ+ by part (e). Furthermore
Iα (p;W) is quasi-concave in p for all α ∈ ℜ+ by Lemma
6. Then we can change the order of the supremum and
the infimum in (129) using Sion’s minimax theorem, [94,
Cor. 3.3], [57] because P(W) is compact.

w

Thus there exist an φ ∈ ( 12 , 5η−1
4η ) such that
d
supα∈[ 1 , 5η−1 ] dα
Iα (p;W)
2
4η

≤ 4Iφ (p;W)+2Eqφ,p

= inf η∈(α,∞) Cη,W

∀α ∈ ℜ≥0 .

Then Cα,W is continuous from the right. On the other
hand Cα,W is continuous from the left because it is
nondecreasing and lower semicontinuous on [0, ∞] by
Lemma 15-(a).

"
Xp
w

Cα,W = inf η∈(α,∞) supp∈P(W) Iη (p;W)

#
h
i
p[φ] (w|y) 2
[φ] (w|y)
ln p(w)
. (125)
φ2
28

P
Cα,Wı
qα,Wı by Theorem 1. because
for ũ =
ı∈T e
ũ
Sα,Wı ( /kũk) = Cα,W .

Proof of Lemma 21. supı∈T Cα,Wı ≤ Cα,W :
(a)

Cα,W ≥ Sα,Wı (qα,W )
(b)

Proof of Lemma
By the definition of Iα (p;W) for all p
Q22.
⊗
satisfying p = t∈T pt for some pt ∈ P(Wt ) we have
X
Iα (p;W) =
Iα (pt ;Wt)
∀α ∈ [0, ∞].
(131)
t∈T
Q⊗
Furthermore, {p : p = t∈T pt , pt ∈ P(Wt ), ∀t ∈ T} is a
subset of P(W). Then
X
Cα,W ≥
sup
Iα (pt ;Wt)

≥ Cα,Wı + Dα (qα,Wı k qα,W )

(c)

≥ Cα,Wı +

α∧1
2 kqα,Wı

− qα,W k2

where (a) follows from (1), Theorem 1, and Wı ⊂ W,
(b) follows from Lemma 19, (c) follows from Lemma 10.
Consequently, Cα,W ≥ supı∈T Cα,Wı and if Cα,Wı = Cα,W ,
then qα,W = qα,Wı .
= Cα,W and qα,W = qα,Wı , then
• If Cα,Wı
Sα,W (qα,Wı ) ≤ Cα,Wı by Theorem 1.
• If Sα,W (qα,Wı ) ≤ Cα,Wı , then Cα,W ≤ Cα,Wı because
Cα,W = Sα,W by Theorem 1 and Sα,W ≤ Sα,W (qα,Wı )
by definition. Then Sα,W (qα,Wı ) ≤ Cα,Wı implies
Cα,W = Cα,Wı because Cα,W ≥ Cα,Wı by definition.
P
Cα,W ≤ ln ı∈T eCα,Wı : If T is infinite, then the inequality
holds trivially because the right hand side is infinite. Thus,
we will
W establish the inequality assuming T is finite. Let v be
v , ı∈T eCα,Wı qα,Wı . Then

p1 ,p2 ,...,p|T|

≤ maxı∈T Sα,Wı (qα,Wı ) − ln eCα,Wı + ln kv k
(130)

where (a) follows from (1) and (2), (b) follows from Lemma
8 because eCα,Wı qα,Wı ≤ P
v , and (c) follows from Theorem 1.
Cα,Wı
by the definition of v .
On the other hand,
kv
k
≤
ı∈T e
P
Cα,Wı
by Theorem 1.
Then Cα,W ≤ ln ı∈T e
P
Cα,Wı
is infinite. If T is finite
• If T is infinite, then
ı∈T e
singular
for some distinct
but qα,Wı and qα,W are not
P
ı and , then Cα,W < ln P ı∈T eCα,Wı by (130) and
Theorem 1 because
< ı∈T eCα,Wı . Consequently,
P kvCkα,W
ı < ∞, then T is finite and
if Cα,W = ln ı∈T e
qα,Wı ⊥ qα,W for all ı 6=  in T.
• If T is finite and qα,Wı ⊥ qα,W for all ı 6= , then any
P
u ∈ P(Y, Y) can be written as u = |T|
ı=0 uı where uı are
for
ı ∈ {1, . . . , |T|}
finite measures
such
that
u
≺q
ı
α,W
ı
P
and u0 ⊥ ( ı∈T qα,Wı ) by the Lebesgue decomposition
theorem [30, 5.5.3]. Then using Lemmas 8 and 9, we get

Proof of Lemma 23. (19) implies that
Dα (p⊛Wk p ⊗ qα,W ) ≤ supw∈supp(p) Dα (w k qα,W ) ,
Dα (p⊛Wk p ⊗ qα,W ) ≥ inf w∈supp(p) Dα (w k qα,W ) .

On the other hand, (22) and (23) imply that
Dα (p⊛Wk p ⊗ qα,W ) = Iα (p;W) + Dα (qα,p k qα,W ) .
Then (61) follows from (60) and Theorem 1.
Note that Cα,Wα,ǫ is bounded above by Cα,W and hence
finite by definition. Thus Wα,ǫ has a unique order α Rényi center by Theorem 1. If qα,Wα,ǫ = qα,W , then Cα,Wα,ǫ = Cα,W
by the definition of Wα,ǫ and Theorem 1.
We show in the following by contradiction that qα,Wα,ǫ
ǫ
ǫ
equals to qα,W . Let q = (1 − e− /2 )qα,Wα,ǫ + e− /2 qα,W . Then
using Lemma 8 and (60) we get

Dα (qα,Wı k u) ≥ − ln kuı k.
Thus Lemma 19 implies
∀u ∈ P(Y, Y).

supw∈W\Wα,ǫ Dα (w k q) ≤ Cα,W − ǫ/2.

Since Sα,W (u) = maxı∈T Sα,Wı (u) for all u in P(Y, Y)
and Cα,W = inf u∈P(Y,Y) Sα,W (u) by Theorem 1, we get
Cα,W ≥ inf u∈P(Y,Y) maxı∈T ln
P

eCα,Wı
kuı k

Cα,W
ı

e

ı∈T
≥ inf u∈P(Y,Y) ln P
ı∈T kuı k
X
≥ ln
eCα,Wı .
ı∈T
P
Then Cα,W = ln ı∈T eCα,Wı because we have already
proved the reverse inequality. Furthermore, qα,W = ũ/kũk

Cα,Wt

∀wt ∈ Wt .
Q⊗
Recall that all w ’s in W can be written as w = t∈T wt for
Q⊗
some wt ∈ Wt by the hypothesis. Then for q , t∈T qα,Wt
by the definition of the Rényi divergence given (19) and
Tonelli-Fubini theorem [30, 4.4.5] we have
X
Dα (w k q) =
Dα (wt k qα,Wt )
Xt∈T
≤
∀w ∈ W.
(133)
Cα,Wt
t∈T
P
Then Cα,W ≤
t∈T Cα,Wt by (33) Thus (59) holds and
qα,W = q follows from (133) and Theorem 1 for the case
when Cα,W < ∞.

(b)

Sα,Wı (u) ≥ Cα,Wı − ln kuı k

t∈T

Dα (wt k qα,Wt ) ≤ Cα,Wt

(a)

= ln kv k

t∈T

∀α ∈ [0, ∞]. (132)
P
Let us proceed with proving Cα,W ≤ t∈T Cα,Wt . If there
exists a t ∈ T such that Cα,Wt = ∞, then the inequality holds
trivially. Else, Cα,Wt < ∞ for all t ∈ T and by Theorem 1
there exists a qα,Wt for each t ∈ T such that
=

Sα,W (v/kv k) = maxı∈T Sα,Wı (v/kv k)
(c)

X

(134)

The convexity of the Rényi divergence in its second argument,
i.e. Lemma 11, and Theorem 1 imply that
supw∈Wα,ǫ Dα (w k q)
h
i

ǫ
ǫ
≤ sup (1 − e− /2 )Dα w k qα,Wα,ǫ + e− /2 Dα (w k qα,W )
w∈Wα,ǫ

≤ (1 − e− /2 )Sα,Wα,ǫ (qα,Wα,ǫ ) + e− /2 Sα,Wα,ǫ (qα,W )
ǫ

ǫ

= (1 − e− /2 )Cα,Wα,ǫ + e− /2 Cα,W .
ǫ

29

ǫ

(135)

Since Cη,W is finite this implies that µη,p ≺qη,W . On the
other hand µα,p is nondecreasing in α, in the sense that
if α < η then µα,p ≤ µη,p , by Lemma 3-(a,b). Hence,

If qα,Wα,ǫ 6= qα,W , then Cα,Wα,ǫ < Cα,W by Lemma 21.
Then Sα,W (q) < Cα,W by (134) and (135). However, this is
a contradiction by Theorem 1. Thus qα,Wα,ǫ = qα,W holds.
As a result of the definition of Wα,ǫ , anTelement of W is in
Wα,0 iff it is in Wα,ǫ for all ǫ > 0, i.e. ǫ>0 Wα,ǫ = Wα,0 .
Consequently, if W is a finite set, then Wα,ǫ = Wα,0 for small
enough ǫ. Then Cα,Wα,0 = Cα,Wα,ǫ = Cα,W . Furthermore,
(61) holds for ǫ = 0 because (61)
T holds for all ǫ > 0.
For arbitrary W’s, identity ǫ>0 Wα,ǫ = Wα,0 does not
imply that Wα,ǫ = Wα,0 for some ǫ > 0. Wα,0 can be the
empty set or a non-empty set such that Cα,Wα,0 < Cα,W , see
Example 4.

Z

for all p in P(W) and α in [0, η]. Then
dµα,p
{ dqη,W

Dα (µ1,p k qα,W ) ≤ maxw∈supp(p) Dα (w k qα,W )
≤ Cα,W
for all p ∈ P(W). Then Cα,chW ≤ Cα,W by Theorem 1.
(b) Cα,W ≤ Cα,clW by definition because W ⊂ clW. If
Cα,W = ∞, then the reverse inequality Cα,clW ≤ Cα,W
holds trivially. If Cα,W < ∞, then ∃!qα,W satisfying
supw∈W Dα (w k qα,W ) = Cα,W by Theorem 1. Furthermore, for all v ∈ P(Y, Y) and ǫ > 0 there exists an open
set N containing v , i.e. a neighborhood of v , such that

Z

∀s ∈ N

by the lower semicontinuity, i.e. Lemma 13. If v ∈ clW,
then every open set containing v contains a member of
W. Thus Dα (v k qα,W ) − ǫ < Cα,W for every v in clW
and positive ǫ. Then40 Dα (v k qα,W ) ≤ Cα,W for every
v ∈ clW and Cα,clW ≤ Cα,W by Theorem 1.
The closure of W for a topology stronger than the
topology of setwise convergence is a subset of the closure
of W for the topology of setwise convergence and a
superset of W. Thus its Rényi capacity is bounded from
below and from above by Cα,W .
(c) If Cη,W < ∞, then as a result Theorem 1, Lemma 14,
and (22) there exists a unique qη,W satisfying
Dη (qη,p k qη,W ) ≤ Cη,W − Iη (p;W)

dµα,p
dqη,W ’s

are qη,W -

: p ∈ P(W), α ∈ [0, η]}
integrable and the set
satisfies the necessary and sufficient condition for the uniform integrability41 determined by de la Vallée Poussin
[8, Thm. 4.5.9], for the growth function G(x ) = x η .
But when the reference measure is finite, the uniform
integrability is equivalent to the uniform absolute continuity of the integrals and boundedness in L1 (qη,W ) by [8,
Thm. 4.5.3], which in our case is nothing but the uniform
absolute continuity with respect to qη,W and boundedness
in total variation norm for the set of all mean measures.
Thus {µα,p : p ∈ P(W), α ∈ [0, η]}≺uni qη,W .
On the other hand by [8, Thm. 4.7.25], a set of measures
is uniformly absolutely continuous with respect to a finite
measure and bounded in variation norm iff it has compact
closure in the topology of setwise convergence. A set
of measures has compact closure in the topology of
setwise convergence iff it has compact closure in the weak
topology by [8, Thm. 4.7.25], as well.
If η = 1, then using x ln x ≥ −1/e, kµ1,p k = 1, and the
definition of the Rényi divergence given in (19) we get,

Proof of Lemma 24.
(a) Cα,W ≤ Cα,chW by definition because W ⊂ chW. If
Cα,W = ∞, then the reverse inequality Cα,chW ≤ Cα,W
holds trivially. If Cα,W < ∞, then ∃!qα,W satisfying
supw∈W Dα (w k qα,W ) = Cα,W by Theorem 1. Then as
a result of the quasi-convexity of the Rényi divergence in
its first argument, i.e. Lemma 12, we have

Dα (v k qα,W ) − ǫ < Dα (sk qα,W )

dµ

α,p η
) qη,W (dy) ≤ e(η−1)Cη,W
( dqη,W

dµ1,p
dq1,W

dµ

1,p
ln dq1,W

+

q1,W (dy) ≤ C1,W − I1 (p;W) +

1
e

+

for all p in P(W) where |x | = x ∨ 0. Since mean
measure is a nondecreasing function of the order by
+
Lemma 3-(a,b) and |x ln x | is a nondecreasing function
of x . Then we have,
Z
+
dµα,p
dµα,p
q1,W (dy) ≤ C1,W + 1e
dq1,W ln dq1,W

∀p ∈ P(W).

If η > 1, then using the definitions of Rényi information
and divergence given in (13) and (19) we get
Z
dqη,W 1−η
dµ
)
ν(dy) ≤ e(η−1)Cη,W ∀p ∈ P(W).
( dνη,p )η ( dν
40 This observation is nothing but the definition of the continuity: A function
f : X → Z is continuous iff for any A ⊂ X, f (clA) ⊂ clf (A) by [68, Thm.
18.1]. If we chose X to be P(Y, Y) with the topology of setwise convergence,
Z to be (−∞, ∞] with the topology generated
 by the sets of the form (z , ∞]
for z ∈ ℜ , and f to be f (·) = Dα ·k qα,W , then the lower semicontinuity of
the Rényi divergence in its first argument is equivalent to the continuity of f .
On the other hand, f (W) ⊂ (−∞, Cα,W ] by Theorem 1 and (−∞, Cα,W ] is
a closed set for the topology we have chosen for (−∞, ∞]. Thus f (clW) ⊂
clf (W) ⊂ (−∞, Cα,W ], i.e. Dα v k qα,W ≤ Cα,W for all v ∈ clW.

for all p in P(W) and α in [0, 1].
+
We use the growth function G(x ) = |x ln x | instead
of G(x ) = x η , the rest of the proof for η = 1 case is
identical to that of η > 1 case.
(d) The equivalence of the last three statements to one
another is a version of Dunford-Pettis theorem [8, 4.7.25].
Thus we will only prove the equivalence of the first two
statements.
Let us first prove the direct part: if there exists a µ in
P(Y, Y) satisfying W≺uni µ, then limα↑1 1−α
α Cα,W = 0.
41 A set of q
η,W -integrable functions is uniformly integrable iff it has
compact closure in the weak topology of L1 (qη,W ) by Dunford-Pettis
dµ
theorem [8, 4.7.18]. Thus { dq α,p : p ∈ P(W), α ∈ [0, η]} has compact
η,W
closure in the weak topology of L1 (qη,W ). Since we have chosen to work
with the space of measures rather than the space of integrable functions we
have stated our result in terms of relative compactness in the space of measures
rather than integrable functions.

30

Note that Cα,W ≤ supw∈W Dα (w k q) for all α ∈ (0, 1)
and q ∈ P(Y, Y) by Theorem 1. Thus using (19) we get

ACKNOWLEDGMENT

Since W≺ µ, for all ǫ > 0 there exists a δ > 0 such
that if µ(E) ≤ δ for an E ∈ Y, then w (E) ≤ ǫ for all
1
w ∈ W. On the other hand µ( dw
dµ > δ ) ≤ δ by Markov
inequality. Hence

Author would like to thank Fatma Nakiboğlu and Mehmet
Nakiboğlu for their hospitality; this work simply would
not have been possible without it. Author would like to
thank Harikrishna R. Palaiyanur for sending him Augustin’s
manuscript, Imre Csiszár for pointing out Agustin’s work [6] at
Austin in 2010 ISIT, Igal Sason for pointing out [2], [83], [84],
Reviewer I for pointing out [53], [58], [66], [67], [73], [89],
[104], and Güneş Nakiboğlu, Robert G. Gallager, and both of
the reviewers for their suggestions on the manuscript.

1
w ( dw
dµ > δ ) ≤ ǫ.

R EFERENCES

lim sup 1−α
α Cα,W ≤ lim sup sup D1−α (µk w )
α↑1 w∈W
α↑1
h
i
dw α
≤ lim sup sup −1
α lnEµ ( dµ ) . (136)
α↑1

w∈W

uni

On the other hand using (19) we get

h
i
α−1
dw α
Eµ ( dµ ) ≥ Ew ( dw
1 dw
dµ )

1
{ dµ ∈(0, δ ]}

1
≥ δ 1−α (1 − w ( dw
dµ > δ ))

(137)


[1] S. M. Ali and S. D. Silvey. A general class of coefficients of divergence
of one distribution from another. Journal of the Royal Statistical
Society. Series B (Methodological), 28(1):131–142, 1966.
[2] D. Amir. Characterizations of Inner Product Spaces, volume 20 of
Operator Theory: Advances and Applications. Birkhäuser Basel, 1
edition, 1986.
[3] E. Arikan. An inequality on guessing and its application to sequential
decoding. IEEE Transactions on Information Theory, 42(1):99–105,
Jan 1996.
[4] S. Arimoto. Information measures and capacity of order α for discrete
memoryless channels. In I. Csiszár and P. Elias, editors, Topics in
Information Theory, volume 16, pages 41–52. Math. Soc. J. Bolyai,
North-Holland, Amsterdam, 1977.
[5] U. Augustin. Error estimates for low rate codes. Zeitschrift für
Wahrscheinlichkeitstheorie und Verwandte Gebiete, 14(1):61–88, 1969.
[6] Udo Augustin. Noisy Channels. Habilitation thesis, Universitat Erlangen, 852 Erlangen, West Germany, 1978. (https://goo.gl/8wupWM).
[7] S. G. Bobkov and G. P. Chistyakov. Entropy power inequality for the
Rényi entropy. IEEE Transactions on Information Theory, 61(2):708–
714, Feb 2015.
[8] Vladimir I. Bogachev. Measure Theory. Springer-Verlag, 2007.
[9] Pierre Bremaud. Point Processes and Queues: Martingale Dynamics.
Springer Series in Statistics. Springer New York, 1981.
[10] C. Bunte and A. Lapidoth. Encoding tasks and Rényi entropy. IEEE
Transactions on Information Theory, 60(9):5065–5076, Sept 2014.
[11] C. Bunte and A. Lapidoth. On the listsize capacity with feedback. IEEE
Transactions on Information Theory, 60(11):6733–6748, Nov 2014.
[12] C. Bunte and A. Lapidoth. Maximum Rényi entropy rate. IEEE
Transactions on Information Theory, 62(3):1193–1205, March 2016.
[13] M. V. Burnashev and Yu. A. Kutoyants. On the sphere-packing
bound, capacity, and similar results for Poisson channels. Problems
of Information Transmission, 35(2):95–111, 1999.
[14] Z. H. Chen, Z. H. Ma, I. Nikoufar, and S. M. Fei. Sharp continuity
bounds for entropy and conditional entropy. Science China Physics,
Mechanics & Astronomy, 60(2):020321, Feb 2017.
[15] H. C. Cheng and M. H. Hsieh. Concavity of the auxiliary function for
classical-quantum channels. IEEE Transactions on Information Theory,
62(10):5960–5965, Oct 2016.
[16] H. C. Cheng and M. H. Hsieh. Moderate deviation analysis for
classical-quantum channels and quantum hypothesis testing. IEEE
Transactions on Information Theory, 64(2):1385–1403, Feb 2018.
[17] H-C Cheng, M-H Hsieh, and M Tomamichel. Quantum sphere-packing
bounds with polynomial prefactors. ArXiv e-prints, 1704.05703v1,
2017.
[18] Thomas M Cover and Joy A Thomas. Elements of information theory.
Wiley-Interscience, 2 edition, 2006.
[19] I. Csiszár. Eine informationstheoretisehe ungleichung und ihre anwendung auf den beweis der ergodizität von markoffschen ketten. Magyar
Tud. Akad. Mat. Kutató Int. Közl., 8:85–108, 1963.
[20] I. Csiszár. A note on jensen’s inequality. Studia Sci. Math. Hungar.,
1:185–188, 1966.
[21] I. Csiszár. Information-type measures of difference of probability
distributions and indirect observations. Studia Sci. Math. Hungar.,
2:299–318, 1967.
[22] I. Csiszár. On topological properties of f -divergences. Studia Sci.
Math. Hungar., 2:329–339, 1967.
[23] I. Csiszár. A class of measures of informativity of observation channels.
Periodica Mathematica Hungarica, 2(1-4):191–213, 1972.

∀w ∈ W.

Then as a result of (136) and (137) we have
lim supα↑1 1−α
α Cα,W ≤

1
1−ǫ

∀ǫ > 0.

limα↑1 1−α
α Cα,W

Then
= 0 because Cα,W ≥ 0.
We are left with proving the converse statement: if
limα↑1 1−α
α Cα,W = 0, then there exists a µ ∈ P(Y, Y)
such that W≺uni µ. We start with proving the following
statement about the Rényi centers: For every ǫ > 0 there
exists a (φ, δ) pair such that φ ∈ (0, 1), δ ∈ (0, ǫ), and if
qφ,W (E) ≤ δ, then w (E) < ǫ for all w ∈ W.
For any ǫ > 0 there exists a φ ∈ (0, 1) such that
φ−1
e φ Cφ,W > 1− 2ǫ because limα↑1 1−α
α Cα,W = 0. On the
σ({E})
other hand, Dα
(w k qα,W ) ≤ Cα,W for any w ∈ W
and E ∈ Y, as a result of Lemma 9 and Theorem 1. Then
the above described φ satisfies
f (w (E), qφ,W (E)) ≥ (1 − 2ǫ )φ

(138)

for all E ∈ Y and w ∈ W where the function f (x , z ) is
defined for all x ∈ [0, 1] and z ∈ [0, 1] as
f (x , z ) , x φ z 1−φ + (1 − x )φ (1 − z )1−φ .

Given ǫ ∈ (0, 0.5) and the corresponding φ ∈ (0, 1), let
δ be the unique z in (0, ǫ) satisfying f (ǫ, z ) = (1 − ǫ/2)φ .
Such a z exists because f (ǫ, 0) = (1 − ǫ)φ , f (ǫ, ǫ) = 1
and f (ǫ, z ) is monotone increasing and continuous in z on
[0, ǫ]. On the other hand f (x , z ) < f (ǫ, δ) = (1− ǫ/2)φ for
any z ∈ [0, δ) and x ∈ [ǫ, 1] because f (x , z ) is monotone
increasing in z on [0, x ] for any x ∈ (0, 1] and monotone
decreasing in x on [z , 1] for any z ∈ [0, 1). Hence, using
(138) we can conclude that if qφ,W (E) < δ for a E ∈ Y,
then w (E) < ǫ for all w ∈ W. In the following we use
this property
a µ such that W≺uni µ.
Pto construct
−ı
Let µ be
ı∈Z+ 2 qφı ,W where (φı , δı ) is the pair
associate with ǫ = 1/ı. Then for any E ∈ Y and ı ∈ Z+ ,
if µ(E) ≤ 2−ı δı , then qφı ,W (E) ≤ δı and consequently
w (E) ≤ 1/ı for all w in W. Thus for any ǫ > 0 if
1
µ(E) ≤ 2−⌈ /ǫ⌉ δ⌈1/ǫ⌉ for an E ∈ Y, then w (E) < ǫ for all
w in W.

31

[54] J. Jeon. A generalized typicality for abstract alphabets. ArXiv e-prints,
1401.6728, 2014.
[55] Yu. M. Kabanov. The capacity of a channel of the Poisson type. Theory
of Probability & Its Applications, 23(1):143–147, 1978.
[56] J. H. B. Kemperman. On the Shannon capacity of an arbitrary channel.
Indagationes Mathematicae (Proceedings), 77(2):101–115, 1974.
[57] H. Komiya. Elementary proof for Sion’s minimax theorem. Kodai
Mathematical Journal, 11(1):5–7, 1988.
[58] R. König and S. Wehner. A strong converse for classical channel coding
using entangled inputs. Phys. Rev. Lett., 103:070504, Aug 2009.
[59] S. Kullback. A lower bound for discrimination information in terms
of variation (corresp.). IEEE Transactions on Information Theory,
13(1):126–127, January 1967.
[60] S. Kullback. Correction to a lower bound for discrimination information in terms of variation. IEEE Transactions on Information Theory,
16(5):652–652, September 1970.
[61] M. A. Kumar and I. Sason. Projection theorems for the Rényi
divergence on α-convex sets. IEEE Transactions on Information
Theory, 62(9):4924–4935, Sept 2016.
[62] M. A. Kumar and R. Sundaresan. Minimization problems based
on relative α-entropy I: Forward projection. IEEE Transactions on
Information Theory, 61(9):5063–5080, Sept 2015.
[63] M. A. Kumar and R. Sundaresan. Minimization problems based
on relative α-entropy II: Reverse projection. IEEE Transactions on
Information Theory, 61(9):5081–5095, Sept 2015.
[64] P. Mitran. On a Markov lemma and typical sequences for polish
alphabets. IEEE Transactions on Information Theory, 61(10):5342–
5356, Oct 2015.
[65] T. Morimoto. Markov processes and the h-theorem. Journal of the
Physical Society of Japan, 18(3):328–331, 1963.
[66] M. Mosonyi and F. Hiai. On the quantum Rényi relative entropies and
related capacity formulas. IEEE Transactions on Information Theory,
57(4):2474–2487, April 2011.
[67] M. Mosonyi and T. Ogawa. Strong converse exponent for classicalquantum channel coding. Communications in Mathematical Physics,
355(1):373–426, Oct 2017.
[68] J. R. Munkres. Topology. Prentice Hall Inc., 2000.
[69] B. Nakiboğlu. The Augustin capacity and center. in preparation.
[70] B. Nakiboğlu. The sphere packing bound for memoryless channels. in
preparation.
[71] B. Nakiboğlu. The sphere packing bound via Augustin’s method. ArXiv
e-prints, 1611.06924v3, 2016.
[72] B. Nakiboğlu. The Augustin center and the sphere packing bound
for memoryless channels.
In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1401–1405, June 2017.
(http://arxiv.org/abs/1701.06610).
[73] M. Ohya, D. Petz, and N. Watanabe. On capacities of quantum
channels. Probability and Mathematical Statistics, 17:179–196, 1997.
[74] Y. Polyanskiy and S. Verdú. Arimoto channel coding converse
and Rényi divergence. In Communication, Control, and Computing
(Allerton), 2010 48th Annual Allerton Conference on, pages 1327 –
1333, Oct 2010.
[75] M. Raginsky. Empirical processes, typical sequences, and coordinated
actions in standard borel spaces. IEEE Transactions on Information
Theory, 59(3):1288–1301, March 2013.
[76] E. Ram and I. Sason. On Rényi entropy power inequalities. IEEE
Transactions on Information Theory, 62(12):6800–6815, Dec 2016.
[77] A. E. Rastegin. Some general properties of unified entropies. Journal
of Statistical Physics, 143(6):1120, Jun 2011.
[78] A. Rényi. On measures of entropy and information. In Proceedings of
the 4th Berkeley Symposium on Mathematics, Statistics and Probability,
pages 547–561, 1960.
[79] Walter Rudin. Principles of Mathematical Analysis. McGraw-Hill,
1976.
[80] B. Ryabko. Encoding of a source with unknown but ordered probabilities. Problems of Informution Transmission, 15(2):134–138, October
1979.
[81] I. Sason. On the Rényi divergence, joint range of relative entropies, and
a channel coding theorem. IEEE Transactions on Information Theory,
62(1):23–34, Jan 2016.
[82] I. Sason and S. Verdú. f -divergence inequalities. IEEE Transactions
on Information Theory, 62(11):5973–6006, Nov 2016.
[83] I. Sason and S. Verdú. Arimoto-Rényi conditional entropy and bayesian
M -ary hypothesis testing. IEEE Transactions on Information Theory,
64(1):4–25, Jan 2018.

[24] I. Csiszár. Arbitrarily varying channels with general alphabets and
states. IEEE Transactions on Information Theory, 38(6):1725–1742,
Nov 1992.
[25] I. Csiszár. Generalized cutoff rates and Rényi’s information measures.
IEEE Transactions on Information Theory, 41(1):26 –34, Jan 1995.
[26] Imre Csiszár and János Körner. Information theory: coding theorems
for discrete memoryless systems. Cambridge University Press, 2011.
[27] M. Dalai. Lower bounds on the probability of error for classical and
classical-quantum channels. IEEE Transactions on Information Theory,
59(12):8027–8056, Dec 2013.
[28] M. Davis. Capacity and cutoff rate for Poisson-type channels. IEEE
Transactions on Information Theory, 26(6):710–715, Nov 1980.
[29] L. D. Davisson and A. Leon-Garcia. A source matching approach to
finding minimax codes. IEEE Transactions on Information Theory,
26(2):166–174, Mar 1980.
[30] Richard M. Dudley. Real analysis and probability, volume 74.
Cambridge University Press, 2002.
[31] T. van Erven and P. Harremoës. Rényi divergence and Kullback-Leibler
divergence. IEEE Transactions on Information Theory, 60(7):3797–
3820, July 2014.
[32] A. A. Fedotov, P. Harremoës, and F. Topsøe. Refinements of Pinsker’s
inequality. IEEE Transactions on Information Theory, 49(6):1491–
1498, June 2003.
[33] S. Fehr and S. Berens. On the conditional Rényi entropy. IEEE
Transactions on Information Theory, 60(11):6801–6810, Nov 2014.
[34] S. L. Fong and V. Y. F. Tan. Strong converse theorems for classes of
multimessage multicast networks: A Rényi divergence approach. IEEE
Transactions on Information Theory, 62(9):4953–4967, Sept 2016.
[35] R. G. Gallager. A simple derivation of the coding theorem and some
applications. IEEE Transactions on Information Theory, 11(1):3–18,
Jan. 1965.
[36] R. G. Gallager. Source coding with side information and universal
coding. Tech. Rep. LIDS-P-937, MIT Lab. Inform. Decision Syst,
September 1979. http://web.mit.edu/gallager/www/papers/paper5.pdf.
[37] Robert G. Gallager. Information theory and reliable communication.
John Wiley & Sons, Inc., 1968.
[38] Robert G. Gallager. Stochastic processes : theory for applications.
Cambridge University Press, 2013.
[39] A. L. Garkavi. The best possible net and the best possible cross-section
of a set in a normed space. Am. Math. Soc., Transl., II. Ser, 39:111–
132, 1964.
[40] G. L. Gilardoni. On the minimum f -divergence for given total
variation. Comptes Rendus Mathematique, 343(11):763 – 766, 2006.
[41] G. L. Gilardoni. Corrigendum to the note “on the minimum f divergence for given total variation”[c. r. acad. sci. paris, ser. i 343
(2006) 763-766]. Comptes Rendus Mathematique, 348(5):299, 2010.
[42] G. L. Gilardoni. On Pinsker’s and Vajda’s type inequalities for
Csiszár’s f -divergences. IEEE Transactions on Information Theory,
56(11):5377–5386, Nov 2010.
[43] A. Guntuboyina, S. Saha, and G. Schiebinger. Sharp inequalities for
f -divergences. IEEE Transactions on Information Theory, 60(1):104–
121, Jan 2014.
[44] A. Gushchin and D. A. Zhdanov. A minimax result for f -divergences.
In From stochastic calculus to mathematical finance. The Shiryaev
Festschrift., pages 287–294. Berlin: Springer, 2006.
[45] E. P. Hanson and N. Datta. Tight uniform continuity bound for a family
of entropies. ArXiv e-prints, 1707.04249v2, 2017.
[46] E. A. Haroutunian. Estimates of the error probability exponent for
a semicontinuous memoryless channel. Problems of Information
Transmission, 4(4):37–48, 1968.
[47] E. A. Haroutunian. Lower bound for error probability in channels with
feedback. Problems of Information Transmission, 13(2):36–44, 1977.
[48] P. Harremoës. private communications, August 2016.
[49] D. Haussler. A general minimax result for relative entropy. IEEE
Transactions on Information Theory, 43(4):1276–1280, Jul 1997.
[50] M. Hayashi and V. Y. F. Tan. Equivocations, exponents and secondorder coding rates under various Rényi information measures. IEEE
Transactions on Information Theory, 63(2):975–1005, Feb 2017.
[51] Masahito Hayashi. Quantum Information Theory: Mathematical Foundation. Graduate Texts in Physics. Springer-Verlag Berlin Heidelberg,
2 edition, 2017.
[52] S. W. Ho and S Verdú. Convexity/concavity of Rényi entropy and
alpha-mutual information. In 2015 IEEE International Symposium on
Information Theory (ISIT), pages 745–749, June 2015.
[53] S. W. Ho and R. W. Yeung. On the discontinuity of the shannon
information measures. IEEE Transactions on Information Theory,
55(12):5362–5374, Dec 2009.

32

[84] I. Sason and S. Verdú. Improved bounds on lossless source coding
and guessing moments via Rényi measures. IEEE Transactions on
Information Theory, 64(99):1–1, 2018.
[85] B. Schumacher and M. D. Westmoreland. Optimal signal ensembles.
Phys. Rev. A, 63:022308, Jan 2001.
[86] C. E. Shannon. A mathematical theory of communication. Bell System
Technical Journal, The, 27(3 and 4):379–423 and 623–656, July and
October 1948.
[87] C. E. Shannon, R. G. Gallager, and E. R. Berlekamp. Lower bounds
to error probability for coding on discrete memoryless channels. I.
Information and Control, 10(1):65–103, 1967.
[88] Claude E Shannon and Warren Weaver. The mathematical theory of
communication. University of Illinois Press, 1949.
[89] N. Sharma and N. A. Warsi. Fundamental bound on the reliability of
quantum information transmission. Phys. Rev. Lett., 110:080501, Feb
2013. (arXiv:1302.5281v1 [quant-ph]).
[90] O. Shayevitz. On Rényi measures and hypothesis testing. In Information Theory Proceedings (ISIT), 2011 IEEE International Symposium
on, pages 894–898, July 2011.
[91] A. Yu Sheverdyaev. Lower bound for error probability in a discrete
memoryless channel with feedback. Problems of Information Transmission, 18(4):5–15, 1982.
[92] Albert N. Shiryaev. Probability. Springer-Verlag, 1995.
[93] R. Sibson. Information radius. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 14:149–160, 1969.
[94] Maurice Sion. On general minimax theorems. Pacific Journal of
Mathematics, 8(1):171–176, 1958.
[95] R. Sundaresan. Guessing under source uncertainty. IEEE Transactions
on Information Theory, 53(1):269–287, Jan 2007.
[96] V. Y. F. Tan and M. Hayashi. Analysis of remaining uncertainties and
exponents under various conditional Rényi entropies. IEEE Transactions on Information Theory, PP(99):1–1, 2018. (arXiv:1605.09551v1
[cs.IT]).
[97] A. Teixeira, A. Matos, and L. Antunes. Conditional Rényi entropies.
IEEE Transactions on Information Theory, 58(7):4273–4277, July
2012.
[98] Bui Van Thanh. Semi-continuous arbitrarily varying channels with general state constraints. ACTA MATHEMATICA VIETNAMICA, 17(1):31–
50, 1992.
[99] M. Tomamichel and M. Hayashi. Operational interpretation of Rényi
information measures via composite hypothesis testing against product
and markov distributions. IEEE Transactions on Information Theory,
64(2):1064–1082, Feb 2018.
[100] F. Topsøe. An information theoretical identity and a problem involving
capacity. Studia Scientiarum Mathematicarum Hungarica, 2:291–292,
1967.
[101] F. Topsøe. A new proof of a result concerning computation of the capacity for a discrete channel. Zeitschrift für Wahrscheinlichkeitstheorie
und Verwandte Gebiete, 22(2):166–168, 1972.
[102] I. Vajda. Note on discrimination information and variation (corresp.).
IEEE Transactions on Information Theory, 16(6):771–773, November
1970.
[103] S. Verdú. α-mutual information. In 2015 Information Theory and
Applications Workshop, 2015.
[104] M. M. Wilde, A. Winter, and D. Yang. Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a
sandwiched Rényi relative entropy. Communications in Mathematical
Physics, 331(2):593–622, Oct 2014.
[105] A. D. Wyner. Capacity and error exponent for the direct detection photon channel. I. IEEE Transactions on Information Theory, 34(6):1449–
1461, Nov 1988.
[106] A. D. Wyner. Capacity and error exponent for the direct detection photon channel. II. IEEE Transactions on Information Theory, 34(6):1462–
1471, Nov 1988.

33

P ROOFS O MITTED F ROM TIT M ANUSCRIPT
P Q
Unless specified explicitly to be otherwise all w , Pw , ∨w , maxw , minw in the appendix stands for the corresponding
expression with the subscript “w : p(w ) > 0”, such as w .

D. Proofs of the Lemmas on the Mean Measure
Proof of Lemma 1.
(1-a) For any w̃ such that p(w̃ ) > 0 and α ∈ ℜ+ , the following inequalities hold ν-a.e.
X
X
_
α  α1
1
dw
p(w ) dw
≤
(p(w̃ )) α ddνw̃ ≤
dν
dν ≤
w

w

Then for any w̃ such that p(w̃ ) > 0, α ∈ (0, ∞], and E ∈ Y,
1

(p(w̃ )) α w̃ (E) ≤ µα,p (E) ≤

X

w

dw
.
w dν

w (E).

Thus for any α ∈ (0, ∞], µα,p (E) = 0 iff w (E) = 0 for all w such that p(w ) > 0. Then µ1,p ∼ µα,p for all α ∈ (0, ∞].
1
Note that kw k = 1 for all w in P(Y, Y), then kµ1,p k = 1 for all p. Furthermore, there exists a w̃ such that p(w̃ ) ≥ |supp(p)|
−1

for all p, then |supp(p)| α ≤ kµα,p k ≤ |supp(p)|.
(1-b) As a result of the Hölder’s inequality,

µ0,p (E) =

Z Y

w

E

≤
=

Y Z

Y

w

w

E


dw p(w)
dν

ν(dy)
p(w)

dw
dν ν(dy)

(w (E))

p(w)

.

Then µ0,p (E) = 0 whenever w (E) = 0 and µ0,p ≺w for all w such that p(w ) > 0. Since w (Y) = 1 for all w in P(Y, Y),
kµ0,p k = µ0,p (Y) ≤ 1.
Proof of Lemma 2.
dw
for all w such that
(2-a) Let us establish the expressions for πα,p (y) and p[α] (w |y), first. Note that p[1] (w |y) = p(w ) dµ
1,p
p(w ) > 0 by the definition of p[α] (w |y) given in (10). Then the expressions for πα,p (y) follows from the definitions of
dµα,p
and πα,p given in (7) and (9), respectively.
dν
On the other hand, w ≺µ1,p for all w such that p(w ) > 0 by definition and µα,p ∼ µ1,p by Lemma 1. Thus,
dw
dµα,p

=
=

dµ1,p dw
dµα,p dµ1,p
1 p[1] (w|y)
πα,p p(w)

∀w : p(w ) > 0.

Then the expression for p[α] (w |y) follows from its definition given in (10).
In order to bound πα,p from below and from above µ1,p -a.e. we use the expression for πα,p we have just derived. Note
1
P
α /α
≥ 1 for α ∈ (0, 1]. Then
that
w p[1] (w |y)
X
1/α X
1/α
≥
p[1] (w |y)α p(w )1−α
p[1] (w |y)α δ 1−α
w

w

≥δ

1−α
α

.

On the other hand, as a result of the Hölder’s inequality we have
X
1/α X
 X
 1−α
α
≤
p[1] (w |y)α p(w )1−α
p[1] (w |y)
p(w )
w

w

w

= 1.

1−α

Thus δ α ≤ πα,p ≤ 1 for α ∈ (0, 1].
1
P
α /α
≤ 1, which is valid for all α in
In order to obtain the bound for α in [1, ∞), we use the identity
w p[1] (w |y)
[1, ∞), together with the reverse Hölder’s inequality.
p (w|y)
p (w|y)
(2-b) [1]p(w) is a non-negative real number for all w such that p(w ) > 0 and [1]p(w) is positive at least for one such w .
Then expression for πα,p given in part (a) is a smooth function42 of α on ℜ+ . Identities for the derivatives of πα,p follow
from the chain rule and elementary rules of differentiation.
P
1
α α is a smooth function of α on ℜ ,
any positive integer K, non-negative real numbers aı and bı for ı in {1, 2, . . . , K}, the function ( K
+
ı=1 aı bı )
because the exponential function and the logarithm are smooth functions and composition, sum, and product of smooth functions are also smooth.
42 For

34

(2-c) As a result of the Hölder’s inequality we have,
παβ ,p

αβ

=
≤

X

w

X

p(w )
w



p(w )

p[1] (w|y)
p(w)



α1 β 

p[1] (w|y)
p(w)

p[1] (w|y)
p(w)

α1 β X

w

α0 (1−β)
p(w )

= (πα1 ,p )α1 β (πα0 ,p )α0 (1−β)



p[1] (w|y)
p(w)

α0 (1−β)

p[1] (w|y) α1
p(w) )

Furthermore, the inequality is strict unless there exists a γ such that p(w )(

p[1] (w|y) α0
p(w) )
p (w̃ |y)
p[1] (w|y)
> [1]p(w̃ )
p(w)

= γp(w )(

for all w

> 0.
such that p[1] (w |y) > 0. Thus inequality is strict iff there exist w , w̃ ∈ supp(p) such that
(2-d) The continuity of πα,p in α on ℜ+ follows from the smoothness of πα,p established in part (b). In order to show the
continuity on [0, ∞] we need to establish the continuity at zero and at infinity. Note that x α is a smooth function of α
for any x ∈ ℜ+ and weighted sums of smooth functions are also smooth. Thus (πα,p )α (y) is a smooth function of α and
we can use L’Hospital’s rule [79, Thm. 5.13] for calculating the limits of πα,p (y) at zero and infinity:
lim

α→0

lim

α→∞

X

w

X

w

p(w )
p(w )





p[1] (w|y)
p(w)
p[1] (w|y)
p(w)

α  α1
α  α1

=

Y p

[1] (w|y)

w

= maxw

p(w)

p[1] (w|y)
p(w)

p(w)

(139)
(140)

Thus limα→0 πα,p (y) = π0,p (y) and limα→∞ π∞,p (y) = π∞,p (y) hold µ1,p almost everywhere. Thus πα,p (y) is
continuous on [0, ∞].
On the other hand, using the Jensen’s inequality and the convexity of the function ln 1/x we get,
X
π
′
p(w )
πα,p
≥ − αα,p
2 ln
w:p[1] (w|y)>0

≥ 0.

(141)

′
Since the function ln 1/x is strictly convex, the first inequality is strict and πα,p
(y) is positive unless p(w ) = p[1] (w |y)
for all w such that p(w ) > 0. Thus πα,p (y) is monotone increasing in α unless p(w ) = p[1] (w |y) for all w such that
p(w ) > 0. Boundedness is already established in part (a).

Proof of Lemma 3.
(3-a) For all y ∈ Y —except for a µ1,p -measure zero set— density πα,p is a non-negative function of α continuous on [0, ∞]
by Lemma 2-(d). Thus for any sequence {αı } such that limı→∞ αı = α we have limı→∞ παı ,p = πα,p µ1,p -a.e. Since
παı ,p ≤ π∞,p by Lemma 2-(d) and π∞,p ≤ minw1p(w) by Lemma 2-(a), we can apply the dominated convergence theorem
L1 (µ1,p )

[8, 2.8.1]. Thus {παı ,p } −−−−−→ πα,p , i.e.
lim

ı→∞

Z

|παı ,p − πα,p |µ1,p (dy) = 0.

Then {µαı ,p } converges to µα,p in the total variation topology, for any sequence {αı } such that limı→∞ αı = α. Then
+
µα,p is a continuous function of α from [0, ∞] with its usual topology to M0 (Y, Y) with the total variation topology
because [0, ∞] with its usual topology is a metrizable space, see [68, Thm. 21.3].
′
′
(3-b) For µ′α,p defined in (11) to be a finite measure, πα,p
should be a non-negative µ1,p -integrable function. The density πα,p
′
′
is non-negative by (141). By the expression for πα,p given Lemma 2-(b) and the bound for πα,p given in Lemma 2-(a)
we have
X
p (w|y)
π
′
p[α] (w |y) ln [α]
πα,p
= αα,p
2
p(w)
≤

=

w
πα,p
1
α2 ln minw p(w) .
1
1
1
α2 minw p(w) ln minw p(w)
+

′
Thus πα,p
is bounded and µ′α,p is a finite measure, i.e. µ′α,p ∈ M0 (Y, Y). We can apply the dominated convergence
theorem [8, 2.8.1] for µ′α,p as we did for µα,p in part (a) in order to establish the continuity of µ′α,p as a function of α.
d
′
′
Furthermore, dα
µα,p (E) α=φ = µ′φ,p (E) follows from the boundedness of πα,p
and the definitions of µ′α,p and πα,p
by
[8, Cor. 2.8.7.(ii)] for X = E. One can apply the Tonelli-Fubini theorem [30, 4.4.5] to obtain an equivalent result, instead
of invoking [8, Cor. 2.8.7.(ii)].

35

′′
(3-c) For µ′′α,p defined in (12) to be a finite signed measure, πα,p
should be a µ1,p -integrable function. By the expression for
′′
πα,p given in Lemma 2-(b) we have





2
′′
1
1
4
1+α
2
(142)
− α3 ln minw p(w) πα,p ≤ πα,p ≤ α4 ln minw p(w) + e2 α3 πα,p

d ′
The proof of the continuity is similar to the corresponding proofs in parts (a) and (b). The identity dα
µα,p (E) α=φ =
′′
µφ,p (E) follows from (142) by applying [8, Cor. 2.8.7.(ii)] for X = E.
(3-d) For any β ∈ [0, 1] and α0 , α1 ∈ ℜ+ let αβ be αβ = βα1 + (1 − β)α0 . Then as a result of the Hölder’s inequality,
Z
(1−β)α0
βα1
(1−β)α0
βα1
(143)
(πα1 ,p ) αβ (πα0 ,p ) αβ µ1,p (dy) ≤ (kµα1 ,p k) αβ (kµα0 ,p k) αβ .

On the other hand by Lemma 2-(c)

βα1

παβ ,p ≤ (πα1 ,p ) αβ (πα0 ,p )

α

(1−β)α0
αβ

.

(144)

Then the log-convexity of kµα,p k as a function of α follows from (143) and (144).
α
If µ1,p (∪γ≥1 A(p, γ)) < 1, then the log-convexity of kµα,p k is strict because the inequality in (144) is strict for y’s
α−1
that are not in ∪γ≥1A(p, γ) by Lemma 2-(c). For y ∈ A(p, γ), the inequality in (144) is an equality and πα,p = γ α
α
for all α. Consequently if µ1,p (∪γ≥1 A(p, γ)) = 1, then the log-convexity of kµα,p k is strict iff the inequality in (143)
is strict. But if µ1,p (∪γ≥1 A(p, γ)) = 1 the Hölder’s inequality in (143) is strict unless there exists a γ ≥ 1 such that
µ1,p (A(p, γ)) = 1.
We proceed with calculating the limit at zero. As a result of the expression for πα,p given in part (a) we have,
X
 α−1
 1
X

α
p (w|y) α α
p(w)
where p[0] (w |y) = P
πα,p =
p[0] (w |y) p[1]
p(w )
p(w̃ ) .
[0] (w|y)
w:p[1] (w|y)>0

w

w̃ :p[1] (w̃ |y )>0

Then using L’Hospital’s rule [79, Thm. 5.13] for calculating limits and the Hölder’s inequality we get,
X
 α−1
p[1] (w|y)
P
α
p[0] (w|y) ln p (w|y)
[0]
µ1,p − a.e.
p(w )
lim
πα,p = e w
w:p[1] (w|y)>0

α→0

X

w:p[1] (w|y)>0

 α−1
α
πα,p ≤ 1
p(w )

∀α ∈ (0, 1), µ1,p − a.e.

(145)
(146)

P
The sum w:p[1] (w|y)>0 p(w ) is a simple function of y, i.e. its range is a finite set, because supp(p) has a finite number
of distinct subsets. Thus the essential supremum is the maximum value of the sum with positive probability. Therefore
X

X
µ1,p
p(w ).
(147)
p(w ) = ψ
>0
where
ψ = ess sup
w:p[1] (w|y)>0

µ1,p

w:p[1] (w|y)>0

Then using (145) we get
lim ψ

α−1
α

α→0

πα,p = 1{Pw:p

[1]

e
(w|y )>0 p(w)=ψ}

P

w

p[1] (w|y)
p[0] (w|y) ln p (w|y)
[0]

µ1,p -a.e.

α−1

On the other hand ψ α πα,p ≤ 1 for all α ∈ (0, 1), µ1,p −a.e. by (146) and the definition of ψ given in (147). Thus we
can apply the dominated convergence theorem [8, 2.8.1]:
Z
p[1] (w|y)
P
α−1
p[0] (w|y) ln p (w|y)
[0]
µ1,p (dy) = 0.
(148)
ψ α πα,p − 1{Pw:p (w|y )>0 p(w)=ψ} e w
lim
α→0

[1]

Consequently,
Z
1

α α
(α−1)
kπα,p k
lim ψ
= 1{Pw:p

α→0

[1]

e
(w|y )>0 p(w)=ψ}

P

w

p[1] (w|y)
p[0] (w|y) ln p (w|y)
[0]

µ1,p (dy).

(149)

The right hand side of (149) is a real number between 0 and 1 by (147). Thus we have,
lim ψ α−1 kπα,p kα = 1.

α→0

(150)

(3-e) kµα,p k ≤ |supp(p)| by Lemma 1-(a). The continuity of kµα,p k in α is implied by the continuity of µα,p in α for the
+
+
total variation topology on M0 (Y, Y), proved in part (a). Furthermore, kµα,p k = µα,p (Y) because µα,p ∈ M0 (Y, Y) by
d
part (a). In addition dα
µα,p (Y) ≥ 0 by part (b). Hence kµα,p k is a nondecreasing function of α.
36

Let Ep be Ep = {y : p[1] (·|y) 6= p(·)}. Then ∀y ∈ Ep , p[α] (·|y) 6= p(·) and πα,p is monotone increasing in α on ℜ≥0 . On
the other hand, if there are two or more distinct w ’s in supp(p), then µ1,p (Ep ) R> 0. Thus kµα,p k is monotone increasing
if there exist w , w
e ∈ supp(p) such that w 6= w
e . Else πα,p = 1 thus kµα,p k = πα,p µ1,p (dy) = 1 for all α ∈ [0, ∞].

Proof of Lemma 4.
(4-a) Let us start with α = 0 case. Since the weighted arithmetic mean of any two non-negative real numbers is greater than
their weighted geometric mean, for any reference measure ν for µ1,p1 and µ1,p2 we have,
 


dµ0,p2
dµ0,p1 β dµ0,p2 1−β
dµ0,p1
+ (1 − β) dν
≥
β dν
dν
dν
=

For any α ∈ (0, 1] the function x
the Jensen’s inequality we have,
β

dµα,p1
dν

1
α

dµ0,pβ
dν

.

is convex in x . Then for any reference measure ν for µα,p1 and µα,p2 as a result of

+ (1 − β)

dµα,p2
dν

≥
=

dµ

X


dw α
dν

(βp1 (w ) + (1 − β)p2 (w ))

w
dµα,pβ
dν .

1/α

dµ

kµα,p k is convex in p because dνα,p is convex in p and dνα,p is non-negative.
1
(4-b) For α ∈ [1, ∞) the function x α is concave in x . Thus the inequalities are reversed. Hence both the Radon-Nikodym
dµα,p
derivative dν and the norm kµα,p k are concave in p.
dµ∞,p
For any reference measure ν for µ∞,p1 and µ∞,p2 by the definition of dν
given in (7), we have
β

dµ∞,p1
dν

dµ

+ (1 − β)

dµ∞,p2
dν
dµ

≤

dµ∞,pβ
dν

.

∞,p
∞,p
is concave in p and dν
is non-negative.
kµ∞,p k is concave in p because dν
(4-c) Identities are confirmed using the definitions of s∧ , s1 and s2 by substitution. On the other hand,

kp1 − p2 k = kp1 ∨ p2 k − kp1 ∧ p2 k
= 2 − 2kp1 ∧ p2 k.

Hence s∧ ∈ P(P(Y, Y)). Using the fist identity together with s∧ ∈ P(P(Y, Y)) and p1 ∈ P(P(Y, Y)) we get s1 ∈
P(P(Y, Y)). Similarly s2 ∈ P(P(Y, Y)) follows from the second identity, s∧ ∈ P(P(Y, Y)) and p1 ∈ P(P(Y, Y)).
1k
. For any reference measure ν for µα,p1 and µα,p2 and α ∈ (0, 1],
(4-d) Let δ be δ = kp2 −p
2
i1
i1
h
h
dµα,p1
dµα,p2
dµα,s1 α /α
dµα,s2 α /α
dµα,s∧ α
dµα,s∧ α
− dν
= (1 − δ)( dν
) + δ( dν
)
) + δ( dν
)
− (1 − δ)( dν
dν
i1
h
1 dµ
dµα,s1 α /α
dµα,s∧ α
α,s∧
− (1 − δ) α dν
) + δ( dν
)
≤ (1 − δ)( dν
i
h
1
dµα,s1
dµα,s∧
dµα,s∧
− (1 − δ) /α dν
+ δ dν
.
≤ (1 − δ) dν
1

where the last inequality follows from the Jensen’s inequality and the convexity of x α in x for α ∈ (0, 1].
dµα,p2
dµα,p1
We bound dν
− dν
in a similarly way. Using these two bounds we can bound kµα,p1 − µα,p2 k as follows
Z
Z
dµα,p2
dµα,p1
dµα,p1
dµα,p2
kµα,p1 − µα,p2 k = dµα,p dµα,p ( dν
− dν
)ν(dy ) + dµα,p dµα,p ( dν
− dν
)ν(dy)
1

>

2

2

>

1

dν
dν
dν
h dν
i
1
α
≤ 2 1 − δ − (1 − δ) kµα,s∧ k + δkµα,s1 k + δkµα,s2 k
i
h
1
≤ 2 1 − (1 − δ) α

≤

2
α δ.

(4-e) One can confirm using the derivative test that for any α ∈ [1, ∞), x0 ≥ 0 and x1 ≥ x2 ≥ 0 we have
1

1

1

[(1 − δ)x0α + δx1α ] α − [(1 − δ)x0α + δx2α ] α ≤ δ α (x1 − x2 ).
Then for any reference measure ν for µα,p1 and µα,p2 we have
i1
i1
h
h
dµα,p2
dµα,s1 α /α
dµα,s2 α /α
dµα,p1
dµα,s∧ α
dµα,s∧ α
−
(1
−
δ)(
−
=
(1
−
δ)(
)
+
δ(
)
)
+
δ(
)
dν
dν
dν
dν
dν
dν
h
i
1
dµα,s1
dµα,s2
.
≤ δα
− dν
dν
37

dµ

dµ

dµ

dµ

dµ

dµ

α,p1
α,p1
α,p2
α,s1
α,s2
α,p2
− dν
in a similarly way. On the other hand dν
≥ dν
iff dν
≥ dν
. Thus we can
We can bound dν
dµα,p1
dµα,p2
dµα,p2
dµα,p1
− dν
and dν
− dν
:
bound kµα,p1 − µα,p2 k using the bounds on dν
Z
Z
dµα,p2
dµα,p1
dµα,p1
dµα,p2
− dν
)ν(dy )
kµα,p1 − µα,p2 k = dµα,p dµα,p ( dν − dν )ν(dy ) + dµα,p dµα,p ( dν
1

1

≤ δα
1

dν
Z

>

2

2

dν

dν

dµα,s1 dµα,s2
dν > dν

(

dµα,s1
dν

−

dµα,s2
dν

1

)ν(dy ) + δ α

Z

>

1

dν

dµα,s2 dµα,s1
dν > dν

(

dµα,s2
dν

−

dµα,s1
dν

)ν(dy )

= δ α kµα,s1 − µα,s2 k.

E. Proofs of the Lemmas on the Rényi Information
Proof of Lemma 5. I∞ (α;W) ≤ ln |supp(p)| because kµ∞,p k ≤ |supp(p)| by Lemma 3-(e).
limα↓0 Iα (p;W) = I0 (p;W) follows from Lemma 3-(d) and the definition of Iα (p;W) given in (13).
limα↑∞ Iα (p;W) = I∞ (p;W) follows from the continuity of kµα,p k as a function of α at infinity, i.e. Lemma 3-(e), and the
definition of Iα (p;W) given in (13).
d
d
kµα,p k = µ′α,p and dα
µ′α,p = µ′′α,p (Y) because
Both kµα,p k and µ′α,p are continuously differentiable on ℜ+ , dα
of Lemma 3-(a,b,c). Then as a result of its definition given in (13), Iα (p;W) is continuously differentiable in α on (0, 1) and
(1, ∞). The expression for the derivative for α 6= 1 given in (16) follows from the chain rule.
In order to extend the continuous differentiability to α = 1, first we establish that Iα (p;W) is continuous at α = 1. As a result
α
of L’Hospital’s rule [79, Thm. 5.13] and Lemma 3-(b) lim α−1
ln kµα,p k = µ′1,p . On the other hand µ′1,p = I1 (p;W) as
α→1
a result of (11), Lemma 2-(b) and the definition of I1 (p;W). Thus Iα (p;W) is continuous at α = 1. Then,
h
i
′
d
1
α
I
(p;W)
=
lim
ln
kµ
k
.
µ
−
α
α,p
1,p
dα
1−α
α−1
α=1
α→1

kµα,p k and µ′α,p
d
µ′α,p
identity dα

are continuously differentiable by Lemma 3-(b,c). Then using L’Hospital’s rule [79, Thm. 5.13] and the
= µ′′α,p (Y) we get
h
h
i
i
2
1
α
lim 1−α
ln kµα,p k = 21 µ′′1,p (Y) + 2 µ′1,p − µ′1,p
µ′1,p − α−1
.
α→1

Hence Iα (p;W) is differentiable at α = 1 and its derivative at α = 1 is the one given in (16). Finally, in order to show that
d
dα Iα (p;W) is continuous at α = 1 we apply L’Hospital’s rule [79, Thm. 5.13] to confirm,
d
Iα (p;W)
α→1 dα

lim

α(α−1)kµ′α,p k−kµα,p k ln kµα,p k
= lim
kµα,p k(α−1)2
α→1
h
i
2
= 21 µ′′1,p (Y) + 2 µ′1,p − µ′1,p
.

As a function α on ℜ+ , α ln kµα,p k is convex by Lemma 3-(d) and differentiable by Lemma 3-(b). Then α ln kµα,p k has a
tangent at each α ∈ ℜ+ and it lays above all of its tangents, i.e. for all α, η ∈ ℜ+ such that α 6= η,


αkµ′α,p k
(151)
η ln kµη,p k ≥ α ln kµα,p k + ln kµα,p k + kµα,p k (η − α).

Then for all α, η ∈ ℜ+ such that α 6= η we have

′
α kµα,p k
α−η kµα,p k

+

η
(α−η)2

kµ

k

η,p
ln kµα,p
k ≥ 0.

(152)

d
If we apply the above inequality at η = 1 we can conclude, using (16), that dα
Iα (p;W) ≥ 0 for α 6= 1. For α = 1 using
Lemma 2-(b) and Lemma 3-(c) we get
Z X
2

p (w|y)
1
d
I
(p;W)
=
p[1] (w |y) ln [1]p(w) − I1 (p;W) µ1,p (dy)
dα α
2
α=1
w

≥ 0.

(153)

d
Thus dα
Iα (p;W) is non-negativeP
for all α ∈ ℜ+ and Iα (p;W) is a nondecreasing function of α. Then Iα (p;W) is non-negative
as well because I0 (α;W) ≥ − ln w p(w ) = 0 and limα↓0 Iα (p;W) = I0 (α;W).
α−1
If µ1,p (A(p, γ)) = 1 for a γ, then kµα,p k = γ α for all α ∈ ℜ+ and Iα (p;W) = ln γ for all α ∈ [0, ∞], because
α−1
πα,p = γ α for all y ∈ A(p, γ).
If there does not exist a γ such that µ1,p (A(p, γ)) = 1, then the convexity of α ln kµα,p k is strict by Lemma 3-(d) and the
p (w|y)
d
variance of the random variable ln [1]p(w) is positive. Thus the inequalities (151), (152), and (153) are strict and dα
Iα (p;W)
is positive for all α ∈ ℜ+ .

38

Proof of Lemma 6.
+
α
ln(·) : ℜ+ → ℜ are continuous
(6-a) Let us start with the values of α in (0, 1). Recall that k·k : M (Y, Y) → ℜ+ and α−1
functions and the composition of two continuous functions is a continuous function, [68, Thm. 18.2.c]. Furthermore, the
function kµα,p k is continuous in p on P(P(Y, Y)), —and hence on P(W)— for α ∈ (0, 1) by Lemma 4-(d). Thus Iα (p;W)
is continuous in p on P(W) for α ∈ (0, 1).
For any p1 , p2 ∈ P(W) and β ∈ [0, 1] let pβ = βp1 + (1 − β)p2 . Recall that kµα,p k is convex in p for α ∈ (0, 1) by
Lemma 4-(a). Then by the definition of Iα (p;W) given in (13) we have
Iα (pβ ;W) ≥

≥

α
α−1
α
α−1

ln (βkµα,p1 k + (1 − β)kµα,p2 k)
ln (kµα,p1 k ∨ kµα,p2 k)

≥ Iα (p1 ;W) ∧ Iα (p2 ;W)

Thus Rényi information is continuous and quasi-concave in p for α ∈ (0, 1).
For α = 0 case, first note that e−I0(p1 ;W) − e−I0(p2 ;W) ≤ kp1 − p2 k. Thus e−I0(p;W) is continuous in p. Since − ln x is
continuous on ℜ+ , I0 (p;W) is continuous in p. In order to prove that I0 (p;W) is quasi-concave, note that for any β ∈ (0, 1)
and p1 , p2 ∈ P(W) we have,
 X

X
p1 (w ) + (1 − β)
I0 (pβ ;W) = − ln ess sup β
p2 (w )
µ1,pβ

"

≥ − ln ess sup
µ1,p1

w:p1 (w|y)>0

X

w:p1 (w|y)>0

= I0 (p1 ;W) ∧ I0 (p2 ;W) .

w:p2 (w|y)>0

X
_
p1 (w )
ess sup

w:p2 (w|y)>0

µ1,p2

#
p2 (w )

(6-b) For any p1 , p2 ∈ P(W) and β ∈ [0, 1] let pβ = βp1 + (1 − β)p2 . Recall that kµα,p k is concave in p for α ∈ (1, ∞] by
Lemma 4-(b). Then by the definition of Iα (p;W) we have
Iα (pβ ;W) ≥
≥

α
α−1 ln (βkµα,p1 k + (1 − β)kµα,p2 k)
α
α
β α−1
ln kµα,p1 k + (1 − β) α−1
ln kµα,p2 k

= βIα (p1 ;W) + (1 − β)Iα (p2 ;W)

where the second inequality follows from the Jensen’s inequality and the concavity of the logarithm function.
For α = 1 case, note that as a result of the definition of Iα (p;W) we have
Z h
i
dµ1,p1
dµ1,p2
dµ1,p2
dµ1,p1
ln dµ1,p
+ (1 − β) dµ1,p
ln dµ1,p
µ1,pβ (dy)
I1 (pβ ;W) = βI1 (p1 ;W) + (1 − β)I1 (p2 ;W) +
β dµ1,p
β

≥ βI1 (p1 ;W) + (1 − β)I1 (p2 ;W)
dµ

β

β

β

dµ

1,p1
1,p2
where the inequality follows from β dµ1,p
+ (1 − β) dµ1,p
= 1, the convexity of the function x ln x and the Jensen’s
β
β
inequality.

F. Proof of the Lemma on the Rényi Mean
Proof of Lemma 14. For α = 0, as a result of the definition of the order zero Rényi information given in (13) and the definition
of the order zero Rényi divergence given in (19) we have
Z X
p(w ) dq
D0 (p⊛Wk p ⊗ q) = − ln
dν 1{p (w|y) dµ1,p >0} ν(dy )
w
[1]
dν
P
Z
w:p[1] (w|y )>0 p(w)
dq
P
= I0 (p;W) − ln ess sup
p(w) 1 dµ1,p
dν ν(dy).
µ1,p

{ dν >0}

w:p[1] (w|y )>0

Then the definition of q0,p given in (21) implies (23) and (24).
For α ∈ (0, ∞], (23) follows from the definitions of the Rényi information, divergence, and mean given in (13), (19) (21)
by substitution. Using (22) and (23) we get,
Dα (p⊛Wk p ⊗ q) = Iα (p;W) + Dα (qα,p k q)

∀α ∈ (0, ∞].

(154)

On the other hand qα,p is a probability measure by definition. Then (24) and uniqueness of Rényi mean as the minimizer
follow from (23), (154), and Lemma 10.
The following identity and (24) imply (25).
+

Dα (p⊛Wk p ⊗ q) = Dα (µα,p k q)

∀p ∈ P(W), q ∈ M (Y, Y), α ∈ (0, ∞] \ {1}.

39

G. The Ergodic Theorem and the Rényi Capacity
For W[f ] described in Example 5 we have Dα (w k l ) = Dα (wf k l ) for all w ∈ W[f ] where l is the Lebesgue measure. Thus
by (33) of Theorem 1 we have
Cα,W[f ] ≤ Dα (wf k l ) .
We prove the reverse inequality, Cα,W[f ] ≥ Dα (wf k l ), using the Birkoff-Khinchin ergodic theorem [30, 8.4.1]. In particular,
we show that there exists a sequence of priors {pı }ı∈Z+ such that43 limı→∞ Iα (pı ;W[f ]) ≥ Dα (wf k l ) for all α ∈ (0, ∞].
For any κ ∈ Z and x ∈ ℜ let Tκx be the transformation resulting from κ successive applications of Tx . As a result of the
definition of Tx given in (63), Tκx = Tκx for any κ ∈ Z and x ∈ ℜ. For any g ∈ L1 (l ), x ∈ ℜ and ı ∈ Z+ let g ıx be
Xı−1
g ıx (y) , 1ı
g ◦ Tκx (y)
κ=0
Xı−1
g(y − κx − ⌊y − κx ⌋).
= 1ı
κ=0

For any x ∈ ℜ, the transformation Tx isR measure preserving for the measure space (Y, Y, l ); if in addition x is irrational,
then Tx is ergodic. Hence g ıx converges to g(y)dy l −a.e. for any g ∈ L1 (l ) and x ∈ ℜ \ Q , by the Birkoff-Khinchin Ergodic
theorem [30, 8.4.1]:
Z
ı l−a.e.
g x −−−−→ g(y)dy
∀g ∈ L1 (l ) and ∀x ∈ ℜ \ Q .
(155)

Let x be an irrational number that will be fixed for the rest of the proof. For any ı ∈ Z+ , let pı be the prior that has equal
probability mass on each probability measure corresponding to a f ◦ Tκx for some κ ∈ {0, . . . , (ı − 1)}. Then
1/α
 X
ı−1
dµα,pı
α
κ
1
(f ◦ Tx )(y)
dl (y) =
ı
κ=0

=

X
ı−1

1 α
f
κ=0 ı

y−

κx
ı

− ⌊y −

κx
ı ⌋

1
 /α

∀α ∈ ℜ+ .

For α ∈ ℜ+ \ {1}, we calculate the limit limı→∞ Iα (pı ;W[f ]) by calculating the limit limı→∞ kµα,pı k. For α = 1 and α = ∞
the result follows from continuity arguments.
R
R
α
(a) α ∈ (0, 1) case: f α dy ≤
f (y)dy = 1 by the Jensen’s inequality. Hence f α ∈ L1 (l ) as a result of (155) we have
Z
1/α
Z
α

l−a.e.
dµα,pı l−a.e.
dµα,pı
α
α
−
−
−
−
→
−
−
−
−
→
f
(y)dy
⇒
f
(y)dy
.
dl
dl

For any ǫ > 0 there exists a δ > 0 such that if l (E) < δ for a E ∈ Y, then wf (E) < ǫ, because wf ≺l . Since l is
invariant under translations and W[f ] is the set of all mod one translations of wf , µ1,p (E) < ǫ whenever l (E) < δ, as
dµα,pı
well. Then {µα,p : p ∈ P(W[f ] ), α ∈ (0, 1]}≺uni l and { dl
}ı∈Z+ is uniformly l −integrable because µα,p (E) is a
nondecreasing function of α for all E ∈ Y by Lemma 3-(b). Since almost everywhere convergence implies convergence in
dµα,pı
measure by [8, Thm. 2.2.3], using Lebesgue-Vitali convergence theorem [8, 4.5.4], we can conclude that dl
converges
1
R α
 α1
R

R
 α1
dµα,pı L1 (l)
α
α
α
to
f (y)dy
f (y)dy . Then limı→∞ kµα,pı k =
f (y)dy . Using the
in L1 (l ), as well: dl −−−→
definition of Rényi information given in (13) we get
Z

1
limı→∞ Iα (pı ;W[f ]) = α−1
ln
f α (y)dy
= Dα (wf k l )

∀α ∈ (0, 1).

(b) α = 1 case: The Rényi information is a nondecreasing function of the order by Lemma 5. Then
lim inf ı→∞ I1 (pı ;W[f ]) ≥ lim inf ı→∞ Iα (pı ;W[f ])
= Dα (wf k l )

∀α ∈ (0, 1).

Since the Rényi divergence is a nondecreasing and lower semicontinuous function of the order by Lemma 7, we have
lim inf ı→∞ I1 (pı ;W[f ]) ≥ limα↑1 Dα (wf k l )
(c) α ∈ (1, ∞) case: We analyze the finite
43 Finding

R

= D1 (wf k l ) .

f α (y)dy and infinite

R

f α (y)dy cases separately.


a different sequence of priors for each order α in (0, ∞] would have been sufficient for establishing Cα,W[f ] ≥ Dα wf l . The existence of
a sequence of priors {pı }ı∈Z+ such that limı→∞ Iα (pı ;W[f ]) = Cα,W[f ] for all orders α in ℜ+ allows us to assert the convexity of (α − 1)Cα,W[f ] in
α on ℜ+ , rather than just [1, ∞).

40

•

R α
1/α
R
dµα,pı l
→
−
f (y)dy
by (155) because almost everywhere convergence
If f α (y)dy < ∞, then f α ∈ L1 (l ) and dl
implies convergence in measure by [8, Thm. 2.2.3]. On the other hand, as a result of the concavity of the function
1
z α in z for α ∈ (1, ∞) and the Jensen’s inequality we have
!1/α
Xı−1 Z
α
1
f (y)dy
µα,pı (E) ≤ ı
.
κ=0

Tκ
xE

dµ

α,pı
follows from the translational invariance of l and the l −integrability of
Then the uniform l −integrability of dl
α
f following an argument similar to the one we have for α ∈ (0, 1) case. Thus using Lebesgue-Vitali convergence
theorem [8, 4.5.4] and the definition of Rényi information exactly the same way we did for α ∈ (0, 1) case we get
Z
[f ]
limı→∞ Iα (pı ;W ) = Dα (wf k l )
if
f α (y)dy < ∞.

•

If

R

f α dy = ∞, then we repeat the above analysis for f ∧ γ for a γ ∈ ℜ+ instead of f . As a result we get,
Z

α
1
[f ]
lim inf ı→∞ Iα (pı ;W ) ≥ α−1 ln
(f (y) ∧ γ) dy
∀γ ∈ ℜ+

Note that as γ ↑ ∞,

R

(f (y) ∧ γ)α dy ↑

R

f α (y)dy . Thus

limı→∞ Iα (pı ;W ) = ∞

if

[f ]

Z

f α (y)dy = ∞.

(d) α = ∞ case: Repeat the analysis for α = 1 case by replacing α = 1 and (0, 1) by α = ∞ and (1, ∞).
We have used the ergodic theorem [30, 8.4.1] in order to be able to conduct our analysis for arbitrary measurable functions. If
we restrict our attention to functions that are bounded and continuous at all but finite number of points, we can choose pı to be
the priors that have 2−ı probability mass on each probability measure corresponding to a f ◦ Tκ2−ı for κ ∈ {0, 1, . . . , (2ı − 1)}.
R α

dµα,pı α l−a.e.
) −−−−→
f (y)dy is a result of Riemann integrability of f α rather than the ergodicity.
Then the identity ( dl
We have used the Lebesgue-Vitali convergence theorem [8, 4.5.4] instead of the dominated convergence theorem [8, 2.8.1].
That is a matter of taste; one can prove the same statements using the dominated convergence theorem. First, do the analysis
for f˜ = f ∧ γ, and then take the limit as γ diverges to infinity.

41

