betaFeedback

WorksComputer Science

Third-Order Asymptotics for Fixed-Length Lossy Compression of Discrete Memoryless Sources

Abstract

This paper determines the third-order asymptotics of the logarithm of the minimum codebook size for fixed-length lossy compression of discrete memoryless sources. For an excess-distortion probability constraint ε∈(0,1)\varepsilon\in(0,1) and every interior distortion level, we establish a third-order correction of 12log⁡n+O(1)\frac12\log n+O(1), where nn is the blocklength. This sharpens the general bounds of Kostina and Verdú [IEEE Trans. Inf. Theory, 2012]. The main technical innovation lies in the converse for positive dispersion. Under a reverse change of measure, we retain the exponential weights associated with tilted information and distortion slack and control them jointly using the multivariate weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [Proc. IEEE ISIT, 2015]. A pairing argument verifies the required covariance nondegeneracy uniformly over all reconstruction words whose distortion balls meet a typical set, yielding the matching converse.

Introduction

Lossy source coding, a fundamental problem in Shannon theory, seeks to compress a source subject to a prescribed reconstruction distortion. For a discrete memoryless source Xn=(X1,…,Xn)∼PnX^n=(X_1,\ldots,X_n)\sim P^n and a single-letter distortion function dd, Shannon [1] showed that the minimum asymptotically achievable compression rate under an average distortion constraint DD is the rate-distortion function

R(P,D)=min⁡W:EP×W[d(X,Y)]≤DI(P,W),(1)R(P,D)=\min_{W:\mathbb{E}_{P\times W}[d(X,Y)]\le D} I(P,W), \tag*{(1)}

where the minimization is over all conditional distributions WW, or test channels, from the source alphabet to the reconstruction alphabet. Lossy source coding underpins widely used image and video compression standards, including JPEG and MPEG.

Beyond this first-order characterization, Marton [2] used the type covering lemma to determine the error exponent which governs the exponential decay of the excess-distortion probability at fixed rates above R(P,D)R(P,D). For fixed rates below R(P,D)R(P,D), Omura [3] obtained an early bound on the probability of meeting the distortion constraint. The optimal strong converse exponent, which characterizes the exponential decay of this probability, is given in Csiszár and Körner [4 Problem 9.6]. The present author [5] studied the moderate deviations regime.

In this paper, we study fixed-error asymptotics, where the excess-distortion probability is constrained to be at most a fixed ε∈(0,1)\varepsilon\in(0,1), independent of the blocklength. Our object of interest is M∗(n,D,ε)M^*(n,D,\varepsilon), the minimum number of reconstruction codewords required by a length-nn code whose probability of exceeding distortion DD is at most ε\varepsilon.

Under their respective regularity assumptions, Ingber and Kochman [6 Theorem 1] and Kostina and Verdú [7 Theorem 12] independently established the second-order expansion

log⁡M∗(n,D,ε)=nR(P,D)+nV(P,D)Q−1(ε)+O(log⁡n)(2)\log M^*(n,D,\varepsilon)=nR(P,D)+\sqrt{nV(P,D)}Q^{-1}(\varepsilon)+O(\log n) \tag*{(2)}

for fixed ε∈(0,1)\varepsilon\in(0,1), where QQ is the complementary CDF of the standard Gaussian distribution. The coefficient V(P,D)V(P,D) is called the excess distortion dispersion in [6] and the rate-dispersion function in [7]. For finite-alphabet sources satisfying their smoothness assumptions, Ingber and Kochman [6 Eqs. (7)–(9)] express the dispersion as

V(P,D)=Var⁡P(RP′(X,D)),where RP′(x,D):=∂∂p(x)R(p,D)∣p=P.(3)V(P,D)=\operatorname{Var}_{P}\left(R'_P(X,D)\right),\qquad\text{where }R'_P(x,D):=\left.\frac{\partial}{\partial p(x)}R(p,D)\right|_{p=P}. \tag*{(3)}

Here the coordinate derivatives are defined using a differentiable extension of R(⋅,D)R(\cdot,D) off the probability simplex. Kostina and Verdú [7 Theorem 12, Eq. (83)] give the representation

V(P,D)=Var⁡P(j(X,D)),(4)V(P,D)=\operatorname{Var}_{P}(j(X,D)), \tag*{(4)}

where j(X,D)j(X,D) is the DD-tilted information (cf. Eq. (18)). We use this representation in the present work. Under the conditions of Kostina’s thesis [8 Theorem 2.2, Eq. (2.17)], the two variance expressions coincide; also see [9].

Our Main Contribution

Our main contribution is to determine the third-order term in (2) for finite-alphabet discrete memoryless sources at interior distortion levels. Specifically, we establish

log⁡M∗(n,D,ε)=nR(P,D)+nV(P,D)Q−1(ε)+12log⁡n+O(1),(5)\log M^*(n,D,\varepsilon)=nR(P,D)+\sqrt{nV(P,D)}Q^{-1}(\varepsilon)+\frac{1}{2}\log n+O(1), \tag*{(5)}

where the remainder is uniform for ε\varepsilon in any fixed compact subinterval of (0,1)(0,1). The result includes the zero-dispersion case V(P,D)=0V(P,D)=0 and does not require a unique or fully supported optimal reproduction distribution.

Kostina and Verdú [7] previously bounded the O(log⁡n)O(\log n) remainder; these bounds are reviewed in the first remark following Theorem 1. Moulin’s two ISIT 2017 papers [10], [11] stated a converse with a 12log⁡n\frac{1}{2}\log n correction and an achievability bound with an additional log⁡log⁡n\log\log n term. However, both proofs rely on incorrect auxiliary distortion-ball estimates, as explained in the fourth remark following Theorem 1. We provide independent achievability and converse proofs establishing (5).

For achievability when V(P,D)>0V(P,D)>0, we apply the quantitative delta method of Pinelis and Molzon [12] to obtain a normal approximation for the empirical distortion-ball exponent. We then average the random coding bound, controlling the excess-distortion probability to obtain the third-order term in the log codebook size.

For the converse when V(P,D)>0V(P,D)>0, we retain the exponential weights associated with tilted information and distortion slack in the reverse change of measure step. The multivariate weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [13 Lemma 3] then gives an n−1n^{-1} prefactor by controlling both coordinates jointly. A deterministic argument identifying two inequivalent frequent distortion columns verifies the required covariance nondegeneracy uniformly over all relevant reconstruction words. This uniform estimate yields the matching converse.

Logarithmic corrections have a long history in lossy source coding. Pilc [14] obtained an achievability refinement for the minimum expected distortion at a fixed coding rate, and Zhang, Yang, and Wei [15] established the matching asymptotic correction for finite-alphabet memoryless sources under their regularity assumptions. Yang and Zhang [16] extended redundancy achievability results to abstract alphabets. These works already identify a correction proportional to log⁡n2n\frac{\log n}{2n} in expected distortion, with a coefficient determined by the slope of the distortion-rate function. Their criterion differs from the fixed excess-distortion probability considered here: an expected-distortion expansion does not determine the fixed-ε\varepsilon expansion. More recently, Sriramu and Wagner [17 Theorem III.1] determined the logarithmic redundancy coefficient for variable-length coding of uniform sources with permutation-symmetric distortion measures. Under both almost-sure and expected distortion constraints, they established a redundancy of log⁡n2n+o(log⁡nn)\frac{\log n}{2n}+o\left(\frac{\log n}{n}\right) in the minimum expected rate. The present paper considers fixed-length coding under a fixed excess-distortion probability constraint and determines the expansion up to a bounded remainder.

Classical distortion-ball estimates provide another important connection. Yang and Zhang [16 Theorem 3] give product-measure ball bounds with an n−1/2n^{-1/2} prefactor. Related pointwise expansions and distorted waiting-time asymptotics appear in Kontoyiannis [18] and Dembo and Kontoyiannis [19], respectively. These results identify the local probability scale underlying the 12log⁡n\frac{1}{2}\log n correction. Related logarithmic corrections also arise in channel coding and exact channel synthesis. Tomamichel and Tan [20] established a 12log⁡n+O(1)\frac{1}{2}\log n+O(1) upper bound on the third-order term for discrete memoryless channels with positive ε\varepsilon-dispersion. Under a positive reverse-dispersion condition, this matches Polyanskiy’s achievability bound [21 Corollary 54]. For exact channel synthesis, Sriramu and Wagner [22 Theorems 1 and 2] determined the coefficient of log⁡n\log n in the minimum expected communication length for full-support nonsingular discrete memoryless channels.

The weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [13 Lemma 3] used in our converse generalizes Polyanskiy’s scalar exponentially weighted tail bound [21 Lemma 20]. Both estimates originate in finite blocklength channel coding.

Problem Formulation and Main Result

Source Model and Definitions

Let Xn=(X1,…,Xn)∼PnX^n=(X_1,\ldots,X_n)\sim P^n be a length-nn block from a discrete memoryless source with finite alphabet X\mathcal{X}, and let Y\mathcal{Y} be a finite reconstruction alphabet. Here PnP^n denotes the nn-fold product distribution of PP, and X∼PX\sim P denotes a generic source symbol. By restricting the source alphabet to supp⁡(P):={x:P(x)>0}\operatorname{supp}(P):=\{x:P(x)>0\}, we may assume that PP has full support on X\mathcal{X}.

For a finite alphabet A\mathcal{A}, let P(A)\mathcal{P}(\mathcal{A}) denote the set of probability mass functions on A\mathcal{A}. We use PP for the fixed source distribution, p∈P(X)p\in\mathcal{P}(\mathcal{X}) for a generic source distribution, q∈P(Y)q\in\mathcal{P}(\mathcal{Y}) for a reproduction distribution, and W(y∣x)W(y|x) for the conditional probability of reproducing yy given source symbol xx. The source distribution pp and conditional distribution WW induce the joint distribution and output marginal (p×W)(x,y):=p(x)W(y∣x)(p\times W)(x,y):=p(x)W(y|x) and (pW)(y):=∑x∈Xp(x)W(y∣x)(pW)(y):=\sum_{x\in\mathcal{X}}p(x)W(y|x). We identify probability mass functions with their probability vectors. For a positive integer MM, write [M]={1,…,M}[M]=\{1,\ldots,M\}. All logarithms are natural, so information is measured in nats.

For a deterministic vector xn∈Xnx^n\in\mathcal{X}^n, we denote its type or empirical distribution as

P^xn(a):=1n∑i=1n1{xi=a},a∈X.(6)\widehat{P}_{x^n}(a):=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\{x_i=a\},\qquad a\in\mathcal{X}. \tag*{(6)}

Let Pn(X)\mathcal{P}_n(\mathcal{X}) be the set of all nn-types (empirical distributions of length-nn vectors). For P^∈Pn(X)\widehat{P}\in\mathcal{P}_n(\mathcal{X}), let

Tn(P^):={xn∈Xn:P^xn=P^}(7)\mathcal{T}_n(\widehat{P}):=\{x^n\in\mathcal{X}^n:\widehat{P}_{x^n}=\widehat{P}\} \tag*{(7)}

be the type class of P^\widehat{P} [4]. Types and type classes on Y\mathcal{Y} are defined analogously, with reproduction types denoted by Q^\widehat{Q}. Norms of finite-dimensional vectors are Euclidean, and neighborhoods of probability distributions are relative to the probability simplex.

The distortion function d:X×Y→[0,∞)d:\mathcal{X}\times\mathcal{Y}\to[0,\infty) is bounded from above. Define the nn-letter distortion function and maximum distortion as

dn(xn,yn):=1n∑i=1nd(xi,yi)anddmax⁡:=max⁡x,yd(x,y).(8)d_n(x^n,y^n):=\frac{1}{n}\sum_{i=1}^{n}d(x_i,y_i)\quad\text{and}\quad d_{\max}:=\max_{x,y}d(x,y). \tag*{(8)}

Definition 1 (Non-asymptotic fundamental limits for lossy compression). An (n,M,D,ε)(n,M,D,\varepsilon)-code for the (fixed-length) lossy compression problem consists of an encoder fn:Xn→[M]f_n:\mathcal{X}^n\to[M] and a decoder φn:[M]→Yn\varphi_n:[M]\to\mathcal{Y}^n such that the probability of excess distortion

Pr⁡(dn(Xn,φn(fn(Xn)))>D)≤ε.(9)\Pr\left(d_n(X^n,\varphi_n(f_n(X^n)))>D\right)\le\varepsilon. \tag*{(9)}

For a positive integer nn, distortion level D≥0D\ge0, and error tolerance ε∈(0,1)\varepsilon\in(0,1), define the non-asymptotic fundamental limit

M∗(n,D,ε):=min⁡{M∈N:∃ (n,M,D,ε)-code}.(10)M^*(n,D,\varepsilon):=\min\{M\in\mathbb{N}:\exists\ (n,M,D,\varepsilon)\text{-code}\}. \tag*{(10)}

If the feasible set is empty, M∗(n,D,ε)=+∞M^*(n,D,\varepsilon)=+\infty.

We now review some known results for this non-asymptotic fundamental limit, putting our main result in context. For a source distribution pp, define the average distortion, mutual information, rate-distortion function, minimum achievable distortion, and zero-rate distortion threshold as follows:

Ep×W[d(X,Y)]:=∑x,yp(x)W(y∣x)d(x,y),(11)\mathbb{E}_{p\times W}[d(X,Y)]:=\sum_{x,y}p(x)W(y|x)d(x,y), \tag*{(11)}
I(p,W):=∑x,yp(x)W(y∣x)log⁡W(y∣x)(pW)(y),(12)I(p,W):=\sum_{x,y}p(x)W(y|x)\log\frac{W(y|x)}{(pW)(y)}, \tag*{(12)}
R(p,D):=min⁡W:Ep×W[d(X,Y)]≤DI(p,W),(13)R(p,D):=\min_{W:\mathbb{E}_{p\times W}[d(X,Y)]\le D}I(p,W), \tag*{(13)}
Dmin⁡(p):=∑xp(x)min⁡yd(x,y),(14)D_{\min}(p):=\sum_x p(x)\min_y d(x,y), \tag*{(14)}
Dzr(p):=min⁡y∑xp(x)d(x,y).(15)D_{\mathrm{zr}}(p):=\min_y\sum_x p(x)d(x,y). \tag*{(15)}

Throughout, we assume that the source-distortion pair (P,D)(P,D) satisfies Dmin⁡(P)<D<Dzr(P)D_{\min}(P)<D<D_{\mathrm{zr}}(P). Hence, R(P,D)>0R(P,D)>0. Choose an optimal conditional distribution (also called test channel) W∗W^* that achieves the minimum in the definition of the rate-distortion function in (13). Let q∗=PW∗q^*=PW^* be the induced output distribution. Let λ>0\lambda>0 be a distortion multiplier at (P,D)(P,D), meaning that −λ-\lambda is a subgradient of R(P,⋅)R(P,\cdot) at DD. Equivalently,

R(P,D′)≥R(P,D)−λ(D′−D)for every D′≥Dmin⁡(P).(16)R(P,D') \ge R(P,D)-\lambda(D'-D) \qquad\text{for every }D'\ge D_{\min}(P). \tag*{(16)}

Lemma 2 establishes uniqueness of the distortion multiplier at every D∈(Dmin⁡(P),Dzr(P))D\in(D_{\min}(P),D_{\mathrm{zr}}(P)). Consequently, R(P,⋅)R(P,\cdot) is differentiable on this interval and λ=−∂DR(P,D)\lambda=-\partial_D R(P,D). Following Kostina and Verdú [7 Sec. II-C, Eq. (28)], for a reproduction distribution q∈P(Y)q\in\mathcal{P}(\mathcal{Y}) define the generalized DD-tilted information as

Λq(x,θ):=−log⁡∑yq(y)eθ(D−d(x,y)),θ≥0.(17)\Lambda_q(x,\theta):=-\log\sum_y q(y)e^{\theta(D-d(x,y))}, \qquad\theta\ge0. \tag*{(17)}

The DD-tilted information is

ȷ(x,D):=Λq∗(x,λ)=−log⁡Zx−λDwhere Zx:=∑yq∗(y)e−λd(x,y).(18)\jmath(x,D):=\Lambda_{q^*}(x,\lambda)=-\log Z_x-\lambda D \qquad\text{where }Z_x:=\sum_y q^*(y)e^{-\lambda d(x,y)}. \tag*{(18)}

The rate-dispersion function [7] is defined as

V(P,D):=Var⁡P(ȷ(X,D)).(19)V(P,D):=\operatorname{Var}_P(\jmath(X,D)). \tag*{(19)}

We will also use the notations ϕ(x):=12πe−x2/2\phi(x):=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}, Φ(t):=∫−∞tϕ(x) dx\Phi(t):=\int_{-\infty}^{t}\phi(x)\,\mathrm{d}x, and Q(t):=1−Φ(t)Q(t):=1-\Phi(t) to denote the standard Gaussian probability density function, cumulative distribution function (CDF) and complementary CDF respectively. In the following, positive constants denoted by C,cC,c may change from line to line; they do not depend on nn or on the variables over which a bound is stated to be uniform.

