1

Refined Asymptotics for Rate-Distortion using
Gaussian Codebooks for Arbitrary Sources
Lin Zhou, Vincent Y. F. Tan and Mehul Motani

arXiv:1708.04778v2 [cs.IT] 26 Dec 2017

Abstract
The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an
arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding
is employed. We extend Lapidoth’s analysis in several directions in this paper. Firstly, we consider refined asymptotics. In particular,
when the source is stationary and memoryless, we establish the second-order, moderate, and large deviation asymptotics of the
problem. Secondly, by “random Gaussian codebook”, Lapidoth refers to a collection of random codewords, each of which is drawn
independently and uniformly from the surface of an n-dimensional sphere. To be more precise, we term this as a spherical Gaussian
codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product
Gaussian distribution. We derive the second-order, moderate, and large deviation asymptotics when i.i.d. Gaussian codebooks are
employed. Interestingly, in contrast to the recent work on the channel coding counterpart by Scarlett, Tan and Durisi (2017), the
dispersions for spherical and i.i.d. Gaussian codebooks are identical. The optimal excess-distortion exponents for both spherical
and i.i.d. Gaussian codebooks are established for all rates. Furthermore, we prove that the i.i.d. Gaussian codebook has a strictly
larger excess-distortion exponent than the spherical counterpart for any rate larger the first order coding rate.
Index Terms
Lossy data compression, Rate-distortion, Gaussian codebook, Mismatched encoding, Minimum distance encoding, Ensemble
tightness, Second-order asymptotics, Dispersion, Moderate deviations, Large deviations

I. I NTRODUCTION
In the traditional lossy data compression problem [1, Section 3.6], one seeks to find the minimum rate of compression
of a source while allowing it to be reconstructed to within a distortion D at the output of the decompressor. Shannon [2]
established the rate-distortion function for stationary and memoryless sources. However, practical considerations on the system
design often necessitate a particular encoding strategy. This then constitutes a mismatch problem in which the codebook is
optimized for a source with one distribution but used to compress a source of a different distribution. For example, one might be
interested to use a Gaussian codebook—a codebook that is optimal for a memoryless Gaussian source—to compress a source
that is arbitrary. For all ergodic sources with second moment σ 2 , Lapidoth [3, Theorem 3] established that the (ensemble)
rate-distortion function is


1
σ2
∗
Rσ2 (D) = log max 1,
.
(1)
2
D
The term “Gaussian codebook” requires some qualifications; Lapidoth [3] uses this term to mean a collection of random
codewords each of which is drawn independently and uniformly from the surface of a sphere in n-dimensions. In this work, we
term this random codebook as a spherical Gaussian codebook and, for the sake of comparison, we also consider i.i.d. Gaussian
codebooks in which each component of each codeword is drawn independently from a (univariate) Gaussian distribution. In the
spirit of recent emphases on refined asymptotics that bring to light the tradeoff between the coding rate, the blocklength, and
the probability of excess-distortion, in this paper, we establish ensemble-tight second-order coding rates, moderate deviations
constants and excess-distortion exponents.
A. Main Contributions and Related Works
Our main contributions are as follows:
(i) We conduct a second-order asymptotic analysis [4]–[6] for the rate-distortion saddle-point problem for stationary and
memoryless sources that satisfy mild technical conditions. Here, the probability of excess-distortion is allowed to be
non-vanishing and the spotlight is shone on the additional rate, above the rate-distortion function, required at finite
blocklengths to compress the source to within the prescribed probability of excess-distortion. This work complements
that of Kostina and Verdú [7] and Ingber and Kochman [8] who established the second-order asymptotics (or dispersion)
for compressing (discrete and Gaussian) memoryless sources when the encoder is unconstrained. Our main result here
is somewhat surprising. We show that the mismatched dispersions (and the first-order coding rates or rate-distortion
functions) for spherical and i.i.d. Gaussian codebooks are identical; this implies that there is no performance loss in
The authors are with the Department of Electrical and Computer Engineering, National University of Singapore (Emails: lzhou@u.nus.edu, vtan@nus.edu.sg,
motani@nus.edu.sg).

2

terms of the backoff from the first-order fundamental limit regardless of which type of Gaussian codebook one uses.
This is in stark contrast to the recent work by Scarlett, Tan, and Durisi [9] on the channel coding counterpart of this
problem [10]. It was shown in [9] that the dispersions for both types of codebooks are different. For the lossy source
coding case, the dispersions are common and depend only on the second and fourth moments of the source through a
simple formula. We provide intuition for why this is the case after the statement of Theorem 1. We recover the dispersion
of lossy compression of Gaussian memoryless sources (GMSes) [7], [8] by particularizing the arbitrary source to be a
Gaussian.
(ii) Next, we conduct moderate deviations analysis [11], [12] for the same problem under an additional, albeit mild, assumption
on the source. Here, the rate of the codebook approaches the rate-distortion function at a speed slower than the reciprocal of
the square root of the blocklength. One then seeks the subexponential rate of decay of the probability of excess-distortion.
This analysis complements that of Tan [13] who considered the unconstrained encoding case for (discrete and Gaussian)
memoryless sources. This was generalized to the successive refinement problem by the present authors [14]. We again
show that the moderate deviations constants are identical and that for GMSes can be easily recovered.
(iii) Finally, we consider the large deviations regime [15], [16] in which the rate of the codebook is constrained to be
strictly above the rate-distortion function and one seeks to establish the exponential rate of decay of the probability
of excess-distortion. Our analysis complements that of Ihara and Kubo [17] who used ideas from Marton [18] to find
the excess-distortion exponent for compressing a GMS. We establish the optimal excess-distortion exponents for both
spherical and i.i.d. Gaussian codebooks. We recover the excess-distortion exponent of lossy compression of GMSes [17]
by particularizing the source to be a Gaussian when an i.i.d. Gaussian codebook is used. Furthermore, we show that
the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than the spherical counterpart for any rate
R > Rσ∗ 2 (D) (cf. (1)) and illustrate this point using two numerical examples.
B. Organization of the Rest of the Paper
The rest of the paper is organized as follows. We set up the notation, formulate our problem precisely, and present existing
results in Section II. In Section III, we present our main results. These include results concerning second-order, moderate, and
large deviation asymptotics. Sections IV to VI are devoted to the proofs for each of these asymptotic results respectively.
II. T HE R ATE -D ISTORTION S ADDLE -P OINT P ROBLEM
A. Notation
Random variables and their realizations are in upper (e.g., X) and lower case (e.g., x) respectively. All sets are denoted in
calligraphic font (e.g., X ). We use R, R+ , and N to denote the set of real numbers, non-negative real numbers, and natural
numbers respectively. For any two natural numbers a and b we use [a : b] to denote the set of all natural numbers between
a and b (inclusive). We use exp{x} to denote ex . All logarithms are base e. We use Q(·) to denote the standard Gaussian
complementary cumulative distribution function (cdf) and Q−1 (·) its inverse. For any random variable X, we use ΛX (θ) to
denote the cumulant generating function log E[exp{θX}] (where θ ∈ R). We use Λ∗X (t) (where t ∈ R) to denote the FenchelLegendre transform (convex conjugate) of the cumulant generating function, i.e., supθ≥0 {θt−ΛX (θ)}.p
Let X n := (X1 , . . . , Xn )
P 2
n
n
be a random vector of length n and x = (x1 , . . . , xn ) is a particular realization. We use kx k =
i xi to denote the ℓ2
n
n
norm of a vector xn ∈ Rn . Given two sequences
x
and
y
,
the
quadratic
distortion
measure
(squared
Euclidean norm) is
Pn
defined as d(xn , y n ) := n1 kxn − y n k2 = n1 i=1 (xi − yi )2 . For any two sequences {an }n≥1 and {bn }n≥1 , we write an ∼ bn
to mean limn→∞ an /bn = 1.
B. System Model
Consider arbitrary source X with distribution (probability mass function or probability density function) fX satisfying
E[X 2 ] = σ 2 , ζ := E[X 4 ] < ∞, E[X 6 ] < ∞.

(2)

In this paper, we consider memoryless sources and thus X n is an i.i.d. sequence where each component is generated according
to fX . We consider the rate-distortion saddle-point problem [3, Theorem 3] with an admissible distortion level 0 < D < σ 2 .
This is the lossy source coding problem [1, Section 3.6] where one is constrained to use random Gaussian codebooks (spherical
or i.i.d.) and an encoding strategy which chooses the codeword that minimizes the quadratic distortion measure.
Definition 1. An (n, M )-code for the rate-distortion saddle-point problem consists of
n
M
• A set of M codewords {Y (i)}i=1 known by both the encoder and decoder;
n
• An encoder f which maps the source sequence X into the index of the codeword that minimizes the quadratic distortion
n
with respect to the source sequence X , i.e.,

f (X n ) := arg min d X n , Y n (i) .
(3)
i∈[1:M]

3

•

A decoder φ which declares the reproduced sequence as the codeword with index f (X n ), i.e.,
φ(f (X n )) = Y n (f (X n )).

(4)

Throughout the paper, we consider random Gaussian codebooks. To be specific, we consider two types of Gaussian codebooks.
• First, we consider the spherical
Gaussian codebook where each codeword Y n is generated independently and uniformly
p
over a sphere with radius n(σ 2 − D), i.e.,
Y n ∼ fYspn (y n ) =

•

