PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities

Vincent Y. F. Tan

arXiv:1504.02608v1cs.IT

TL;DR

Finite-blocklength information-theoretic quantities are often intractable beyond special cases. This monograph uses non-vanishing-error hypothesis testing to derive second- and third-order coding expansions, including source dispersion and channel backoff from capacity.

  • Problem

    Many finite-blocklength quantities are intractable except for a few special sources and channels.

  • Method

    The monograph develops asymptotic coding expansions by revisiting binary hypothesis testing and applying information-theoretic tools including the method of types.

  • Results

    Second- and sometimes third-order expansions characterize source-rate convergence through dispersion and quantify finite-blocklength channel backoff from capacity.

  • Takeaways & Limitations

    Binary hypothesis testing provides a common basis for analyzing fixed-length source coding and point-to-point channel coding with non-vanishing error probabilities.

  • Takeaways & Limitations

    The treatment excludes several problems whose second-order asymptotics remain incomplete or unavailable, including discrete memoryless Gel’fand-Pinsker and causally known-state channels.

Abstract

from arXiv · show

This monograph presents a unified treatment of single- and multi-user problems in Shannon's information theory where we depart from the requirement that the error probability decays asymptotically in the blocklength. Instead, the error probabilities for various problems are bounded above by a non-vanishing constant and the spotlight is shone on achievable coding rates as functions of the growing blocklengths. This represents the study of asymptotic estimates with non-vanishing error probabilities. In Part I, after reviewing the fundamentals of information theory, we discuss Strassen's seminal result for binary hypothesis testing where the type-I error probability is non-vanishing and the rate of decay of the type-II error probability with growing number of independent observations is characterized. In Part II, we use this basic hypothesis testing result to develop second- and sometimes, even third-order asymptotic expansions for point-to-point communication. Finally in Part III, we consider network information theory problems for which the second-order asymptotics are known. These problems include some classes of channels with random state, the multiple-encoder distributed lossless source coding (Slepian-Wolf) problem and special cases of the Gaussian interference and multiple-access channels. Finally, we discuss avenues for further research.

Fundamentals · Introduction

The monograph studies fixed-error asymptotics, asking how closely finite-blocklength source and channel coding can approach Shannon’s first-order limits. It develops Gaussian and higher-order approximations and surveys their consequences across single- and multi-user information theory.

  • Introduction: Shannon’s work established the theoretical and mathematical foundations underlying modern communication systems and influenced statistics, economics, biology, and cryptography.
  • Introduction: For a DMS, the minimum asymptotic compression rate is H(X) bits per source symbol, while finite blocklengths require analyzing non-vanishing error probabilities.The formal quantity M*(P^n, ε) denotes the minimum code size for error probability ε ∈ (0, 1).
  • Introduction: Exact evaluations of finite-blocklength source and channel fundamental limits are generally intractable, except for a few special sources and channels.
  • Introduction: Strassen’s refinements introduce second-order terms involving source and channel dispersions, quantifying finite-blocklength deviations from entropy and capacity.The source correction includes V(X)/n Φ^-1(1 − ε), while channel dispersion describes the finite-blocklength backoff from capacity.
  • 1.1 Motivation for this Monograph: The monograph focuses exclusively on problems with error probabilities bounded by ε ∈ (0, 1), seeking asymptotic expansions or second-order terms.
  • 1.1 Motivation for this Monograph: Fixed-error asymptotics reveal effects absent from first-order limits, including nonoptimal source-channel separation, feedback gains, universality penalties, and benefits from encoder side information.These phenomena concern excess-distortion source coding, variable-length or full-output feedback, third-order universality penalties, and Slepian-Wolf corner points.
  • 1.2 Preview of this Monograph: Its roadmap reviews information-theoretic quantities, method-of-types tools, and Berry-Esseen bounds before applying hypothesis-testing expansions to compression and surveying network problems with conclusive second-order characterizations.The network examples include channels with random state and other selected multi-user settings.

1. Introduction · 3. Source Coding