Main Result and Discussions

Our main result is stated as follows.

Theorem 1 (Third-order asymptotics of lossy compression). Under the preceding assumptions, as n→∞n\to\infty, uniformly for ϵ\epsilon in any compact subinterval of (0,1)(0,1),

log⁡M∗(n,D,ϵ)=nR(P,D)+nV(P,D)Q−1(ϵ)+12log⁡n+O(1).(20)\log M^*(n,D,\epsilon)=nR(P,D)+\sqrt{nV(P,D)}Q^{-1}(\epsilon)+\frac{1}{2}\log n+O(1). \tag*{(20)}

Let Δn\Delta_n denote the third-order remainder in the expansion of log⁡M∗(n,D,ϵ)\log M^*(n,D,\epsilon), i.e.,

Δn:=log⁡M∗(n,D,ϵ)−[nR(P,D)+nV(P,D)Q−1(ϵ)].(21)\Delta_n:=\log M^*(n,D,\epsilon)-\left[nR(P,D)+\sqrt{nV(P,D)}Q^{-1}(\epsilon)\right]. \tag*{(21)}

Theorem 1 says that

Δn=12log⁡n+O(1).(22)\Delta_n=\frac{1}{2}\log n+O(1). \tag*{(22)}

The achievability and converse are proved in Sections III and § 4, respectively. A few remarks are in order.

  1. Kostina and Verdú [7 Theorem 12] show for general stationary memoryless sources satisfying regularity conditions that Δn\Delta_n satisfies, for nn sufficiently large,

−12log⁡n−K≤Δn≤Clog⁡n+log⁡log⁡n+K,(23)-\frac{1}{2}\log n-K\le\Delta_n\le C\log n+\log\log n+K, \tag*{(23)}

where CC and KK are source- and distortion-dependent constants. For the biased binary source under the Hamming distortion [7 Theorem 23] with 0<D<min⁡xP(x)0<D<\min_x P(x),

−K≤Δn≤12log⁡n+log⁡log⁡n+K.(24)-K\le\Delta_n\le\frac{1}{2}\log n+\log\log n+K. \tag*{(24)}

For a uniform source on an mm-symbol alphabet under Hamming distortion [7 Theorem 27], Kostina and Verdú show that V(P,D)=0V(P,D)=0 and that (22) holds for 0<D<1−1/m0<D<1-1/m. Our result tightens (23) for discrete memoryless sources and identifies the third-order term.

  1. For an i.i.d. N(0,σ2)\mathcal{N}(0,\sigma^2) source under squared-error distortion with 0<D<σ20<D<\sigma^2, Kostina and Verdú [7 Theorem 40] show that V(P,D)=1/2V(P,D)=1/2 and that, for fixed ϵ\epsilon and all sufficiently large nn, (24) holds for some constant KK. Mahmood’s recent joint source–channel coding bounds [23 Theorems 2 and 4] give the matching expansion in (22) upon setting the channel block size to one bit and all erasure probabilities to zero.

  1. Under Hamming distortion, the case D=0D=0 corresponds to almost-lossless compression. For a source with positive varentropy V(P):=Var⁡P(−log⁡P(X))V(P):=\operatorname{Var}_{P}(-\log P(X)), Strassen [24 Theorem 1.1] showed that, for fixed ϵ\epsilon,

log⁡M∗(n,0,ϵ)=nH(P)+nV(P)Q−1(ϵ)−12log⁡n+O(1).(25)\log M^*(n,0,\epsilon)=nH(P)+\sqrt{nV(P)}Q^{-1}(\epsilon)-\frac{1}{2}\log n+O(1). \tag*{(25)}

The coefficient of log⁡n\log n changes sign at the lossless endpoint. Figure 1 illustrates how the same n−1/2n^{-1/2} factor enters the two arguments.

Diagram comparing almost-lossless and lossy source coding

Figure 1. The origin of the opposite logarithmic corrections in almost-lossless and lossy source coding. Almost-lossless source coding. Count the selected source words. ιn(xn)≤b\iota_n(x^n) \le b. Xn\mathcal{X}^n. Mcount=∣{xn:ιn(xn)≤b}∣M_{\mathrm{count}} = \left|\left\{x^n:\iota_n(x^n)\le b\right\}\right|. Mcount≍n−1/2ebM_{\mathrm{count}}\asymp n^{-1/2}e^b. log⁡Mcount=b−12log⁡n+O(1)\log M_{\mathrm{count}}=b-\frac{1}{2}\log n+O(1). Lossy source coding. Sum the probabilities in the ball. BD(xn)\mathcal{B}_D(x^n). Yn\mathcal{Y}^n. Dot area ∝\propto probability mass. pcov=∑yn∈BD(xn)q∗n(yn)p_{\mathrm{cov}}=\sum_{y^n\in\mathcal{B}_D(x^n)}q^{*n}(y^n). pcov≍n−1/2e−an(xn)p_{\mathrm{cov}}\asymp n^{-1/2}e^{-a_n(x^n)} (Lower bound in (54)). Mcov≍1/pcovM_{\mathrm{cov}}\asymp1/p_{\mathrm{cov}} at fixed covering probability η\eta. log⁡Mcov=an(xn)+12log⁡n+O(1)\log M_{\mathrm{cov}}=a_n(x^n)+\frac{1}{2}\log n+O(1).

For almost-lossless coding, write ιn(xn):=−log⁡Pn(xn)\iota_n(x^n):=-\log P^n(x^n), the self-information of xnx^n. The optimal code represents the most probable source sequences, with ties resolved as needed at a (1−ϵ)(1-\epsilon)-quantile bb of ιn(Xn)\iota_n(X^n). The number of sequences at or below bb is

Mcount=∣{xn:ιn(xn)≤b}∣=ebE[e−(b−ιn(Xn))1{ιn(Xn)≤b}].(26)M_{\mathrm{count}}=\left|\left\{x^n:\iota_n(x^n)\le b\right\}\right|=e^b\mathbb{E}\left[e^{-(b-\iota_n(X^n))}\mathbf{1}\{\iota_n(X^n)\le b\}\right]. \tag*{(26)}

