Non-Asymptotic Bounds and a General Formula for
the Rate-Distortion Region of the Successive Refinement Problem ∗
Tetsunao Matsuta†

arXiv:1802.07458v1 [] 21 Feb 2018

source symbol
X

encoder 1

✲ f1
encoder 2

✲ f2

decoder 1
✲ ϕ1

reprod. symbol 1

decoder 2

reprod. symbol 2

✲ϕ
✲ 2

Tomohiko Uyematsu‡
rate-distortion region. Since a codeword is used in both decoders, we cannot always optimize rates like the case where
each codeword is used for each reconstruction separately. However, there are some cases where we can achieve the optimum
rates. Necessary and sufficient conditions for such cases were
independently given by Koshelev [3], [4] and Equitz and Cover
[5]. The complete characterization of the rate-distortion region
for discrete stationary memoryless sources was given by Rimoldi
[6]. Yamamoto [7] also gave the rate-distortion region as a special case of a more general coding problem. Later, Effros [8]
characterized the rate-distortion region for discrete stationary
ergodic and non-ergodic sources.
Recently, the asymptotic analysis of the second-order rates to
the blocklength becomes an active target of the study. Especially, for the successive refinement problem, No et al. [9] and
Zhou et al. [10] gave a lot of results to the set of second-order
rates for discrete and Gaussian stationary memoryless sources.
No et al. [9] considered separate excess-distortion criteria such
that a probability that a distortion exceeds a given distortion
level is less than a given probability level separately for each
reconstruction. On the other hand, Zhou et al. [10] considered
the joint excess-distortion criterion such that a probability that
either of distortions exceeds a given distortion level is less than
a given probability level. Although they also gave several nonasymptotic bounds on the set of pairs of rates, they mainly focus
on the asymptotic behavior of the set.
On the other hand, in this paper, we consider non-asymptotic
bounds on pairs of rates in finite blocklengths. Especially, since
a rate is easily calculated by a number of codewords, we focus on
pairs of two numbers of codewords. Although we adopt separate
excess-distortion criteria, our result can be easily applied to the
joint excess-distortion criterion. We give inner and outer bounds
on pairs of numbers of codewords. These bounds are characterized by using the smooth max Rényi divergence introduced by
Warsi [11]. For the point-to-point lossy source coding problem,
we also used the smooth max Rényi divergence to characterize
the rate-distortion function which is the minimum rate when
the blocklength is unlimited [12]. Proof techniques are similar
to that of [12], but we employ several extended results for the
successive refinement problem. The inner bound is derived by
using an extended version of the previous lemma [12, Lemma
2]. We give this lemma as a special case of an extended version of the previous generalized covering lemma [13, Lemma
1]. The outer bound is derived by using an extended version of
the previous converse bound [12, Lemma 4].
In this paper, we also consider the rate-distortion region for

✲ Y

✲ Z

Figure 1: Successive refinement problem

SUMMARY In the successive refinement problem, a fixed-length
sequence emitted from an information source is encoded into two
codewords by two encoders in order to give two reconstructions of
the sequence. One of two reconstructions is obtained by one of two
codewords, and the other reconstruction is obtained by all two codewords. For this coding problem, we give non-asymptotic inner and
outer bounds on pairs of numbers of codewords of two encoders such
that each probability that a distortion exceeds a given distortion level is
less than a given probability level. We also give a general formula for
the rate-distortion region for general sources, where the rate-distortion
region is the set of rate pairs of two encoders such that each maximum
value of possible distortions is less than a given distortion level.
Key words: general source, information spectrum, non-asymptotic
bound, rate-distortion region, successive refinement

1 Introduction
The successive refinement problem is a fixed-length lossy source
coding problem with many terminals (see Fig. 1). In this coding
problem, a fixed-length sequence emitted from an information
source is encoded into two codewords by two encoders in order to give two reconstructions of the sequence. One of two
reconstructions is obtained by one of two codewords by using
a decoder, and the other reconstruction is obtained by all two
codewords by using the other decoder.
An important parameter of the successive refinement problem is a pair of rates of two encoders such that each distortion
between the source sequence and a reconstruction is less than
a given distortion level. The set of these pairs when the length
(blocklength) of the source sequence is unlimited is called the
∗ Portions of this paper were presented at the 38th Symposium on Information
Theory and Its Applications [1], and at the 2016 IEICE Society Conference [2].
† tetsu@ict.e.titech.ac.jp
‡ uematsu@ict.e.titech.ac.jp
The authors are with Dept. of Information and Communications Engineering, Tokyo Institute of Technology, Tokyo, 152-8552 Japan.

1

general sources. In this case, we adopt the maximum-distortion
criterion such that the maximum value of possible distortion is
less than a given distortion level for each reconstruction. By
using the spectral sup-mutual information rate (cf. [14]) and
the non-asymptotic inner and outer bounds, we give a general
formula for the rate-distortion region. We show that our ratedistortion region coincides with the region obtained by Rimoldi
[6] when a source is discrete stationary memoryless. Furthermore, we consider a mixed source which is a mixture of two
sources and show that the rate-distortion region is the intersection of those of two sources.
The rest of this paper is organized as follows. In Section
2, we provide some notations and the formal definition of the
successive refinement problem. In Section 3, we give several
lemmas for an inner bound on pairs of numbers of codewords and
the rate-distortion region. These lemmas are extended versions
of our previous results [12, Lemma 2] and [13, Lemma 1]. In
Section 4, we give outer and inner bounds using the smooth max
Rényi divergence on pairs of numbers of codewords. In Section
5, we give a general formula for the rate-distortion region. In
this section, we consider the rate-distortion region for discrete
stationary memoryless sources and mixed sources. In Section
6, we conclude the paper.

note numbers of codewords. Two decoders decoder 1 and decoder 2 are represented as functions ϕ1 : [1 : M1 ] → Y and
ϕ2 : [1 : M1 ] × [1 : M2 ] → Z, respectively. We refer to a tuple of encoders and decoders ( f1, f2, ϕ1, ϕ2 ) as a code. In order
to measure distortions between the source symbol and reconstruction symbols, we introduce distortion measures defined by
functions d1 : X × Y → [0, +∞) and d2 : X × Z → [0, +∞).
We define two events of exceeding given distortion levels
D1 ≥ 0 and D2 ≥ 0 as follows:
E1 (D1 ) , {d1 (X, ϕ1 ( f1 (X))) > D1 },
E2 (D2 ) , {d2 (X, ϕ2 ( f1 (X), f2 (X))) > D2 }.
Then, we define the achievability under the excess-distortion
criterion.
Definition 1. For positive integers M1, M2 , real numbers
D1, D2 ≥ 0, and ǫ1, ǫ2 ∈ [0, 1], let M = (M1, M2 ), D = (D1, D2 ),
and ǫ = (ǫ1, ǫ2 ). Then, for a source X, we say (M, D) is ǫachievable if and only if there exists a code ( f1, f2, ϕ1, ϕ2 ) such
that numbers of codewords of encoder 1 and encoder 2 are M1
and M2 , respectively, and
Pr{Ei (Di )} ≤ ǫi,

∀i ∈ {1, 2}.

In what follows, for constants M1, M2, D1, D2, ǫ1, and ǫ2 , we
often use the above simple notations: M = (M1, M2 ), D =
(D1, D2 ), and ǫ = (ǫ1, ǫ2 ). In this setting, we consider the set of
all pairs (M1, M2 ) of numbers of codewords under the excessdistortion criterion. According to the ǫ-achievability, this set is
defined as follows:

2 Preliminaries
Let N, R, and R ≥0 be sets of positive integers, real numbers, and
non-negative real numbers, respectively.
Unless otherwise stated, we use the following notations. For
a pair of integers i ≤ j, the set of integers {i, i + 1, · · · , j}
is denoted by [i : j]. For finite or countably infinite sets X
and Y, the set of all probability distributions over X and X ×
Y are denoted by PX and PX Y , respectively. The set of all
conditional probability distributions over X given Y is denoted
by PX |Y . The probability distribution of a random variable (RV)
X is denoted by the subscript notation PX , and the conditional
probability distribution for X given an RV Y is denoted by PX |Y .
The n-fold Cartesian product of a set X is denoted by X n while
an n-length sequence of symbols (a1, a2, · · · , an ) is denoted by
∞ is denoted by the bold-face
an . The sequence of RVs {X n }n=1
∞ and
letter X. Sequences of probability distributions {PX n }n=1
∞
conditional probability distributions {PX n |Y n }n=1 are denoted
by bold-face letters PX and PX |Y , respectively.
For the successive refinement problem (Fig. 1), let X, Y,
and Z be finite or countably infinite sets, where X represents
the source alphabet, and Y and Z represent two reconstruction
alphabets. Let X over X be an RV which represents a single
source symbol. Since the source can be characterized by X, we
also refer to it as the source. When we consider X as an n-fold
Cartesian product of a certain finite or countably infinite set, we
can regard the source symbol X as an n-length source sequence.
Thus, for the sake of brevity, we deal with the single source
symbol unless otherwise stated.
Two encoders encoder 1 and encoder 2 are represented as
functions f1 : X → [1 : M1 ] and f2 : X → [1 : M2 ], respectively, where M1 and M2 are positive integers which de-