The monograph develops fixed-error asymptotics across channel and source-coding problems, supported by information-theoretic preliminaries, the method of types, and quantitative probability bounds. The introductory material emphasizes conclusive operational results while acknowledging that the broader area is rapidly expanding and not exhaustively covered.

  • 3. Source Coding: The monograph covers channel coding, channels with state, Slepian-Wolf source coding, Gaussian interference channels, and Gaussian multiple-access channels with degraded message sets.The latter MAC is also called the cognitive or asymmetric MAC.
  • 1. Introduction: The author presents the surveyed fixed-error results as conclusive operational characterizations, while noting that the rapidly expanding field is not exhaustively covered.Chapter 9 summarizes additional results and open problems.
  • 1.3 Fundamentals of Information Theory: The treatment assumes information theory at the level of Cover and Thomas and extensively uses the method of types.The method of types receives a dedicated development for finite alphabets.
  • 1.3.1 Notation: The notation follows Csiszár–Körner and Han, distinguishing random variables, realizations, finite alphabets, vectors, and matrices with standard conventions.The monograph also specifies coordinatewise vector inequalities, transposes, zero vectors, identity matrices, norms, and asymptotic notation.
  • 1.3.2 Information-Theoretic Quantities: Core information-theoretic quantities include entropy, conditional and joint entropy, mutual information, conditional mutual information, and relative entropy.Relative entropy is nonnegative, with equality exactly when the two distributions coincide, and mutual information is a special case of relative entropy.
  • 1.4 The Method of Types: The method of types represents sequences through empirical distributions, type classes, conditional types, and V-shells.Its key counting property is that the number of types is polynomial in the blocklength n, while type-class probabilities have exponential behavior governed by relative entropy.
  • 1.5 Probability Bounds: Basic probability tools include Markov’s inequality, Chebyshev’s inequality, the weak law of large numbers, and Gaussian convergence under 1/√n scaling.For i.i.d. zero-mean variables with finite variance, the sample average converges to zero in probability and the normalized sum converges in distribution to a Gaussian.
  • 1.5.2 Central Limit-Type Bounds: Berry–Esseen bounds provide uniform quantitative Gaussian convergence with remainder O(1/√n), supporting third-order asymptotics for hypothesis testing and coding problems.The framework also includes independent non-identically distributed, vector, non-identity covariance, and function-of-vector versions.

Binary Hypothesis Testing

This section develops binary hypothesis testing with a non-vanishing type-I error, introducing ε-hypothesis-testing and ε-information-spectrum divergences as tools for asymptotic coding analyses. It relates these quantities for product distributions and derives asymptotic bounds, including the Chernoff–Stein lemma.

  • Binary hypothesis testing: The chapter studies simple binary tests with type-I error bounded by ε while minimizing the type-II error, yielding the operational quantity β_{1−ε}(P,Q).This quantity characterizes the non-asymptotic performance of the optimal test and supports later coding theorems.
  • Binary hypothesis testing: The ε-hypothesis-testing divergence measures distinguishability, is positive unless P = Q, and obeys the data processing inequality.The monograph uses this divergence because it shares important properties with relative entropy.
  • Binary hypothesis testing: The ε-information-spectrum divergence instead analyzes the distribution of the log-likelihood ratio, making it easier to compute than the ε-hypothesis-testing divergence.For product measures, the log-likelihood ratio is a sum of independent random variables, enabling probability-tail estimates.
  • Binary hypothesis testing: The two divergences can be converted into one another through bounds valid for every ε ∈(0, 1) and η ∈(0, 1 −ε).The bounds are established using likelihood-ratio tests and threshold arguments.
  • Asymptotic expansions: For product distributions, asymptotic expansions of the information-spectrum divergence are developed under finite relative-entropy variance and a uniformly positive variance lower bound.The analysis permits non-identical component distributions and uses Berry–Esseen estimates.
  • Asymptotic expansions: The resulting bounds extend to deterministic tests, show that randomization is unnecessary for the relevant lower bound, and yield the Chernoff–Stein lemma.These observations enable the connection between hypothesis testing and fixed-to-fixed length lossless source coding.

Point-To-Point Communication · Source Coding