The exponential weight makes the count depend mainly on words within a constant distance below bb. A sufficiently wide window of fixed width there has probability of order n−1/2n^{-1/2}. A window strictly below bb also gives a lower bound when only some sequences at bb are represented. Thus the code size is of order n−1/2ebn^{-1/2}e^b.

For lossy coding at a fixed interior distortion, fix a source sequence xnx^n whose type is close to PP and draw a reconstruction word from q∗q^*. Exponentially tilt the reconstruction distribution so that the total distortion has mean nDnD. The change-of-measure weight concentrates the contribution near nDnD, where a window of sufficiently large constant width has tilted probability of order n−1/2n^{-1/2}. The covering probability pcovp_{\mathrm{cov}} is therefore of order n−1/2e−an(xn)n^{-1/2}e^{-a_n(x^n)} (cf. (54) in Lemma 3 and [16 Eq. (3.17)]), where

an(xn):=sup⁡θ≥0∑i=1nΛq∗(xi,θ).(27)a_n(x^n):=\sup_{\theta\ge0}\sum_{i=1}^{n}\Lambda_{q_*}(x_i,\theta). \tag*{(27)}

Its Taylor approximation about PP is

an(xn)=∑i=1nj(xi,D)+O(n∥P^xn−P∥2).(28)a_n(x^n)=\sum_{i=1}^{n}j(x_i,D)+O\left(n\left\|\hat{P}_{x^n}-P\right\|^2\right). \tag*{(28)}

To cover xnx^n with probability at least a fixed η∈(0,1)\eta\in(0,1), the number McovM_{\mathrm{cov}} of independent reconstruction draws needed is of order 1/pcov1/p_{\mathrm{cov}}, hence of order nean(xn)\sqrt{n}e^{a_n(x^n)}. Taking the logarithm gives the +12log⁡n+\frac{1}{2}\log n correction in the achievability argument.

  1. We give counterexamples to distortion-ball estimates in Moulin’s two ISIT 2017 papers using binary Hamming distortion. Take

P(1)=38,D=14,q∗(1)=14,(29)P(1)=\frac{3}{8},\qquad D=\frac{1}{4},\qquad q_*(1)=\frac{1}{4}, \tag*{(29)}

where q∗q_* is an optimal reproduction distribution. Write R=R(P,D)R=R(P,D) and ζ=log⁡3\zeta=\log3.

In the converse paper [10], fix xn∈Tn(P)x^n\in\mathcal{T}_n(P) and let Uq∗U_{q_*} be the uniform distribution on the type class Tn(q∗)\mathcal{T}_n(q_*). For these marginals, D=1/4D=1/4 lies strictly between the minimum distortion 1/81/8 and the distortion 7/167/16 under independence, as required by Proposition 4.1 in [10]. The total Hamming distortion is S:=ndn(xn,Yn)=5n8−2N11S:=nd_n(x^n,Y^n)=\frac{5n}{8}-2N_{11}, where N11N_{11} counts positions at which both sequences equal one. For n≡8(mod16)n\equiv8\pmod{16}, every attainable value of SS is odd, whereas nDnD is even. The shell {nD−n−1/2<S≤nD}\{nD-n^{-1/2}<S\le nD\} contains no integer other than nDnD along this subsequence. Its width in normalized distortion is n−3/2n^{-3/2}, which satisfies the prescribed condition n−2≪n−3/2≪n−1n^{-2}\ll n^{-3/2}\ll n^{-1}. This contradicts the positive shell asymptotic in [10 Eq. (20)].

For 16∣n16\mid n, the boundary S=nDS=nD is attained exactly when N11=3n/16N_{11}=3n/16. Counting and applying Stirling’s formula give

Uq∗(S=nD)=(5n/8n/16)(3n/83n/16)(nn/4)=e−nRn(8532π+o(1)).(30)U_{q_*}(S=nD)=\frac{\binom{5n/8}{n/16}\binom{3n/8}{3n/16}}{\binom{n}{n/4}}=\frac{e^{-nR}}{\sqrt{n}}\left(\frac{8\sqrt{5}}{3\sqrt{2\pi}}+o(1)\right). \tag*{(30)}

For marginals pp and qq, define Moulin’s fixed-marginal exponent [10 Eq. (10)] by

J(p,q,t):=min⁡π:πX=p, πY=qEπ[d(X,Y)]≤t∑x,yπ(x,y)log⁡π(x,y)p(x)q(y).(31)J(p,q,t):=\min_{\substack{\pi:\,\pi_X=p,\ \pi_Y=q\\ \mathbb{E}_{\pi}[d(X,Y)]\le t}}\sum_{x,y}\pi(x,y)\log\frac{\pi(x,y)}{p(x)q(y)}. \tag*{(31)}

where the minimization is over joint distributions π\pi. Write J(t):=J(P,q∗,t)J(t):=J(P,q_*,t). For tt near DD, the constraint is active. Indeed, mixing a joint distribution of distortion below tt with the product distribution P×q∗P\times q_*, whose distortion is 7/167/16, decreases its mutual information until the distortion reaches tt. Let π(t)\pi^{(t)} be the unique binary joint distribution with marginals PP, q∗q_* and Hamming distortion tt. Then J(t)=H(P)+H(q∗)−H(π(t))J(t)=H(P)+H(q_*)-H(\pi^{(t)}). The boundary distribution π(D)\pi^{(D)} has entries (9,1,3,3)/16(9,1,3,3)/16 in the order 00, 01, 10, 11 and attains the rate-distortion minimum, so J(D)=RJ(D)=R. The four entries of π(t)\pi^{(t)} have derivatives (−1,1,1,−1)/2(-1,1,1,-1)/2 with respect to tt. Hence

ν=−J′(D)=12log⁡9⋅31⋅3=log⁡3andγ=J′′(D)=14∑x,y1π(D)(x,y)=649.(32)\nu=-J'(D)=\frac{1}{2}\log\frac{9\cdot3}{1\cdot3}=\log3 \quad\text{and}\quad \gamma=J''(D)=\frac{1}{4}\sum_{x,y}\frac{1}{\pi^{(D)}(x,y)}=\frac{64}{9}. \tag*{(32)}

The constant in [10 Eq. (19)] is cP,q∗=4/5c_{P,q_*}=4/5. Consequently, [10 Eq. (21)] would imply

lim sup⁡n→∞16∣nnenRUq∗(S≤nD)≤cP,q∗γν=310log⁡3≈0.27.(33)\limsup_{\substack{n\to\infty\\16\mid n}}\sqrt{n}e^{nR}U_{q_*}(S\le nD)\le\frac{c_{P,q_*}}{\sqrt{\gamma}\nu}=\frac{3}{10\log3}\approx0.27. \tag*{(33)}

The boundary atom alone contributes 85/(32π)≈2.388\sqrt{5}/(3\sqrt{2\pi})\approx2.38. This contradicts the ball bound used to control π2\pi_2 in the converse [10 Eq. (41)]. There is also a separate variational error in [10]. The minimization defining J(p,q,t)J(p,q,t) in [10 Eq. (10)] fixes the output marginal qq. In our notation, the Gibbs formula immediately before [10 Eq. (11)] reads W∗(y∣x)=q(y)exp⁡{−νd(x,y)+β(x,ν)}W^*(y|x)=q(y)\exp\{-\nu d(x,y)+\beta(x,\nu)\} where β(x,ν)\beta(x,\nu) normalizes each row, and ν\nu is the Lagrange multiplier for the distortion constraint. In general, this formula produces an output marginal different from qq. Enforcing pW∗=qpW^*=q requires an additional output-dependent Lagrange multiplier in the exponent.

In the achievability paper, [11 Prop. 5.1, Eq. (37)] uses the nonlattice factor 1/ζ1/\zeta for the product reproduction distribution in this example. Under the tilted distribution, the mismatch probabilities at source symbols 0 and 1 are 1/101/10 and 1/21/2, respectively. Hence SS has mean nDnD, variance 3n/203n/20, and lattice span one. Exponential tilting and the lattice local central limit theorem give, for 8∣n8\mid n and every xn∈Tn(P)x^n\in\mathcal{T}_n(P),

q∗(S≤nD)=e−nR2πn(3/20)(32+o(1)).(34)q_*(S\le nD)=\frac{e^{-nR}}{\sqrt{2\pi n(3/20)}}\left(\frac{3}{2}+o(1)\right). \tag*{(34)}

The factor 3/23/2 comes from summing the contributions of the layers S=nD−jS=nD-j:

∑j=0∞e−ζj=11−e−ζ=32≠1log⁡3.(35)\sum_{j=0}^{\infty}e^{-\zeta j}=\frac{1}{1-e^{-\zeta}}=\frac{3}{2}\ne\frac{1}{\log3}. \tag*{(35)}

Eq. (37) is used to derive Eq. (39) in Corollary 5.2 (all in [11]), which in turn enters the achievability proof. The converse and achievability derivations thus both require corrected distortion-ball estimates. Theorem 1 confirms the 12log⁡n\frac{1}{2}\log n converse coefficient claimed in [10] and removes the log⁡log⁡n\log\log n term in [11].

Tilted Information and the Reverse Distribution

We record several properties of the quantities defined in the previous subsection that aid in the achievability and converse proofs. For each y∈Yy \in\mathcal{Y}, define the unnormalized tilted reverse subprobability mass function py(λ)p_y^{(\lambda)} and its total mass sys_y by

py(λ)(x):=P(x)eȷ(x,D)+λ(D−d(x,y)),(36)p_y^{(\lambda)}(x) := P(x)e^{\jmath(x,D)+\lambda(D-d(x,y))}, \tag*{(36)}
sy:=∑xpy(λ)(x).(37)s_y := \sum_x p_y^{(\lambda)}(x). \tag*{(37)}

Lemma 2 (Tilted information identities). At every D∈(Dmin⁡(P),Dzr(P))D \in(D_{\min}(P),D_{\mathrm{zr}}(P)), the supporting distortion multiplier is unique and satisfies

λ=−∂DR(P,D)>0.(38)\lambda= -\partial_D R(P,D) > 0. \tag*{(38)}

For every x∈Xx \in\mathcal{X}, the value of ȷ(x,D)\jmath(x,D) is independent of the choice of optimal test channel W∗W^* (a minimizer in the rate-distortion function (13)).

For any optimal test channel W∗W^* with output distribution q∗=PW∗q_* = PW^*,

EP×W∗[d(X,Y)]=D,(39)\mathbb{E}_{P \times W^*}[d(X,Y)] = D, \tag*{(39)}
W∗(y∣x)=q∗(y)e−λd(x,y)Zx,(40)W^*(y|x) = \frac{q_*(y)e^{-\lambda d(x,y)}}{Z_x}, \tag*{(40)}
EP[ȷ(X,D)]=R(P,D).(41)\mathbb{E}_P[\jmath(X,D)] = R(P,D). \tag*{(41)}

Moreover, 0<sy≤10 < s_y \le1 for every y∈Yy \in\mathcal{Y}, and sy=1s_y = 1 whenever q∗(y)>0q_*(y) > 0.

The identities in the lemma are well known in the literature. We include the proof for completeness.

Proof. The multiplier is unique if R(P,⋅)R(P,\cdot) is differentiable at DD, since −λ-\lambda is a supporting slope at that point. To apply Gallager’s differentiability result [25 Corollary 9.4.1], put

