PaperlayerView exact revision on arXiv

Source-linked AI summary

Mismatched Decoding: Error Exponents, Second-Order Rates and Saddlepoint Approximations

Jonathan Scarlett, Alfonso Martinez, Albert Guillén i Fàbregas

arXiv:1303.6166v3cs.ITmath.IT

TL;DR

Mismatched decoding uses a possibly suboptimal maximum-metric rule, and the paper examines random-coding performance beyond achievable rates. It introduces a multiple-cost cost-constrained ensemble and saddlepoint approximations for i.i.d. coding bounds. The ensemble matches constant-composition exponents and second-order rates with at most two costs, while the approximations unify fixed- and varying-rate asymptotics.

  • Problem

    The paper addresses the open problem of analyzing random-coding error probability comprehensively for mismatched decoding, beyond the existing focus on achievable rates.

    Source: §I · p. 1

  • Method

    The paper introduces a cost-constrained random-coding ensemble with multiple auxiliary costs and uses saddlepoint approximations for two i.i.d. random-coding bounds.

    Source: §II · p. 3, §VI · p. 13

  • Results

    At most two auxiliary costs match constant-composition error exponents and second-order rates, while the saddlepoint expressions characterize the bounds at fixed and varying rates.

    Source: §VI · p. 13

  • Takeaways & Limitations

    The cost-constrained ensemble offers constant-composition-like performance while applying to infinite or continuous alphabets, and the i.i.d. approximations are reported accurate at short block lengths.

    Source: §VI · p. 13

    For fixed rates, the prefactor estimate based on (111) diverges as ρ̂ approaches 0 or 1, making the omitted-higher-order estimate inaccurate near Rcr unless n is large.

    Source: B. Approximation for rcus(n, M) · p. 11

Abstract

from arXiv · show

This paper considers the problem of channel coding with a given (possibly suboptimal) maximum-metric decoding rule. A cost-constrained random-coding ensemble with multiple auxiliary costs is introduced, and is shown to achieve error exponents and second-order coding rates matching those of constant-composition random coding, while being directly applicable to channels with infinite or continuous alphabets. The number of auxiliary costs required to match the error exponents and second-order rates of constant-composition coding is studied, and is shown to be at most two. For i.i.d. random coding, asymptotic estimates of two well-known non-asymptotic bounds are given using saddlepoint approximations. Each expression is shown to characterize the asymptotic behavior of the corresponding random-coding bound at both fixed and varying rates, thus unifying the regimes characterized by error exponents, second-order rates and moderate deviations. For fixed rates, novel exact asymptotics expressions are obtained to within a multiplicative 1+o(1) term. Using numerical examples, it is shown that the saddlepoint approximations are highly accurate even at short block lengths.

I. INTRODUCTION

The paper studies random-coding error probability for mismatched maximum-metric decoding, where the decoder's metric may differ from the optimal choice. It introduces a multiple-cost ensemble and analyzes its error exponents, second-order rates, and refined asymptotics.

A. System Setup

  • Under mismatched decoding, a decoder maximizes a possibly suboptimal metric over codewords, while the highest achievable rate remains an open problem.The setup uses a uniform message and a codebook transmitted through a channel; maximum-likelihood decoding is recovered by setting q(x,y) = W(y|x).Source: §I · p. 1, A. System Setup · p. 1

I. INTRODUCTION

  • The paper analyzes random-coding error probability beyond achievable rates, covering error exponents, second-order coding rates, and saddlepoint-based refined asymptotics.The considered decoder uses maximum-metric decoding with a metric that may differ from the optimal choice.Source: §I · p. 1

B. Notation

  • The paper uses empirical distributions, joint and marginal distributions, expectations, and mutual information to express its coding results.Rates are in nats except in the examples, where bits are used.Source: B. Notation · p. 2

C. Overview of Achievable Rates

  • The i.i.d., constant-composition, and cost-constrained ensembles can yield different achievable rates under mismatched decoding, although all yield mutual information under maximum-likelihood decoding.The LM rate can exceed the GMI, and the LM rate has been shown valid for continuous alphabets in the cited work.Source: C. Overview of Achievable Rates · p. 2

D. Contributions

  • A cost-constrained ensemble with multiple auxiliary costs provides an alternative to constant-composition coding, and at most two costs can recover its error exponent, sometimes fewer.The ensemble is applicable to channels with infinite or continuous alphabets.Source: D. Contributions · p. 2
  • The paper gives cost-constrained second-order achievability results and saddlepoint approximations for two i.i.d. random-coding bounds across fixed and varying positive rates.For fixed rates, the approximations characterize prefactor growth and novel multiplicative O(1) terms; numerical examples show accuracy at small block lengths.Source: D. Contributions · p. 3

