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 and every interior distortion level, we establish a third-order correction of , where 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 and a single-letter distortion function , Shannon [1] showed that the minimum asymptotically achievable compression rate under an average distortion constraint is the rate-distortion function
where the minimization is over all conditional distributions , 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 . For fixed rates below , 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 , independent of the blocklength. Our object of interest is , the minimum number of reconstruction codewords required by a length- code whose probability of exceeding distortion is at most .
Under their respective regularity assumptions, Ingber and Kochman [6 Theorem 1] and Kostina and Verdú [7 Theorem 12] independently established the second-order expansion
for fixed , where is the complementary CDF of the standard Gaussian distribution. The coefficient 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
Here the coordinate derivatives are defined using a differentiable extension of off the probability simplex. Kostina and Verdú [7 Theorem 12, Eq. (83)] give the representation
where is the -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
where the remainder is uniform for in any fixed compact subinterval of . The result includes the zero-dispersion case and does not require a unique or fully supported optimal reproduction distribution.
Kostina and Verdú [7] previously bounded the 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 correction and an achievability bound with an additional 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 , 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 , 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 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.
Other Related Work
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 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- 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 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 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 correction. Related logarithmic corrections also arise in channel coding and exact channel synthesis. Tomamichel and Tan [20] established a upper bound on the third-order term for discrete memoryless channels with positive -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 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 be a length- block from a discrete memoryless source with finite alphabet , and let be a finite reconstruction alphabet. Here denotes the -fold product distribution of , and denotes a generic source symbol. By restricting the source alphabet to , we may assume that has full support on .
For a finite alphabet , let denote the set of probability mass functions on . We use for the fixed source distribution, for a generic source distribution, for a reproduction distribution, and for the conditional probability of reproducing given source symbol . The source distribution and conditional distribution induce the joint distribution and output marginal and . We identify probability mass functions with their probability vectors. For a positive integer , write . All logarithms are natural, so information is measured in nats.
For a deterministic vector , we denote its type or empirical distribution as
Let be the set of all -types (empirical distributions of length- vectors). For , let
be the type class of [4]. Types and type classes on are defined analogously, with reproduction types denoted by . Norms of finite-dimensional vectors are Euclidean, and neighborhoods of probability distributions are relative to the probability simplex.
The distortion function is bounded from above. Define the -letter distortion function and maximum distortion as
Definition 1 (Non-asymptotic fundamental limits for lossy compression). An -code for the (fixed-length) lossy compression problem consists of an encoder and a decoder such that the probability of excess distortion
For a positive integer , distortion level , and error tolerance , define the non-asymptotic fundamental limit
If the feasible set is empty, .
We now review some known results for this non-asymptotic fundamental limit, putting our main result in context. For a source distribution , define the average distortion, mutual information, rate-distortion function, minimum achievable distortion, and zero-rate distortion threshold as follows:
Throughout, we assume that the source-distortion pair satisfies . Hence, . Choose an optimal conditional distribution (also called test channel) that achieves the minimum in the definition of the rate-distortion function in (13). Let be the induced output distribution. Let be a distortion multiplier at , meaning that is a subgradient of at . Equivalently,
Lemma 2 establishes uniqueness of the distortion multiplier at every . Consequently, is differentiable on this interval and . Following Kostina and Verdú [7 Sec. II-C, Eq. (28)], for a reproduction distribution define the generalized -tilted information as
The -tilted information is
The rate-dispersion function [7] is defined as
We will also use the notations , , and to denote the standard Gaussian probability density function, cumulative distribution function (CDF) and complementary CDF respectively. In the following, positive constants denoted by may change from line to line; they do not depend on 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 , uniformly for in any compact subinterval of ,
Let denote the third-order remainder in the expansion of , i.e.,
Theorem 1 says that
The achievability and converse are proved in Sections III and § 4, respectively. A few remarks are in order.
Kostina and Verdú [7 Theorem 12] show for general stationary memoryless sources satisfying regularity conditions that satisfies, for sufficiently large,
where and are source- and distortion-dependent constants. For the biased binary source under the Hamming distortion [7 Theorem 23] with ,
For a uniform source on an -symbol alphabet under Hamming distortion [7 Theorem 27], Kostina and Verdú show that and that (22) holds for . Our result tightens (23) for discrete memoryless sources and identifies the third-order term.
For an i.i.d. source under squared-error distortion with , Kostina and Verdú [7 Theorem 40] show that and that, for fixed and all sufficiently large , (24) holds for some constant . 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.
Under Hamming distortion, the case corresponds to almost-lossless compression. For a source with positive varentropy , Strassen [24 Theorem 1.1] showed that, for fixed ,
The coefficient of changes sign at the lossless endpoint. Figure 1 illustrates how the same factor enters the two arguments.

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. . . . . . Lossy source coding. Sum the probabilities in the ball. . . Dot area probability mass. . (Lower bound in (54)). at fixed covering probability . .
For almost-lossless coding, write , the self-information of . The optimal code represents the most probable source sequences, with ties resolved as needed at a -quantile of . The number of sequences at or below is
The exponential weight makes the count depend mainly on words within a constant distance below . A sufficiently wide window of fixed width there has probability of order . A window strictly below also gives a lower bound when only some sequences at are represented. Thus the code size is of order .
For lossy coding at a fixed interior distortion, fix a source sequence whose type is close to and draw a reconstruction word from . Exponentially tilt the reconstruction distribution so that the total distortion has mean . The change-of-measure weight concentrates the contribution near , where a window of sufficiently large constant width has tilted probability of order . The covering probability is therefore of order (cf. (54) in Lemma 3 and [16 Eq. (3.17)]), where
Its Taylor approximation about is
To cover with probability at least a fixed , the number of independent reconstruction draws needed is of order , hence of order . Taking the logarithm gives the correction in the achievability argument.
We give counterexamples to distortion-ball estimates in Moulin’s two ISIT 2017 papers using binary Hamming distortion. Take
where is an optimal reproduction distribution. Write and .
In the converse paper [10], fix and let be the uniform distribution on the type class . For these marginals, lies strictly between the minimum distortion and the distortion under independence, as required by Proposition 4.1 in [10]. The total Hamming distortion is , where counts positions at which both sequences equal one. For , every attainable value of is odd, whereas is even. The shell contains no integer other than along this subsequence. Its width in normalized distortion is , which satisfies the prescribed condition . This contradicts the positive shell asymptotic in [10 Eq. (20)].
For , the boundary is attained exactly when . Counting and applying Stirling’s formula give
For marginals and , define Moulin’s fixed-marginal exponent [10 Eq. (10)] by
where the minimization is over joint distributions . Write . For near , the constraint is active. Indeed, mixing a joint distribution of distortion below with the product distribution , whose distortion is , decreases its mutual information until the distortion reaches . Let be the unique binary joint distribution with marginals , and Hamming distortion . Then . The boundary distribution has entries in the order 00, 01, 10, 11 and attains the rate-distortion minimum, so . The four entries of have derivatives with respect to . Hence
The constant in [10 Eq. (19)] is . Consequently, [10 Eq. (21)] would imply
The boundary atom alone contributes . This contradicts the ball bound used to control in the converse [10 Eq. (41)]. There is also a separate variational error in [10]. The minimization defining in [10 Eq. (10)] fixes the output marginal . In our notation, the Gibbs formula immediately before [10 Eq. (11)] reads where normalizes each row, and is the Lagrange multiplier for the distortion constraint. In general, this formula produces an output marginal different from . Enforcing requires an additional output-dependent Lagrange multiplier in the exponent.
In the achievability paper, [11 Prop. 5.1, Eq. (37)] uses the nonlattice factor for the product reproduction distribution in this example. Under the tilted distribution, the mismatch probabilities at source symbols 0 and 1 are and , respectively. Hence has mean , variance , and lattice span one. Exponential tilting and the lattice local central limit theorem give, for and every ,
The factor comes from summing the contributions of the layers :
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 converse coefficient claimed in [10] and removes the 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 , define the unnormalized tilted reverse subprobability mass function and its total mass by
Lemma 2 (Tilted information identities). At every , the supporting distortion multiplier is unique and satisfies
For every , the value of is independent of the choice of optimal test channel (a minimizer in the rate-distortion function (13)).
For any optimal test channel with output distribution ,
Moreover, for every , and whenever .
The identities in the lemma are well known in the literature. We include the proof for completeness.
Proof. The multiplier is unique if is differentiable at , since is a supporting slope at that point. To apply Gallager’s differentiability result [25 Corollary 9.4.1], put
Replacing by reduces the mean distortion of every test channel by . Thus, writing for the rate-distortion function under , we have . The distortion has a zero in each row, and lies strictly between zero and its zero-rate distortion threshold. Gallager [25 Corollary 9.4.1] gives differentiability at , hence at . The unique supporting multiplier is therefore . Evaluating the supporting inequality (16) at gives
This proves (38).
Let be the mean distortion of an optimal test channel . Since , the inequalities
force . This proves (39).
For any test channel with mean distortion , the supporting inequality (16) gives
By (39), every optimal test channel attains the right-hand side. Replacing by shifts the objective by a constant and thus preserves its minimizers.
For this minimization under , Gallager [25, Theorem 9.4.1] gives a unique factor such that every optimal channel satisfies
Summing over gives . Since is unique and is fixed, both and are independent of the choice of optimal test channel . Substituting this expression for into the channel representation in (46) proves (40).
Using (40) and (39), we obtain
This proves (41).
Finally, substituting the expression for into the definition of gives
Gallager [25, Eq. (9.4.9)] bounds this sum by one, with equality when . Finiteness of and full support of give . 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 . For each source sequence whose type is close to , we lower bound the probability that one reconstruction word covers by a constant times . The factor accounts for the term in the achievable log codebook size.
The main refinement is to retain the random exponent 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 on an event of probability . This accounts for the extra in in (23). When , we use (28) and the quantitative delta method of Pinelis and Molzon [12, Theorem 2.9] to approximate the distribution of directly, with a uniform error in its distribution function. We then average the conditional covering error directly, which also avoids the separate term in (23). When , a direct bound on the quadratic remainder suffices.
Generalized Tilted Information and Distortion Balls
For and , define
The associated generalized tilted information is in (17). Fix an optimal reproduction distribution and put . The variational representations in [19 Proposition 1] and [16 Property 1] give the fixed reproduction distribution exponent
The block exponent introduced in (27) satisfies the identity
Thus is the per-symbol exponent, whereas is the corresponding block exponent. Furthermore, in (50)–(51), is an optimized expectation of generalized tilted information. Here is held fixed as varies, while is optimized for each . At the true source distribution and , whereas in general. The expansion below is the counterpart, with the reproduction distribution held fixed, of Ingber and Kochman’s expansion of the fully optimized [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 of , constants , and an integer such that is smooth on , , and every satisfies
For every , every , and every , if , then
Proof. Put and . The saddlepoint identities [16 Property 1] give
The strict positivity follows because otherwise every row is constant on , making and . The implicit function theorem gives a smooth positive maximizer near with . Since is strictly concave, this stationary point is its unique maximizer. Let
After shrinking , there is a constant such that for every and every between and . Taylor’s theorem gives
This proves (53). At , this also gives .
To apply Theorem 3 of Yang and Zhang [16], restrict the reconstruction alphabet to and shrink so that every has full support on . Define . The tilted mean satisfies
Every tilted conditional distribution is positive on , and at least one distortion row is nonconstant on this support. Consequently,
These are the distortion-range conditions required by the theorem. Its finiteness conditions hold because is bounded.
Viewing as a function of , the saddlepoint identities [16 Property 3] give
The third moment term in [16 Theorem 3] is
Put . By the continuity of and the tilted variances, there exist constants , , , such that for a sufficiently small ,
Choose a fixed such that . For a source sequence of type , apply Yang and Zhang’s Eq. (3.18) [16] with source distribution . For large enough such that , it yields
This proves (54) with .
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 , define the reproduction ball .
Lemma 4 (Kostina–Verdú random coding bound). For every positive integer , there exist an encoder and a decoder whose excess-distortion probability satisfies
Using for and choosing , we obtain the relaxation
We evaluate this bound after establishing the normal approximation for its empirical exponent. Define the (truncated) empirical exponent by
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 , then
Proof. Let and set , where is the unit vector at . Then,
On define where , and zero otherwise. The space , equipped with the Euclidean norm, is a finite-dimensional Hilbert space. The function is Borel measurable, satisfies , and obeys . Set . Lemma 3 verifies the local quadratic condition Eq. (2.1) [12]:
Theorem 2.9 of [12] now gives
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 in a fixed compact subset of , there is a constant such that for all sufficiently large ,
Proof. Write and , and let . Also define the event and set . Hoeffding’s inequality for the empirical distribution gives for sufficiently large . The relaxed random coding bound in (68) and Lemma 3 give
For the case , define the standard Gumbel probability density
which satisfies
Since , Tonelli’s theorem gives
Lemma 5, followed by the bound , now yields
Take . Choose so that for all and . For fixed and large enough ,
when .
For the case , define the event . Choose sufficiently large and then . Since almost surely, Markov’s inequality, (53) and (68) give, for all sufficiently large , and ,
In either case, put with the corresponding , and choose
Then . Since , for all sufficiently large ,
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 . We bound the probability that a source sequence with is covered by the codebook. For , the key strengthening of Kostina and Verdú’s converse is a bound of 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 factor.
We choose so that the contribution of the distortion balls to the union bound is of order , i.e., . This threshold is lower by than the threshold used to evaluate Kostina and Verdú’s converse [7 Theorem 7]. The normal approximation then improves the third-order lower bound from to . The following subsections establish the uniform ball estimate and complete this argument.
Reconstruction Codewords That Cover Typical Inputs
For a reconstruction codeword , define its source-space distortion ball by
We show that if , where is the typical set defined in (92) below, then contains two reconstruction symbols , each occurring linearly often, such that is nonconstant in . These symbols will verify the full-rank covariance condition required by the weighted-strip estimate in [13 Lemma 3].
Put and
Write if is constant in . This defines an equivalence relation on . The equivalence class containing is . Put . Fix with . Call a symbol in a reconstruction codeword frequent if it occurs at least times.
Lemma 7 (Distortion columns of a typical ball). There exist constants such that for every . If , then contains two frequent symbols satisfying .
Proof. Put . Since , Hoeffding’s inequality gives
At least one symbol of is infrequent. Suppose that all frequent symbols lie in one equivalence class . Choose minimizing within at one . Since the column differences are constant, this minimizes at every . Every letter outside occurs fewer than times, so . Thus, for every ,
Hence , 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 in (36) and its mass in (37). Normalize it to obtain the probability mass function
For fixed , define the reverse product distribution
Also define the accumulated -tilted information and the total distortion, respectively, by
The component likelihood ratios multiply to give
where and are evaluated at .
The likelihood ratio in (102) contains the exponential weights and . When , 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 while restricting to an interval of fixed width. When , 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 third-order term in the converse.
Proposition 8 (Uniform ball and tilted information bound). For , every and every satisfy
Proof. Let the event in the probability in (103) be . Define the scaled distortion slack . If the ball has an empty intersection with , then the event is empty. Otherwise, Lemma 7 supplies two inequivalent frequent symbols in . Form disjoint pairs of coordinates, each containing one occurrence of and one occurrence of , where
See Figure 2. Under , the pair contributions to are i.i.d. copies of the random vector

Figure 2. Illustration of the paired and remaining coordinates in the proof of Proposition 8
Their covariance has rank . Indeed, a linear functional constant on the support would give
Inequivalence forces , and if , this then forces . If , the -coordinate is constant and at least one of the two distortion columns is nonconstant, so the remaining scalar variance is positive.
Split into sums over the paired and remaining coordinates, denoted by subscripts pair and rem, and let be the -field generated by the remaining source coordinates. The exponential-weight estimates in [13 Lemma 3] and [21 Lemma 20] give
For , this is [13 Lemma 3] with sample size and strip half-width . For , dropping the constant -strip indicator gives the scalar bound in [21 Lemma 20]. The scalar bound at the closed threshold follows by applying [21 Lemma 20] at and letting . The constants are uniform over the finitely many pairs .
Average over , partition into unit intervals and use (102). For both values of ,
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 such that every -code satisfies
for all sufficiently large , uniformly over in a compact subinterval of .
Proof. Given a code with decoder , write for the reconstruction sequence associated with index . Given the set of reproduction sequences , define its source-space distortion balls as in (91) and their union by
A source sequence outside cannot be reproduced within distortion . Therefore . For a threshold , put and . Since , Proposition 8 gives
Since , Lemma 7 gives
For , take . Applying the Berry–Esseen theorem to ,
The inverse normal tail is Lipschitz on compact subintervals of . Hence, uniformly for in such an interval and all sufficiently large ,
For , gives . Then (116) implies that
If , the factor in brackets is at least for all sufficiently large , which gives .
Propositions 6 and 9 together prove Theorem 1.
Conclusion and Future Work
We established the third-order correction 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 .
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]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]K. Marton, “Error exponent for source coding with a fidelity criterion,” IEEE Trans. Inf. Theory, vol. 20, pp. 197–199, Mar. 1974.DOI
- [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]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]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]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]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]V. Kostina, Lossy Data Compression: Nonasymptotic Fundamental Limits. Ph.D. dissertation, Princeton University, Princeton, NJ, USA, Sept. 2013.
- [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]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]P. Moulin, “Source coding with distortion profile constraints,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 3215–3219, June 2017.DOI
- [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]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]R. J. Pilc, Coding Theorems for Discrete Source-Channel Pairs. Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 1967.
- [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]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]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]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]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]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]Y. Polyanskiy, Channel Coding: Non-Asymptotic Fundamental Limits. Ph.D. dissertation, Princeton University, Princeton, NJ, USA, Nov. 2010.
- [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]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]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]R. G. Gallager, Information Theory and Reliable Communication. New York, NY, USA: Wiley, 1968.
- [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]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]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]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]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