δ(ky n k2 − n(σ 2 − D))
p
,
Sn ( n(σ 2 − D))

(5)

where δ(·) is the Dirac delta function, Sn (r) = nπ n/2 rn−1 /Γ( n+2
2 ) is the surface area of an n-dimensional sphere
with radius r, and Γ(·) is the Gamma function. For GMSes, the spherical codebook is second-order optimal (cf. [7,
Theorem 40]).
Second, we consider the i.i.d. Gaussian codebook where each codeword Y n is generated independently according to the
following product Gaussian distribution with variance σ 2 − D, i.e.,


n
Y
1
yi2
n
iid
n
p
.
(6)
exp −
Y ∼ fY n (y ) =
2(σ 2 − D)
2π(σ 2 − D)
i=1

The i.i.d. Gaussian codebook is also second-order optimal (cf. [7, Theorem 12]) for a GMS.
Here, we mention in passing that the techniques herein may also be applicable to the truncated i.i.d. Gaussian codebook [16,
Eqns. (7.3.12)–(7.3.15)] where the codewords are generated from an i.i.d. Gaussian distribution as in (6) but the distribution
is then truncated to the annulus {y n ∈ Rn : σ 2 − D − nη < n1 ky n k2 ≤ σ 2 − D} where η is a fixed positive number. This
distribution is useful for deriving error exponent and second-order results. See [19], [20] for discussions.
The (ensemble) excess-distortion probability is defined as
Pe,n := Pr{d(X n , φ(f (X n ))) > D}
i
h
M
Xn ,
= EfXn 1 − Pr{d(X n , Y n ) ≤ D}

(7)
(8)

where (8) follows from [7, Theorem 9] and the inner probability (over Y n which is independent of X n ) is calculated either
with respect to the right hand side of (5) if we use a spherical Gaussian codebook or the right hand side of (6) if we use an
i.i.d. Gaussian codebook. Note that the probability in (7) is averaged over the source as well as the random codebook. This
is in contrast to the traditional lossy source coding analysis [7], [18] where the excess-distortion probability is averaged over
the source only. The additional average over the codebook allows us to pose questions concerning ensemble tightness in the
spirit of [9], [21].
C. Existing Results and Definitions
∗
Let Msp
(n, ε, σ 2 , D) be the minimum number of codewords required to compress a length-n source sequence so that the
excess-distortion probability with respect to distortion level D is no larger than ε ∈ (0, 1) when a spherical Gaussian codebook
∗
is used. Similarly, let Miid
(n, ε, σ 2 , D) be the corresponding quantity when an i.i.d. Gaussian codebook is used. Lapidoth [3,
Theorem 3] showed that for any ergodic source with finite second moment σ 2 and any ε ∈ (0, 1),

1
σ2
1
∗
log Msp
(n, ε, σ 2 , D) = log
nats per source symbol.
n→∞ n
2
D
As we will show via a by-product of Theorem 1, for any source satisfying (2) and any ε ∈ (0, 1), we also have
lim

(9)

1
1
σ2
∗
log Miid
(n, ε, σ 2 , D) = log
nats per source symbol.
(10)
n→∞ n
2
D
In this paper, we are interested in second-order, large, and moderate deviations analyses. These analyses provide a refined
understanding of the tradeoff between the rate, the blocklength and the excess-distortion probability. In the study of secondorder asymptotics, a non-vanishing excess-distortion probability is allowed and we aim to find the back-off from the first-order
2
coding rate (the rate-distortion function) 21 log σD .
lim

Definition 2. Fix any ε ∈ [0, 1). A number L is said to be a spherical-achievable second-order coding rate if there exists a
sequence of (n, M )-codes using spherical Gaussian codebooks such that


n
σ2
1
≤ L,
(11)
lim sup √ log M − log
n
2
D
n→∞
lim sup Pe,n ≤ ε.
(12)
n→∞

4

The infimum of all spherical-achievable second-order coding rates is the optimal spherical second-order coding rate and is
denoted as L∗sp (ε). In a similar manner, we define i.i.d.-achievable second-order coding rates and denote their infimum as the
optimal i.i.d. second-order coding rate L∗iid (ε).1
The moderate deviations regime interpolates between the large deviations (cf. Definition 4 to follow) and the second-order
regimes. In this regime, we are interested in a sequence of (n, M )-codes whose rates approach the first-order coding rate
1
σ2
2 log D and whose excess-distortion probabilities vanish simultaneously.
Definition 3. Consider any sequence {ξn }n∈N such that as n → ∞
r
n
ξn → 0 and
ξn → ∞.
log n

(13)

A non-negative number ν is said to be a spherical-achievable moderate deviations constant if there exists a sequence of
(n, M )-codes using spherical Gaussian codebooks such that


n
σ2
1
≤ 1,
(14)
log M − log
lim sup
2
D
n→∞ nξn
1
(15)
lim inf − 2 log Pe,n ≥ ν.
n→∞
nξn
The supremum of all spherical-achievable moderate deviations constants is the optimal spherical moderate deviations constant
∗
and is denoted as νsp
. Similarly, we can define i.i.d.-achievable moderate deviations constants and their supremum is the
∗
optimal i.i.d. moderate deviations constant νiid
.
In the large deviations regime, we characterize the speed of the exponential decay of the excess-distortion probability for
codes with a rate upper bounded by R.
Definition 4. A non-negative number E is said to be a rate-R spherical-achievable excess-distortion exponent if there exists
a sequence of (n, M )-codes using spherical Gaussian codebooks such that
lim sup
n→∞

1
log M ≤ R,
n

(16)

1
log Pe,n ≥ E.
(17)
n
The supremum of all rate-R spherical-achievable excess-distortion exponents is denoted as the optimal spherical excess∗
∗
distortion exponent Esp
(R). Similarly, we can define the optimal i.i.d. excess-distortion exponent Eiid
(R).
lim inf −
n→∞

III. M AIN R ESULTS
A. Second-Order Asymptotics
Our first result pertains to the second-order coding rate. Recall the definitions of σ 2 and ζ in (2). Let the mismatched
dispersion be defined as
V(σ 2 , ζ) :=

ζ − σ4
Var[X 2 ]
=
.
4
4σ
4 (E[X 2]2 )

Theorem 1. Consider an arbitrary memoryless source X satisfying (2). For any ε ∈ [0, 1),
p
L∗sp (ε) = L∗iid (ε) = V(σ 2 , ζ)Q−1 (ε).

(18)

(19)

The proof of Theorem 1 is provided in Section IV. In the proof, we show that for any ε ∈ (0, 1),
∗
∗
log Msp
(n, ε, σ 2 , D) = log Miid
(n, ε, σ 2 , D) =

σ2 p
n
log
+ nV(σ 2 , ζ)Q−1 (ε) + O(log n).
2
D

(20)

A few remarks are in order.
First, in contrast to Scarlett, Tan, and Durisi [9] where spherical and i.i.d. Gaussian codebooks achieve different second-order
coding rates for the channel coding saddle-point problem (where the codebook is Gaussian and the channel is additive and
its noise is non-Gaussian) [10], we observe no performance gap in second-order asymptotics between two kinds of Gaussian
codebooks in the rate-distortion saddle-point counterpart. We provide some intuition why this is so. For the channel coding
problem [9], [10], the performance gap between the dispersions appears because the probability of dominant error event depends
strongly on the choice of the random codebook since the mutual information random variable that appears in the random coding
2
2
∗
1 In Definition 2, we allow ε = 0 (signifying that P
∗
e,n is required to vanish) but in the definitions of Msp (n, ε, σ , D) and Miid (n, ε, σ , D) we enforce
that ε ∈ (0, 1).

5

union (RCU) bound [12] is a strong function of the code distribution. Indeed, it is advantageous to use a spherical code as this
ensures that the codewords have exact power P . For an i.i.d. code, each of the codewords has power P averaged over the n
time slots. Due to this additional randomness (in addition to the channel noise), the dispersion or variability for the i.i.d. case is
worse (higher) than that for the spherical case. This is analogous to the well-known fact that for discrete memoryless channels,
fixed composition codes [15] generally perform better than i.i.d. codes [16] in the error exponents regime [19, Chapter 2] [22,
Section 5]. In contrast, for the rate-distortion saddle-point problem we consider in this paper, there is no “power constraint”
on the codewords. Thus, as can be gleaned in the proof in Section IV, the dominant error event in the present rate-distortion
case concerns the atypicality of the source sequence X n . The Gaussian codebook plays a diminished role in the contribution
to the overall randomness or dispersion of the system.
Second, for a GMS (i.e., X ∼ N (0, σ 2 )), the dispersion is known to be V(σ 2 , ζ) = 12 independent of the distortion level or
the source variance [7], [8]. Hence, when specialized to GMSes, our results are consistent with existing results, namely that
both spherical and i.i.d. Gaussian codebooks achieve the optimal second-order coding rate for the rate-distortion problem [7,
Theorems 13 and 40]. Furthermore, our results strengthen those of Lapidoth [3, Theorem 3] in the sense that, using i.i.d.
Gaussian codebooks, it is true that for an arbitrary memoryless source satisfying (2) and for any ε ∈ (0, 1), the first-order
result in (10) holds.
Third, we remark that as (20) indicates, the larger the mismatched dispersion for a source, the larger the back-off from
the first-order coding rate given a fixed non-vanishing excess-distortion probability ε and a blocklength n. This mismatched
dispersion is a function of the fourth moment of the source. Indeed, V(σ 2 , ζ) is related to the kurtosis of the source.
Finally, we mention in passing that our proof strategy differs significantly from Lapidoth’s [3] who, for the direct and
ensemble converse parts, invoked a theorem due to Wyner [23] concerning packings and coverings of n-spheres. The analysis
used to prove this theorem and the subsequent ones naturally require more refined estimates on various probabilities.
B. Moderate Deviation Asymptotics
Theorem 2. Consider an arbitrary memoryless source X satisfying (2) and ΛX 2 (θ) is finite for some positive number θ. If
V(σ 2 , ζ) is positive,
∗
∗
νsp
= νiid
=