Definition 2. For a source X, real numbers D1, D2 ≥ 0, and
ǫ1, ǫ2 ∈ [0, 1], we define
M(D, ǫ |X) , {(M1, M2 ) ∈ N2 : (M, D) is ǫ-achievable}.
Basically, this paper deals with a coding for a single source
symbol. However, in Section 5, we deal with the coding for
an n-length source sequence. Hence in that section, by abuse
of notation, we regard the above sets X, Y, and Z as n-fold
Cartesian products X n , Y n , and Z n , respectively. We also
regard source symbol X on X as an n-length source sequence
∞
X n on X n . Then we call the sequence X = {X n }n=1
of source
sequences the general source that is not required to satisfy the
consistency condition.
We use the superscript (n) for a code, distortion measures,
(n) (n) (n) (n)
and numbers of codewords (e.g., ( f1 , f2 , ϕ1 , ϕ2 )) to make
clear that we are dealing with source sequences of length n. For
a code, we define rates R1(n) and R2(n) as
1
log Mi(n), ∀i ∈ {1, 2}.
n
Hereafter, log means the natural logarithm.
We introduce maximum distortions for a sequence of codes.
To this end, we define the limit superior in probability [14].
Ri(n) ,

Definition 3 (Limit superior in probability). For an arbitrary
∞ of real-valued RVs, we define the limit
sequence S = {S n }n=1
superior in probability by
n
o
p-lim sup Sn , inf α : lim Pr {Sn > α} = 0 .
n→∞

2

n→∞

 h


 M2 i M1
= E E E 1{(A, B̃, C̃) < F } A, B̃
A
,

Now we introduce the maximum distortions:
p-lim sup d1(n) (X n, ϕ1(n) ( f1(n) (X n ))),

n→∞
(n)
p-lim sup d2 (X n, ϕ2(n) ( f1(n) (X n ), f2(n) (X n ))).
n→∞

where 1{·} denotes the indicator function.
Proof. We have

Then, we define the achievability under the maximum distortion
criterion.

Pr

Definition 4. For real numbers R1, R2 ≥ 0, let R = (R1, R2 ).
Then, for a general source X, and real numbers D1, D2 ≥ 0, we
say a pair (R, D) is fm-achievable if and only if there exists a
sequence {( f1(n), f2(n), ϕ1(n), ϕ2(n) )} of codes satisfying
p-lim sup d1(n) (X n, ϕ1(n) ( f1(n) (X n )))
n→∞
(n)
p-lim sup d2 (X n, ϕ2(n) ( f1(n) (X n ), f2(n) (X n )))
n→∞

=

≤ D1,
≤ D2,

=

∀i ∈ {1, 2}.

M1
Ö

PB̃ (b̃i )

M2
Ö

Õ

PC̃ | B̃ (c̃i, j | b̃i )

j=1

× 1{(a, b̃i, c̃i, j ) < F }
=

Õ

P A (a)

a ∈A

M1 Õ
Ö

PB̃ (b̃i )

i=1 b̃i ∈B

× 1{(a, b̃i, c̃i, j ) < F }

Remark 1. We can show that the rate-distortion region R(D|X)
is a closed set by the definition and using the diagonal line
argument (cf. [14]).

=

Õ

a ∈A

P A (a)

M1 Õ
Ö

i=1 b̃ ∈B

PB̃ (b̃)

M2 Õ
Ö

PC̃ | B̃ (c̃i, j | b̃i )

j=1 c̃i, j ∈C

M2
Ö
j=1

Õ

PC̃ | B̃ (c̃| b̃)

c̃ ∈C:
(a, b̃, c̃)<F

ª
© Õ
©Õ
®
­
­
PC̃ | B̃ (c̃| b̃)®
PB̃ (b̃) ­
=
P A (a) ­
­
­
®
c̃ ∈C:
a ∈A
b̃ ∈B
¬
«(a, b̃, c̃)<F
«
Õ

We note that when we regard X as n-length sequence in the
definition of M(D, ǫ |X), it gives a non-asymptotic region of
pairs of rates for a given finite blocklength.

3 Covering Lemma

M2 M1

ª
®
®
®
¬

.

By recalling that ( B̃, C̃) is independent of A, this coincides with
the right side of (1).


In this section, we introduce some useful lemmas and corollaries
for an inner bound on the set M(D, ǫ |X) and R(D|X).
The next lemma is the most basic and important result in the
sense that all subsequent results in this section are given by this
lemma.

This lemma implies an exact analysis of the error probability
of covering a set A in terms of a given condition F by codewords
{ B̃i } and {C̃i, j } of random coding. Hence, this lemma can be
regarded as an extended version of [15, Theorem 9].
Although the above lemma gives an exact analysis, it is difficult to use it for characterizing an inner bound on pairs of
numbers of codewords and the rate-distortion region. Instead of
it, we will use the next convenient lemma.

Lemma 1. Let A ∈ A be an arbitrary RV, and B̃ ∈ B and
C̃ ∈ C be RVs such that the pair ( B̃, C̃) is independent of A.
For an integer M1 ≥ 1, let B̃1, B̃2, · · · , B̃ M1 be RVs which are
independent of each other and of A, and each distributed according to PB̃ . For an integer i ∈ [1 : M1 ] and M2 ≥ 1, let
C̃i,1, C̃i,2, · · · , C̃i, M2 be RVs which are independent of each other
and of A, and each distributed according to PC̃ | B̃ (·| B̃i ). Then,
for any set F ⊆ A × B × C, we have

j=1




M2

i=1

R(D|X) , {(R1, R2 ) ∈ R2≥0 : (R, D) is fm-achievable}.


 i=1

Õ

Ö
Ö
©
ª
× ­P A(a)
PC̃ | B̃ (c̃i, j | b̃i )®
PB̃ (b̃i )
j=1
i=1
«
¬
M
M
2
1
©Ö Ö
ª
×­
1{(a, b̃i, c̃i, j ) < F }®
« i=1 j=1Õ
¬ Õ
Õ

× P A(a)

Definition 5 (Rate-distortion region). For a general source X
and real numbers D1, D2 ≥ 0, we define

{(A, B̃i, C̃i, j ) < F }

j=1





a ∈A (b̃1 ··· , b̃ M )∈B M1 (c̃1,1, ··· , c̃1, M ,c2,1 ··· , c̃ M , M )∈C M1 M2
2
1
2
1

In what follows, for constants R1 and R2 , we often use the
above simple notation: R = (R1, R2 ). In this setting, we consider
the set of all rate pairs under the maximum distortion criterion.
According to the fm-achievability, this set, usually called the
rate-distortion region, is defined as follows:

M2
M1 Ù

Ù



 i=1
Õ

{(A, B̃i, C̃i, j ) < F }

M1

n→∞

Pr

M2
M1 Ù


Ù

a ∈A (b̃1 ··· , b̃ M )∈B M1 (c̃1,1, ··· , c̃1, M ,c2,1 ··· , c̃ M , M )∈C M1 M2
2
1
2
1

and
lim sup Ri(n) ≤ Ri,

(1)

Lemma 2. Let A ∈ A, B ∈ B, and C ∈ C be arbitrary RVs, and
B̃ ∈ B and C̃ ∈ C be RVs such that the pair ( B̃, C̃) is independent
of A. Let ψ1 : A × B → [0, 1] be a function and α1 ∈ [0, 1] be
a constant such that







P A(a)PB̃ (b) ≥ α1 ψ1 (a, b)P AB (a, b),
∀(a, b) ∈ A × B.
3

(2)

Furthermore, let ψ2 : A × B × C → [0, 1] be a function and
α2 ∈ [0, 1] be a constant such that

× PBC | A (b, c|a) − e−α2 M2 −log α1

(3)

Then, we have
 h


 M2 i M1
E E E 1{(A, B̃, C̃) < F } A, B̃
A

©
­
­
P A(a) ­­1 − α1
≤
­
a ∈A:
­
P A (a)>0
«
Õ

≤ 1 − E[ψ1 (A, B)ψ2 (A, B, C)] + Pr {(A, B, C) < F }
+ e−α2 M2 −log α1 + e−α1 M1 .

(4)

Proof. We have

 h
 M i M1

E E E 1{(A, B̃, C̃) < F } A, B̃ 2 A
=

Õ

P A(a)

a ∈A:
P A (a)>0

Õ

a ∈A:
P A (a)>0

©
­
­
P A(a) ­­1 −
≤
­
a ∈A:
­
P A (a)>0
«

(a)

b ∈B

b ∈B

M2 M1

ª
®
®
®
¬

(c)

≤

Õ

ψ1 (a, b)ψ2 (a, b, c)

(b,c)∈B×C:
(a,b,c)∈F,
PB| A (b |a)>0

+ e−α2 M2 −log α1 + e−α1 M1
M2 M1

Õ

(b)

ª
®
®
®
®
®
®
¬

≤ 1 − E[ψ1 (A, B)ψ2 (A, B, C)] + Pr {(A, B, C) < F }
+ e−α2 M2 −log α1 + e−α1 M1 ,

where |x| + = max{0, x}, (a) follows since (1 − x y) M ≤ 1 − y +
e−x M for 0 ≤ x, y ≤ 1 and M > 0, and (b) comes from the fact
that ψ1 (a, b)ψ2 (a, b, c) ≤ 1.