m(x):=min⁡yd(x,y),d0(x,y):=d(x,y)−m(x),D0:=D−Dmin⁡(P).(42)m(x) := \min_y d(x,y), \qquad d_0(x,y) := d(x,y)-m(x), \qquad D_0 := D-D_{\min}(P). \tag*{(42)}

Replacing dd by d0d_0 reduces the mean distortion of every test channel by EP[m(X)]=Dmin⁡(P)\mathbb{E}_P[m(X)] = D_{\min}(P). Thus, writing Rd0R_{d_0} for the rate-distortion function under d0d_0, we have Rd0(P,t)=R(P,t+Dmin⁡(P))R_{d_0}(P,t) = R(P,t+D_{\min}(P)). The distortion d0d_0 has a zero in each row, and D0D_0 lies strictly between zero and its zero-rate distortion threshold. Gallager [25 Corollary 9.4.1] gives differentiability at D0D_0, hence at DD. The unique supporting multiplier is therefore λ=−∂DR(P,D)\lambda= -\partial_D R(P,D). Evaluating the supporting inequality (16) at D′=Dzr(P)D' = D_{\mathrm{zr}}(P) gives

λ≥R(P,D)Dzr(P)−D>0.(43)\lambda\ge\frac{R(P,D)}{D_{\mathrm{zr}}(P)-D} > 0. \tag*{(43)}

This proves (38).

Let Dˉ\bar{D} be the mean distortion of an optimal test channel W∗W^*. Since Dˉ≤D\bar{D} \le D, the inequalities

R(P,D)=I(P,W∗)≥R(P,Dˉ)≥R(P,D)+λ(D−Dˉ)(44)R(P,D) = I(P,W^*) \ge R(P,\bar{D}) \ge R(P,D) + \lambda(D-\bar{D}) \tag*{(44)}

force Dˉ=D\bar{D} = D. This proves (39).

For any test channel WW with mean distortion D~\widetilde{D}, the supporting inequality (16) gives

I(P,W)+λD~≥R(P,D~)+λD~≥R(P,D)+λD.(45)I(P,W) + \lambda\widetilde{D} \ge R(P,\widetilde{D}) + \lambda\widetilde{D} \ge R(P,D) + \lambda D. \tag*{(45)}

By (39), every optimal test channel attains the right-hand side. Replacing dd by d0d_0 shifts the objective by a constant and thus preserves its minimizers.

For this minimization under d0d_0, Gallager [25, Theorem 9.4.1] gives a unique factor f0(x)f_0(x) such that every optimal channel satisfies

W∗(y∣x)=q∗(y)f0(x)P(x)e−λd0(x,y).(46)W^*(y|x)=q^*(y)\frac{f_0(x)}{P(x)}e^{-\lambda d_0(x,y)}. \tag*{(46)}

Summing over yy gives f0(x)=P(x)e−λm(x)/Zxf_0(x)=P(x)e^{-\lambda m(x)}/Z_x. Since f0(x)f_0(x) is unique and m(x)m(x) is fixed, both ZxZ_x and ȷ(x,D)=−log⁡Zx−λD\jmath(x,D)=-\log Z_x-\lambda D are independent of the choice of optimal test channel W∗W^*. Substituting this expression for f0(x)f_0(x) into the channel representation in (46) proves (40).

Using (40) and (39), we obtain

R(P,D)=I(P,W∗)=−EP[log⁡ZX]−λD=EP[ȷ(X,D)].(47)R(P,D)=I(P,W^*)=-\mathbb{E}_P[\log Z_X]-\lambda D=\mathbb{E}_P[\jmath(X,D)]. \tag*{(47)}

This proves (41).

Finally, substituting the expression for f0(x)f_0(x) into the definition of sys_y gives

sy=∑xf0(x)e−λd0(x,y).(48)s_y=\sum_x f_0(x)e^{-\lambda d_0(x,y)}. \tag*{(48)}

Gallager [25, Eq. (9.4.9)] bounds this sum by one, with equality when q∗(y)>0q^*(y)>0. Finiteness of dd and full support of PP give sy>0s_y>0. Also see [7 Eqs. (15)–(19)] for the tilted-information form of these identities.

Achievability Proof of Theorem 1

We use the random coding bound of Kostina and Verdú [7, Theorem 10], drawing reconstruction words independently from (q∗)n(q^*)^n. For each source sequence xnx^n whose type is close to PP, we lower bound the probability that one reconstruction word covers xnx^n by a constant times n−1/2e−an(xn)n^{-1/2}e^{-a_n(x^n)}. The factor n−1/2n^{-1/2} accounts for the 12log⁡n\frac{1}{2}\log n term in the achievable log codebook size.

The main refinement is to retain the random exponent an(Xn)a_n(X^n) when evaluating the covering bound. Kostina and Verdú [7, Lemma 5] bound the difference between the empirical exponent and its linear approximation in (28) by C2log⁡nC_2\log n on an event of probability 1−O(n−1/2)1-O(n^{-1/2}). This accounts for the extra C2log⁡nC_2\log n in Clog⁡n=(12+C2)log⁡nC\log n=(\frac{1}{2}+C_2)\log n in (23). When V(P,D)>0V(P,D)>0, we use (28) and the quantitative delta method of Pinelis and Molzon [12, Theorem 2.9] to approximate the distribution of an(Xn)a_n(X^n) directly, with a uniform O(n−1/2)O(n^{-1/2}) error in its distribution function. We then average the conditional covering error directly, which also avoids the separate log⁡log⁡n\log\log n term in (23). When V(P,D)=0V(P,D)=0, a direct bound on the quadratic remainder suffices.

Generalized Tilted Information and Distortion Balls

For p∈P(X)p\in\mathcal{P}(\mathcal{X}) and q∈P(Y)q\in\mathcal{P}(\mathcal{Y}), define

R0(p,q,D):=inf⁡W:Ep×W[d(X,Y)]≤D∑x,yp(x)W(y∣x)log⁡W(y∣x)q(y).(49)R_0(p,q,D):=\inf_{\substack{W:\mathbb{E}_{p\times W}[d(X,Y)]\le D}}\sum_{x,y}p(x)W(y|x)\log\frac{W(y|x)}{q(y)}. \tag*{(49)}

The associated generalized tilted information is Λq\Lambda_q in (17). Fix an optimal reproduction distribution q∗q^* and put Zx(θ)=∑yq∗(y)e−θd(x,y)Z_x(\theta)=\sum_y q^*(y)e^{-\theta d(x,y)}. The variational representations in [19 Proposition 1] and [16 Property 1] give the fixed reproduction distribution exponent

g(p):=R0(p,q∗,D)=sup⁡θ≥0∑xp(x)Λq∗(x,θ)(50)g(p):=R_0(p,q^*,D)=\sup_{\theta\ge0}\sum_x p(x)\Lambda_{q^*}(x,\theta) \tag*{(50)}
=sup⁡θ≥0{−∑xp(x)log⁡Zx(θ)−θD}.(51)=\sup_{\theta\ge0}\left\{-\sum_x p(x)\log Z_x(\theta)-\theta D\right\}. \tag*{(51)}

The block exponent an(xn)a_n(x^n) introduced in (27) satisfies the identity

an(xn)=ng(P^xn).(52)a_n(x^n)=n g(\widehat{P}_{x^n}). \tag*{(52)}

Thus gg is the per-symbol exponent, whereas ana_n is the corresponding block exponent. Furthermore, in (50)–(51), R0R_0 is an optimized expectation of generalized tilted information. Here q∗q^* is held fixed as pp varies, while θ\theta is optimized for each pp. At the true source distribution Λq∗(x,λ)=ȷ(x,D)\Lambda_{q^*}(x,\lambda)=\jmath(x,D) and g(P)=R(P,D)g(P)=R(P,D), whereas g(p)≥R(p,D)g(p)\ge R(p,D) in general. The expansion below is the counterpart, with the reproduction distribution held fixed, of Ingber and Kochman’s expansion of the fully optimized R(p,D)R(p,D) [6 Eq. (30)]; the corresponding saddlepoint argument appears in [19 Proof of Theorem 3, Eqs. (22)–(26)]. We apply Yang and Zhang’s product-ball estimate [16 Theorem 3] uniformly over nearby types.

Lemma 3 (Uniform product-ball lower bound). There exist a fixed neighborhood UU of PP, constants C,c0>0C,c_0>0, and an integer n0n_0 such that gg is smooth on UU, g(P)=R(P,D)g(P)=R(P,D), and every p∈Up\in U satisfies

∣g(p)−∑xp(x)j(x,D)∣≤C∥p−P∥2.(53)\left|g(p)-\sum_x p(x)j(x,D)\right|\le C\lVert p-P\rVert^2. \tag*{(53)}

For every n≥n0n\ge n_0, every P^∈Pn(X)∩U\widehat{P}\in\mathcal{P}_n(\mathcal{X})\cap U, and every xn∈Tn(P^)x^n\in T_n(\widehat{P}), if Yn∼q∗nY^n\sim q_*^n, then

q∗n(dn(xn,Yn)≤D)≥c0n−1/2e−ng(P^).(54)q_*^n\left(d_n(x^n,Y^n)\le D\right)\ge c_0n^{-1/2}e^{-ng(\widehat{P})}. \tag*{(54)}

Proof. Put F(p,θ):=∑xp(x)Λq∗(x,θ)F(p,\theta):=\sum_xp(x)\Lambda_{q_*}(x,\theta) and W(θ)(y∣x)=q∗(y)e−θd(x,y)/Zx(θ)W^{(\theta)}(y|x)=q_*(y)e^{-\theta d(x,y)}/Z_x(\theta). The saddlepoint identities [16 Property 1] give

∂θF(P,λ):=∂F(P,θ)∂θ∣θ=λ=0and−∂θ2F(P,λ)=∑xP(x)Var⁡W∗(⋅∣x)(d(x,Y))>0.(55)\partial_\theta F(P,\lambda):=\left.\frac{\partial F(P,\theta)}{\partial\theta}\right|_{\theta=\lambda}=0 \quad\text{and}\quad -\partial_\theta^2F(P,\lambda)=\sum_xP(x)\operatorname{Var}_{W_*(\cdot|x)}(d(x,Y))>0. \tag*{(55)}

The strict positivity follows because otherwise every row is constant on supp⁡(q∗)\operatorname{supp}(q_*), making W∗(⋅∣x)=q∗W^*(\cdot|x)=q_* and R(P,D)=0R(P,D)=0. The implicit function theorem gives a smooth positive maximizer θ(p)\theta(p) near PP with θ(P)=λ\theta(P)=\lambda. Since F(p,⋅)F(p,\cdot) is strictly concave, this stationary point is its unique maximizer. Let

α(p)=∂θF(p,λ)=∑x(p(x)−P(x))EW∗(⋅∣x)[d(x,Y)].(56)\alpha(p)=\partial_\theta F(p,\lambda)=\sum_x(p(x)-P(x))\mathbb{E}_{W_*(\cdot|x)}[d(x,Y)]. \tag*{(56)}

After shrinking UU, there is a constant c>0c>0 such that −∂θ2F(p,θ)≥c-\partial_\theta^2F(p,\theta)\ge c for every p∈Up\in U and every θ\theta between λ\lambda and θ(p)\theta(p). Taylor’s theorem gives

0≤g(p)−∑xp(x)j(x,D)=F(p,θ(p))−F(p,λ)(57)0\le g(p)-\sum_xp(x)j(x,D)=F(p,\theta(p))-F(p,\lambda) \tag*{(57)}
≤α(p)(θ(p)−λ)−c2(θ(p)−λ)2(58)\le\alpha(p)(\theta(p)-\lambda)-\frac{c}{2}(\theta(p)-\lambda)^2 \tag*{(58)}
≤α(p)22c≤C∥p−P∥2.(59)\le\frac{\alpha(p)^2}{2c}\le C\lVert p-P\rVert^2. \tag*{(59)}