1
.
2V(σ 2 , ζ)

(21)

The proof of Theorem 2 is provided in Section V. Several remarks are in order.
First, we observe that similarly to second-order asymptotics (Theorem 1), the dispersion V(σ 2 , ζ) is a fundamental quantity
that governs the speed of convergence of the excess-distortion probability to zero.
Second, we remark the constraint in (13) is mild. In fact, ξn = n−t for any t ∈ (0, 0.5) satisfies (13). We believe
√ that the
second condition in (13) may be relaxed by the more common moderate deviations condition [11], [12], namely nξn → ∞,
if a more careful analysis is employed.
Third, we remark that the condition on the source where ΛX 2 (θ) is finite for some θ > 0 is also mild. It is used to assert
that the probability that an average of a sum of i.i.d. random variables deviates from its mean by a constant amount decays
exponentially. See [24, Theorem B.4.1] and Lemma 6 to follow. Note that this condition is satisfied if X is distributed according
to many common distributions such as discrete, Gaussian, Maxwell, or Rayleigh. However, this condition is violated if X has
a Cauchy distribution, which does not even have a finite mean.
C. Large Deviation Asymptotics
We present several definitions before stating our main result. Given s ∈ R and any non-negative number z, define


(z + σ 2 − 2D)2
1
,
Rsp (z) := − log 1 −
2
4z(σ 2 − D)
1
sz
sD
Riid (s, z) := log(1 + 2s) +
−
, and
2
(1 + 2s)(σ 2 − D) σ 2 − D
p


σ 2 − 3D + (σ 2 − D)2 + 4zD
∗
.
s (z) := max 0,
4D

(22)
(23)
(24)

We remark that Rsp (z) is the rate of the exponential decay of the non-excess-distortion probability for any source sequence
xn whose power is z = n1 kxn k2 when its reproduction sequence is generated according to fYspn in (5), i.e.,
1
log Pr{d(xn , Y n ) ≤ D} = Rsp (z), where Y n ∼ fYspn .
(25)
n
Similarly, Riid (s∗ (z), z) is the exponent of the non-excess-distortion probability for any source sequence xn with power z
when Y n ∼ fYiidn .
lim −

n→∞

6

The Fenchel-Legendre transform of the cumulant generating function of X 2 (cf. Section II-A) is
Λ∗X 2 (t) := sup{θt − ΛX 2 (θ)},
θ≥0

t ∈ R.

(26)

This is also known as the large deviations rate function [25] of X 2 . For brevity in presentation of the following theorem, let
p
√
(27)
r2 := σ 2 − D + D.

Theorem 3. The following results on the optimal excess-distortion exponents hold.
1
σ2
• If R < 2 log D , then for both spherical and i.i.d. Gaussian codebooks,
∗
∗
Esp
(R) = Eiid
(R) = 0.

(28)

2

•

If R ≥ 21 log σD ,
– For the spherical Gaussian codebook, the optimal excess-distortion exponent satisfies
∗
Esp
(R) = Λ∗X 2 (α),

(29)

where α ∈ [σ 2 , r22 ) is implicitly determined by R through the equation
R = Rsp (α).

(30)

– For the i.i.d. Gaussian codebook, the optimal excess-distortion exponent is
∗
Eiid
(R) = Λ∗X 2 (α),

(31)

where α ≥ σ 2 is implicitly determined by R through the equation

R = Riid (s∗ (α), α).

(32)

The proof of Theorem 3 is provided in Section VI. Several remarks are in order.
First, as can be gleaned in the proof of Theorem 3 (cf. Lemma 7), Rsp (z) and Riid (s∗ (z), z) are both increasing functions
2
of z if z ≥ σ 2 and Rsp (σ 2 ) = Riid (s∗ (σ 2 ), σ 2 ) = 12 log σD . Furthermore, Λ∗X 2 (t) > 0 for t > σ 2 and Λ∗X 2 (t) = 0 otherwise.
2
∗
∗
∗
Combining these two facts, we can conclude that Esp
(R) and Eiid
(R) are both positive for rates R > 21 log σD . That Esp
(R) > 0
2
1
σ
for R > 2 log D recovers the achievability part of [3, Theorem 3] without recourse to Wyner’s theorem [23].
Second, for the i.i.d. Gaussian codebook, if we consider that each codeword is generated according to (6) with σ 2 replaced
α
. Under this scenario, by particularizing the result to a
by α ∈ R+ , then the right hand side of (32) is replaced by 12 log D
GMS, we can recover the achievability result of Ihara and Kubo [17].2
Furthermore, one may wonder the performance comparison of large deviations for the spherical and i.i.d. Gaussian codebooks.
We give a complete answer to this question in the following lemma.
Lemma 4. For any rate R >

1
2

2

log σD , we have
∗
∗
Eiid
(R) > Esp
(R).

(33)

The proof of Lemma 4 is given in Appendix B. To illustrate the result in Lemma 4, we plot optimal excess-distortion
exponents of spherical and i.i.d. Gaussian codebooks for a discrete and a Rayleigh distribution in Figure 1. We verify from
Figure 1 that for both numerical examples, the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than
2
the spherical Gaussian codebook for any rate R > 12 log σD .

IV. P ROOF

OF

S ECOND -O RDER A SYMPTOTICS (T HEOREM 1)

A. Preliminaries for the Spherical Codebook
In this subsection, we present some definitions and preliminary results for spherical Gaussian codebooks. For simplicity, let
the variance or power of Y be PY := σ 2 − D. Furthermore, for any ε ∈ (0, 1), let
V := Var[X 2 ] = ζ − σ 4 ,
r
log n
,
an := V
n
r
V −1
bn :=
Q (ε),
n

2 Note

that we use α while Ihara and Kubo [17] use α2 to mean the same quantity.

(34)
(35)
(36)

7

0.7

∗
Esp
(R)
∗
Eiid
(R)
R = 12 log

Bounds on the optimal error exponent

1.6

1.4

Bounds on the optimal error exponent

1.8

σ2
D

1.2

1

0.8

0.6

0.4

∗
Esp
(R)
∗
Eiid
(R)
R = 12 log

0.6

σ2
D

0.5

0.4

0.3

0.2

0.1

0.2

0

0
0

0.2

0.4

0.6

0.8

1

1.2

1.4

0

0.2

0.4

0.6

0.8

Rate R

Rate R

(a) Discrete

(b) Rayleigh

1

1.2

1.4

∗ (R) and E (R) for a memoryless source distributed according to a discrete and a Rayleigh distribution. The discrete
Fig. 1. Excess-distortion exponents Esp
iid
distribution is ternary with support X = {a, 2a, 3a} where a2 = 0.3σ2 and its probability mass function is PX = [1/2, 1/3, 1/6] so that E[X 2 ] = σ2 .
The Rayleigh distribution has scale parameter σ2 /2 so that E[X 2 ] = σ2 . Note that α is determined through R by (30) for the spherical Gaussian codebook
and by (32) for the i.i.d. Gaussian codebook.

where the second equality in (34) follows from the definition in (2). Note that for any xn , Pr{d(xn , Y n ) ≤ D} depends on
xn only through its norm kxn k. For any xn such that n1 kxn k2 = z > 0, let
Ψ(n, z) := Pr{d(xn , Y n ) ≤ D}

(37)

= Pr{kxn − Y n k2 ≤ nD}

(38)

= Pr{2hxn , Y n i ≥ n(z + PY − D)}


√
n(z + PY − D)
√
,
= Pr Y1 ≥
2 z

(41)

= Pr{kxn k2 + kY n k2 − 2hxn , Y n i ≤ nD}
= Pr{nz + nPY − 2hxn , Y n i ≤ nD}

(39)
(40)

(42)

where Y1 is the √
first element of sequence Y n = (Y1 , . . . , Yn ) and (42) follows because Y n is spherically symmetric so we
n
may take x = ( nz, 0, . . . , 0) (cf. [9]).
n
source sequence
let fZ
Let Z := n1 kX n k2 be the random variable representing the average power of a √
√ X √. Furthermore,
√
2
be the corresponding probability distribution function (pdf) of Z. Recall that r2 = σ − D + D = PY + D (cf. (27))
and let
p
√
(43)
r1 := PY − D.
√
√
Kostina and Verdú [7, Theorem 37] showed that for any z such that z < r1 or z > r2 ,
Ψ(n, z) = 0,

(44)


 n−1
2
Γ( n+2
(z + PY − D)2
2 )
1−
Ψ(n, z) ≥ √
=: g(n, z),
n+1
4zPY
πnΓ( 2 )

(45)

and otherwise