The importance of this lemma is to be able to change RVs
from (A, B̃, C̃) to arbitrary correlated RVs (A, B, C). This makes
it possible to characterize an inner bound on pairs of numbers
of codewords and the rate-distortion region.
Lemma 2 can be regarded as an extended version of our
previous lemma [13, Lemma 1] to multiple correlated RVs.
Hence, like the previous lemma, by changing functions and
constants, it gives many types of bounds such as the following
two corollaries.

©
Õ
­
α1 ψ1 (a, b)PB | A(b|a)
P A(a) ­1 −
­
a ∈A:
b ∈B:
PB| A (b |a)>0
P A (a)>0
«
Õ

ª
®
ψ2 (a, b, c)PC | AB (c|a, b) + e−α2 M2 ®
×
®
c ∈C:
(a,b,c)∈F
¬

Õ


+ M1

(a,b,c)∈A×B×C:
(a,b,c)∈F, P AB (a,b)>0

©
ª
­
®
Õ
­
®
­
ψ2 (a, b, c)PC | AB (c|a, b)®®
× ­1 − α2
­
®
c ∈C:
­
®
(a,b,c)∈F,
PB| A (b |a)>0
«
¬

Õ

ψ1 (a, b)ψ2 (a, b, c)

(b,c)∈B×C:
(a,b,c)∈F,
PB| A (b |a)>0


+
×PBC | A (b, c|a) − e−α2 M2 −log α1 + e−α1 M1
Õ
ψ1 (a, b)ψ2 (a, b, c)P ABC (a, b, c)
≤ 1−

©
©
­Õ
­
Õ
­
­
P A(a) ­­
≤
PB̃ (b) ­­1 −
ψ2 (a, b, c)
­b ∈B
­
a ∈A:
c
∈C:
­
­
P A (a)>0
(a,b,c)∈F,
PB| A (b |a)>0
«
«
 M1
×PC | AB (c|a, b) + e−α2 M2

(b)

Õ

× PBC | A (b, c|a) − e−α2 M2 −log α1

PB̃ (b)

ª
©
Õ
®
­
PC̃ | B̃ (c|b)®
× ­1 −
­
®
c ∈C:
(a,b,c)∈F
«
¬
Õ
(a) Õ
≤
P A(a)
PB̃ (b)

,

where (a) comes from (3), (b) follows since (1 − x y) M ≤ 1 −
y + e−x M for 0 ≤ x, y ≤ 1 and M > 0 (cf. [16, Lemma 10.5.3]),
and (c) comes from (2). Since the probability is not grater than
1, we have

 h

 M2 i M1
E E E 1{(A, B̃, C̃) < F } A, B̃
A

P AB (a, b)PC̃ | B̃ (c|b) ≥ α2 ψ2 (a, b, c)P ABC (a, b, c),
∀(a, b, c) ∈ A × B × C.

  M1

Corollary 1. For any real numbers γ1, γ2 ∈ R, and any integers
M1, M2 ≥ 1 such that M1 ≥ exp(γ1 ) and M2 ≥ exp(γ2 ), we have
 h


 M2 i M1
E E E 1{(A, B̃, C̃) < F } A, B̃
A

PB | A (B| A)
≤ Pr log
> log M1 − γ1
PB̃ (B)
)
PC | AB (C| A, B)
or log
> log M2 − γ2
PC̃ | B̃ (C|B)

M1

©
©
­
­ Õ
­
­
P A(a) ­­1 − α1 ­­
=
ψ1 (a, b)ψ2 (a, b, c)
­
­ (b,c)∈B×C:
a ∈A:
­
­ (a,b,c)∈F,
P A (a)>0
«
« PB| A (b |a)>0
Õ

+ Pr {(A, B, C) < F } + e− exp(γ2 )−γ1 +log M1 + e− exp(γ1 ) .
4

Proof. Let α1 =

exp(γ1 )
M1 ,

α2 =

exp(γ2 )
M2 ,

On the other hand, let α1 and α2 be constants such that


δ1
α1 = exp − D̄∞
(P AB kP A × PB̃ |ψ1 ) ,


δ2
α2 = exp − D̄∞
(P ABC kP AB × PC̃ | B̃ |ψ2 ) .



PB | A (b|a)
≤ log M1 − γ1 ,
ψ1 (a, b) = 1 log
PB̃ (b)
(
)
PC | AB (c|a, b)
ψ2 (a, b, c) = 1 log
≤ log M2 − γ2 .
PC̃ | B̃ (c|b)

Then, for any (a, b, c) ∈ A × B × C, we have

α1 ψ1 (a, b)P AB (a, b)


P A(a)PB̃ (b)
≤
inf
ψ1 (a, b)P AB (a, b)
(a,b)∈A×B ψ1 (a, b)P AB (a, b)

Then, we can easily check that these constants and functions
satisfy (2) and (3). Plugging these functions and constants into
(4), we have the desired bound.


≤ P A(a)PB̃ (b),

This corollary can be regarded as a bound in terms of the
information spectrum (cf. [14]). To the best of our knowledge,
this type of bound has not been reported so far (although, there
are some converse bounds [10, Lemma 15] and [17, Theorem
3]).
On the other hand, the next corollary gives a bound in terms
δ
of the smooth max Rényi divergence D∞
(PkQ) defined as
δ
D∞
(PkQ)

where

|x| +

,

Í

inf
ψ:A→[0,1]:
a∈A ψ(a)P(a)≥1−δ

and
α2 ψ2 (a, b, c)P ABC (a, b, c)


P AB (a, b)PC̃ | B̃ (c|b)
≤
inf
(a,b,c)∈A×B×C ψ2 (a, b, c)P ABC (a, b, c)
× ψ2 (a, b, c)P ABC (a, b, c)
≤ P AB (a, b)PC̃ | B̃ (c|b).

ψ(a)P(a) +
,
log sup
Q(a)
a ∈A

Thus, ψ1 , ψ2 , α1 , and α2 satisfy (2) and (3).
Plugging these functions and constants into (4), we have
 h


 M i M1
E E E 1{(A, B̃, C̃) < F } A, B̃ 2 A

= max{0, x}.

Corollary 2. For any real numbers δ1, δ2 ≥ 0, and any integers
M1, M2 ≥ 1, we have
 h


 M i M1
E E E 1{(A, B̃, C̃) < F } A, B̃ 2 A

≤ δ1 + δ2 + Pr {(A, B, C) < F }
δ2

+ e− exp(−D∞
δ1

× e D∞

≤ δ1 + δ2 + Pr {(A, B, C) < F }
δ2

+ e− exp(−D∞
+e

δ
− exp(−D∞1 (P AB

k P A ×PB̃ ))M1

+ e− exp(−D∞

.

(5)

a∈A

where
δ
D̄∞
(PkQ|ψ) = log sup

a ∈A

ψ(a)P(a)
Q(a)

+

.

δ
D∞
(PkQ)− can be simply defined as
δ
D∞
(PkQ)− ,

Then, we have
E[ψ1 (A, B)ψ2 (A, B, C)]

Í

log sup

inf
ψ:A→[0,1]:
ψ(a)P(a)≥1−δ

a ∈A

ψ(a)P(a)
.
Q(a)

a∈A

In this definition, it may be a negative value depending on δ.
δ (PkQ).
Since this case is meaningless in this study, we adopt D∞
Here we also note that

(a)

≥ E[ψ1 (A, B)] + E[ψ2 (A, B, C)] − 1
≥ 1 − δ1 − δ2,

ψ(a)P(a)≥1−δ

Since for non-negative real valued functions f (b) and g(b), it
holds that (cf. e.g. [16, Lemma 16.7.1])
Í
f (b)
f (b)
Íb ∈B
,
≤ sup
g(b)
g(b)
b ∈B
b ∈B

(6)

ǫ,

,

Remark 2. The original definition of the smooth max Rényi
divergence (cf. [12]) is as follows:
Í
ψ(b)P(b)
δ
.
log sup bÍ∈B
D∞
(PkQ)− ,
inf
B⊆A
b ∈B Q(b)
Í ψ:A→[0,1]:

and
δ2
D̄∞
(P ABC kP AB × PC̃ | B̃ |ψ2 )
δ2
≤ D∞
(P ABC kP AB × PC̃ | B̃ ) +

(P AB k P A ×PB̃ )−ǫ )M1

where we use inequalities (5), (6), and (7). Since ǫ > 0 is
arbitrary, this completes the proof.


Proof. For an arbitrarily fixed ǫ > 0, let ψ1 and ψ2 be functions
such that E[ψ1 (A, B)] ≥ 1 − δ1 , E[ψ2 (A, B, C)] ≥ 1 − δ2 ,
δ1
δ1
(P AB kP A × PB̃ ) + ǫ,
(P AB kP A × PB̃ |ψ1 ) ≤ D∞
D̄∞

(P AB k P A ×PB̃ )+ǫ
δ1

δ

(P ABC k P AB ×PC̃ | B̃ ))M2 +D∞1 (P AB k P A ×PB̃ )

(P ABC k P AB ×PC̃ | B̃ )−ǫ )M2

(7)

+

δ
δ
D∞
(PkQ) = D∞
(PkQ)− .

where (a) follows since x y ≥ x + y − 1 for x, y ∈ [0, 1].
5

(8)

4 Inner and Outer Bounds on the Set of
Pairs of Numbers of Codewords

Remark 3. This proof is valid even without the RV Ũ. This
auxiliary RV is introduced merely for consistency with the outer
bound.