The source-coding chapters develop non-asymptotic achievability and converse bounds for fixed-to-fixed length lossless and lossy compression, then derive asymptotic expansions under non-vanishing error or excess-distortion probabilities. They connect lossless coding to binary hypothesis testing and use source dispersion, tilted information, and method-of-types arguments to characterize second-order behavior, including partially universal schemes.

  • Source Coding: Fixed-to-fixed length lossless compression attains the entropy H(P) for discrete memoryless sources, while lossy compression is governed by the rate-distortion function R(P, ∆).For continuous sources, lossless compression is not possible and distortion must be allowed.
  • 3.1 Lossless Source Coding: Non-Asymptotic Bounds: For non-vanishing ε, the chapter formulates lossless coding through the minimum code size M ∗(P, ε) and develops non-asymptotic achievability and converse bounds.For DMSs, the source distribution is replaced by n independent copies and the bounds are evaluated asymptotically.
  • 3.1.1 An Achievability Bound: Fixed-to-fixed length lossless source coding is treated as binary hypothesis testing, yielding an achievability bound based on selecting a typical set with probability of omission at most ε.The bound is expressed using β1−ε(P, Q) or the ε-hypothesis testing divergence.
  • 3.1.2 A Converse Bound: The converse similarly relates every (M, ε)-code to the ε-information spectrum divergence with the alternate measure chosen as counting measure.The converse holds for any η ∈(0, 1 −ε).
  • 3.2 Lossless Source Coding: Asymptotic Expansions: When V (P) > 0, the asymptotic expansion of log M ∗(P n, ε) refines the first-order limit H(P) using the source dispersion, the variance of −log P(X).If V (P) = 0, the source is deterministic or uniform.
  • 3.3 Second-Order Asymptotics of Lossless Source Coding via the Method of Types: The method-of-types construction gives a partially universal lossless code that requires H(P) and V (P), but no other characteristic of P, while controlling the error probability through empirical entropy.Its proof uses the Berry-Esseen theorem rather than Sanov’s theorem because the rate deviation is of second-order scale.
  • 3.4 Lossy Source Coding: Non-Asymptotic Bounds: For lossy compression, the framework introduces a distortion measure, assumes a unique minimizing test channel W ∗, and establishes random-coding achievability together with a converse based on ∆-tilted information.The expectation of ∆-tilted information equals R(P, ∆), and its variance is expected to govern second-order asymptotics.
  • 3.5 Lossy Source Coding: Asymptotic Expansions: Under the stated regularity and moment conditions, the lossy source-coding expansion uses the rate-dispersion function V (P, ∆), whose variance characterization is also obtained through a method-of-types analysis.The asymptotic result is stated for V (P, ∆) > 0.

Channel Coding · Channel Dispersions

The chapter develops fixed-error, non-vanishing-error asymptotics for point-to-point channel coding, beginning with non-asymptotic limits and bounds linked to binary hypothesis testing. It then refines DMC capacity by characterizing the first three terms of log M*(W^n, ε), including dispersion quantities.

  • Channel Coding: The chapter revisits channel coding with non-vanishing error probabilities, deriving and evaluating non-asymptotic fundamental limits as blocklength grows.The limits are studied by replacing W with a blocklength-indexed super-channel W^n.
  • 4.1 Definitions and Non-Asymptotic Bounds: An (M, ε)ave-code uses an encoder and decoder whose average error probability is bounded, while an (M, ε)max-code imposes the corresponding maximum-error condition.The code size is M.
  • 4.1.1 Achievability Bounds: Three achievability bounds are presented: Feinstein’s bound, a strengthened threshold-decoding bound, and the Random Coding Union bound.The bounds apply to arbitrary channels with suitable input distributions and support later asymptotic evaluations.
  • 4.1.1 Achievability Bounds: 1/2 log n + O(1) is achievable for the third-order term of log M*(W^n, ε) under stated DMC and AWGN conditions.This result is obtained using the Random Coding Union bound.
  • 4.1.2 A Converse Bound: The evaluated converse is a symbol-wise bound relating channel coding to binary hypothesis testing and relaxing meta-converse and Hayashi-Nagaoka bounds.It permits optimization over the output distribution Q and applies directly to non-constant-composition DMC codes.
  • 4.1.2 A Converse Bound: 1/2 log n + O(1) is an upper bound for third-order asymptotics of positive ε-dispersion DMCs.The bound comes from the symbol-wise converse.
  • 4.2 Asymptotic Expansions for Discrete Memoryless Channels: For DMCs, the chapter characterizes the first three terms in the asymptotic expansion of log M*(W^n, ε), refining Shannon’s capacity limit.DMCs are stationary and memoryless, with finite input and output alphabets.
  • Channel Dispersions: Channel dispersion is defined through divergence and information variances, including conditional and unconditional information variance over capacity-achieving input distributions.The ε-channel dispersion is operationally characterized using Vmin(W) and Vmax(W).

Singularity