where Γ(·) is the Gamma function. Hence, from (8) and (44), we conclude that the excess-distortion probability for the spherical
Gaussian codebook equals to
Z r22
2
2
(1 − Ψ(n, z))M fZ (z) dz.
(46)
Pe,n = Pr{Z < (max{0, r1 }) } + Pr{Z > r2 } +
(max{0,r1 })2

8

B. Achievability Proof for the Spherical Gaussian Codebook
Using the definition of g(·) in (45), we conclude that g(n, z) is a decreasing function of z if z ≥ |PY − D|. Invoking the
definitions of bn in (36), r1 in (43) and r2 in (27), we conclude that r12 ≤ |PY − D| and r22 ≥ σ 2 + bn for n large enough.
Thus, combining (45), (46) and noting that Ψ(n, z) ≤ 1, for sufficiently large n, we can upper the excess-distortion probability
as follows:
Z σ2 +bn
(1 − g(n, z))M fZ (z) dz + Pr{Z > σ 2 + bn }
Pe,n ≤ Pr{Z < |PY − D|} +
(47)
|PY −D|

≤ Pr{Z < |PY − D|} +

Z

σ2 +bn

|PY −D|

exp{−M g(n, z)}fZ (z) dz + Pr{Z > σ 2 + bn },

≤ Pr{Z < |PY − D|} + exp{−M g(n, σ 2 + bn )} + Pr{Z > σ 2 + bn }

(48)
(49)

where (48) follows since (1 − a)M ≤ exp{−M a} for any a ∈ [0, 1); and (49) follows since g(n, z) is decreasing in z for
z ≥ |PY − D|. Let the third central moment of X 2 be defined as


T := E |X 2 − σ 2 |3 .
(50)

Using the definitions of V in (34), T in (50) and the Berry-Esseen theorem, we conclude that
 X

n
1
Pr{Z < |PY − D|} = Pr
Xi2 < |σ 2 − 2D|
n i=1
r 

 n
6T
2
2
+ Q σ − |σ − 2D|
≤ √
V
n V3/2
2 

2
2
2n σ − |σ − 2D|
6T
≤ √
+ exp −
V
n V3/2


1
=O √ ,
n

(51)
(52)
(53)
(54)

2

where (53) follows since Q(a) ≤ exp{− a2 } while (54) follows since T (cf. (50)) is finite for sources satisfying (2) and
σ 2 − |σ 2 − 2D| > 0 due to the fact that σ 2 > D. Similarly, using the definition of bn in (36) and the Berry-Esseen theorem,
we have

 X
n
1
2
2
2
(55)
X > σ + bn
Pr{Z > σ + bn } = Pr
n i=1 i
6T
≤ε+ √
n V3/2


1
≤ε+O √ .
n

(56)
(57)

Choose M such that

1
log n
log M = − log g(n, σ + bn ) + log
2



1
σ2
bn
log n
=n
log
+ 2 +O
2
D
2σ
n
2
p
σ
n
+ nV(σ 2 , ζ)Q−1 (ε) + O(log n),
= log
2
D
2



(58)
(59)
(60)

√
n+1
where (59) follows from the Taylor expansion of g(n, σ 2 + bn ) (cf. (45)) and noting that Γ( n+2
2 )/Γ( 2 ) = Θ( n); and (60)
follows from the definition of bn (cf. (36)) and V(σ 2 , D) (cf. (18)). Thus, with the choice of M in (58), we conclude that
1
exp{−M g(n, σ 2 + bn )} = √ .
n

(61)

Hence, combining (49), (54), (57) and (61), we have shown that there exists a sequence of (n, M )-codes satisfying (60) and
lim sup Pe,n ≤ ε.
n→∞

(62)

9

C. Ensemble Converse for the Spherical Gaussian Codebook
We now show that the result in (20) is ensemble tight. From Stam’s paper [26, Eq. (4)], the distribution of Y1 is
 n−3

2
Γ( n2 )
1
y2
fY1 (y) = √
1−
1{y 2 ≤ nPY }.
n−1
nPY
πnPY Γ( 2 )

(63)

Recall the definitions of an in (35) and bn in (36). Define the sets
P := {r ∈ R : bn < r − σ 2 ≤ an },

(64)