In this section, we give outer and inner bounds on M(D, ǫ |X)
by using the smooth max Rényi divergence.
First of all, we show a bound on the probability of the two
events E1 (D1 ) and E2 (D2 ) for the successive refinement problem. In what follows, let U be an arbitrary set.

We use the next notation for the sake of simplicity.
Definition 6. For RVs (A, B, C), we define
δ
δ
I∞
(A; B) , D∞
(P AB kP A × PB ),
δ
δ
(A; B|C) , D∞
(P ABC kP AC × PB |C ).
I∞

Theorem 1. For a source X, let (Ũ, Ỹ, Z̃) ∈ U × Y × Z be
RVs such that (Ũ, Ỹ, Z̃) is independent of X. Then, for any real
numbers D1 , D2 ≥ 0, there exists a code ( f1, f2, ϕ1, ϕ2 ) such that
numbers of codewords of encoder 1 and encoder 2 are M1 and
M2 , respectively, and

We also define the following set of probability distributions
for a given source X and constants D and ǫ.
P(D, ǫ |X) , {PUY Z |X ∈ PU Y Z |X :
Pr{d1 (X, Y ) > D1 } ≤ ǫ1,
Pr{d2 (X, Z) > D2 } ≤ ǫ2 }

Pr{E1 (D1 ) ∪ E2 (D2 )}
 h


 M2 i M1
≤ E E E 1{(X, Ũ, Ỹ, Z̃) < D} X, Ũ, Ỹ
X
,

Now, by using the above theorem, we give an inner bound on
M(D, ǫ |X).

where

Theorem 2 (Inner bound). For a source X, real numbers D1 ,
D2 ≥ 0, and ǫ1, ǫ2 > 0, we have
Ø
Ø
M(D, ǫ |X) ⊇
MI (δ, β, PUY Z |X ),

D = {(x, u, y, z) ∈ X × U × Y × Z :
d1 (x, y) ≤ D1, d2 (x, z) ≤ D2 } .
Proof. We generate (ũ1, ỹ1 ), (ũ2, ỹ2 ), · · · , (ũ M1, ỹ M1 ) ∈ U × Y
independently subject to the probability distribution PŨỸ , and
define the set C1 , {(ũ1, ỹ1 ), (ũ2, ỹ2 ), · · · , (ũ M1, ỹ M1 )}. For any
i ∈ [1 : M1 ], we generate z̃i,1, z̃i,2, · · · , z̃i, M2 ∈ Z independently subject to the probability distribution PZ̃ |Ũ Ỹ (·|ui, yi ),
and define the set C2,i , { z̃i,1, z̃i,2, · · · , z̃i, M2 }. We denote
{C2,1, C2,2, · · · , C2, M1 } as C2 . For a given set C1 , C2 and a
given symbol x ∈ X, we choose i ∈ [1 : M1 ] and j ∈ [1 : M2 ]
such that

(δ,β,γ)∈S(ǫ ) PUY Z | X ∈P(D,γ |X)

where δ = (δ1, δ2 ), β = (β1, β2 ), γ = (γ1, γ2 ),

S(ǫ) , (δ, β, γ) ∈ (0, 1]6 : δ1 + δ2 + γ1 + γ2
+β1 + β2 ≤ min{ǫ1, ǫ2 }} ,

MI (δ, β, PUY Z |X ) , (M1, M2 ) ∈ N2 :
1
δ1
log M1 ≥ I∞
(X; U, Y ) + log log ,
β1

d1 (x, ỹi ) ≤ D1 and d2 (x, z̃i, j ) ≤ D2 .

δ2
(X; Z |U, Y )
log M2 ≥ I∞


1
δ1
(X; U, Y ) + log
+ log I∞
,
β2

If there not exists such pair, we set (i, j) = (1, 1). For this pair,
we define encoders f1 and f2 as
f1 (x) = i and f2 (x) = j.

(9)

(10)

and (X, U, Y, Z) is a tuple of RVs with the probability distribution
PX × PUY Z |X .

On the other hand, we define decoders ϕ1 and ϕ2 as

Proof. We only have to show that (M, D) is ǫ-achievable for
(δ, β, γ) ∈ S(ǫ), PUY Z |X ∈ P(D, γ|X), and M1, M2 ≥ 1 such
that




1
δ1
M1 = exp I∞
(X; U, Y ) log
,
(11)
β1




1
δ2
δ1
.
M2 = exp I∞
(X; Z |U, Y) I∞
(X; U, Y) + log
β2
(12)

ϕ1 (i) = ỹi and ϕ2 (i, j) = z̃i, j .
By taking the average over the random selection of C1 and C2 ,
the average probability of Pr{E1 (D1 ) ∪ E2 (D2 )} is as follows:
E[Pr{E1 (D1 ) ∪ E2 (D2 )}]
M2
M1 Ù




Ù

{d1 (X, Ỹi ) > D1 or d2 (X, Z̃i, j ) > D2 }
= Pr



 i=1 j=1
M
M


2
1
Ù
Ù




{(X, Ũi, Ỹi, Z̃i, j ) < D} ,
= Pr



 i=1 j=1

To this end, let (Ũ, Ỹ, Z̃) ∈ U × Y × Z be RVs that is independent of X and has the same marginal distribution as (U, Y, Z),
i.e., PŨỸ Z̃ = PUY Z . Then, according to Theorem 1, there exists
a code ( f1, f2, ϕ1, ϕ2 ) such that numbers of codewords of encoder
1 and encoder 2 are M1 and M2 , respectively, and

where {(Ũi, Ỹi, Z̃i, j )} denote randomly selected sequences in C1
and C2 . Now, by noting that Z̃i, j is generated for a given (Ũi, Ỹi ),
the theorem follows from Lemma 1 by setting that A = X,
B̃ = (Ũ, Ỹ ), and C̃ = Z̃.


max{Pr{E1 (D1 )}, Pr{E2 (D2 )}}
6

 h


 M2 i M1
≤ E E E 1{(X, Ũ, Ỹ, Z̃) < D} X, Ũ, Ỹ
X
. (13)

Lemma 4. For a function g : A → B × C and c ∈ C, let kgkc
denote the size of the image of g when one output is fixed to c,
i.e.,

On the other hand, according to Corollary 2, we have
 h
i M1 

M
E E E 1{(X, Ũ, Ỹ, Z̃) < D} X, Ũ, Ỹ 2 X

kgkc = |{b ∈ B : g(a) = (b, c), ∃a ∈ A}|.
Then, for any δ ∈ (0, 1], any RV A ∈ A, and (B, C) = g(A), we
have

≤ δ1 + δ2 + Pr {(X, U, Y, Z) < D}
δ2

+ e− exp(−I∞

δ
log sup kgkc ≥ I∞
(A; B|C) + log δ.

δ

(X;Z |U,Y))M2 +I∞1 (X;U,Y)

c ∈C

δ

+e

− exp(−I∞1 (X;U,Y))M1

Proof. Let M = supc ∈C kgkc . Define a subset Dδ ⊆ B × C and
the function ψo : A × B × C → [0, 1] as


δ
,
(16)
Dδ , (b, c) ∈ B × C : PB |C (b|c) ≥
M

(a)

≤ δ1 + δ2 + γ1 + γ2 + β1 + β2

(b)

≤ min{ǫ1, ǫ2 },

(14)

ψo (a, b, c) , 1{(a, b, c) ∈ A × Dδ }.
(17)
Í
Since PBC (b, c) = a ∈A P A(a)1{(b, c) = g(a)}, PB |C (b|c) > 0
for c ∈ C such that PC (c) > 0 if and only if there exists a ∈ A
such that (b, c) = g(a) and P A (a) > 0. Thus, for c ∈ C such that
PC (c) > 0, we have

where (a) follows from (11), (12) and the fact that PUY Z |X ∈
P(D, γ|X), and (b) comes from (9). This implies that (M, D) is
ǫ-achievable.

Remark 4. The proof is also valid if we do not restrict (Ũ, Ỹ, Z̃)
to be the same distribution as (U, Y, Z). However, for the sake
of simplicity, we consider the restricted case.

|{b ∈ B : PB |C (b|c) > 0}
= |{b ∈ B : (b, c) = g(a), ∃a ∈ A s.t. P A (a) > 0}

An outer bound on M(D, ǫ |X) is given in the next theorem.

≤ kgkc
≤ M.

Theorem 3 (Outer bound). For a source X, real numbers D1 ,
D2 ≥ 0 and ǫ1, ǫ2 > 0, and any set U such that |U| ≥ |X|, we
have
Ø
Ù
M(D, ǫ |X) ⊆
MO (δ, PUY Z |X ),

Then, by using Lemma 3, it is easy to see that
Õ
ψo (a, b, c)P ABC (a, b, c)

PUY Z | X ∈P(D,ǫ |X) δ ∈(0,1]2



δ
= Pr PB |C (B|C) ≥
M

(a,b,c)∈A×B×C

where


MO (δ, PUY Z |X ) = (M1, M2 ) ∈ N2 :
log M1 ≥

δ1
I∞
(X; U, Y)

log M2 ≥

δ2
I∞
(X; Z |U, Y )

+ log δ1,

> 1 − δ.

o

Thus, we have

+ log δ2 .

δ
I∞
(A; B|C)

Before proving the theorem, we show some necessary lemmas.

≤ log