The channel’s singularity determines which asymptotic expansions apply. Singular DMCs have equal positive transition probabilities for any output reachable from two inputs, with symmetric binary erasure channels as an example.

  • Singularity: A DMC is singular when W(y|x) = W(y|z) whenever W(y|x)W(y|z) > 0; otherwise, it is non-singular.The asymptotic expansions in Theorems 4.1 and 4.3 depend on this distinction.
  • Singularity: For singular DMCs, feasibility checking is optimum decoding, and the channel capacity equals its zero-undetected error capacity.Given the channel output, decoding selects the uniquely feasible codeword.
  • Singularity: When δ0 = δ1 = δ > 0, the binary erasure channel is singular; when δ0 ≠ δ1, it is non-singular.The erasure output has W(e|0) = W(e|1) = δ in the symmetric case, while unequal erasure probabilities break singularity.

Symmetry

This section defines symmetric discrete memoryless channels and provides lower bounds to log M∗_max(W^n, ε), focusing on the positive ε-dispersion case.

  • Symmetry: A DMC is symmetric when its channel-output subsets have transition matrices whose rows and columns are permutations of one another.The outputs are partitioned into subsets, with the permutation condition holding within each subset.
  • Symmetry: The section provides lower bounds to log M∗_max(W^n, ε).
  • Symmetry: The analysis focuses on the positive ε-dispersion case; other cases are referred to [119, Thm. 47].

Independent and Identically Distributed (i.i.d.) Codes

For i.i.d. random codes, the maximal code size achieves the Gaussian approximation up to a constant term. For non-singular DMCs, evaluating the RCU bound additionally yields a third-order 1/2 log n+O(1) term, whereas the basic Feinstein bound gives −1/2 log n+O(1).

  • i.i.d. random codes: max(W^n, ε) is lower bounded by nC + √nVεΦ−1(ε) plus a constant term.This bound uses the strengthened version of Feinstein’s theorem.
  • i.i.d. random codes: 1/2 log n+O(1) is an achievable third-order term for log M∗_ave(W^n, ε) under the non-singularity condition.The proof uses the RCU bound, and the term applies to non-singular DMCs.
  • i.i.d. random codes: −1/2 log n+O(1) is the third-order term obtained when using the basic Feinstein theorem with an i.i.d. codebook.The argument sets η=1/√n in Feinstein’s theorem.

Constant Composition Codes and Cost Constraints

Constant composition codes enforce additive cost constraints by assigning every codeword the same type, while still achieving Gaussian approximations. Under cost constraints, the asymptotic expansion retains the same third-order term, with capacity and dispersion optimized over feasible input distributions; partially universal decoding requires only capacity and ε-dispersion.

  • Cost-constrained constant composition coding: Constant composition codes use codewords with a common type P, which guarantees the additive cost constraint when P satisfies the corresponding expected-cost bound.This approach avoids using i.i.d. codes when every codeword must obey an additive cost constraint.
  • Cost-constrained constant composition coding: The Gaussian approximation can be achieved with constant composition codes, including for DMCs with additive costs and the AWGN channel via increasingly fine discretization.Hayashi used constant composition coding for cost-constrained DMCs and then derived AWGN second-order asymptotics.
  • Cost-constrained constant composition coding: With additive cost constraints, the leading term becomes the capacity-cost function, while ε-dispersion uses the maximum and minimum dispersions over input distributions satisfying E_P[b(X)] ≤ Γ.The third-order term remains unchanged from the unconstrained expansion.
  • Partially universal decoding: Partially universal constant composition codes achieve the Gaussian approximation using only the channel capacity and ε-dispersion.Decoding compares each codeword’s empirical mutual information with a threshold depending on those two channel statistics.
  • Converse bounds: For non-singular channels, the third-order term is 1/2 log n + O(1), while symmetric singular channels have third-order term O(1).The converse bound gives at most 1/2 log n + O(1) generally, and symmetry plus singularity tightens it to O(1).

Network Information Theory · Channels with Random State