II. RANDOM-CODING BOUNDS AND ENSEMBLES

  • The cost-constrained ensemble conditions i.i.d. codeword generation on empirical means of auxiliary costs being close to their expected values.The generalization includes multiple costs and applies to infinite or continuous alphabets.Source: D. Contributions · p. 2, §II · p. 3

III. RANDOM-CODING ERROR EXPONENTS

The section derives an ensemble-tight error exponent for cost-constrained random coding. The ensemble includes i.i.d. and constant-composition coding as special cases, and a direct derivation extends to more general alphabets under finite second-moment conditions.

III. RANDOM-CODING ERROR EXPONENTS

  • The section presents an ensemble-tight error exponent for cost-constrained random coding, with i.i.d. and constant-composition ensembles as special cases.The exponent is motivated as a measure of the asymptotic exponential behavior of coded-communication error probability.Source: §III · p. 4

A. Cost-Constrained Ensemble

  • The random-coding error probability for the cost-constrained ensemble satisfies an exponent characterized by an optimization over distributions constrained by the auxiliary costs.The theorem gives an exponent expression for the ensemble defined by the auxiliary costs.Source: A. Cost-Constrained Ensemble · p. 4
  • A direct exponent derivation extends to more general alphabets when the cost functions have finite second moments, although it does not establish ensemble tightness.The derivation also extends straightforwardly to channels with input constraints.Source: A. Cost-Constrained Ensemble · p. 4
  • With one auxiliary cost, the cost-constrained exponent can be strictly higher than the earlier achievable exponent described in the section.The subexponential normalizing factor does not affect the exponent.Source: A. Cost-Constrained Ensemble · p. 5

B. i.i.d. and Constant-Composition Ensembles

The section relates cost-constrained exponents to the i.i.d. and constant-composition ensembles, then determines how many auxiliary costs are needed to match the constant-composition exponent. The required number decreases when the input distribution or decoding metric is optimized.

B. i.i.d. and Constant-Composition Ensembles

  • With constant-composition constraints, the cost-constrained exponent recovers Csiszár’s constant-composition exponent, which is tight with respect to the ensemble average.Setting L = 0 recovers the i.i.d. exponent of Kaplan and Shamai.Source: B. i.i.d. and Constant-Composition… · p. 5
  • The cost-constrained exponent recovers the LM rate when its auxiliary cost is optimized, while the i.i.d. exponent is positive below the GMI rate.The constant-composition exponent recovers the stronger LM rate.Source: B. i.i.d. and Constant-Composition… · p. 6

C. Number of Auxiliary Costs Required

  • Reducing the number of auxiliary costs is relevant because the subexponential prefactor grows more slowly when L is smaller.The section studies the number of costs needed to match the constant-composition exponent.Source: C. Number of Auxiliary Costs Required · p. 6
  • At most two auxiliary costs recover the constant-composition exponent; one suffices if either the input distribution or decoding rule is optimized, and none if both are optimized.For a given input distribution, the constant-composition ensemble can have a strictly higher exponent than the cost-constrained ensemble even with one cost; among the three ensembles, it yields the best exponent.Source: C. Number of Auxiliary Costs Required · p. 6

D. Numerical Example

The numerical example compares random-coding exponents for a ternary channel under minimum-Hamming-distance decoding. The section also develops second-order achievability for the cost-constrained ensemble and describes extensions to more general channels.

D. Numerical Example

  • The cost-constrained ensemble has the highest exponent, while the i.i.d. exponent is lower than the alternatives and yields a worse achievable rate.For the stated channel parameters, the achievable rates are IGMI(Q) = 0.387, ILM(Q) = 0.449, and I(X;Y) = 0.471 bits/use.Source: D. Numerical Example · p. 6

IV. SECOND-ORDER CODING RATES

  • Theorem 5 gives an achievable second-order expansion for the cost-constrained ensemble, analyzed as a normal approximation of rcus.The analysis also defines the mismatched information density and relates its LM rate to Is,a(Q) after optimizing s and a(·).Source: A. Cost-Constrained Ensemble · p. 7, §IV · p. 7

A. Cost-Constrained Ensemble

  • The second-order result extends beyond finite alphabets when the required moments exist; an alternative adds two auxiliary costs and requires a finite sixth moment.The techniques cover memoryless input-constrained channels with infinite or continuous alphabets under these conditions; for AWGN with maximal power and ML decoding, s = 1 and a(·) = 0 yield the achievability part of dispersion.Source: A. Cost-Constrained Ensemble · pp. 8–9

B. i.i.d. and Constant-Composition Ensembles

The cost-constrained ensemble has a third-order term that avoids the alphabet-size growth stated for constant-composition coding. The required number of auxiliary costs depends on which parameters are optimized.