Lemma 3. Suppose that a pair of RVs (A, B) on A × B satisfies

= log

sup
(a,b,c)∈A×D δ

|{a ∈ A : P A|B (a|b) > 0}| ≤ M,
∀b ∈ B s.t. PB (b) > 0,

sup
(a,b,c)∈A×B×C

(a)

(15)

≤ log

sup
(a,b,c)∈A×D δ

for some M > 0. Then, for any ǫ ∈ (0, 1], we have

ψo (a, b, c)P ABC (a, b, c)
P AC (a, c)PB |C (b|c)

PB | AC (b|a, c)
PB |C (b|c)

+

PB | AC (b|a, c)
δ/M

+

+

≤ log M − log δ,

ǫ o
> 1 − ǫ.
Pr P A|B (A|B) ≥
M
n

where (a) comes from the definition (16). This completes the
proof.


Proof. Since the lemma can be proved in a similar manner as
[14, Lemma 2.6.2], we omit the proof.


Now, we give the proof of Theorem 3.
Proof of Theorem 3. Let k f1 k be the size of the image of an
encoder f1 . Since k f1 k ≤ |X| and |X| ≤ |U| by the assumption,
there exists an injective function id : [1 : k f1 k] → U. For this

The next lemma is an extended version of [12, Lemma 4],
which gives a bound on the size of the image of a function.
7

function, let Uid ⊆ U be the image of id and id−1 : Uid → [1 :
k f1 k] be the inverse function of id on Uid .
Suppose that (M, D) is ǫ-achievable. Then, there exists a code
( f1, f2, ϕ1, ϕ2 ) such that

Since δ1 ∈ (0, 1] and δ2 ∈ (0, 1] are arbitrary, (22) and (25)
imply that
Ù
(M1, M2 ) ∈
MO (δ, PUY Z |X ).
δ ∈(0,1]2

Pr {d1 (X, ϕ1 ( f1 (X))) > D1 } ≤ ǫ1,
Pr {d2 (X, ϕ2 ( f1 (X), f2 (X))) > D2 } ≤ ǫ2 .

Now, by recalling that (X, U, Y, Z) satisfy (18) and (19), for
any ǫ-achievable pair (M, D), we have
Ø
Ù
(M1, M2 ) ∈
MO (δ, PUY Z |X ).

Thus, by setting U = id( f1 (X)), Y = ϕ1 ( f1 (X)), and Z =
ϕ2 ( f1 (X), f2 (X)), we have
Pr {d1 (X, Y) > D1 } ≤ ǫ1,
Pr {d2 (X, Z) > D2 } ≤ ǫ2 .

PUY Z | X ∈P(D,ǫ |X) δ ∈(0,1]2

(18)
(19)

Remark 5. If we do not employ the RV U which has a role
in fixing the RV f1 (X) to a certain codeword, we cannot bound
kg2 k(u, y) by M2 in (24). Thus in this proof, introducing U is
quite important.

For a constant value c, let g1 (x) = (id( f1 (x)), ϕ1 ( f1 (x)), c),
A = X, B = (U, Y), and C = c. According to Lemma 4, for any
δ1 ∈ (0, 1], we have
δ1
log kg1 kc ≥ I∞
(X; U, Y |C) + log δ1
δ1
= I∞
(X; U, Y) + log δ1 .

Remark 6. In [1], we gave inner and outer bounds on M(D,ǫ |X)
by using the α-mutual information of order infinity [18], where
the α-mutual information is a generalized version of the mutual
information. In this paper, however, we use the smooth max
Rényi divergence. This is because it is compatible with the
information spectrum quantity which is well studied and useful
to analyze rates of a code.

(20)

On the other hand, we have
kg1 kc = |{(u, y) ∈ Uid × Y : g1 (x) = (u, y, c), ∃x ∈ X}|
Õ Õ
=
1{g1 (x) = (u, y, c), ∃x ∈ X}
Õ

u ∈Uid y ∈Y

=

1{g1 (x) = (u, ϕ1 (id−1 (u)), c), ∃x ∈ X}

5 General Formula
Distortion Region

u ∈Uid

≤ M1,

(21)

where the last inequality follows since the size of Uid is at most
k f1 k and k f1 k ≤ M1 . Combining (20) and (21), we have
δ1
log M1 ≥ I∞
(X; U, Y) + log δ1 .

δ2
kg2 k(u, y) ≥ I∞
(X; Z |U, Y) + log δ2 .

sup

(22)

(23)

Rate-

PY n |X n (Y n |X n )
1
log
,
PY n (Y n )
n→∞ n
PY n |X n Z n (Y n |X n, Z n )
1
.
I(X; Y|Z) , p-lim sup log
PY n |Z n (Y n |Z n )
n→∞ n
I(X; Y) , p-lim sup

On the other hand, for any (u, y) ∈ Uid × Y, we have
Õ
kg2 k(u, y) =
1{z = ϕ2 (id−1 (u), f2 (x)),
z ∈Z
−1

The smooth max Rényi divergence is related to the spectral
sup-mutual information rate as shown in the corollary of the next
lemma.

id (u) = f1 (x), y = ϕ1 (id−1 (u)), ∃x ∈ X}
Õ
≤
1{∃x ∈ X, z = ϕ2 (id−1 (u), f2 (x))}
Õ

z ∈Z

Lemma 5. Consider two sequences X and Y of RVs over the
same set. Then, we have

1{∃ j ∈ [1 : M2 ], z = ϕ2 (id−1 (u), j)}

Õ

z ∈Z

≤

the

∞ of
Definition 7. For a sequence (X, Y, Z) = {(X n, Y n, Z n )}n=1
RVs, we define

(u, y)∈U×Y

≤

for

In this section, we deal with the coding for an n-length source
sequence and give a general formula for the rate-distortion region.
First of all, we introduce the spectral (conditional) sup-mutual
information rate [14].

Let g2 (x) = (ϕ2 ( f1 (x), f2 (x)), id( f1 (x)), ϕ1 ( f1 (x))), A = X,
B = Z, and C = (U, Y). Then, according to Lemma 4, for any
δ2 ∈ (0, 1], we have
log



This completes the proof.

Õ

1 δ
1
PX n (X n )
lim lim sup D∞
(PX n kPY n ) = p-lim sup log
.
δ↓0 n→∞ n
PY n (X n )
n→∞ n

1{z = ϕ2 (id−1 (u), j)}

j ∈[1:M2 ] z ∈Z

= M2 .

∞ of real numbers, it holds that
Proof. For a sequence {an }n=1
+
lim supn→∞ |an | = | lim supn→∞ an | + . Thus, according to (8),
we have

(24)

We note that for any (u, y) ∈ {U \ Uid } × Y, it holds that
kg2 k(u, y) = 0. Combining (23) and (24), we have
δ2
log M2 ≥ I∞
(X; Z |U, Y ) + log δ2 .

1 δ
(PX n kPY n )
lim lim sup D∞
δ↓0 n→∞ n

(25)
8

+

1 δ
= lim lim sup D∞
(PX n kPY n )− .
δ↓0 n→∞ n

5.1 Direct Part

(26)

In this section, we show
Ø
R(D|X) ⊇

According to [11, Lemma 3], it holds that
1 δ
(PX n kPY n )−
lim lim sup D∞
δ↓0 n→∞ n
PX n (X n )
1
.
= p-lim sup log
PY n (X n )
n→∞ n

R G (PUYZ|X |X).

Let PUYZ|X ∈ PG (D|X) and suppose that I(X; U, Y) < ∞
and I(X; Z|U, Y) < ∞. Then, for any ǫ, ǫ1, ǫ2 > 0 such that
ǫ1 = ǫ2 = ǫ, any (δ, β, γ) ∈ S(ǫ) in (9), and every sufficiently
large n, we have

(27)

Furthermore, according to [14, Lemma 3.2.1], the right side of
(27) is non-negative. Thus, by combining (26) and (27), we have
the lemma.


Pr{d1(n) (X n, Y n ) > D1 + ǫ } ≤ γ1,
(n)

Pr{d2 (X n, Z n ) > D2 + ǫ } ≤ γ2 .

Corollary 3. For a sequence (X, Y, Z) of RVs, we have
1 δ n n
lim lim sup I∞
(X ; Y ) = I(X; Y),
δ↓0 n→∞ n
1 δ n n n
(X ; Y |Z ) = I(X; Y|Z).
lim lim sup I∞
δ↓0 n→∞ n

Hence, according to Theorem 2, there exists a sequence of codes
{( f1(n), f2(n), ϕ1(n), ϕ2(n) )} such that for sufficiently large n,
Pr{d1(n) (X n, Ŷ n ) > D1 + ǫ } ≤ ǫ,
Pr{d2(n) (X n, Ẑ n ) > D2 + ǫ } ≤ ǫ,

Proof. Since this corollary immediately follows from Lemma 5
and Definition 7, we omit the proof.


and

Let PUYZ|X be a sequence of conditional probability distributions PU n Y n Z n |X n ∈ PU n Y n Z n |X n . We define
PG (D|X) , {PUYZ|X : D1 (X, Y) ≤ D1,
D2 (X, Z) ≤ D2 },
(n)

D1 (X, Y) , p-lim sup d1 (X n, Y n ),
n→∞

D2 (X, Z) , p-lim sup d2(n) (X n, Z n ),