The chapter develops fixed-error asymptotics for channels with random states, covering states known at the decoder, both terminals, or only noncausally at the encoder. It also treats mixed and quasi-static channels, highlighting how state randomness shapes dispersion and finite-blocklength behavior.

  • 5.1 Random State at the Decoder: For i.i.d. random states known at the decoder, capacity is CSI−D(W, PS) = max P∈P(X) I(X; Y |S).The model is converted into a DMC whose output is the pair (Y, S).
  • 5.1 Random State at the Decoder: The decoder-state dispersion separates conditional channel randomness ES[V(WS)] from state randomness VarS[C(WS)].The theorem assumes Vε(Ws) > 0 for every state and state-independent Vε(Ws).
  • 5.2 Random State at the Encoder and Decoder: For binary symmetric channels with different crossover probabilities, the optimizing input distribution is uniform for every state, so CSI−ED(W, PS) = CSI−D(W, PS).The equality holds when the optimizing PX|S does not depend on s.
  • 5.2 Random State at the Encoder and Decoder: When the i.i.d. state is known noncausally at both encoder and decoder, the second-order expansion has dispersion VSI−ED(W, PS), given by the expression in (5.3).The proof uses empirical capacities and dispersions over strongly typical state types.
  • 5.3 Writing on Dirty Paper: In dirty-paper coding, decoder state knowledge is unnecessary for capacity: Costa’s result gives C(snr) even when the state is known only noncausally at the encoder.The Gaussian state is additive, and the channel input satisfies a power constraint not exceeding snr.
  • 5.3 Writing on Dirty Paper: There is no degradation through the second-order dispersion term, and the result holds under a mild state-sequence condition.Choosing α∗ = snr/(snr+1) makes I(τ)(U; Y ) − I(τ)(U; S) equal C(snr) for every power type τ.
  • 5.4 Mixed Channels: Mixed channels yield log M*mix(W n, PS, ε) = nCε(W, PS) + √nL(ε; W, PS) + o(√n).When C(W0) = C(W1), L depends on both dispersions, π0, and ε; unequal capacities reduce the analysis to one Gaussian cdf.
  • 5.5 Quasi-Static Fading Channels: For quasi-static fading with state known at both terminals, log M*SI−ED(W n, PHr, snr, ε) = nCε(W, PHr) + O(log n).The usual Θ(√n) dispersion term is absent, so ε-capacity is a useful finite-blocklength benchmark.

Distributed Lossless Source Coding

The section develops second-order asymptotics for distributed lossless source coding by centering analysis at a boundary rate pair of the Slepian-Wolf region. At corner points, the attainable second-order region is governed by joint Gaussian behavior and a multivariate Gaussian cdf.

  • Problem formulation: Slepian-Wolf coding separately compresses two correlated sources, with each encoder observing only its own source while the decoder reconstructs both losslessly.The problem concerns distributed encoding of correlated sources and extends lossless coding with shared side information.
  • Second-order formulation: Second-order analysis fixes a boundary point (R∗_1, R∗_2) and characterizes the rate offsets (L_1, L_2) achievable by ε-reliable code sequences.Unlike point-to-point problems, multi-terminal systems have a continuum of first-order limits, so the analysis is local around a selected boundary point.
  • Corner-point asymptotics: At corner points, the second-order rate-offset set is characterized by a multivariate Gaussian cdf rather than the univariate Gaussian cdf used in single-terminal problems.The relevant Gaussian cdf is parameterized by the generally full covariance matrix V_1,12, because two error events remain in the central-limit regime.
  • Regimes across the rate region: Away from active constraints, corresponding error events vanish exponentially fast, placing those parts of the analysis in the error-exponents regime.At the corner point, by contrast, the remaining events require a multivariate Berry-Esseen approximation.
  • Universality: Partially universal source codes can achieve the same second-order coding rate region without full knowledge of the source statistics.The construction uses type-based arguments and achieves asymptotic error probability no larger than ε.
  • Alternative formulations: The section recommends local, weighted sum-rate, and dispersion-angle formulations as information-theoretic setups for studying multi-terminal second-order asymptotics.Dispersion-angle pairs correspond one-to-one with second-order coding rate pairs, and weighted sum-rates capture unequal transmission costs.

A Special Class of Gaussian Interference Channels