This proves (53). At p=Pp=P, this also gives g(P)=R(P,D)g(P)=R(P,D).

To apply Theorem 3 of Yang and Zhang [16], restrict the reconstruction alphabet to supp⁡(q∗)\operatorname{supp}(q_*) and shrink UU so that every p∈Up\in U has full support on X\mathcal{X}. Define μp(θ):=Ep×W(θ)[d(X,Y)]\mu_p(\theta):=\mathbb{E}_{p\times W^{(\theta)}}[d(X,Y)]. The tilted mean satisfies

μp′(θ)=−∑xp(x)Var⁡W(θ)(⋅∣x)[d(x,Y)]<0.\mu_p'(\theta)=-\sum_xp(x)\operatorname{Var}_{W^{(\theta)}(\cdot|x)}[d(x,Y)]<0.

Every tilted conditional distribution is positive on supp⁡(q∗)\operatorname{supp}(q_*), and at least one distortion row is nonconstant on this support. Consequently,

∑xp(x)min⁡y∈supp⁡(q∗)d(x,y)<μp(θ(p))=D<μp(0)=Ep×q∗[d(X,Y)].(60)\sum_xp(x)\min_{y\in\operatorname{supp}(q_*)}d(x,y)<\mu_p(\theta(p))=D<\mu_p(0)=\mathbb{E}_{p\times q_*}[d(X,Y)]. \tag*{(60)}

These are the distortion-range conditions required by the theorem. Its finiteness conditions hold because dd is bounded.

Viewing R0(p,q∗,t)R_0(p,q_*,t) as a function of tt, the saddlepoint identities [16 Property 3] give

∂tR0(p,q∗,t)∣t=D=−θ(p),(61)\left.\partial_tR_0(p,q_*,t)\right|_{t=D}=-\theta(p), \tag*{(61)}
Hp:=∂t2R0(p,q∗,t)∣t=D=(∑xp(x)Var⁡W(θ(p))(⋅∣x)[d(x,Y)])−1.(62)H_p:=\left.\partial_t^2R_0(p,q_*,t)\right|_{t=D} =\left(\sum_xp(x)\operatorname{Var}_{W^{(\theta(p))}(\cdot|x)}[d(x,Y)]\right)^{-1}. \tag*{(62)}

The third moment term in [16 Theorem 3] is

D3(p)=∑x,yp(x)q∗(y)d(x,y)3.(63)D_3(p)=\sum_{x,y}p(x)q_*(y)d(x,y)^3. \tag*{(63)}

Put B3:=dmax⁡3B_3 := d_{\max}^3. By the continuity of θ(p)\theta(p) and the tilted variances, there exist constants θ+\theta_+, H−H_-, H+H_+, such that for a sufficiently small U\mathcal{U},

0<θ(p)≤θ+,0<H−≤Hp≤H+andD3(p)≤B3.(64)0 < \theta(p) \le\theta_+,\quad0 < H_- \le H_p \le H_+ \quad\text{and}\quad D_3(p) \le B_3. \tag*{(64)}

Choose a fixed γ>0\gamma> 0 such that γH−22π≥16H+3/2B3+1\frac{\gamma\sqrt{H_-}}{2\sqrt{2\pi}} \ge16H_+^{3/2}B_3+1. For a source sequence xnx^n of type P^∈U\hat{P} \in\mathcal{U}, apply Yang and Zhang’s Eq. (3.18) [16] with source distribution P^\hat{P}. For nn large enough such that e−γ2H+/(2n)≥1/2e^{-\gamma^2H_+/(2n)} \ge1/2, it yields

q∗n(dn(xn,Yn)≤D)n−1/2e−ng(P^)≥e−γθ(P^)(γHP^2πe−γ2HP^/(2n)−16HP^3/2D3(P^))(65)\frac{q_*^n\left(d_n(x^n,Y^n)\le D\right)}{n^{-1/2}e^{-ng(\hat{P})}} \ge e^{-\gamma\theta(\hat{P})}\left(\frac{\gamma\sqrt{H_{\hat{P}}}}{\sqrt{2\pi}}e^{-\gamma^2H_{\hat{P}}/(2n)}-16H_{\hat{P}}^{3/2}D_3(\hat{P})\right) \tag*{(65)}
≥e−γθ+(γH−22π−16H+3/2B3)≥e−γθ+.(66)\ge e^{-\gamma\theta_+}\left(\frac{\gamma\sqrt{H_-}}{2\sqrt{2\pi}}-16H_+^{3/2}B_3\right)\ge e^{-\gamma\theta_+}. \tag*{(66)}

This proves (54) with c0:=e−γθ+c_0 := e^{-\gamma\theta_+}.

The Random Coding Bound and Normal Approximation

The random coding bound of Kostina and Verdú [7 Theorem 10] is quoted in the notation used here. For xn∈Xnx^n \in\mathcal{X}^n, define the reproduction ball BD(xn):={yn∈Yn:dn(xn,yn)≤D}\mathcal{B}_D(x^n) := \{y^n \in\mathcal{Y}^n : d_n(x^n,y^n) \le D\}.

Lemma 4 (Kostina–Verdú random coding bound). For every positive integer MM, there exist an encoder and a decoder whose excess-distortion probability ϵn\epsilon_n satisfies

ϵn≤inf⁡qn∈P(Yn)E[(1−qn(BD(Xn)))M].(67)\epsilon_n \le\inf_{q_n\in\mathcal{P}(\mathcal{Y}^n)} \mathbb{E}\left[\left(1-q_n(\mathcal{B}_D(X^n))\right)^M\right]. \tag*{(67)}

Using (1−u)M≤e−Mu(1-u)^M \le e^{-Mu} for u∈[0,1]u \in[0,1] and choosing qn=q∗nq_n=q_*^n, we obtain the relaxation

ϵn≤E[(1−q∗n(BD(Xn)))M]≤E[exp⁡(−Mq∗n(BD(Xn)))].(68)\epsilon_n \le\mathbb{E}\left[\left(1-q_*^n(\mathcal{B}_D(X^n))\right)^M\right]\le\mathbb{E}\left[\exp\left(-Mq_*^n(\mathcal{B}_D(X^n))\right)\right]. \tag*{(68)}

We evaluate this bound after establishing the normal approximation for its empirical exponent. Define the (truncated) empirical exponent by