Q := {r ∈ R : r + PY − D ≥ 0}.
√
√
−D)
√Y
≤ nPY , using the definition of Ψ(·) in (42), we obtain that
Then, for any z ∈ P ∩ Q satisfying n(z+P
2 z


√
n(z + PY − D)
√
Ψ(n, z) = Pr Y1 ≥
2 z

 n−3
Z √nPY
2
Γ( n2 )
y2
1
√
1
−
= √
dy
n(z+PY −D)
nPY
πnPY Γ( n−1
√
2 )
2 z
 n−3

Z √nPY
2
Γ( n2 )
(z + PY − D)2
1
√
≤ √
1
−
dy
n−1
n(z+PY −D)
4zPY
πnPY Γ( 2 )
√
2 z

 n−3
2
(z + PY − D)2
1 Γ( n2 )
1−
≤ √
n−1
4zPY
π Γ( 2 )



n
Γ(
)
1
(z + PY − D)2
n−3
2
= √
=: g(n, z),
log
1
−
exp
π Γ( n−1
2
4zPY
2 )

(65)

(66)
(67)

(68)

(69)
(70)

√

−D)
√Y
where (67) follows from the definition in (63) and the condition that z ∈ Q (cf. (65)) which implies n(z+P
≥0>
2 z
√
2
y
− nPY ; (68) follows since (1 − nPY ) is decreasing in y for positive y; and (69) follows by enlarging the integration region
√
n(z+PY −D)
√
2 z

≥ 0). Note that g(n, z) is decreasing in z for z ≥ |PY − D| and g(n, z) ≥ 0 for all z ∈ P. Hence,
√
√
−D)
√Y
for any z ∈ P ∩ Q such that n(z+P
> nPY , we still have g(n, z) ≥ Ψ(n, z).
2 z
Recall that Z = n1 kX n k2 and fZ is the corresponding pdf of Z. Thus, according to (8), for n sufficiently large, we have

(recall that

Pe,n = EX n [(1 − Pr{d(X n , Y n ) ≤ D})M |X n ]
Z ∞
=
(1 − Ψ(n, z))M fZ (z) dz
0
Z ∞
≥
(1 − g(n, z))M 1{z ∈ P ∩ Q}fZ (z) dz
0
Z
(1 − g(n, σ 2 + bn ))M fZ (z) dz
≥
z∈P∩Q


Z
g(n, σ 2 + bn )
exp − M
≥
fZ (z) dz
1 − g(n, σ 2 + bn )




Zz∈P∩Q
1
g(n, σ 2 + bn )
g(n, σ 2 + bn )
exp − M
≥
1 M
≤ √
fZ (z)dz
1 − g(n, σ 2 + bn )
1 − g(n, σ 2 + bn )
n
z∈P∩Q  Z


1
1
g(n, σ 2 + bn )
≤ √
≥ 1− √
fZ (z)dz
1 M
2
1
−
g(n,
σ
+
b
)
n
n
n
 z∈P∩Q



1 − g(n, σ 2 + bn ) 1
1
√
Pr Z ∈ P ∩ Q, M ≤
= 1− √
n
g(n, σ 2 + bn )
n


 
1
1
= 1− √
Pr Z ∈ P ∩ Q, log M ≤ log(1 − g(n, σ 2 + bn )) − log g(n, σ 2 + bn ) − log n
2
n


 
1
1
≥ 1− √
Pr Z ∈ P ∩ Q, log M ≤ − log 2 − log g(n, σ 2 + bn ) − log n} ,
2
n

(71)
(72)
(73)
(74)
(75)
(76)
(77)
(78)
(79)
(80)

where (72) follows from the definition of Ψ(n, z) in (42); (73) follows by restricting z ∈ P ∩ Q and using the definition of
a
g(·) in (70); (74) follows since g(n, z) is decreasing in z for z ∈ P ∩ Q; (75) follows since (1 − a)M ≥ exp{−M 1−a
} for
g(n,z)
1
√
,
exp{−a}
is
decreasing
in
a,
and
exp{−a}
≥
1
−
a
for
a
≥
0;
and
(80)
any a ∈ [0, 1); (77) follows since M 1−g(n,z) ≤ n
1
2
follows since g(n, z) ≤ 2 for n large enough if z > σ .

10

Combining (70), (80) and applying a Taylor expansion of g(n, σ 2 + bn ) similarly to (59), we conclude that for any (n, M )code such that
1
log M ≤ − log 2 − log n − log g(n, σ 2 + bn )
(81)
2



2
σ
bn
log n
1
,
(82)
log
+ 2 +O
=n
2
D
2σ
n
we have
Pe,n



1
≥ 1− √
Pr{Z ∈ P ∩ Q}.
n

(83)

The following lemma is essential to complete the converse proof.
Lemma 5. Consider any source X such that (2) are satisfied and σ 2 < ∞. Then, we have


1
Pr{Z ∈ P ∩ Q} ≥ ε + O √ .
n

(84)

The proof of Lemma 5 is deferred to Appendix A.
Using the definition of V(σ 2 , ζ) in (18), the definition of bn in (36), the bounds in (82), (83), and Lemma 5, we conclude
that for any sequence of (n, M )-codes such that
n
σ2 p
log M ≤ log
(85)
+ nV(σ 2 , ζ)Q−1 (ε) + O(log n),
2
D
we have
lim sup Pe,n ≥ lim inf Pe,n ≥ ε
n→∞

n→∞

(86)

as desired.
D. Preliminaries for the I.I.D. Gaussian Codebook
Now we consider the i.i.d. Gaussian codebook (cf. (6)). Note that Pr{d(xn , Y n ) ≤ D} depends on xn only through its
norm kxn k (cf. [17]). Given any sequence xn such that n1 kxn k2 = z, define
Υ(n, z) := Pr{d(xn , Y n ) ≤ D}.

(87)

From (6), we obtain that
fYiidn (y n )

1
exp
=
2
(2π(σ − D))n/2




ky n k2
.
−
2(σ 2 − D)

(88)

Since fYiidn (y n ) is decreasing in ky n k, we conclude that Υ(n, z) is a decreasing function of z (cf. [17]). Using the definition
of Υ(·) in (87), we have
Υ(n, z) = Pr{kxn − Y n k2 ≤ nD}

X
n
√
(Yi − z)2 ≤ nD
= Pr

(89)
(90)

i=1

= Pr




n
√ 2
1 X
D
(Yi − z) ≥ −
−
.
nPY i=1
PY

(91)

√
where (90) follows since the probability depends on xn only through its power and thus we can choose xn such that x√
z
i =
1
2
for all i ∈ [1 : n] (cf. [9, Eq. (94)]). For the i.i.d. Gaussian codebook, each Yi ∼ N (0, PY ) and hence PY (Yi − z) is
distributed according to a non-central χ2 distribution with one degree of freedom.
Given z and s, let
κ(s, z) :=

(PY (1 + 2s) + 2z)2
PY (1 + 2s)3

(92)

Using the result of [27, Section 2.2.12] concerning the cumulant generating function of a non-central χ2 distribution, the
definition of Riid (·) in (23), the definition of s∗ (·) in (24), and the Bahadur-Ranga Rao (strong large deviations) theorem for
non-lattice random variables [25, Theorem 3.7.4], we obtain
Υ(n, z) ∼

exp{−nRiid(s∗ (z), z)}
p
,
s∗ (z) κ(s∗ (z), z)2πn

n → ∞.

(93)

11

E. Achievability Proof for the I.I.D. Gaussian Codebook
According to (8), the excess-distortion probability under the i.i.d. Gaussian codebook can be upper bounded as follows:
i
h
(94)
Pe,n = E (1 − Pr{d(X n , Y n ) ≤ D})M X n
Z ∞
=
(1 − Υ(n, z))M fZ (z) dz
(95)
0

≤

Z

≤

Z

σ2 −an

0
σ2 +bn

σ2 −an

fZ (z) dz +

Z

σ2 +bn

σ2 −an

(1 − Υ(n, z))M fZ (z) dz +

Z

∞

fZ (z) dz

(96)

σ2 +bn

exp{−M Υ(n, z)}fZ (z) dz + Pr{Z < σ 2 − an } + Pr{Z > σ 2 + bn }

≤ exp{−M Υ(n, σ 2 + bn )} + Pr{Z < σ 2 − an } + Pr{Z > σ 2 + bn },

(97)
(98)

where (96) follows since Υ(n, z) ≥ 0; (97) follows since (1−a)M ≤ exp{−M a}; and (98) follows since Υ(n, z) is decreasing
in z and Pr{σ 2 − an ≤ Z ≤ σ 2 + bn } ≤ 1.
Using the definitions of Riid (·) in (23) and s∗ (·) in (24), we have
Riid (s∗ (σ 2 + bn ), σ 2 + bn )
p
p
PY + PY2 + 4(σ 2 + bn )D z(PY − 2D + PY2 + 4(σ 2 + bn )D)
1
p
= log
+
2
2D
2PY (PY + PY2 + 4(σ 2 + bn )D)
p
PY − 2D + PY2 + 4(σ 2 + bn )D
−
4PY
2
σ
bn
1
+ 2 + O(b2n ),
= log
2
D r
2σ
 
V(σ 2 , ζ) −1
1
σ2
1
= log
,
+
Q (ε) + O
2
D
n
n

(99)
(100)
(101)

where (100) follows from a Taylor expansion at z = σ 2 and recalling that PY = σ 2 − D; and (101) follows from the definitions
of V(σ 2 , ζ) in (18) and bn in (36).
Choose M such that


1
2
log n .
(102)
log M ≥ − log Υ(n, σ + bn ) + log
2
Then, we have
1
exp{−M Υ(n, σ 2 + bn )} ≤ √ .
n
Furthermore, using the result in (93) and (101), we obtain
σ2 p
n
+ nV(σ 2 , ζ)Q−1 (ε) + O(log n).
log M ≥ log
2
d
Similarly as the proof of Lemma 5, using the Berry-Esseen theorem and the definition of an in (35), we obtain
r

 X
n
log n
1
2
2
2
(X − σ ) < V
Pr{Z < σ − an } = Pr
n i=1 i
n
p
6T
≤ Q( log n) + √
n V3/2


1
=O √ .
n

(103)

(104)

(105)
(106)
(107)

Hence, combining (57), (98), (103) and (107), we conclude that there exists a sequence of (n, M )-codes using i.i.d. Gaussian
codebooks with M satisfying (104) and
lim sup Pe,n ≤ ε.

(108)

n→∞

F. Ensemble Converse for the I.I.D. Gaussian Codebook
The ensemble converse proof for the i.i.d. Gaussian codebook is omitted since it is similar to the ensemble converse proof
for the spherical Gaussian codebook in Section IV-C starting from (71) except for the following two points: i) replace g(n, z)
with Υ(n, z); ii) replace P ∩ Q with P.

12

V. P ROOF

OF

M ODERATE D EVIATION A SYMPTOTICS (T HEOREM 2)

A. Preliminaries
The following slight strengthening of the Chernoff bound [24, Theorem B.4.1] is crucial in our proof.
Lemma 6. Given an i.i.d. sequence X n , suppose that the cumulant generating function Λ|X| (θ) is finite for some positive
number θ. Then for any t > E[X],

 X
n
1
Xi > t ≤ exp{−nΛ∗X (t)}.
(109)
Pr
n i=1
and for any t < E[X],
Pr



n

1X
Xi < t
n i=1



≤ exp{−nΛ∗X (t)}.

(110)

In both cases, Λ∗X (t) > 0.
In other words, if the threshold t deviates from the mean by a constant amount, the probability in question decays
exponentially fast.
B. Achievability Proof for the Spherical Gaussian Codebook
Let
cn := 2σ 2 ξn .

(111)

The proof of the achievability follows from Section IV-B up till (49) with cn taking the role of bn . Invoking Lemma 6, we
conclude that under the conditions in Theorem 2, we have

 X
n
1
2
X < |PY − D|
(112)
Pr{Z < |PY − D|} = Pr
n i=1 i
≤ exp{−nt1 }
2

2

(113)
2

for some t1 > 0 since |PY − D| = |σ − 2D| < σ due to the fact that σ > D. Invoking the moderate deviations theorem [25,
Theorem 3.7.1] and the definition of V in (34), we conclude that
 X

n
1
2
2
Pr{Z > σ 2 + cn } = Pr
(114)
(X − σ ) > cn
n i=1 i


nc2
= exp − n + o(nc2n )
(115)
2V


nξn2
+ o(nξn2 ) ,
(116)
= exp −
2V(σ 2 , ζ)
where (116) follows from the definitions of V(σ 2 , ζ) in (18), V in (34) and cn in (111).
Recall the definition of g(·) in (45). Choose M such that
log M = − log g(n, σ 2 + cn ) + log n


1
σ2
=n
log
+ ξn + o(ξn ) ,
2
D

(117)
(118)

where (118) follows from a Taylor expansion similar to (59), the definition of cn in (111), and the conditions on ξn in (13).
With this choice of M , we have
exp{−M g(n, σ 2 + cn )} = exp(−n).

(119)

Combining the results in (49), (113), (116), (118) and (119), we conclude that there exists a sequence of (n, M )-codes such
that


n
σ2
1
≤ 1,
(120)
log M − log
lim sup
2
D
n→∞ nξn
1
1
lim inf − 2 log Pe,n ≥
.
(121)
n→∞
nξn
2V(σ 2 , ζ)

13

C. Ensemble Converse Proof for the Spherical Gaussian Codebook
The converse proof follows from Section IV-C up till (83). However, we use (P ′ , cn ) in place of (P, bn ) where
P ′ := {r ∈ R : ξn < r − σ 2 < 2ξn }.

(122)

Now recall the definition of g(·) in (70). Applying a Taylor expansion similar to (118), invoking Lemma 6, and using the
moderate deviations theorem in [25, Theorem 3.7.1], we conclude that for any (n, M )-code such that
1
log M ≤ − log 2 − log n − log g(n, σ 2 + cn )
2


σ2
1
log
+ ξn + o(ξn ) ,
=n
2
D

(123)
(124)

we have
Pe,n
≥ exp
1 − √1n






4nξn2
nξn2
2
2
+ o(nξn ) − exp −
+ o(nξn ) − exp{−nt2 },
−
2V(σ 2 , ζ)
2V(σ 2 , ζ)

(125)

for some t2 > 0. Note that the first term on the right hand side of (125) dominates as n → ∞. From the results in (124)
and (125), we conclude that for any sequence of (n, M )-codes such that