The section derives second-order asymptotics for Gaussian interference channels in the strictly very strong interference (SVSI) regime. Under SVSI, the second-order region depends on the direct-channel dispersions, while the two decoding error events are asymptotically almost independent.

  • Proof strategy: The achievability strategy first decodes the interference, subtracts it from the received output, and then decodes the intended message reliably.The SVSI condition ensures that the rate constraints for the second decoding steps dominate.
  • Problem and regime: SVSI assumes strict inequalities defining the very strong interference regime, enabling second-order asymptotic results for this Gaussian interference-channel class.The general memoryless interference channel remains analytically intractable, whereas the very strong interference capacity region is known.
  • Second-order characterization: Under SVSI, the second-order coding-rate region is characterized entirely by the dispersions V(snrj) of the two direct AWGN channels.These dispersions are unaffected by interference, paralleling the first-order capacity property of very strong interference.
  • Second-order characterization: Under SVSI, the error events for incorrectly decoding messages 1 and 2 are almost independent in the second-order asymptotic setting.The converse has only two error events, and SVSI eliminates two events from the achievability bound so the bounds match in the second-order sense.
  • Proof strategy: The achievability analysis lifts the information-spectrum bound to higher dimensions to apply limit theorems for independent random vectors.This proof technique, developed by MolavianJazi-Laneman, is also applicable to multi-terminal Gaussian channels.

A Special Class of Gaussian Multiple Access Channels

The chapter characterizes second-order asymptotics for the asymmetric Gaussian multiple access channel, enabled by Gaussianity and partial cooperation. Its second-order region depends jointly on capacity derivatives and dispersions, yielding a half-space characterization on relevant boundary points.

  • Model: The asymmetric MAC lets encoder 1 know both messages while encoder 2 knows only its own, with Gaussian law Y = X1 + X2 + Z.The noise Z is standard Gaussian, and the channel gains are set to unity without loss of generality.
  • Main result: Gaussianity and partial cooperation enable determination of the A-MAC’s second-order asymptotics.The resulting characterization differs from earlier multi-terminal results because it involves more than information-density covariances or dispersions.
  • Main result: Capacity derivatives with respect to ρ interact subtly with dispersions, and their appearance is presented as novel.For ρ < 1, the second-order region is a half-space whose slope and intercept are expressible through dispersions and capacity derivatives.
  • Local second-order rates: Case (i) has a second-order region determined by V1(0) and Φ−1 because only the R1 constraint is active, while the sum-rate constraint contributes only a large-deviations event.This case corresponds to R∗1 = I1(0) and R∗1 + R∗2 ≤ I12(0).
  • Local second-order rates: In Cases (ii)–(iii), active constraints require dispersion matrices and Gaussian approximations, while gradient terms also contribute to second-order behavior.Case (ii) uses a bivariate Gaussian cdf; Case (iii) has a singular covariance matrix and restricts the union to β ≤ 0.
  • Local second-order rates: A single Gaussian input distribution cannot achieve all second-order coding rates in the curved-boundary case, because achievable regions extend beyond its trapezoid.The curved boundary is parametrized by 0 < ρ < 1, with (R∗1, R∗2) = (I1(ρ), I12(ρ) − I1(ρ)).

Summary, Other Results, Open Problems

The monograph consolidates fixed-error asymptotic results across information theory, including single-user coding and several multi-user problems with conclusive second-order characterizations. It also identifies omissions and open directions, especially feedback, variable-length coding, third-order asymptotics, and strong converses for network problems.

  • Summary: The monograph uses hypothesis-testing and information-spectrum expansions to derive asymptotic expansions for minimum code size in lossless compression, then treats lossy compression and channel coding.These results form the core fixed-error asymptotic treatment developed in the monograph.
  • Summary: Three network information theory examples admit conclusive second-order results for rate pairs approaching boundaries of capacity or optimal rate regions.The examples concern multi-user problems studied through the speed of convergence toward fixed boundary points.
  • Open Problems: The monograph omits channels with feedback and variable-length terminations, while existing feedback analyses generally lack the Θ(√n) dispersion term.Polyanskiy-Poor-Verdú studied incremental redundancy schemes and derived several asymptotic expansions.
  • Open Problems: Third-order asymptotics for fully universal source and channel coding remain an open research direction, despite partially universal codes achieving source and channel dispersion.The partially universal source code requires only entropy and varentropy, whereas third-order terms are more difficult to quantify.
  • Open Problems: Second-order converses for network problems may require first understanding strong-converse techniques, for which only three approaches are known when capacity characterizations use auxiliary random variables.The information spectrum method is identified as the first such approach.
  • Other Results: Further conclusive results include best known inner bounds for discrete memoryless MAC rate regions and second-order asymptotics for secret key agreement.Constant composition codes can help discrete memoryless multi-user problems even without cost constraints, while secret-key converses relate key size to ε-hypothesis testing divergence.
Loading 1504.02608v1…