Tn:={an(Xn)=ng(P^Xn),P^Xn∈U,nR(P,D),P^Xn∉U.(69)T_n := \begin{cases} a_n(X^n)=ng(\hat{P}_{X^n}), & \hat{P}_{X^n}\in\mathcal{U},\\ nR(P,D), & \hat{P}_{X^n}\notin\mathcal{U}. \end{cases} \tag*{(69)}

We apply the i.i.d. quantitative delta method of Pinelis and Molzon [12 Theorem 2.9], explicitly verifying the required local quadratic bound, finite third moment, and positive variance.

Lemma 5 (Normal approximation for empirical exponent). If V(P,D)>0V(P,D)>0, then

sup⁡t∈R∣Pr⁡(Tn≤t)−Φ(t−nR(P,D)nV(P,D))∣≤Cn.(70)\sup_{t\in\mathbb{R}}\left|\Pr(T_n\le t)-\Phi\left(\frac{t-nR(P,D)}{\sqrt{nV(P,D)}}\right)\right|\le\frac{C}{\sqrt{n}}. \tag*{(70)}

Proof. Let H={z∈R∣X∣:∑xz(x)=0}\mathcal{H}=\{z\in\mathbb{R}^{|\mathcal{X}|}:\sum_x z(x)=0\} and set Ui:=eXi−PU_i:=e_{X_i}-P, where exe_x is the unit vector at xx. Then,

E[Ui]=0,E[∥Ui∥3]<∞andU‾n:=1n∑i=1nUi=P^Xn−P(71)\mathbb{E}[U_i]=0,\quad\mathbb{E}[\lVert U_i\rVert^3]<\infty\quad\text{and}\quad\overline{U}_n:=\frac{1}{n}\sum_{i=1}^nU_i=\hat{P}_{X^n}-P \tag*{(71)}

On H\mathcal{H} define f(z):=g(P+z)−R(P,D)f(z):=g(P+z)-R(P,D) where P+z∈UP+z\in\mathcal{U}, and zero otherwise. The space H\mathcal{H}, equipped with the Euclidean norm, is a finite-dimensional Hilbert space. The function ff is Borel measurable, satisfies f(0)=0f(0)=0, and obeys Tn=nR(P,D)+nf(U‾n)T_n=nR(P,D)+nf(\overline{U}_n). Set L(z):=∑xz(x)ȷ(x,D)L(z):=\sum_xz(x)\jmath(x,D). Lemma 3 verifies the local quadratic condition Eq. (2.1) [12]:

∣f(z)−L(z)∣≤C∥z∥2  near 0,L(Ui)=ȷ(Xi,D)−R(P,D)andE[L(Ui)2]=V(P,D)>0.(72)|f(z)-L(z)|\le C\lVert z\rVert^2\ \text{ near }0,\quad L(U_i)=\jmath(X_i,D)-R(P,D)\quad\text{and}\quad\mathbb{E}[L(U_i)^2]=V(P,D)>0. \tag*{(72)}

Theorem 2.9 of [12] now gives

sup⁡t∈R∣Pr⁡(Tn≤t)−Φ(t−nR(P,D)nV(P,D))∣=sup⁡s∈R∣Pr⁡(nf(U‾n)V(P,D)≤s)−Φ(s)∣≤Cn(73)\sup_{t\in\mathbb{R}}\left|\Pr(T_n\le t)-\Phi\left(\frac{t-nR(P,D)}{\sqrt{nV(P,D)}}\right)\right| = \sup_{s\in\mathbb{R}}\left|\Pr\left(\frac{\sqrt{n}f(\overline{U}_n)}{\sqrt{V(P,D)}}\le s\right)-\Phi(s)\right| \le\frac{C}{\sqrt{n}} \tag*{(73)}

as desired.

Completion of Achievability Proof

We now substitute the product-ball estimate (Lemma 3) into the random coding bound (the relaxation of Lemma 4 in (68)).

Proposition 6 (Achievable code size). For ε\varepsilon in a fixed compact subset of (0,1)(0,1), there is a constant K+K_{+} such that for all sufficiently large nn,

log⁡M∗(n,D,ε)≤nR(P,D)+nV(P,D)Q−1(ε)+12log⁡n+K+.(74)\log M^{*}(n,D,\varepsilon) \le nR(P,D) + \sqrt{nV(P,D)}Q^{-1}(\varepsilon) + \frac{1}{2}\log n + K_{+}. \tag*{(74)}

Proof. Write R=R(P,D)R=R(P,D) and V=V(P,D)V=V(P,D), and let ε∈[ε0,ε1]⊂(0,1)\varepsilon\in[\varepsilon_{0},\varepsilon_{1}] \subset(0,1). Also define the event En:={P^Xn∈U}\mathcal{E}_{n}:=\{\hat{P}_{X^{n}}\in\mathcal{U}\} and set b=log⁡M−12log⁡n+log⁡c0b=\log M-\frac{1}{2}\log n+\log c_{0}. Hoeffding’s inequality for the empirical distribution gives Pr⁡(Enc)≤e−cn\Pr(\mathcal{E}_{n}^{c})\le e^{-cn} for sufficiently large nn. The relaxed random coding bound in (68) and Lemma 3 give

εn≤E[exp⁡(−Mq∗n(BD(Xn)))](75)\varepsilon_{n}\le\mathbb{E}\left[\exp\left(-Mq_{*}^{n}(\mathcal{B}_{D}(X^{n}))\right)\right] \tag*{(75)}
≤E[1Enexp⁡(−Mc0n−1/2e−Tn)]+Pr⁡(Enc)(76)\le\mathbb{E}\left[\mathbf{1}_{\mathcal{E}_{n}}\exp\left(-Mc_{0}n^{-1/2}e^{-T_{n}}\right)\right]+\Pr(\mathcal{E}_{n}^{c}) \tag*{(76)}
≤E[exp⁡(−eb−Tn)]+e−cn.(77)\le\mathbb{E}\left[\exp\left(-e^{b-T_{n}}\right)\right]+e^{-cn}. \tag*{(77)}

For the case V=V(P,D)>0V=V(P,D)>0, define the standard Gumbel probability density

κ(u):=exp⁡(−u−e−u),\kappa(u):=\exp(-u-e^{-u}),

which satisfies

∫Rκ(u) du=1andK0:=∫R∣u∣κ(u) du<∞.(78)\int_{\mathbb{R}}\kappa(u)\,\mathrm{d}u=1 \quad\text{and}\quad K_{0}:=\int_{\mathbb{R}}|u|\kappa(u)\,\mathrm{d}u<\infty. \tag*{(78)}

Since ∫−∞vκ(u) du=exp⁡(−e−v)\int_{-\infty}^{v}\kappa(u)\,\mathrm{d}u=\exp(-e^{-v}), Tonelli’s theorem gives

E[exp⁡(−eb−Tn)]=E[∫−∞Tn−bκ(u) du]=∫Rκ(u)Pr⁡(Tn>b+u) du.(79)\mathbb{E}\left[\exp\left(-e^{b-T_{n}}\right)\right] =\mathbb{E}\left[\int_{-\infty}^{T_{n}-b}\kappa(u)\,\mathrm{d}u\right] =\int_{\mathbb{R}}\kappa(u)\Pr(T_{n}>b+u)\,\mathrm{d}u. \tag*{(79)}

Lemma 5, followed by the bound sup⁡zϕ(z)=1/2π\sup_{z}\phi(z)=1/\sqrt{2\pi}, now yields

εn≤∫Rκ(u)Q(b+u−nRnV)du+Cn+e−cn(80)\varepsilon_{n}\le\int_{\mathbb{R}}\kappa(u)Q\left(\frac{b+u-nR}{\sqrt{nV}}\right)\mathrm{d}u+\frac{C}{\sqrt{n}}+e^{-cn} \tag*{(80)}
≤Q(b−nRnV)+K02πnV+Cn+e−cn(81)\le Q\left(\frac{b-nR}{\sqrt{nV}}\right)+\frac{K_{0}}{\sqrt{2\pi nV}}+\frac{C}{\sqrt{n}}+e^{-cn} \tag*{(81)}
≤Q(b−nRnV)+C1n.(82)\le Q\left(\frac{b-nR}{\sqrt{nV}}\right)+\frac{C_{1}}{\sqrt{n}}. \tag*{(82)}

Take b≥nR+nVQ−1(ε)+Kb\ge nR+\sqrt{nV}Q^{-1}(\varepsilon)+K. Choose η>0\eta>0 so that ϕ(Q−1(ε)+u)≥η\phi(Q^{-1}(\varepsilon)+u)\ge\eta for all ε∈[ε0,ε1]\varepsilon\in[\varepsilon_{0},\varepsilon_{1}] and u∈[0,1]u\in[0,1]. For fixed K>0K>0 and large enough nn,

εn≤Q(Q−1(ε)+KnV)+C1n(83)\varepsilon_{n}\le Q\left(Q^{-1}(\varepsilon)+\frac{K}{\sqrt{nV}}\right)+\frac{C_{1}}{\sqrt{n}} \tag*{(83)}
=ε−∫0K/nVϕ(Q−1(ε)+u) du+C1n(84)=\varepsilon-\int_{0}^{K/\sqrt{nV}}\phi(Q^{-1}(\varepsilon)+u)\,\mathrm{d}u+\frac{C_{1}}{\sqrt{n}} \tag*{(84)}
≤ε+C1−ηK/Vn≤ε(85)\le\varepsilon+\frac{C_{1}-\eta K/\sqrt{V}}{\sqrt{n}}\le\varepsilon \tag*{(85)}

when K≥C1V/ηK\ge C_{1}\sqrt{V}/\eta.

For the case V=V(P,D)=0V=V(P,D)=0, define the event FL:={n∥P^Xn−P∥2≤L}\mathcal{F}_{L}:=\{n\|\hat{P}_{X^{n}}-P\|^{2}\le L\}. Choose L>0L>0 sufficiently large and then K≥CL+log⁡log⁡(2/ε0)K\ge CL+\log\log(2/\varepsilon_{0}). Since Jn:=∑i=1nȷ(Xi,D)=nRJ_{n}:=\sum_{i=1}^{n}\jmath(X_{i},D)=nR almost surely, Markov’s inequality, (53) and (68) give, for all sufficiently large nn, and b≥nR+Kb\ge nR+K,

Pr⁡(FLc)≤1−∥P∥2L≤ε02(86)\Pr(\mathcal{F}_{L}^{c})\le\frac{1-\|P\|^{2}}{L}\le\frac{\varepsilon_{0}}{2} \tag*{(86)}
Tn≤nR+Cn∥P^Xn−P∥2≤nR+CLon FL⊂En,(87)T_{n}\le nR+Cn\|\hat{P}_{X^{n}}-P\|^{2}\le nR+CL\quad\text{on }\mathcal{F}_{L}\subset\mathcal{E}_{n}, \tag*{(87)}
εn≤exp⁡(−eK−CL)+ε02≤ε0≤ε.(88)\varepsilon_{n}\le\exp\left(-e^{K-CL}\right)+\frac{\varepsilon_{0}}{2}\le\varepsilon_{0}\le\varepsilon. \tag*{(88)}

In either case, put bε:=nR+nVQ−1(ε)+Kb_{\varepsilon}:=nR+\sqrt{nV}Q^{-1}(\varepsilon)+K with the corresponding KK, and choose

M:=⌈ebε+12log⁡n−log⁡c0⌉.(89)M:=\left\lceil e^{b_{\varepsilon}+\frac{1}{2}\log n-\log c_{0}}\right\rceil. \tag*{(89)}

Then b≥bεb\ge b_{\varepsilon}. Since R>0R>0, for all sufficiently large nn,

log⁡M∗(n,D,ε)≤log⁡M≤bε+12log⁡n−log⁡c0+log⁡2.(90)\log M^{*}(n,D,\varepsilon)\le\log M\le b_{\varepsilon}+\frac{1}{2}\log n-\log c_{0}+\log2. \tag*{(90)}

This proves the proposition and completes the proof of the achievability part of Theorem 1. □

Converse Proof of Theorem 1

In the converse proof, we fix a threshold bb. We bound the probability that a source sequence XnX^{n} with Jn=∑i=1nȷ(Xi,D)≥bJ_{n}=\sum_{i=1}^{n}\jmath(X_{i},D)\ge b is covered by the codebook. For V=V(P,D)>0V=V(P,D)>0, the key strengthening of Kostina and Verdú’s converse is a bound of Ce−b/nCe^{-b/n} on the contribution of each distortion ball, uniformly over its center, outside a common exponentially small set of source sequences.

To obtain this bound, we retain both exponential weights in the reverse change of measure and apply the multivariate weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [13 Lemma 3]. This estimate controls the joint concentration of tilted information and distortion, producing an n−1n^{-1} factor.

We choose b=log⁡M−12log⁡nb=\log M-\frac{1}{2}\log n so that the contribution of the MM distortion balls to the union bound is of order n−1/2n^{-1/2}, i.e., MCe−b/n=C/nMCe^{-b/n}=C/\sqrt{n}. This threshold bb is lower by log⁡n\log n than the threshold log⁡M+12log⁡n\log M+\frac{1}{2}\log n used to evaluate Kostina and Verdú’s converse [7 Theorem 7]. The normal approximation then improves the third-order lower bound from −12log⁡n-\frac{1}{2}\log n to +12log⁡n+\frac{1}{2}\log n. The following subsections establish the uniform ball estimate and complete this argument.

Reconstruction Codewords That Cover Typical Inputs

For a reconstruction codeword yn∈Yny^{n}\in\mathcal{Y}^{n}, define its source-space distortion ball by

BD(yn):={xn∈Xn:dn(xn,yn)≤D}.(91)B_{D}(y^{n}):=\{x^{n}\in\mathcal{X}^{n}:d_{n}(x^{n},y^{n})\le D\}. \tag*{(91)}

We show that if BD(yn)∩An≠∅B_{D}(y^{n})\cap\mathcal{A}_{n}\ne\emptyset, where An\mathcal{A}_{n} is the typical set defined in (92) below, then yny^{n} contains two reconstruction symbols y,z∈Yy,z\in\mathcal{Y}, each occurring linearly often, such that d(x,y)−d(x,z)d(x,y)-d(x,z) is nonconstant in x∈Xx\in\mathcal{X}. These symbols will verify the full-rank covariance condition required by the weighted-strip estimate in [13 Lemma 3].

Put Δ:=(Dzr(P)−D)/2>0\Delta:=(D_{\mathrm{zr}}(P)-D)/2>0 and

An:={xn:Dzr(P^xn)≥D+Δ}.(92)\mathcal{A}_{n}:=\left\{x^{n}:D_{\mathrm{zr}}(\hat{P}_{x^{n}})\ge D+\Delta\right\}. \tag*{(92)}

Write y∼zy\sim z if d(x,y)−d(x,z)d(x,y)-d(x,z) is constant in x∈Xx\in\mathcal{X}. This defines an equivalence relation on Y\mathcal{Y}. The equivalence class containing yy is {z∈Y:z∼y}\{z\in\mathcal{Y}:z\sim y\}. Put Υ:=max⁡x,y,z∣d(x,y)−d(x,z)∣\Upsilon:=\max_{x,y,z}|d(x,y)-d(x,z)|. Fix 0<δ<10<\delta<1 with δΥ<Δ\delta\Upsilon<\Delta. Call a symbol in a reconstruction codeword yny^{n} frequent if it occurs at least δn/∣Y∣\delta n/|\mathcal{Y}| times.

Lemma 7 (Distortion columns of a typical ball). There exist constants C,c>0C,c>0 such that Pn(Anc)≤Ce−cnP^{n}(\mathcal{A}_{n}^{c})\le Ce^{-cn} for every nn. If BD(yn)∩An≠∅B_{D}(y^{n})\cap\mathcal{A}_{n}\ne\emptyset, then yny^{n} contains two frequent symbols y,zy,z satisfying y≁zy\not\sim z.

Proof. Put νy:=EP[d(X,y)]\nu_{y}:=\mathbb{E}_{P}[d(X,y)]. Since νy≥min⁡z∈YEP[d(X,z)]=Dzr(P)=D+2Δ\nu_{y}\ge\min_{z\in\mathcal{Y}}\mathbb{E}_{P}[d(X,z)]=D_{\mathrm{zr}}(P)=D+2\Delta, Hoeffding’s inequality gives

Pn(Anc)≤∑y∈YPr⁡(1n∑i=1nd(Xi,y)<D+Δ)(93)P^{n}(\mathcal{A}_{n}^{c})\le\sum_{y\in\mathcal{Y}}\Pr\left(\frac{1}{n}\sum_{i=1}^{n}d(X_{i},y)<D+\Delta\right) \tag*{(93)}
≤∑y∈YPr⁡(1n∑i=1n(d(Xi,y)−νy)<−Δ)(94)\le\sum_{y\in\mathcal{Y}}\Pr\left(\frac{1}{n}\sum_{i=1}^{n}\bigl(d(X_{i},y)-\nu_{y}\bigr)<-\Delta\right) \tag*{(94)}
≤∣Y∣e−2nΔ2/dmax⁡2.(95)\le|\mathcal{Y}|e^{-2n\Delta^{2}/d_{\max}^{2}}. \tag*{(95)}

At least one symbol of yny^n is infrequent. Suppose that all frequent symbols lie in one equivalence class C\mathcal{C}. Choose y0∈Cy_0 \in\mathcal{C} minimizing d(x,y)d(x,y) within C\mathcal{C} at one xx. Since the column differences are constant, this y0y_0 minimizes at every xx. Every letter outside C\mathcal{C} occurs fewer than δn/∣Y∣\delta n/|\mathcal{Y}| times, so ∣{i:yi∉C}∣<δn|\{i:y_i \notin\mathcal{C}\}| < \delta n. Thus, for every xn∈Anx^n \in\mathcal{A}_n,

dn(xn,yn)≥1n∑i=1nd(xi,y0)−Γn∣{i:yi∉C}∣(96)d_n(x^n,y^n) \ge\frac{1}{n}\sum_{i=1}^{n}d(x_i,y_0)-\frac{\Gamma}{n}|\{i:y_i \notin\mathcal{C}\}| \tag*{(96)}
≥Dzr(P^xn)−δΓ(97)\ge D_{\mathrm{zr}}(\hat{P}_{x^n})-\delta\Gamma \tag*{(97)}
≥D+Δ−δΓ>D.(98)\ge D+\Delta-\delta\Gamma>D. \tag*{(98)}

Hence BD(yn)∩An=∅B_D(y^n)\cap\mathcal{A}_n=\varnothing, a contradiction.

Probability of a Distortion Ball Above a Threshold

For the next proposition, we define the following notation. Recall the unnormalized tilted reverse subprobability mass function py(λ)p_{y}^{(\lambda)} in (36) and its mass sys_y in (37). Normalize it to obtain the probability mass function

py(x)=py(λ)(x)sy.(99)p_y(x)=\frac{p_y^{(\lambda)}(x)}{s_y}. \tag*{(99)}

For fixed yny^n, define the reverse product distribution

pyn(xn):=∏i=1npyi(xi).(100)p_{y^n}(x^n):=\prod_{i=1}^{n}p_{y_i}(x_i). \tag*{(100)}

Also define the accumulated DD-tilted information and the total distortion, respectively, by

Jn:=∑i=1nȷ(Xi,D)andSn:=∑i=1nd(Xi,yi).(101)J_n:=\sum_{i=1}^{n}\jmath(X_i,D)\quad\text{and}\quad S_n:=\sum_{i=1}^{n}d(X_i,y_i). \tag*{(101)}

The component likelihood ratios multiply to give

Pn(xn)pyn(xn)=∏i=1nP(xi)syipyi(xi)=(∏i=1nsyi)e−Jn−λ(nD−Sn)≤e−Jn−λ(nD−Sn),(102)\frac{P^n(x^n)}{p_{y^n}(x^n)} =\prod_{i=1}^{n}\frac{P(x_i)s_{y_i}}{p_{y_i}(x_i)} =\left(\prod_{i=1}^{n}s_{y_i}\right)e^{-J_n-\lambda(nD-S_n)} \le e^{-J_n-\lambda(nD-S_n)}, \tag*{(102)}

where JnJ_n and SnS_n are evaluated at Xn=xnX^n=x^n.

The likelihood ratio in (102) contains the exponential weights e−Jne^{-J_n} and e−λ(nD−Sn)e^{-\lambda(nD-S_n)}. When V(P,D)>0V(P,D)>0, we apply the multivariate weighted-strip bound of Scarlett, Martinez, and Guillén i Fàbregas [13 Lemma 3] to control the distortion-slack weight e−λ(nD−Sn)e^{-\lambda(nD-S_n)} while restricting JnJ_n to an interval of fixed width. When V(P,D)=0V(P,D)=0, Jn=nR(P,D)J_n=nR(P,D) is deterministic, and Polyanskiy’s scalar exponentially weighted tail bound [21 Lemma 20] suffices. The two inequivalent frequent symbols identified above ensure the required covariance nondegeneracy after pairing coordinates.

The following proposition is the key in obtaining the +12log⁡n+\frac{1}{2}\log n third-order term in the converse.

Proposition 8 (Uniform ball and tilted information bound). For k0=1+1{V(P,D)>0}k_0=1+\mathbb{1}\{V(P,D)>0\}, every yny^n and every b∈Rb\in\mathbb{R} satisfy

Pn(An,Sn≤nD,Jn≥b)≤Ce−bn−k0/2.(103)P^n(\mathcal{A}_n,S_n\le nD,J_n\ge b)\le Ce^{-b}n^{-k_0/2}. \tag*{(103)}

Proof. Let the event in the probability in (103) be Jb:={An,Sn≤nD,Jn≥b}\mathcal{J}_b:=\{\mathcal{A}_n,S_n\le nD,J_n\ge b\}. Define the scaled distortion slack Un:=λ(nD−Sn)U_n:=\lambda(nD-S_n). If the ball BD(yn)B_D(y^n) has an empty intersection with An\mathcal{A}_n, then the event Jb\mathcal{J}_b is empty. Otherwise, Lemma 7 supplies two inequivalent frequent symbols y,zy,z in yny^n. Form kk disjoint pairs of coordinates, each containing one occurrence of yy and one occurrence of zz, where

δn∣Y∣≤k≤⌊n2⌋.(104)\frac{\delta n}{|\mathcal{Y}|}\le k\le\left\lfloor\frac{n}{2}\right\rfloor. \tag*{(104)}

See Figure 2. Under pynp_{y^n}, the pair contributions to (Un,Jn)(U_n,J_n) are i.i.d. copies of the random vector

Illustration of the paired and remaining coordinates in the proof of Proposition 8

Figure 2. Illustration of the paired and remaining coordinates in the proof of Proposition 8

\begin{bmatrix} \lambda(2D-d(X,y)-d(X',z))\\ \jmath(X,D)+\jmath(X',D) \end{bmatrix} \quad\text{where } (X,X') \sim p_y \times p_z. \tag*{(105)}\end{bmatrix}

Their covariance has rank k0k_0. Indeed, a linear functional constant on the support would give

αȷ(x,D)+γd(x,u)=cu(x∈X, u=y,z)⟹γ(d(x,y)−d(x,z))=cy−cz.(106)\alpha\jmath(x,D)+\gamma d(x,u)=c_u \quad(x\in\mathcal{X},\ u=y,z) \quad\Longrightarrow\quad \gamma(d(x,y)-d(x,z))=c_y-c_z. \tag*{(106)}

Inequivalence forces γ=0\gamma=0, and if V=V(P,D)>0V=V(P,D)>0, this then forces α=0\alpha=0. If V=0V=0, the ȷ\jmath-coordinate is constant and at least one of the two distortion columns is nonconstant, so the remaining scalar variance is positive.

Split (Un,Jn)(U_n,J_n) into sums over the paired and remaining coordinates, denoted by subscripts pair and rem, and let Frem\mathcal{F}_{\mathrm{rem}} be the σ\sigma-field generated by the remaining source coordinates. The exponential-weight estimates in [13 Lemma 3] and [21 Lemma 20] give

Epyn[e−Un1{Un≥0,Jn∈[a,a+1)}∣Frem]=e−UremEpyn[e−Upair1{Upair≥−Urem,Jpair∈[a−Jrem,a+1−Jrem)}∣Frem](107)\mathbb{E}_{p_{y^n}}\left[e^{-U_n}\mathbf{1}\{U_n\ge0,J_n\in[a,a+1)\}\mid\mathcal{F}_{\mathrm{rem}}\right] = e^{-U_{\mathrm{rem}}}\mathbb{E}_{p_{y^n}}\left[e^{-U_{\mathrm{pair}}}\mathbf{1}\{U_{\mathrm{pair}}\ge-U_{\mathrm{rem}},J_{\mathrm{pair}}\in[a-J_{\mathrm{rem}},a+1-J_{\mathrm{rem}})\}\mid\mathcal{F}_{\mathrm{rem}}\right] \tag*{(107)}
≤e−UremCk−k0/2eUrem≤C′n−k0/2.(108)\le e^{-U_{\mathrm{rem}}}Ck^{-k_0/2}e^{U_{\mathrm{rem}}}\le C'n^{-k_0/2}. \tag*{(108)}

For k0=2k_0=2, this is [13 Lemma 3] with sample size kk and strip half-width 1/21/2. For k0=1k_0=1, dropping the constant JnJ_n-strip indicator gives the scalar bound in [21 Lemma 20]. The scalar bound at the closed threshold follows by applying [21 Lemma 20] at −Urem−h-U_{\mathrm{rem}}-h and letting h↓0h\downarrow0. The constants are uniform over the finitely many pairs y,zy,z.

Average over Frem\mathcal{F}_{\mathrm{rem}}, partition Jn≥bJ_n\ge b into unit intervals and use (102). For both values of k0k_0,

Pn(Jb)≤∑ℓ≥0e−b−ℓEpyn[e−Un1{Un≥0,Jn∈[b+ℓ,b+ℓ+1)}](109)P^n(\mathcal{J}_b)\le\sum_{\ell\ge0}e^{-b-\ell}\mathbb{E}_{p_{y^n}}\left[e^{-U_n}\mathbf{1}\{U_n\ge0,J_n\in[b+\ell,b+\ell+1)\}\right] \tag*{(109)}
≤Ce−bn−k0/2∑ℓ≥0e−ℓ=Ce−bn−k0/21−e−1.(110)\le Ce^{-bn-k_0/2}\sum_{\ell\ge0}e^{-\ell} =\frac{Ce^{-bn-k_0/2}}{1-e^{-1}}. \tag*{(110)}

This completes the proof of the proposition. □

Completion of Converse

For any code, the union of its source-space distortion balls has probability at least its success probability. Intersecting this union with a tilted information tail and applying Proposition 8 gives the converse immediately.

Proposition 9. There exists a constant K−∈RK_{-} \in\mathbb{R} such that every (n,M,D,ε)(n, M, D, \varepsilon)-code satisfies

log⁡M≥nR(P,D)+nV(P,D)Q−1(ε)+12log⁡n−K−(111)\log M \ge nR(P,D) + \sqrt{nV(P,D)}Q^{-1}(\varepsilon) + \frac{1}{2}\log n - K_{-} \tag*{(111)}

for all sufficiently large nn, uniformly over ε\varepsilon in a compact subinterval of (0,1)(0,1).

Proof. Given a code with decoder φn\varphi_n, write yn(m):=φn(m)y^n(m) := \varphi_n(m) for the reconstruction sequence associated with index m∈[M]m \in[M]. Given the set of reproduction sequences {yn(1),yn(2),…,yn(M)}\{y^n(1), y^n(2), \ldots, y^n(M)\}, define its source-space distortion balls as in (91) and their union by

A:=⋃m=1MBD(yn(m)).(112)\mathcal{A} := \bigcup_{m=1}^{M} \mathcal{B}_D(y^n(m)). \tag*{(112)}

A source sequence outside A\mathcal{A} cannot be reproduced within distortion DD. Therefore Pn(A)≥1−εP^n(\mathcal{A}) \ge1-\varepsilon. For a threshold bb, put E:=An∩{Jn≥b}\mathcal{E} := \mathcal{A}_n \cap\{J_n \ge b\} and k0=1+1{V(P,D)>0}k_0 = 1 + \mathbb{1}\{V(P,D) > 0\}. Since Pn(Ac)≤εP^n(\mathcal{A}^{\mathrm{c}}) \le\varepsilon, Proposition 8 gives

Pn(E)−ε≤Pn(A∩E)(113)P^n(\mathcal{E}) - \varepsilon\le P^n(\mathcal{A} \cap\mathcal{E}) \tag*{(113)}
≤Mmax⁡m∈[M]Pn(BD(yn(m))∩E)(114)\le M \max_{m\in[M]} P^n\bigl(\mathcal{B}_D(y^n(m)) \cap\mathcal{E}\bigr) \tag*{(114)}
≤CMe−bn−k0/2.(115)\le C M e^{-b n - k_0/2}. \tag*{(115)}

Since Pn(E)≥Pn(Jn≥b)−Pn(Anc)P^n(\mathcal{E}) \ge P^n(J_n \ge b) - P^n(\mathcal{A}_n^{\mathrm{c}}), Lemma 7 gives

ε≥Pn(Jn≥b)−CMe−bn−k0/2−Ce−cn.(116)\varepsilon\ge P^n(J_n \ge b) - C M e^{-b n - k_0/2} - C e^{-c n}. \tag*{(116)}

For V=V(P,D)>0V = V(P,D) > 0, take b=log⁡M−12log⁡nb = \log M - \frac{1}{2}\log n. Applying the Berry–Esseen theorem to JnJ_n,

Q(b−nR(P,D)nV(P,D))≤Pn(Jn≥b)+Cn(117)Q\left(\frac{b-nR(P,D)}{\sqrt{nV(P,D)}}\right) \le P^n(J_n \ge b) + \frac{C}{\sqrt{n}} \tag*{(117)}
≤ε+CMe−bn−k0/2+Ce−cn+Cn≤ε+C′n.(118)\le\varepsilon+ C M e^{-b n-k_0/2} + C e^{-c n} + \frac{C}{\sqrt{n}} \le\varepsilon+ \frac{C'}{\sqrt{n}}. \tag*{(118)}

The inverse normal tail is Lipschitz on compact subintervals of (0,1)(0,1). Hence, uniformly for ε\varepsilon in such an interval and all sufficiently large nn,

log⁡M−12log⁡n=b≥nR(P,D)+nV(P,D)Q−1(ε+C′n)(119)\log M - \frac{1}{2}\log n = b \ge nR(P,D) + \sqrt{nV(P,D)}Q^{-1}\left(\varepsilon+ \frac{C'}{\sqrt{n}}\right) \tag*{(119)}
≥nR(P,D)+nV(P,D)Q−1(ε)−K−.(120)\ge nR(P,D) + \sqrt{nV(P,D)}Q^{-1}(\varepsilon) - K_{-}. \tag*{(120)}

For V=0V = 0, b=nR(P,D)b = nR(P,D) gives Pn(Jn≥b)=1P^n(J_n \ge b) = 1. Then (116) implies that

M≥C−1(1−ε−Ce−cn)nenR(P,D).(121)M \ge C^{-1}(1-\varepsilon-Ce^{-c n})\sqrt{n}e^{nR(P,D)}. \tag*{(121)}

If ε≤εmax⁡<1\varepsilon\le\varepsilon_{\max} < 1, the factor in brackets is at least (1−εmax⁡)/2(1-\varepsilon_{\max})/2 for all sufficiently large nn, which gives log⁡M≥nR(P,D)+12log⁡n−K−\log M \ge nR(P,D) + \frac{1}{2}\log n - K_{-}.

Propositions 6 and 9 together prove Theorem 1.

Conclusion and Future Work

We established the third-order correction 12log⁡n+O(1)\frac{1}{2}\log n + O(1) for fixed-length lossy compression of finite-alphabet discrete memoryless sources at interior distortion levels. This result complements third-order analyses of channel coding [20], [26], [27], source coding redundancy [17], and channel simulation [22], [28], [29], among other studies. The proof combines classical distortion-ball estimates [15], [16], [18], [19] with a quantitative normal approximation for achievability and a multivariate weighted-strip estimate for the converse [13]. Together, these tools yield a bounded remainder uniformly over excess-distortion probabilities in compact subintervals of (0,1)(0,1).

A natural direction for future work is to investigate refined asymptotics for the minimum covering radius of block codes within the information spectrum framework of Chen and Han [30]. The close connection with rate-distortion theory suggests that the uniform distortion-ball estimates used here may provide a useful starting point. In particular, identifying the higher order terms in the covering radius could clarify how the geometry of distortion balls influences finite blocklength covering limits.

Acknowledgments

Generative-AI use disclosure. The author used OpenAI Codex (GPT-6 Astra, Ultra mode) and Anthropic’s Claude (Opus 5) during the development and preparation of this manuscript. These systems assisted in exploring and stresstesting proof strategies, formulating and refining intermediate lemmas, checking algebraic and probabilistic calculations, identifying possible logical gaps, and refining portions of the exposition. The author wrote the manuscript, independently verified every mathematical statement, proof, and reference, and assumes full responsibility for its contents.

References

  1. [1]C. E. Shannon, “Coding theorems for a discrete source with a fidelity criterion,” IRE Int. Conv. Rec., vol. 7, pp. 142–163, 1959. Part 4.
  2. [2]K. Marton, “Error exponent for source coding with a fidelity criterion,” IEEE Trans. Inf. Theory, vol. 20, pp. 197–199, Mar. 1974.DOI
  3. [3]J. K. Omura, “A lower bounding method for channel and source coding probabilities,” Inf. Control, vol. 27, pp. 148–177, Feb. 1975.DOI
  4. [4]I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge, U.K.: Cambridge University Press, 2nd ed., 2011.
  5. [5]V. Y. F. Tan, “Moderate-deviations of lossy source coding for discrete and Gaussian sources,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), (Cambridge, MA, USA), pp. 920–924, July 2012.arxiv.org/abs/1111.2217
  6. [6]A. Ingber and Y. Kochman, “The dispersion of lossy source coding,” in Proc. Data Compression Conf. (DCC), pp. 53–62, Mar. 2011.arxiv.org/abs/1102.2598
  7. [7]V. Kostina and S. Verdú, “Fixed-length lossy compression in the finite blocklength regime,” IEEE Trans. Inf. Theory, vol. 58, pp. 3309–3338, June 2012.
  8. [8]V. Kostina, Lossy Data Compression: Nonasymptotic Fundamental Limits. Ph.D. dissertation, Princeton University, Princeton, NJ, USA, Sept. 2013.
  9. [9]A. Ingber, I. Leibowitz, R. Zamir, and M. Feder, “Distortion lower bounds for finite dimensional joint source-channel coding,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), (Toronto, ON, Canada), pp. 1183–1187, July 2008.DOI
  10. [10]P. Moulin, “Lower bounds on rate of fixed-length source codes under average- and ε-fidelity constraints,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 3220–3224, June 2017.
  11. [11]P. Moulin, “Source coding with distortion profile constraints,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 3215–3219, June 2017.DOI
  12. [12]I. Pinelis and R. Molzon, “Optimal-order bounds on the rate of convergence to normality in the multivariate delta method,” Electron. J. Stat., vol. 10, no. 1, pp. 1001–1063, 2016.arxiv.org/abs/0906.0177
  13. [13]J. Scarlett, A. Martinez, and A. Guillén i Fàbregas, “Refinements of the third-order term in the fixed error asymptotics of constant-composition codes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 2954–2958, June 2015.DOI
  14. [14]R. J. Pilc, Coding Theorems for Discrete Source-Channel Pairs. Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 1967.
  15. [15]Z. Zhang, E.-h. Yang, and V. K. Wei, “The redundancy of source coding with a fidelity criterion—Part I: Known statistics,” IEEE Trans. Inf. Theory, vol. 43, pp. 71–91, Jan. 1997.
  16. [16]E.-h. Yang and Z. Zhang, “On the redundancy of lossy source coding with abstract alphabets,” IEEE Trans. Inf. Theory, vol. 45, pp. 1092–1110, May 1999.DOI
  17. [17]S. M. Sriramu and A. B. Wagner, “Exact redundancy for symmetric rate-distortion,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 1–6, June 2026.
  18. [18]I. Kontoyiannis, “Pointwise redundancy in lossy data compression and universal lossy data compression,” IEEE Trans. Inf. Theory, vol. 46, pp. 136–152, Jan. 2000.DOI
  19. [19]A. Dembo and I. Kontoyiannis, “The asymptotics of waiting times between stationary processes, allowing distortion,” Ann. Appl. Probab., vol. 9, pp. 413–429, May 1999.DOI
  20. [20]M. Tomamichel and V. Y. F. Tan, “A tight upper bound for the third-order asymptotics for most discrete memoryless channels,” IEEE Trans. Inf. Theory, vol. 59, pp. 7041–7051, Nov. 2013.DOI
  21. [21]Y. Polyanskiy, Channel Coding: Non-Asymptotic Fundamental Limits. Ph.D. dissertation, Princeton University, Princeton, NJ, USA, Nov. 2010.
  22. [22]S. M. Sriramu and A. B. Wagner, “Optimal redundancy in exact channel synthesis,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 1913–1918, July 2024.arxiv.org/abs/2401.16707
  23. [23]A. Mahmood, “Joint source-channel coding of Gaussian sources over block erasure channels: Nonasymptotic bounds and channel-uniform normal approximations.” arXiv:2609.38725v2, 2026.arxiv.org/abs/2609.38725
  24. [24]V. Strassen, “Asymptotische Abschätzungen in Shannons Informationstheorie,” in Trans. Third Prague Conf. Inf. Theory, Statist. Decision Functions, Random Processes, (Prague), pp. 689–723, Publishing House of the Czechoslovak Academy of Sciences, 1964. Conference held at Liblice, June 1962.
  25. [25]R. G. Gallager, Information Theory and Reliable Communication. New York, NY, USA: Wiley, 1968.
  26. [26]Y. Altuğ and A. B. Wagner, “The third-order term in the normal approximation for singular channels,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 1897–1901, June 2014.arxiv.org/abs/1309.5126
  27. [27]V. Y. F. Tan and M. Tomamichel, “The third-order term in the normal approximation for the AWGN channel,” IEEE Trans. Inf. Theory, vol. 61, pp. 2430–2438, May 2015.
  28. [28]G. Flamich, S. M. Sriramu, and A. B. Wagner, “The redundancy of non-singular channel simulation.” arXiv:2501.14053, 2025.arxiv.org/abs/2501.14053
  29. [29]V. Lungu, A. B. Wagner, and I. Kontoyiannis, “Fine asymptotics for approximate simulation of symmetric channels.” arXiv:2620.15877, 2026.arxiv.org/abs/2610.15877
  30. [30]P.-N. Chen and Y. S. Han, “Asymptotic minimum covering radius of block codes,” SIAM J. Discrete Math., vol. 14, pp. 549–564, Aug. 2001.DOI

Paper details

vlnc:W_tuuaezhk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex, Claude Opus 5 (bare)

View statement
Looking for related papers…
Contents