n
σ2
1
≤ 1,
(126)
log M − log
lim sup
2
D
n→∞ nξn
we have
lim inf −
n→∞

1
1
1
log Pe,n ≤ lim sup − 2 log Pe,n ≤
.
2
nξn
nξn
2V(σ 2 , ζ)
n→∞

(127)

D. Proof for the I.I.D. Gaussian Codebook
The proof for i.i.d. Gaussian codebooks is similar to the proof in Section IV-E and IV-F with the use of Lemma 6 and [25,
Theorem 3.7.1] as in Sections V-B and V-C and is thus omitted.
VI. P ROOF

OF

L ARGE D EVIATION A SYMPTOTICS (T HEOREM 3)

A. Preliminaries
The following properties of the quantities Rsp (z) in (22), Riid (s∗ (z), z) (cf. (23) and (24)) and Λ∗X 2 (t) in (26) are useful
in the proof of Theorem 3.
Lemma 7. The following claims hold.
(i) Concerning Rsp (z),
(a) Rsp (z) is increasing in z if z ≥ |σ 2 − 2D|;
2
(b) Rsp (σ 2 ) = 12 log σD , limz→r22 Rsp (z) = ∞.
(ii) Concerning Riid (s∗ (z), z),
(a) s∗ (z) > 0 if and only if z > max(0, 2D − σ 2 );
2
(b) Riid (s∗ (z), z) = 0 if z = max{0, 2D − σ 2 } and Riid (s∗ (σ 2 ), σ 2 ) = 12 log σD ;
(c) Riid (s∗ (z), z) = sups≥0 Riid (s, z) and thus Riid (s∗ (z), z) is increasing in z for z ≥ max{0, 2D − σ 2 }.
(iii) Concerning Λ∗X 2 (t) (cf. [25, Chapter 3]),
(a) Λ∗X 2 (t) is convex and non-decreasing in t for t ≥ 0;
(b) Λ∗X 2 (t) = 0 if t ≤ σ 2 ;
(c) Λ∗X 2 (t) is increasing in t for t ≥ σ 2 .
The proof of Lemma 7 is omitted since it follows either from simple algebra or from [25, Chapter 3].
Furthermore, we have the following lemma concerning an important property of the function g(n, z) (cf. (45)), which plays
an important role in proving the ensemble tight excess-distortion exponent for spherical Gaussian codebooks.
Lemma 8. For any α ∈ [σ 2 , r22 ), there exists a unique β ∈ (r12 , |σ 2 − 2D|) such that
g(n, β) = g(n, α),
2

α + β ≤ 2σ .
The proof of Lemma 8 is given in Appendix C.

(128)
(129)

14

B. Achievability Proof for the Spherical Gaussian Codebook
Recall that PY = σ 2 − D. Invoking the definitions of r1 in (43) and g(·) in (45), we concluce that r12 ≤ |σ 2 − 2D| < σ 2 ,
g(n, z) is decreasing in z if z ∈ (|σ 2 − 2D|, r22 ) and g(n, z) is increasing in z if z ∈ (r12 , |σ 2 − 2D|)
Using the expression for the excess-distortion probability in (46), given any α such that α ∈ [σ 2 , r22 ), we can upper bound
Pe,n as follows

 X
 Z r22
 X
n
n
1
1
(1 − Ψ(n, z))M fZ (z) dz
(130)
Xi2 < r12 + Pr
Xi2 > r22 +
Pe,n ≤ Pr
n i=1
n i=1
r12
 X

 X
 Z |σ2 −2D|
n
n
1
1
≤ Pr
Xi2 < β + Pr
Xi2 > α +
(1 − g(n, z))M fZ (z) dz
n i=1
n i=1
β
Z α
+
(1 − g(n, z))M fZ (z) dz
(131)
|σ2 −2D|
n
X


n
1X 2
Xi > α + (1 − g(n, α))M
n i=1
i=1

 X

 X
n
n
1
1
(Xi2 − σ 2 ) > σ 2 − β} + Pr
Xi2 > α + exp{−M g(n, α)}
≤ Pr
n i=1
n i=1

 X
n
1
X 2 > α + exp{−M g(n, α)},
≤ 2 Pr
n i=1 i
= Pr



1
n

(Xi2 − σ 2 ) < β − σ 2



+ Pr



(132)
(133)
(134)

where (131) follows from the result in Lemma 8 which states that there exists a unique β ∈ (r22 , |σ 2 − 2D|) such that
g(n, β) = g(n, α) for any α ∈ [σ 2 , r22 ); (132) follows since i) g(n, z) is decreasing for z ≥ |σ 2 − 2D| and α ≥ σ 2 > |σ 2 − 2D|,
ii) g(n, z) is increasing for z ∈ (r12 , |σ 2 − 2D|); and iii) the result in Lemma 8 which states that g(n, β) = g(n, α) (cf. (128))
and β ∈ (r12 , |σ 2 − 2D|); (133) follows since (1 − a)M ≤ exp{−M a} for any a ∈ [0, 1); and (134) follows since 2σ 2 − β ≥ α,
which is implied by (129) in Lemma 8.
Now, given any positive δ ∈ (0, 1), recalling the definition of Rsp (·) in (22), we choose M such that
√
πnΓ( n+1
2 )
log M = (1 + δ)(n − 1)Rsp (α) + log
.
(135)
n+2
Γ( 2 )
Using the definitions of Rsp (·) in (22) and g(n, z) in (45), we obtain that

exp{−M g(n, z)} = exp − exp{(n − 1)δRsp (α)} ,

(136)

which vanishes doubly exponentially fast for α ≥ σ 2 . Invoking Cramér’s Theorem [25, Theorem 2.2.3] and the definition of
Λ∗X 2 (·) in (26), we obtain that
 X

n

1
Pr
(137)
Xi2 > α ≤ exp − nΛ∗X 2 (α) .
n i=1
√
√
n+2
Therefore, using (134), (135), (136), (137) and noting that πnΓ( n+1
2 )/Γ( 2 ) = Θ(1/ n), we conclude that for all
α ∈ [σ 2 , r22 ), there exists a sequence of (n, M )-codes such that
lim

n→∞

1
log M = (1 + δ)Rsp (z),
n

(138)

1
log Pe,n ≥ Λ∗X 2 (α).
(139)
n
Now, note that σ 2 > |σ 2 − 2D| due to the fact that σ 2 > D. Recall that Rsp (z) is increasing in z for z ≥ σ 2 (cf. Claim (i)(a)
2
in Lemma 7) and Rsp (σ 2 ) = 21 log σD (cf. Claim (i)(b) in Lemma 7). Hence, by letting δ ↓ 0, (138) and (139) imply that for
2
all R ≥ 12 log σD , there exists a sequence of (n, M )-codes such that
lim inf −
n→∞

1
log M = R,
n
and (139) both hold, where α is determined from R = Rsp (α) (cf. (22)).
2
The proof for R ∈ [0, 12 log σD ) follows trivially by noting that any (n, M )-code satisfies that Pe,n ≤ 1.
lim

n→∞

(140)

15

C. Ensemble Converse Proof for the Spherical Gaussian Codebook
Fix any α such that α ∈ [σ 2 , r22 ) (cf. (27) for the definition of r2 ). Let
P̃ := {r ∈ R : α ≤ r < r22 },
2

Q̃ := {r ∈ R : r − |σ − 2D| ≥ 0}.
Note that r ∈ Q̃ implies that r + (σ 2 − 2D) ≥ 0.
Using the result in (8) and the definition of g(·) in (70), we conclude that for sufficiently large n,
Z r22
(1 − g(n, z))M 1{z ∈ P̃ ∩ Q̃}fZ (z) dz
Pe,n ≥
α
 X

n
1
M
2
≥ (1 − g(n, α)) Pr
X ∈ P̃ ∩ Q̃
n i=1 i
  X


n
1
g(n, α)
2
X ∈ P̃ ∩ Q̃
Pr
≥ exp − M
1 − g(n, α)
n i=1 i

 X
n

1
2
X ∈ P̃ ∩ Q̃ ,
≥ exp − 2M g(n, α) Pr
n i=1 i

(141)
(142)

(143)
(144)
(145)
(146)