B. i.i.d. and Constant-Composition Ensembles

  • The cost-constrained ensemble yields a third-order term −L/2 log n + O(1), while the constant-composition bound has an O(log n) term growing linearly in |X|.The i.i.d. second-order expansion follows using the mean and variance identities for i.i.d. coding; under technical conditions, its O(1) term can improve to 1/2 log n + O(1).Source: B. i.i.d. and Constant-Composition… · p. 9

C. Number of Auxiliary Costs Required

  • For ML decoding, the auxiliary cost a1(·) is unnecessary; for any metric, a2(·) is unnecessary when Q and a(·) are optimized.The latter follows because optimizing makes the conditional expectation of the information density constant over inputs in the support of Q.Source: C. Number of Auxiliary Costs Required · p. 9
  • The auxiliary-cost count matching constant-composition performance is L = 2 generally, L = 1 if the metric or input distribution is optimized, and L = 0 if both are optimized.The same counts apply to matching both the random-coding exponent and second-order rates.Source: C. Number of Auxiliary Costs Required · p. 9

V. SADDLEPOINT APPROXIMATIONS

The section develops saddlepoint approximations for i.i.d. random-coding bounds, aiming to characterize their behavior at fixed and varying rates. For rcus, the approximation remains accurate near rate boundaries, while a simpler fixed-rate prefactor can become inaccurate near them unless block length is large.

V. SADDLEPOINT APPROXIMATIONS

  • The analysis targets i.i.d. random-coding bounds across fixed-rate, fixed-error-probability, and moderate-deviations regimes.The section seeks approximations for both rcu and rcus that remain tight for fixed and varying rates.Source: §V · p. 9

A. Preliminary Definitions and Results

B. Approximation for rcus(n, M)

  • Theorem 6 formally derives the rcus approximation for lattice and non-lattice cases; when U_s(Q)=0, rcus is exactly computable.A heuristic non-lattice derivation appeared in.Source: B. Approximation for rcus(n, M) · p. 10
  • The fixed-rate prefactor estimate can diverge as ρ̂ approaches 0 or 1, making it inaccurate near those boundaries unless n is large.The alternative expression remains bounded for ρ̂ in [0, 1] and characterizes rcus for varying rates as well.Source: B. Approximation for rcus(n, M) · p. 11
  • Theorem 6’s saddlepoint approximation characterizes rcus within multiplicative 1+o(1) for fixed and varying rates, including rates approaching the critical rate or I_s(Q).When U_s(Q)=0, rcus can instead be computed exactly.Source: B. Approximation for rcus(n, M) · pp. 10–11

C. Approximation for rcu(n, M)

The section refines the analysis of rcu with a tighter bound under technical assumptions and develops its saddlepoint approximation. Under the stated assumptions, the approximating bound yields matching rate asymptotics up to the specified remainder, and fixed-rate prefactors characterize constants left unspecified in prior work.

C. Approximation for rcu(n, M)

1) Technical Assumptions:

  • The passages state that rcu = rcus for any s > 0; consequently, c rcus also approximates rcu, without establishing a more specific preceding condition.Source: 1) Technical Assumptions · p. 11

2) Definitions:

  • The set I_s is the support of a random variable used to analyze the inner probability; its lattice span and that of i_s(X,Y) coincide when Y_1(Q)=Y.Source: 2) Definitions · p. 11

3) Main Result:

  • Under Theorem 7’s setup and assumptions (114)–(115), the approximating bound’s rate expansion matches that of rcu* up to the O(1) term, which is 2 log n + O(1).Source: 3) Main Result · p. 12
  • For R≥I_s(Q), β_n and α_n have matching asymptotics, and the expansion specifies multiplicative Θ(1) terms left unspecified in [22].Source: 3) Main Result · p. 12

D. Numerical Examples

The numerical examples compare saddlepoint approximations and random-coding bounds at short block lengths, then discuss the ensemble’s broader scope and its extension to system input constraints.

D. Numerical Examples

  • At n = 60, c_rcus and c_rcu*s are indistinguishable across rates, while the normal approximation is less precise, particularly at low rates.The error-exponent approximation is close to rcus at low rates but pessimistic at high rates; c_rcu*s lies slightly above rcu at low rates.Source: D. Numerical Examples · p. 12, Figure 2 · p. 13
  • At target error probability ǫ = 10−8, c_rcus and rcus are indistinguishable, while the exact-asymptotics approximations are accurate except near the critical rate.The gap between the error-exponent approximation and rcus widens at larger block lengths.Source: D. Numerical Examples · p. 12, Figure 3 · p. 13