1
1
1
(n)
δ1
n
n n
log M1 = log exp I∞ (X ; U , Y ) log
,
n
n
β1
l


1
1
δ2
log M2(n) = log exp I∞
(X n ; Z n |U n, Y n )
n
n 

1
δ1
n
n n
.
× I∞ (X ; U , Y ) + log
β2

Thus, we have

n→∞

1 δ1 n n n
lim sup R1(n) ≤ lim sup I∞
(X ; U , Y )
n→∞
n→∞ n

R G (PUYZ|X |X) , {(R1, R2 ) ∈ R2 : R1 ≥ I(X; U, Y),
R2 ≥ I(X; Z|U, Y)},
where (X, U, Y, Z) is a sequence of RVs (X n, U n, Y n,

(a)

≤ I(X; U, Y),

Z n ) induced

by PUYZ|X and a general source X.
The main result of this section is the next theorem which gives
a general formula for the rate-distortion region.

and
lim sup R2(n)




1
δ2
(X n ; Z n |U n, Y n )
≤ lim sup log exp I∞
n→∞ n


1
δ1
+1
× I∞
(X n ; U n, Y n ) + log
β2



1
δ2
≤ lim sup log exp I∞
(X n ; Z n |U n, Y n )
n→∞ n


1 δ1 n n n
(X ; U , Y ) + δ2
× n lim sup I∞
n→∞ n



(a)
1
δ2
≤ lim sup log exp I∞
(X n ; Z n |U n, Y n )
n→∞ n


× n I(X; U, Y) + δ2
n→∞

Theorem 4. For a general source X, real numbers D1, D2 ≥ 0,
and any set U such that |U| ≥ |X|, we have
Ø
R(D|X) =
R G (PUYZ|X |X).
(28)
PUYZ|X ∈PG (D |X)

Remark 7. We can show that the right side of (28) is a closed
set by using the diagonal line argument (cf. [14, Remark 5.7.5]).
Remark 8. We are not sure whether a sequence U of auxiliary
RVs is really necessary or not. It may be possible to characterize
the region without it.
The proof of this theorem is presented in the subsequent two
sections. In these sections, for a code, we denote
Ŷ n =
Ẑ n =

(29)

PUYZ|X ∈PG (D |X)

1 δ2 n n n n
(X ; Z |U , Y )
= lim sup I∞
n→∞ n

(b)

(n) (n)
ϕ1 ( f1 (X n )),
ϕ2(n) ( f1(n) (X n ), f2(n) (X n )).

(a)

≤ I(X; Z|U, Y),

9

This means that (M (n), D + γn ) is γn -achievable. According to
∞
Theorem 3, there exists a sequence PUYZ|X = {PU nY n Z n |X n }n=1
of conditional probability distributions such that PU n Y n Z n |X n ∈
P(D + γn, γn |X n ) and for any δ ∈ (0, 1]2 ,

δ is a nonwhere (a) comes from Corollary 3 and the fact that I∞
increasing function of δ, and (b) follows since I(X; U, Y) < ∞.
Now, by using the usual diagonal line argument, we can construct a sequence of codes {( f1(n), f2(n), ϕ1(n), ϕ2(n) )} such that

1
1 δ n n n
log M1(n) ≥ lim sup I∞
(X ; U , Y ),
n→∞ n
n→∞ n
1
1 δ n n n n
lim sup log M2(n) ≥ lim sup I∞
(X ; Z |U , Y ).
n
n
n→∞
n→∞

(n)

lim sup R1 ≤ I(X; U, Y),

lim sup

n→∞

lim sup R2(n) ≤ I(X; Z|U, Y).
n→∞

and for any ǫ > 0,

Since this holds for any δ ∈ (0, 1]2 , we have

lim Pr{d1(n) (X n, Ŷ n ) > D1 + ǫ } = 0,

lim sup

n→∞

n→∞

lim Pr{d2(n) (X n, Ẑ n ) > D2 + ǫ } = 0.

1 δ n n n
1
log M1(n) ≥ lim lim sup I∞
(X ; U , Y )
n
δ↓0 n→∞ n
(a)

n→∞

= I(X; U, Y),

This implies that
lim sup
n→∞

p-lim sup d1(n) (X n, Ŷ n ) ≤ D1,

1 δ n n n n
1
(n)
log M2 ≥ lim lim sup I∞
(X ; Z |U , Y )
n
δ↓0 n→∞ n
(a)

n→∞

p-lim sup d2(n) (X n,
n→∞

(32)

= I(X; Z|U, Y).

n

(33)

Ẑ ) ≤ D2 .
where (a) are comes from Corollary 3. On the other hand,
since PU nY n Z n |X n ∈ P(D + γn, γn |X n ), PUYZ|X must satisfy
D1 (X; Y) ≤ D1 and D2 (X; Z) ≤ D1 , i.e., PUYZ|X ∈ PG (D|X).
By combining (31), (32), and (33), we can conclude that for
any fm-achievable pair (R, D),
Ø
(R1, R2 ) ∈
R G (PUYZ|X |X).

Thus, for any PUYZ|X ∈ PG (D|X) such that I(X; U, Y) ∈ R and
I(X; Z|U, Y) ∈ R, we have
(I(X; U, Y), I(X; Z|U, Y)) ∈ R(D|X).
This implies (29).

PUYZ|X ∈PG (D |X)

5.2 Converse Part

This implies (30).

In this section, we show that
Ø
R(D|X) ⊆
R G (PUYZ|X |X).

5.3 Discrete Stationary Memoryless Sources
(30)

In this section, we show that the rate-distortion region given in
Theorem 4 coincides with the region by Rimoldi [6] when a
source X is a discrete stationary memoryless source.
∞ is a
Let X, Y, and Z be finite sets. Since X = {X n }n=1
discrete stationary memoryless source, we assume that X n =
(X1, X2, · · · , Xn ) is a sequence of independent copies of an RV
X on X. We also assume that distortion measures d1(n) and d2(n)
are additive, i.e., for two functions d1 : X × Y → [0, +∞) and
d2 : X × Z → [0, +∞), distortion measures are represented as

PUYZ|X ∈PG (D |X)

Suppose that (R, D) is fm-achievable. Then, there exists a
sequence of codes satisfying
p-lim sup d1(n) (X n, Ŷ n ) ≤ D1,
n→∞

p-lim sup d2(n) (X n, Ẑ n ) ≤ D2,
n→∞

and

1Õ
d1 (xi, yi ),
n i=1
n

1
lim sup log Mi(n) ≤ Ri,
n→∞ n

∀i ∈ {1, 2}.

d1(n) (x n, y n ) =

(31)

Thus, we have for any γ > 0
(n)

lim Pr{d1 (X n, Ŷ n ) > D1 + γ} = 0,

We define

n→∞

lim Pr{d2(n) (X n, Ẑ n ) > D2 + γ} = 0.

PM (D|X) , {PY Z |X ∈ PY Z |X : E[d1 (X, Y)] ≤ D1,

n→∞

E[d2 (X, Z)] ≤ D2 },

∞
This implies that there exists a sequence {γn }n=1
such that
limn→∞ γn = 0 and

Pr{d1(n) (X n, Ŷ n )
Pr{d2(n) (X n, Ẑ n )

1Õ
d2 (xi, zi ).
n i=1
n

d2(n) (x n, z n ) =

and for PY Z |X ∈ PY Z |X ,

> D1 + γ n } ≤ γ n ,

R M (PY Z |X |X) , {(R1, R2 ) ∈ R2≥0 : R1 ≥ I(X; Y ),
R1 + R2 ≥ I(X; Y, Z)},

> D2 + γ n } ≤ γ n .
10

(X, Ȳ, Z̄) = {(X n, Ȳ n, Z̄ n )} be a sequence of RVs such
that (X1, Ȳ1, Z̄1 ), (X2, Ȳ2, Z̄2 ), · · · , (Xn, Ȳn, Z̄n ) are independent
and

where (X, Y, Z) is the tuple of RVs induced by a conditional
probability distribution PY Z |X ∈ PY Z |X and a given RV X.
Then, we have the next theorem.
Theorem 5. For a discrete stationary memoryless source X,
additive distortion measures, and any set U such that |U| ≥
|Z| + 1, we have
Ø
R G (PUYZ|X |X)
Ø

PXi Ȳi Z̄i (x, y, z) = PXi Yi Zi (x, y, z),
where PXi Yi Zi (x, y, z) is the i-th marginal distribution of
(X n, Y n, Z n ). Then, according to [14, Lemma 5.8.1 and
5.8.2], we have D1 (X, Y) ≥ D1 (X, Ȳ), D2 (X, Z) ≥ D2 (X, Z̄),
I(X; Y) ≥ I(X; Ȳ), and I(X; Y, Z) ≥ I(X; Ȳ, Z̄). Thus, by introducing the set I of probability distributions for independent
RVs as
(
n
Ö
PYi Zi |Xi ,
I , PYZ|X = {PY n Z n |X n } : PY n Z n |X n =

PUYZ|X ∈PG (D |X)

=

R M (PY Z |X |X).

(34)

PY Z | X ∈PM (D |X)

Remark 9. The right side of (34) can be written as

i=1

{(R1, R2 ) ∈ R2≥0 : R1 ≥ R1 (D1 ), R1 + R2 ≥ Rb (R1, D1, D2 )},

∃PYi Zi |Xi ∈ PYZ |X, i ∈ [1 : n] ,

(35)
we have
where R1 (D1 ) is the rate-distortion function and Rb (R1, D1, D2 )
gives the boundary for a given R1 , which are defined as (see,
e.g., [19, Corollary 1], [10, (22)])
R1 (D1 ) ,

min

PY | X ∈PY |X :E[d1 (X,Y )]≤D1

Rb (R1, D1, D2 ) ,

min

R1 + R2 ≥ I(X; Y, Z)}
Ø
⊆
{(R1, R2 ) : R1 ≥ I(X; Y),

I(X; Y, Z).

PYZ|X ∈I:
D 1 (X,Y)≤D1,D 2 (X,Z)≤D2

R1 + R2 ≥ I(X; Y, Z)}.