where (144) follows since g(n, z) is decreasing in z for z ≥ |σ 2 − 2D| and α ≥ σ 2 > |σ 2 − 2D|; (145) follows since
a
} for any a ∈ [0, 1); and (146) follows since g(n, α) ≤ 21 for n sufficiently large.
(1 − a)M ≥ exp{−M 1−a
For any M such that
1
log n,
2
using (146) and the inequality that exp{−a} ≥ 1 − a, we have that for sufficiently large n,
  X


n
1
1
2
Pr
X ∈ P̃ ∩ Q̃ .
Pe,n ≥ 1 − √
n
n i=1 i
log M ≤ − log g(n, α) − log 2 −

(147)

(148)

Note that

n
1X 2
Xi ∈ P̃ ∩ Q̃
n i=1


n
1X 2
= Pr max{α, |σ 2 − 2D|} ≤
Xi < r22
n i=1


 X
 X
n
n
1
1
Xi2 ≥ α − Pr
Xi2 ≥ r22 ,
= Pr
n i=1
n i=1

Pr



(149)
(150)

where the final equality holds because α2 is chosen to be in [σ 2 , r22 ) so α2 ≥ σ 2 > |σ 2 − 2D|. Invoking Cramér’s theorem [25,
Theorem 2.2.3], we obtain that for sufficiently large n and any positive number δ ∈ (0, 1),

 X
n
1
2
X ∈ P̃ ∩ Q̃
Pr
n i=1 i




(151)
≥ exp − n(1 + δ)Λ∗X 2 (α) − exp − n(1 + δ)Λ∗X 2 (r22 )


1
(152)
≥ exp − n(1 + δ)Λ∗X 2 (α) ,
2
where (152) holds since σ 2 ≤ α < r22 and Λ∗X 2 (t) (cf. (26)) is increasing in t for all t ≥ σ 2 (cf. Claim (iii)(c) in Lemma 7).
Invoking the definition of g(·) in (70), the definition of Rsp (·) in (22), and the bounds in (147), (148), (152), we conclude
that for any sequence of (n, M )-codes and any α ∈ [σ 2 , r22 ) if
1
log M ≤ Rsp (α),
n

(153)

1
log Pe,n ≤ (1 + δ)Λ∗X 2 (α).
n

(154)

lim sup
n→∞

then
lim inf −
n→∞

16

Note that σ 2 > |σ 2 − 2D| because σ 2 > D. Recall that Rsp (z) is increasing in z for z ≥ σ 2 (cf. Claim (i)(a) in Lemma 7)
2
and Rsp (σ 2 ) = 12 log σD (cf. Claim (i)(b) in Lemma 7). Hence, the converse proof is complete by letting δ ↓ 0 and noting that
Λ∗X 2 (t) = 0 if t ≤ σ 2 (cf. Claim (iii)(b) in Lemma 7).
D. Achievability Proof for the I.I.D. Gaussian Codebook
Fix α such that α > max{0, 2D − σ 2 }. Invoking the conclusion in (93), for any xn such that
for sufficiently large n and any positive δ,


1
Υ n, kxn k2 ≥ Υ(n, α)
n
≥ exp{−n(1 + δ)Riid (s∗ (α), α)}.

1
n 2
n kx k

Invoking (8), the excess-distortion probability can be upper bounded as follows
i
h
Pe,n = EX n (1 − Pr{d(X n , Y n ) ≤ D})M |X n
Z ∞
=
(1 − Υ(n, z))M fZ (z) dz
0

 X
Z α
n
1
Xi2 > α
=
(1 − Υ(n, z))M fZ (z) dz + Pr
n i=1
0
 X

Z α
n
M
1
1 − exp{−n(1 + δ)Riid (s∗ (α), α)} fZ (z) dz + Pr
≤
Xi2 > α
n i=1
0

 X
n

1
Xi2 > α ,
≤ exp − M exp{−n(1 + δ)Riid (s∗ (α), α)} + Pr
n i=1

≤ α, we have that
(155)
(156)

(157)
(158)
(159)
(160)
(161)

where (158) follows from the definition of Υ(·) in (87); (159) follows since Υ(n, z) ≤ 1; (160) follows from (156); and (161)
follows since (1 − a)M ≤ exp{−M a} for any a ∈ [0, 1).
Recall the definitions of s∗ (·) in (24) and Riid (·) in (23). Choose M such that
log M = n(1 + 2δ)Riid (s∗ (α), α).

(162)

Invoking the definition of Λ∗X 2 (·) in (26), the conclusion in (161) and Cramér’s Theorem [25, Theorem 2.2.3], we conclude
that for sufficiently large n and arbitrary positive δ,



Pe,n ≤ exp − exp nδRiid (s∗ (α), α) + exp − nΛ∗X 2 (α) .
(163)
2

Recall that Riid (s∗ (σ 2 ), σ 2 ) = 12 log σD and Riid (s∗ (z), z) is positive and increasing for z > max(0, 2D − σ 2 ) (cf. Claim
(ii) in Lemma 7. Thus, the first term in (163) vanishes doubly exponentially fast since α > max(0, 2D − σ 2 ). From (162)
and (163), we conclude that for any α > max(0, 2D − σ 2 ), there exists a sequence of (n, M )-codes such that
lim

n→∞

lim inf −
n→∞

1
log M = (1 + 2δ)Riid (s∗ (α), α),
n

1
log Pe,n ≥ Λ∗X 2 (α).
n

(164)
(165)

The proof of the achievability part is done by letting δ ↓ 0 and using the fact that Λ∗X 2 (t) = 0 if t ≤ σ 2 (cf. Claim (iii)(b) in
Lemma 7).
E. Ensemble Converse Proof for the I.I.D. Gaussian Codebook
Fix any α such that α > max{0, 2D − σ 2 }. Using the strong large deviations result in (93), we conclude that for n large
enough and any positive number δ ∈ (0, 1), given any xn such that n1 kxn k2 ≥ α,


1 n 2
Υ n, kx k ≤ Υ(n, α)
(166)
n
≤ exp{−n(1 − δ)Riid (s∗ (α), α)}.
(167)
From (8) and (167), we conclude that for sufficiently large n,
Z ∞
(1 − Υ(n, z))M fZ (z) dz
Pe,n =
0

(168)

17

≥

Z

∞

Zα∞

(1 − Υ(n, z))M fZ (z) dz

(169)


M
1 − exp − n(1 − δ)Riid (s∗ (α), α)
fZ (z) dz
(170)
α

 X
n


1
X2 > α ,
(171)
≥ exp − 2M exp − n(1 − δ)Riid (s∗ (α), α) Pr
n i=1 i

a
where (171) follows because i) (1−a)M ≥ exp{−M 1−a
} and ii) for n sufficiently large, exp −n(1−δ)Riid(s∗ (α), α) ≤ 21 .
Using the bound in (171) and Cramér’s theorem [25, Theorem 2.2.3], we conclude that for any α > max(0, 2D − σ 2 ), if M
is chosen such that
≥

log M ≤ n(1 − δ)Riid (s∗ (α), α) − log n − log 2,
then for sufficiently large n, using the inequality exp(−a) ≥ 1 − a for a ∈ [0, 1), we obtain



1
exp − n(1 + δ)Λ∗X 2 (α) .
Pe,n ≥ 1 −
n

(172)

(173)

Hence, given any α > max(0, 2D − σ 2 ), we have shown that for any seqeunce of (n, M )-codes such that
lim sup
n→∞

1
log M ≤ (1 − δ)Riid (s∗ (α), α),
n

(174)

1
log Pe,n ≤ (1 + δ)Λ∗X 2 (α).
n

(175)

we have
lim inf −
n→∞
2

Finally, recall that Riid (s∗ (σ 2 ), σ 2 ) = 12 log σD and Riid (s∗ (z), z) is positive and increasing for z > max(0, 2D − σ 2 )
(cf. Claim (ii) in Lemma 7). Thus, the converse proof is complete by letting δ ↓ 0 and using the fact that Λ∗X 2 (t) = 0 if t ≤ σ 2
(cf. Claim (iii)(b) in Lemma 7).
A PPENDIX
A. Proof of Lemma 5
Note that T (cf. (50)) is finite since E[X 6 ] is finite (cf. (2)). Using the definitions of an in (35), bn in (36), P in (64), and
the Berry-Esseen theorem, we obtain
 X

 X

n
n
1
1
2
2
2
2
(176)
Pr{Z ∈ P} = Pr
X > σ + bn − Pr
X > σ + an
n i=1 i
n i=1 i
r
r
 X


 X
n
n
V −1
1
log n
1
2
2
2
2
= Pr
(X − σ ) >
(X − σ ) > V
(177)
Q (ε) − Pr
n i=1 i
n
n i=1 i
n


p
6T
6T
√
−
Q(
(178)
≥ε− √
log
n)
+
n V3/2
n V3/2


1
≥ε+O √ ,
(179)
n
2

where (179) follows since Q(x) ≤ exp{− x2 } and T is finite. Similarly, using the definition of Q in (65) and the Berry-Esseen
theorem, we obtain

 X
n
1
2
X + PY − D ≤ 0
(180)
Pr{Z ∈
/ Q} = Pr
n i=1 i

 X
n
1
2
2
2
X ≤ σ + (D − PY − σ )
(181)
= Pr
n i=1 i
 X

n
1
2
2
= Pr
(182)
X ≤ σ − 2PY
n i=1 i

 r
6T
n
PY + √
(183)
≤Q 2
V
n V3/2


6T
2nPY
+√
(184)
≤ exp −
V
n V3/2

18



1
=O √ ,
n

(185)

where (185) follows since the first term in (184) vanishes exponentially fast and is thus dominated by the second term.
Combining (179) and (185), we have
Pr{Z ∈ P ∩ Q} ≥ Pr{Z ∈ P} − Pr{Z ∈
/ Q}


1
≥ε+O √ .
n

(186)
(187)

B. Proof of Lemma 4
For simplicity, in the proof of Lemma 4, for any z ∈ R+ , we let

∗
Riid
(z) := Riid (s∗ (z), z).

(188)

Recalling the results in (29) and (31), we find that the optimal excess-distortion exponents of the spherical and i.i.d Gaussian
codebooks for a given rate R are determined by the corresponding parameters α in Λ∗X 2 (α) (cf. (26)). Using conclusions (i)
∗
and (ii) regarding the increasing properties of Rsp (z) and Riid
(z) in Lemma 7, we obtain that for any given R, there exists
unique αsp (R) and αiid (R) such that,
Rsp (αsp (R)) = R,
∗
Riid
(αiid (R))

= R.