VI. DISCUSSION AND CONCLUSION

  • The cost-constrained ensemble with multiple auxiliary costs performs similarly to constant-composition coding while remaining applicable to infinite or continuous alphabets.The required number of auxiliary costs can be reduced when the input distribution or decoding metric is optimized.Source: §VI · p. 13

Extension to Channels with Input Constraints

  • For a system cost constraint, the codeword cost must not exceed its mean, and the stated exponent and second-order results remain valid when φc ≤ Γ.The i.i.d. ensemble can produce constraint-violating codewords with positive probability in non-trivial cases; the cost-constrained ensemble requires modifying Dn to impose the system-cost constraint.Source: Extension to Channels with Input… · p. 13

APPENDIX

The appendix proves the ensemble exponent result through type-based probability estimates, minimax and duality arguments, and necessary optimality conditions.

A. Proof of Theorem 2

  • The proof of Theorem 2 uses type classes to express codeword distributions and probability terms, then replaces type minimizations with joint-distribution minimizations.The replacement uses continuity, and auxiliary-cost constraints become equalities in the limiting optimization.Source: A. Proof of Theorem 2 · pp. 13–14

B. Proof of Theorem 3

  • The proof of Theorem 3 converts the positive-part expression into an optimization and uses Fan’s minimax theorem and Lagrange duality to obtain an equivalent form.The argument applies minimax to a convex objective in PXY and a jointly concave objective in the optimization parameters.Source: B. Proof of Theorem 3 · p. 14

C. Necessary Conditions for the Optimal Parameters

  • The optimal-parameter analysis applies KKT conditions to Q and a, with the resulting condition making the logarithm in (39) independent of x.The derivation substitutes the KKT conditions and rearranges them to obtain the stated implication.Source: C. Necessary Conditions for the… · pp. 14–15

D. Asymptotic Behavior of the Saddlepoint Approximation

The asymptotic analysis distinguishes rates around the critical and mutual-information thresholds, and treats lattice sums through Gaussian sampling and bounds on their terms.

D. Asymptotic Behavior of the Saddlepoint Approximation

  • Below Rcr_s(Q), the non-lattice approximation has ρ̂ = 1 and c1 < 0; at the critical rate, c1 = 0 and the leading term changes to a Gaussian tail contribution.For rates above I_s(Q), the roles of the two terms reverse, with ρ̂ = 0 and c1 > 0; at I_s(Q), c1 = 0.Source: D. Asymptotic Behavior of the… · p. 15
  • In the lattice case below Rcr_s(Q), the Gaussian sum approaches one as n increases because fixed-width discrete sampling better approximates the Gaussian integral.The added terms contribute only an exponentially small amount when c1 < 0.Source: D. Asymptotic Behavior of the… · p. 15
  • For the lattice case at the critical and mutual-information boundaries, the analysis handles both sums with related bounds and derives the stated asymptotics.The proof weakens one sum to its first term up to an O(remainder term), and obtains the second term similarly.Source: D. Asymptotic Behavior of the… · p. 15

E. Proof of Theorem 6

The proof of Theorem 6 rewrites the random-coding bound using a tilted distribution and refined limit arguments, controlling approximation errors even when rates vary with block length.

E. Proof of Theorem 6

  • The Bahadur–Rao tail estimates cannot be applied directly because the event threshold is random and rates may lie where the MGF derivative at zero is nonzero.That derivative equals c1 in the paper’s notation.Source: E. Proof of Theorem 6 · p. 16
  • The proof tilts the distribution of R − is(X, Y), then uses the tilted variable’s mean c1 and variance c2 to apply a refined central limit theorem.The proof assumes U_s(Q) > 0, which implies c2 > 0.Source: 1) Alternative Expressions for rcus · p. 16, 2) Non-lattice Case · p. 16

2) Non-lattice Case:

  • For varying rates, Table I shows I2,n = o(αn) and I3,n = o(αn) for every limiting rate R*, establishing the required error control.The table tracks the growth rates of αn, I2,n, and I3,n and identifies which integral dominates each term.Source: 2) Non-lattice Case · pp. 16–17

3) Lattice case:

The lattice-case argument uses a local limit theorem to split the sum across lattice indices, obtaining I1,n = αn and I2,n = o(αn).

3) Lattice case:

  • The argument invokes a local limit theorem with E[Z] = c1 and Var[Z] = c2 > 0.Source: 3) Lattice case · p. 17
  • I1,n = αn and I2,n = o(αn) in the lattice case.The first sum is over nonnegative lattice indices and the second over negative indices.Source: 3) Lattice case · p. 17

F. Proof of Theorem 7

The proof combines technical lemmas to control the RCU bound, including when rates vary with blocklength. Local limit arguments cover lattice and non-lattice sums.

F. Proof of Theorem 7

Loading 1303.6166v3…