We note that R1 (D1 ) and Rb (R1, D1, D2 ) are convex and continuous functions of a triple (R1, D1, D2 ) (see, e.g., [14, Remark
5.2.1] and [20, Lemma 4]).

I(X; Y) ≥ I(X; Y ) − δ,

Proof: The left side of (34) ⊆ The right side of (34). We have
Ø
R G (PUYZ|X |X)

I(X; Y, Z) ≥ I(X; Y, Z) − δ,
and

PUYZ|X ∈PG (D |X)

⊆

{(R1, R2 ) : R1 ≥ I(X; U, Y),

D1 ≥ E[d1 (X, Y )] − γ,

PUYZ|X ∈PG (D |X)

D2 ≥ E[d2 (X, Z)] − γ.

R1 + R2 ≥ I(X; U, Y) + I(X; Z|U, Y)}
Ø
(a)
⊆
{(R1, R2 ) : R1 ≥ I(X; U, Y),

Thus, we have

PUYZ|X ∈PG (D |X)

Ø

{(R1, R2 ) : R1 ≥ I(X; Y),

PYZ|X ∈I:
D 1 (X,Y)≤D1,D 2 (X,Z)≤D2

R1 + R2 ≥ I(X; U, Y, Z)}
Ø
(b)
⊆
{(R1, R2 ) : R1 ≥ I(X; Y),
PYZ|X :
D 1 (X,Y)≤D1,D 2 (X,Z)≤D2

R1 + R2 ≥ I(X; Y, Z)},

(37)

On the other hand, in the same way as [14, p.372], for any
δ > 0, γ > 0, and any PYZ|X ∈ I such that D1 (X, Y) ≤ D1 and
D2 (X, Z) ≤ D2 , there exists PY Z |X ∈ PY Z |X such that

We will prove the theorem by two parts separately.

Ø

{(R1, R2 ) : R1 ≥ I(X; Y),

PYZ|X :
D 1 (X,Y)≤D1,D 2 (X,Z)≤D2

I(X; Y ),

PY Z | X ∈PYZ|X :
E[d1 (X,Y)]≤D1,E[d2 (X, Z)]≤D2,
I (X;Y )≤R1

Ø

⊆

R1 + R2 ≥ I(X; Y, Z)}
ÙÙ
Ø

{(R1, R2 ) :

γ>0 δ>0 PY Z | X ∈PM (D+γ |X)

(36)

R1 ≥ I(X; Y ) − δ, R1 + R2 ≥ I(X; Y, Z) − δ}
ÙÙ
=
{(R1, R2 ) : R1 + δ ≥ R1 (D1 + γ),

where (a) and (b) respectively come from the fact that

γ>0 δ>0

I(X; U, Y) + I(X; Z|U, Y) ≥ I(X; U, Y, Z),

R1 + R2 + δ ≥ Rb (R1 + δ, D1 + γ, D2 + γ)},

(38)

I(X; U, Y) ≥ I(X; Y).
For a sequence (X, Y, Z)
=
{(X n, Y n, Z n )}
RVs induced by PYZ|X and a given source X,

where the last equality comes from (35).
Since R1 (D1 ) and Rb (R1, D1, D2 ) are convex and continuous
functions of a triple (R1, D1, D2 ) (see Remark 9), it holds that

of
let
11

we have

for any ǫ > 0, there exist sufficiently small γǫ > 0 and δǫ > 0
such that
ÙÙ
{(R1, R2 ) : R1 + δ ≥ R1 (D1 + γ),

I(X; Z |U, Y ) = H(X |U, Y) − H(X |U, Y, Z)
= αH(X |Y, Z) + (1 − α)H(X |Y) − H(X |Y, Z)

δ>0 γ>0

= (1 − α)I(X; Z |Y ).

R1 + R2 + δ ≥ Rb (R1 + δ, D1 + γ, D2 + γ)}
Ù
Ù
⊆
{(R1, R2 ) : R1 ≥ R1 (D1 ) − δ − ǫ,

Now by defining PUYZ|X as
PU n Y n Z n |X n (un, y n, z n |x n ) =

δǫ >δ>0 γǫ >γ>0

R1 + R2 ≥ Rb (R1, D1, D2 ) − δ − ǫ }
Ù
=
{(R1, R2 ) : R1 ≥ R1 (D1 ) − δ − ǫ,

(X, U, Y, Z) becomes a sequence of independent copies of RVs
(X, U, Y, Z). Thus, we have
(39)

I(X; U, Y) = I(X; U, Y) = αI(X; Z, Y) + (1 − α)I(X; Y),
I(X; Z|U, Y) = I(X; Z |U, Y ) = (1 − α)I(X; Z |Y ),

By combining (36), (37), (38), and (39), we have
Ø
R G (PUYZ|X |X)
Ù Ù

D1 (X, Y) = E[d1 (X, Y)] ≤ D1,
D2 (X, Z) = E[d2 (X, Z)] ≤ D2,

PUYZ|X ∈PG (D |X)

⊆

∞ ,
where we use the fact that for i.i.d. RVs {Ai }i=1
Í
n
Ai = E[A1 ]. Hence, by noting that PUYZ|X ∈
p-lim sup n1 i=1

{(R1, R2 ) : R1 ≥ R1 (D1 ) − δ − ǫ,

ǫ >0 δǫ >δ>0

n→∞

R1 + R2 ≥ Rb (R1, D1, D2 ) − δ − ǫ }

PG (D|X), we have for any α ∈ [0, 1],

= {(R1, R2 ) : R1 ≥ R1 (D1 ), R1 + R2 ≥ Rb (R1, D1, D2 )}.
According to Remark 9, this completes the proof.

(αI(X; Z, Y) + (1 − α)I(X; Y), (1 − α)I(X; Z |Y ))
Ø
∈
R G (PUYZ|X |X).



(40)

PUYZ|X ∈PG (D |X)

Proof: The left side of (34) ⊇ The right side of (34). Since
|U| ≥ |Z| + 1, there exists an injective function id : Z → U.
For this function, let Uid ⊆ U be the image of id and
id−1 : Uid → Z be the inverse function of id on Uid . Let
u∗ ∈ U be a symbol such that u∗ < Uid .
For any PY Z |X ∈ PM (D|X) and any α ∈ [0, 1], we define
PUY Z |X ∈ PU Y Z |X as


αP
(y, z|x)

 Y Z |X

PUY Z |X (u, y, z|x) , (1 − α)PY Z |X (y, z|x)


0


PUY Z |X (ui, yi, zi |xi ),

i=1

δǫ >δ>0

R1 + R2 ≥ Rb (R1, D1, D2 ) − δ − ǫ }.

n
Ö

This implies that for any (R1, R2 ) ∈ R M (PY Z |X |X), it holds that
Ð
(R1, R2 ) ∈ PUYZ|X ∈PG (D |X) R G (PUYZ|X |X). This is because for
any (R1, R2 ) ∈ R M (PY Z |X |X) such that I(X; Y, Z) ≥ R1 , there
exists α ∈ [0, 1] such that
R1 = αI(X; Z |Y ) + I(X; Y )
= αI(X; Y, Z) + (1 − α)I(X; Y ).

if u = id(z),
if u = u∗,
otherwise.

Then, we have
R2 ≥ I(X; Y, Z) − R1
= I(X; Y, Z) − αI(X; Y, Z) − (1 − α)I(X; Y )

Since

= (1 − α)I(X; Z |Y ).

(41)



αP
(x, y, id−1 (u)) if u ∈ Uid,

 XY Z

PXUY (x, u, y) = (1 − α)PXY (x, y)
if u = u∗,


0
otherwise,



P
(x| y, id−1 (u)) if u ∈ Uid,

 X |Y Z

PX |UY (x|u, y) = PX |Y (x| y)
if u = u∗,


0
otherwise,


According to (40), such pair (R1, R2 ) is included in the reÐ
gion PUYZ|X ∈PG (D |X) R G (PUYZ|X |X). On the other hand, for
any (R1, R2 ) ∈ R M (PY Z |X |X) such that R1 > I(X; Y, Z),
we have R2 ≥ 0. Since it holds that (I(X; Y, Z), 0) ∈
Ð
PUYZ|X ∈PG (D |X) R G (PUYZ|X |X)
Ð due to (40), such pair (R1, R2 )
is also included in the region PUYZ|X ∈PG (D |X) R G (PUYZ|X |X).
Therefore, we have
Ø
R G (PUYZ|X |X) ⊇ R M (PY Z |X |X).

I(X; U, Y ) = H(X) − αH(X |Y, Z) − (1 − α)H(X |Y )
= αI(X; Y, Z) + (1 − α)I(X; Y).

Since this holds for any PY Z |X ∈ PM (D|X), this completes the
proof.


we have

PUYZ|X ∈PG (D |X)

Remark 10. Unlike the rate-distortion region by Rimoldi, our
region includes a sequence U of auxiliary RVs. This comes
from the fact that the time-sharing argument as in (41) cannot
be employed because it holds that in general,

Furthermore, since


P
(x| y, z)

 X |Y Z

PX |UY Z (x|u, y, z) = PX |Y Z (x| y, z)


0


if u = id(z),
if u = u∗,
otherwise,

I(X; Y, Z) , I(X; Y) + I(X; Z|Y).
12

5.4 Mixed Sources

R G (PŨỸZ̃|X |X)

PU1 Y1 Z1 |X1 ,PU2 Y2 Z2 |X2 :

In this section, we give the rate-distortion region for mixed
sources.
∞ and X =
The mixed source X is defined by X1 = {X1n }n=1
2
n ∞
{X2 }n=1 as

Ø

D 1 (X, Ỹ)≤D1,D 2 (X, Z̃)≤D2
(a)

=

{(R1, R2 ) :

PU1 Y1 Z1 |X1 ,PU2 Y2 Z2 |X2 :
max{D 1 (X1,Y1 ),D 1 (X2,Y2 )} ≤D1,
max{D 2 (X1,Z1 ),D 2 (X2,Z2 )} ≤D2

PX n (x n ) = α1 PX1n (x n ) + α2 PX2n (x n ),

R1 ≥ max{I(X1 ; U1, Y1 ), I(X; U2, Y2 )}

where α1, α2 ∈ [0, 1] and α1 + α2 = 1.
The next lemma shows a fundamental property of the information spectrum of mixed sources.

=

R2 ≥ max{I(X; Z1 |U1, Y1 ), I(X; Z2 |U2, Y2 )}}
Ø
Ø
PU1 Y1 Z1 |X1 ∈PG (D |X1 ) PU2 Y2 Z2 |X2 ∈PG (D |X2 )

Lemma 6. For sequences of RVs (X1, Y1, Z1 ) and (X2, Y2, Z2 ),
let (X, Y, Z) be defined by

R G (PU1 Y1 Z1 |X1 |X1 ) ∩ R G (PU2 Y2 Z2 |X2 |X2 )
= R(D|X1 ) ∩ R(D|X2 ).

PX n Y n Z n (x n, y n, z n ) = α1 PX1n Y1n Z1n (x n, y n, z n )

where (a) comes from [14, Lemma 1.4.2], Lemma 6 and the fact
that

+ α2 PX2n Y2n Z2n (x n, y n, z n ).
Then, we have

PX n Ũ n Ỹ n Z̃ n (x n, un, y n, z n )

I(X; Y) = max{I(X1 ; Y1 ), I(X2 ; Y2 )},

= α1 PX1n U1n Y1n Z1n (x n, un, y n, z n )
+ α2 PX2n U2n Y2n Z2n (x n, un, y n, z n ).

I(X; Y|Z) = max{I(X1 ; Y1 |Z1 ), I(X2 ; Y2 |Z2 )}.
Proof. Since this lemma can be proved in the same way as
[14, Lemma 7.9.1] by using [14, Lemma 1.4.2], we omit the
details.


This completes the proof.



6 Conclusion

The next theorem shows that the rate-distortion region for a
mixed source is the intersection of those of two sources.

In this paper, we have dealt with the successive refinement problem. We gave inner and outer bounds using the smooth max
Rényi divergence on the set of pairs of numbers of codewords.
These bounds are obtained by extended versions of our previous
covering lemma and converse bound. By using these bounds,
we also gave a general formula using the spectral sup-mutual information rate for the rate-distortion region. Further, we showed
some special cases of our rate-distortion region for discrete stationary memoryless sources and mixed sources.

Theorem 6. For a mixed source X defined by X1 and X2 , and
any real numbers D1, D2 ≥ 0, we have
R(D|X) = R(D|X1 ) ∩ R(D|X2 ).
Proof. For PU1 Y1 Z1 |X1 and PU2 Y2 Z2 |X2 , we define PŨỸZ̃|X by
PŨ n Ỹ n Z̃ n |X n (un, y n, z n |x n )
=

Ø

=

α1 PX1n (x n )PU1nY1n Z1n |X1n (un, y n, z n |x n )
α2 P
+

X2n

PX n (x n )
n
(x )PU2n Y2n Z2n |X2n (un,

Acknowledgment

y n, z n |x n )

PX n (x n )

.

This work was supported in part by JSPS KAKENHI Grant
Number 15K15935.

When PU1 Y1 Z1 |X1 = PU2 Y2 Z2 |X2 = PUYZ|X , we have PŨỸZ̃ |X =
PUYZ|X by the definition. This implies that for any PUYZ|X , there
exist PU1 Y1 Z1 |X1 and PU2 Y2 Z2 |X2 such that PUYZ|X = PŨỸZ̃ |X . On
the other hand, for any PU1 Y1 Z1 |X1 and PU2 Y2 Z2 |X2 , there trivially
exists PUYZ|X such that PUYZ|X = PŨỸZ̃|X . Thus, we have
Ø
R G (PUYZ|X |X)
Ø

References
[1] T. Matsuta and T. Uyematsu, “Non-asymptotic bounds
on numbers of codewords for the successive refinement
problem,” Proc. 38th Symp. on Inf. Theory and its Apps.
(SITA2015), pp.43–48, Nov. 2015.

PUYZ|X ∈PG (D |X)

=

[2] T. Matsuta and T. Uyematsu, “A general formula of the
achievable rate region for the successive refinement problem,” Proc. IEICE Society Conference, p.37, Sep. 2016.

R G (PŨỸZ̃|X |X).

PU1 Y1 Z1 |X1 ,PU2 Y2 Z2 |X2 :
D 1 (X, Ỹ)≤D1,D 2 (X, Z̃)≤D2

[3] V. N. Koshelev, “Estimation of mean error for a discrete
successive-approximation scheme,” Problemy Peredachi
Informatsii, vol.17, no.3, pp.20–33, 1981.

Thus, according to Theorem 4, we have
R(D|X)
13

[20] V. Kostina and E. Tuncel, “Successive refinement of abstract sources,” arXiv preprint arXiv:1707.09567, July
2017.

[4] V. N. Koshelev, “Hierarchical coding of discrete sources,”
Problemy Peredachi Informatsii, vol.16, no.3, pp.31–49,
1980.
[5] W. Equitz and T. Cover, “Successive refinement of information,” IEEE Trans. Inf. Theory, vol.37, no.2, pp.269–275,
Mar. 1991.
[6] B. Rimoldi, “Successive refinement of information: characterization of the achievable rates,” IEEE Trans. Inf. Theory, vol.40, no.1, pp.253–259, Jan. 1994.
[7] H. Yamamoto, “Source coding theory for a triangular communication system,” IEEE Trans. Inf. Theory, vol.42, no.3,
pp.848–853, May 1996.
[8] M. Effros, “Distortion-rate bounds for fixed- and variablerate multiresolution source codes,” IEEE Trans. Inf. Theory, vol.45, no.6, pp.1887–1910, Sep. 1999.
[9] A. No, A. Ingber, and T. Weissman, “Strong successive
refinability and rate-distortion-complexity tradeoff,” IEEE
Trans. Inf. Theory, vol.62, no.6, pp.3618–3635, June 2016.
[10] L. Zhou, V.Y.F. Tan, and M. Motani, “Second-order and
moderate deviations asymptotics for successive refinement,” IEEE Trans. Inf. Theory, vol.63, no.5, pp.2896–
2921, May 2017.
[11] N.A. Warsi, “One-shot bounds for various information theoretic problems using smooth min and max Rényi divergences,” Proc. 2013 IEEE Inf. Theory Workshop, pp.1–5,
Sep. 2013.
[12] T. Uyematsu and T. Matsuta, “Revisiting the rate-distortion
theory using smooth max Rényi divergence,” Proc. 2014
IEEE Inf. Theory Workshop, pp.202–206, Nov. 2014.
[13] T. Matsuta and T. Uyematsu, “New non-asymptotic bounds
on numbers of codewords for the fixed-length lossy compression,” IEICE Trans. Fundamentals, vol.E99-A, no.12,
pp.2116–2129, Dec. 2016.
[14] T. S. Han, Information-Spectrum Methods in Information
Theory, Springer, 2003.
[15] V. Kostina and S. Verdú, “Fixed-length lossy compression
in the finite blocklength regime,” IEEE Trans. Inf. Theory,
vol.58, no.6, pp.3309–3338, June 2012.
[16] T. M. Cover and J. A. Thomas, Elements of Information
Theory, 2nd ed., Wiley, New York, 2006.
[17] V. Kostina and E. Tuncel, “The rate-distortion function for
successive refinement of abstract sources,” Proc. IEEE Int.
Symp. on Inf. Theory, pp.1923–1927, June 2017.
[18] S. Verdú, “α-mutual information,” 2015 Inf. Theory and
Apps. Workshop, pp.1–6, Feb. 2015.
[19] A. Kanlis and P. Narayan, “Error exponents for successive refinement by partitioning,” IEEE Trans. Inf. Theory,
vol.42, no.1, pp.275–282, Jan. 1996.
14