(189)
(190)

From conclusion (iii) in Lemma 7, we know that Λ∗X 2 (t) is an increasing function of t for t ≥ σ 2 . Thus, to prove Lemma 4,
2
it suffices to show that given any rate R > 12 log σD , we have
For any R ≥ Riid (s

∗

(r22 ), r22 ),

αsp (R) < αiid (R).

(191)

αiid (R) ≥ r22 ≥ αsp (R),

(192)

we have

since αsp (R) < r22 for any R ∈ [σ 2 , ∞) (cf. (22)).
2
∗
(r22 )). Recall that both Rsp (z) and Riid (z)
In the following, we will show that (191) also holds for any R ∈ ( 12 log σD , Riid
2
2 2
∗
are increasing in z for z ∈ (σ , r2 ) (cf. Lemma 7). Thus, to prove (191) for R ∈ ( 12 log σD , Riid
(r22 )) is equivalent to show
2 2
that for any z ∈ (σ , r2 ),
∗
Rsp (z) > Riid
(z).

(193)

∗
lim Rsp (z) = ∞ > Riid
(r22 ).

(194)

∗
Rsp (z1 ) = Riid
(r22 ).

(195)

From Lemma 7, we have that
z→∞

Therefore, there exists z1 ∈ (σ 2 , r22 ) such that

∗
Using the increasing nature of Rsp (z) and Riid
(z), we conclude that for any z ∈ [z1 , r22 ), we have
∗
∗
Rsp (z) > Rsp (z1 ) = Riid
(r22 ) > Riid
(z).

(196)

∗
Note that Rsp (z1 ) > Riid
(z1 ). Thus, there exists z2 ∈ (σ 2 , z1 ) such that for any z ∈ [z2 , z1 ), we have
∗
∗
(z).
Rsp (z) > Rsp (z2 ) = Riid
(z1 ) > Riid

(197)

Similarly, we can show that there exists a sequence of values {zi }i≥3 such that zi ∈ (σ 2 , zi−1 ), limi→∞ zi = σ 2 , and for each
z ∈ [zi , zi−1 ), we have
∗
∗
(zi−1 ) > Riid
(z).
Rsp (z) > Rsp (zi ) = Riid

We illustrate the proof idea in Figure 2.

(198)

19

Rate functions

Rsp (z)
∗
Riid
(z)

σ2

z3 z2

z

r22

z1

Fig. 2. Illustration of the proof idea for (193).

C. Proof of Lemma 8
Recall that PY = σ 2 − D. Given any z ∈ R+ , let
h(z) :=

(z + PY − D)2
.
4zPY

(199)

Recall the definition of g(n, z) in (45), we conclude that it suffices to show that for any α ∈ [σ 2 , r22 ), there exists a unique
β ∈ (r12 , |σ 2 − 2D|) such that
h(α) = h(β), α + β ≤ 2σ 2 .

(200)

By simple algebra, we obtain that
z 2 − (σ 2 − 2D)2
∂h(z)
=
,
∂z
4z 2 (σ 2 − D)
h(r12 ) = h(r22 ) = 1.

(201)
(202)
2

2D|, r22 )
2

Note that (201) implies that the function h(z) is increasing in z for z ∈ [|σ −
and decreasing in z for z ∈
(r12 , |σ 2 − 2D|). Hence, using (202), we can conclude that, given any α ∈ [σ 2 , r22 ] ⊆ [|σ − 2D|, r22 ), there exists a unique
β ∈ (r12 , |σ 2 − 2D|) such that h(α) = h(β). Thus, in the following, we just need to show that β ≤ 2σ 2 − α. By noticing that
h(z) ≤ h(α) = h(β) only for all z ∈ [α, β], we conclude that it suffices to show that h(2σ 2 − α) ≤ h(α). To illustrate our
arguments here, we plot h(z) in Figure 3 for the case where σ 2 = 12 and D = 3.
For any α ∈ [σ 2 , r22 ), by calculation, we find that
h(α) − h(2σ 2 − α) =

(α − σ 2 )((α − σ 2 )2 + 4D(D − σ 2 ))
.
2α(σ 2 − D)(α − 2σ 2 )

(203)

Since α ∈ [σ 2 , r22 ), using the definitions of r1 in (43) and r2 in (27), we have r22 < r12 + r22 = 2σ 2 and thus α < 2σ 2 . Recalling
the fact that σ 2 > D, we conclude that
2α(σ 2 − D)(α − 2σ 2 ) < 0.

(204)

20

1

0.95

0.9

h(z)

0.85

0.8

0.75

β
|σ 2 − 2D|
σ2
α

0.7

0.65

0.6
0

5

10

15

20

25

z
Fig. 3. Plot for h(z).

Furthermore, for any α ∈ [σ 2 , r22 ), we have α − σ 2 ≥ 0.

(α − σ 2 )2 + 4D(D − σ 2 ) < (r22 − σ 2 )2 + 4D(D − σ 2 ) = 0.

(205)

Therefore, combining (203), (204) and (205), we conclude that h(2σ 2 − α) ≤ h(α) and thus completing the proof of Lemma
8.
R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]

A. El Gamal and Y.-H. Kim, Network Information Theory. Cambridge University Press, 2011.
C. E. Shannon, “Coding theorems for a discrete source with a fidelity criterion,” IRE Nat. Conv. Rec, vol. 4, no. 142-163, p. 1, 1959.
A. Lapidoth, “On the role of mismatch in rate distortion theory,” IEEE Trans. Inf. Theory, vol. 43, no. 1, pp. 38–47, 1997.
V. Strassen, “Asymptotische abschätzungen in shannons informationstheorie,” in Trans. Third Prague Conf. Information Theory, 1962, pp. 689–723.
M. Hayashi, “Second-order asymptotics in fixed-length source coding and intrinsic randomness,” IEEE Trans. Inf. Theory, vol. 54, no. 10, pp. 4619–4637,
2008.
Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Trans. Inf. Theory, vol. 56, no. 5, pp. 2307–2359,
2010.
V. Kostina and S. Verdú, “Fixed-length lossy compression in the finite blocklength regime,” IEEE Trans. Inf. Theory, vol. 58, no. 6, pp. 3309–3338,
2012.
A. Ingber and Y. Kochman, “The dispersion of lossy source coding,” in IEEE Data Compression Conference (DCC), 2011, pp. 53–62.
J. Scarlett, V. Y. F. Tan, and G. Durisi, “The dispersion of nearest-neighbor decoding for additive Non-Gaussian channels,” IEEE Trans. Inf. Theory,
vol. 63, no. 1, pp. 81–92, 2017.
A. Lapidoth, “Nearest neighbor decoding for additive non-Gaussian noise channels,” IEEE Trans. Inf. Theory, vol. 42, no. 5, pp. 1520–1529, 1996.
Y. Altuğ and A. B. Wagner, “Moderate deviations in channel coding,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4417–4426, 2014.
Y. Polyanskiy and S. Verdú, “Channel dispersion and moderate deviations limits for memoryless channels,” in Proc. 48th Annu. Allerton Conf., 2010,
pp. 1334–1339.
V. Y. F. Tan, “Moderate-deviations of lossy source coding for discrete and Gaussian sources,” in IEEE ISIT, 2012, pp. 920–924.
L. Zhou, V. Y. F. Tan, and M. Motani, “Second-order and moderate deviation asymptotics for successive refinement,” IEEE Trans. Inf. Theory, vol. 63,
no. 5, pp. 2896–2921, 2017.
I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
R. G. Gallager, Information Theory and Reliable Communication. New York: Wiley, 1968.
S. Ihara and M. Kubo, “Error exponent for coding of memoryless Gaussian sources with a fidelity criterion,” IEICE Trans. Fundamentals, vol. 83,
no. 10, pp. 1891–1897, 2000.
K. Marton, “Error exponent for source coding with a fidelity criterion,” IEEE Trans. Inf. Theory, vol. 20, no. 2, pp. 197–199, 1974.
J. Scarlett, “Reliable communication under mismatched decoding,” Ph.D. dissertation, Department of Engineering, University of Cambridge, 2014.
J. Scarlett, A. Martinez, and A. Guillén i Fàbregas, “Mismatched decoding: Error exponents, second-order rates and saddlepoint approximations,” IEEE
Trans. Inf. Theory, vol. 60, no. 5, pp. 2647–2666, May 2014.
R. Gallager, “The random coding bound is tight for the average code (corresp.),” IEEE Trans. Inf. Theory, vol. 19, no. 2, pp. 244–246, 1973.
R. G. Gallager, “Fixed composition arguments and lower bounds to error probability,” MIT, 6.441 Supplementary notes, Jul 1994,
http://www.rle.mit.edu/rgallager/documents/notes5.pdf.
A. D. Wyner, “Random packings and coverings of the unit n-sphere,” Bell Syst. Tech. J., vol. 46, no. 9, pp. 2111–2118, 1967.
N. Bouleau and D. Lépingle, Numerical Methods for Stochastic Processes. Wiley, 1993.
A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications. Springer-Verlag Berlin Heidelberg, 2009, vol. 38.

21

[26] A. Stam, “Limit theorems for uniform distributions on spheres in high-dimensional Euclidean spaces,” J. Appl. Probab., vol. 19, no. 1, pp. 221–228,
1982.
[27] H. Tanizaki, Computational methods in statistics and econometrics. CRC Press, 2004.

