PaperlayerView exact revision on arXiv

Source-linked AI summary

Concentration of Measure Inequalities in Information Theory, Communications and Coding (Second Edition)

Maxim Raginsky, Igal Sason

arXiv:1212.4663v8cs.ITmath.PR

TL;DR

The monograph addresses how modern concentration inequalities can be derived, connected to information theory, and applied to communications and coding. It develops martingale and entropy-based methods, including logarithmic Sobolev and transportation-cost approaches, and presents applications ranging from strong converses to channel-code distributions. The authors also report refinements and recent results alongside the survey material.

  • Problem

    The monograph addresses the derivation of concentration inequalities, their links to information theory, and their applications to communications and coding.

  • Method

    It develops martingale inequalities and the entropy method, including logarithmic Sobolev and transportation-cost techniques, for concentration analysis.

  • Results

    The monograph presents refinements and extensions of concentration inequalities and applies them to coding and communications problems, including strong converses and channel-code distributions.

  • Takeaways & Limitations

    Concentration methods are presented as tools for analyzing fundamental limits and probabilistic behavior in information theory, communications, and coding.

  • Takeaways & Limitations

    Some concentration analyses can require absurdly large blocklengths because their proofs pessimistically assume every affected message incurs an error.

Abstract

from arXiv · show

During the last two decades, concentration inequalities have been the subject of exciting developments in various areas, including convex geometry, functional analysis, statistical physics, high-dimensional statistics, pure and applied probability theory, information theory, theoretical computer science, and learning theory. This monograph focuses on some of the key modern mathematical tools that are used for the derivation of concentration inequalities, on their links to information theory, and on their various applications to communications and coding. In addition to being a survey, this monograph also includes various new recent results derived by the authors. The first part of the monograph introduces classical concentration inequalities for martingales, as well as some recent refinements and extensions. The power and versatility of the martingale approach is exemplified in the context of codes defined on graphs and iterative decoding algorithms, as well as codes for wireless communication. The second part of the monograph introduces the entropy method, an information-theoretic technique for deriving concentration inequalities. The basic ingredients of the entropy method are discussed first in the context of logarithmic Sobolev inequalities, which underlie the so-called functional approach to concentration of measure, and then from a complementary information-theoretic viewpoint based on transportation-cost inequalities and probability in metric spaces. Some representative results on concentration for dependent random variables are briefly summarized, with emphasis on their connections to the entropy method. Finally, we discuss several applications of the entropy method to problems in communications and coding, including strong converses, empirical distributions of good channel codes, and an information-theoretic converse for concentration of measure.

Introduction

The introduction frames concentration of measure as exponential control of deviations and surveys major proof techniques, especially martingale, entropy, and transportation-cost methods. It also situates these tools across probability, information theory, coding, and related fields.

  • Concentration inequalities bound the probability that a random variable deviates from a typical value, often with exponential decay in the deviation size.
  • The martingale approach develops concentration results for discrete-time bounded-difference martingales and supports applications in information theory, coding, and communications.
  • The entropy method uses logarithmic Sobolev inequalities to derive concentration bounds and connects these inequalities to information theory.
  • Transportation-cost inequalities provide a related information-theoretic route to concentration and are closely connected to the entropy method and logarithmic Sobolev inequalities.
  • Talagrand inequalities, Stein’s method, statistical-physics techniques, and reverse Lyapunov inequalities are identified as additional approaches, but the last three are not addressed in the monograph.
  • The Azuma–Hoeffding inequality established concentration for bounded-difference martingales, extending earlier work on independent bounded variables and later influencing applications in random graphs and coding theory.

8 CHAPTER 1. INTRODUCTION

This part contrasts the martingale method with information-theoretic entropy techniques, emphasizing the latter’s stronger concentration results and their applications to coding and information theory. It also introduces Gaussian log-Sobolev and transportation-cost perspectives.

  • The martingale method can fail to achieve optimal-order concentration in important settings, motivating entropy-based techniques rooted in information theory.
  • For Gaussian measures, the log-Sobolev inequality bounds relative entropy by an energy-like gradient quantity and yields optimal Gaussian concentration for sufficiently smooth Lipschitz functions.
  • The entropy method extends the log-Sobolev strategy beyond Gaussian distributions by relating relative entropy to an appropriate energy functional.
  • Transportation-cost inequalities bypass functional inequalities by relating relative entropy directly to Wasserstein distances between probability measures.
  • Concentration bounds such as the blowing-up lemma support strong converses for diverse information-theoretic problems, including multi-terminal scenarios.
  • The monograph targets researchers and graduate students in information theory, communications, and coding, assuming background in analysis, functional analysis, probability, and stochastic processes.

10 CHAPTER 1. INTRODUCTION

The monograph organizes its core material around martingale and entropy approaches to concentration of measure. The chapters combine foundational inequalities with information- and communication-theoretic applications.

  • Chapter 2 develops the martingale approach through basic martingale facts, foundational Azuma–Hoeffding and McDiarmid inequalities, and refined Azuma–Hoeffding bounds.
  • The monograph emphasizes applications of concentration inequalities to information, communication, and coding problems.
  • Chapter 3 introduces the entropy method, develops Gaussian and general logarithmic Sobolev inequalities, and applies them to continuous and discrete examples.

Concentration Inequalities via the Martingale Approach

The chapter develops martingale-based concentration inequalities, beginning with Azuma–Hoeffding and McDiarmid and introducing refinements using asymmetric difference and conditional-variance information. It applies these tools to concentration results in coding, communications, and iterative decoding.

  • Core inequalities: The chapter introduces Azuma–Hoeffding, McDiarmid, and refined martingale inequalities for applications in information theory, communications, and coding.The applications include random binary linear block codes, random regular bipartite graphs, and communication systems.
  • Refinements: Additional variance information enables refinements of Azuma–Hoeffding, while McDiarmid’s inequality improves one concentration exponent by a factor of 4.The refinement is motivated by bounds on conditional variance; McDiarmid’s inequality provides the stated exponent improvement in the example.
  • Refinements: The generalized Azuma–Hoeffding inequality handles asymmetric bounded differences and controls the probability that any intermediate martingale value deviates from its initial value.The stronger event includes the existence of an index k with |X_k − X_0| ≥ r, not only the terminal deviation event.
  • Refinements: Theorem 2.3.2 improves Azuma–Hoeffding when conditional variance is constrained, with bounds that tend to zero as ε → 0 and improve as γ decreases.For γ = 1, Corollary 2.3.1 nearly coincides with Azuma–Hoeffding for δ ≤ 0.4, while smaller γ strengthens the exponential bound.
  • Applications: The refinements achieve sharp asymptotic behavior and support concentration results for random codes, bipartite graphs, and other communication-related quantities.Theorem 2.3.2 matches the asymptotic limit in the cited moderate-deviations comparison; applications include minimum distance and graph expansion concentration.

Proof of Bennett’s inequality

The proof of Bennett’s inequality reduces the exponential-moment bound to a two-point comparison under zero-mean and variance constraints. A carefully chosen parabola establishes the comparison, completing the inequality.

  • Bennett’s inequality is proved by comparing an arbitrary bounded random variable with a two-point random variable having matching mean and variance constraints.The comparison assumes E[Y] = 0, Y ≤ b_Y, and var(Y) ≤ σ^2.
  • The proof constructs a unique parabola whose difference from the exponential function has prescribed zeros and tangency conditions.The function f is arranged to vanish at b_Y and to satisfy f(y) = f′(y) = 0 at −σ^2/b_Y.
  • Convexity and concavity of the comparison function show that its expectation is nonnegative for every admissible random variable.The argument splits the real line at y_0 and uses the minimum and maximum values of f on the resulting intervals.
  • For zero-mean variables, the parabola’s expectation depends only on the second moment and is non-decreasing in the variance.The two-point variable Y_0 realizes the relevant variance and takes values in {−σ^2/b_Y, b_Y}.
  • Combining the comparison inequalities with the two-point equality completes the proof of Bennett’s inequality.

2.B On the moderate deviations principle in Section 2.4.2

The analysis compares a refined martingale concentration bound with the Azuma–Hoeffding inequality in a moderate-deviations setting. Under uniformly bounded increments, the refined bound matches the exact asymptotic limit, whereas Azuma–Hoeffding generally does not.

  • The refined inequality differs from Azuma–Hoeffding by attaining the exact asymptotic exponent rather than merely an upper bound with a variance relaxation.
  • Theorem 2.3.2 yields an upper bound that coincides with the exact asymptotic limit under the assumption |X_k| ≤ d almost surely for every k.The result is established by defining a martingale sequence with uniformly bounded differences and analyzing its concentration exponent.
  • Azuma–Hoeffding instead replaces the variance parameter σ^2 with the increment bound d^2 in the asymptotic expression.Therefore, it reaches the exact limit only when σ^2 = d^2, equivalently when |X_k| = d almost surely for every k.
  • The proof applies the same moderate-deviations analysis as Proposition 2.3.1, with adaptations involving γ, Bernoulli divergence, and the deviation term.

2.C Proof of the properties in (2.5.9) for OFDM signals

For OFDM signals, the analysis verifies the martingale properties and bounds conditional variances using independent copies, symmetry, and conditional-expectation inequalities. These bounds provide the ingredients needed for concentration analysis.

  • The OFDM sequence defined in (2.5.7) is a martingale with respect to the filtration generated by progressively revealed signal variables.The conditional expectation for Y_{i−1} conditions on only X_0 through X_{i−2}.
  • Independent copies X′_{i−1} and X_{i−1} are used to represent conditional expectations while preserving independence from the other signal variables.
  • Symmetry of the PSK constellation and the tower property help derive an upper bound on the conditional variance var(Y_i | F_{i−1}).The argument also uses |E(Z)| ≤ E(|Z|) and E[Z]^2 ≤ E[Z^2].
  • The resulting conditional-variance calculation supports the concentration properties asserted for the OFDM signal sequence.

2.D Proof of Theorem 2.5.5

The proof of Theorem 2.5.5 constructs a Doob martingale by exposing graph edges and channel outputs, then bounds each martingale difference through local graph neighborhoods. Applying Azuma–Hoeffding yields concentration for iterative-decoding message errors.

  • Applying the Azuma–Hoeffding inequality to the bounded differences produces the concentration bound used in the theorem.
  • A Doob martingale is formed by exposing all graph edges one by one, followed by the n received channel symbols.Each martingale value is the conditional expectation of the number of incorrect messages after ℓ decoding rounds.
  • Changing one graph edge affects a message only when the edge lies in its directed neighborhood of depth ℓ.The neighborhood expansion determines how many variable-to-check messages can be influenced by an exposure.
  • The martingale difference is bounded by the number of affected messages, with graph-edge changes contributing up to 2N(ℓ) and symbol exposures up to N(ℓ).
  • Comparing the resulting bound with (2.5.16) gives the claimed concentration statement for incorrect variable-to-check messages.
  • The expectation analysis establishes the auxiliary inequality needed for the concentration result by averaging over graph realizations and channel outputs.The argument uses symmetry, linearity of expectation, and the probability that a neighborhood is or is not a tree.

2.E Proof of Lemma 2.5.1

The proof establishes auxiliary properties needed for Lemma 2.5.1, including finite average parity-check degree and uniform convergence that permits exchanging a limit with an infinite sum.

  • Finite average parity-check degree follows from the preceding bounds.
  • Uniform convergence for C ∈ [0, 1] justifies exchanging the limit and infinite sum in (2.E.1).
  • Every term in (2.E.1) converges to zero as C → 1, completing the proof of Lemma 2.5.1.

The Entropy method, Log-Sobolev and Transportation-Cost Inequalities

The chapter develops entropy-method concentration through logarithmic Sobolev and transportation-cost inequalities, connecting functional, information-theoretic, and metric viewpoints. It derives concentration results for Gaussian, discrete, and product measures and relates these tools to coding applications.

  • The entropy method: Tensorization extends single-coordinate inequalities to product measures, paralleling single-letter techniques in information theory.
  • The entropy method: The entropy method bounds deviations by applying functional inequalities to exponentially tilted distributions.
  • Log-Sobolev inequalities: The Gaussian log-Sobolev inequality is linked to Stam’s inequality, and the authors give a new information-theoretic proof avoiding direct use of de Bruijn’s identity and the entropy-power inequality.
  • Log-Sobolev inequalities: For Gaussian inputs, concentration follows for Lipschitz functions, with the bound controlled by the function’s coordinate sensitivity.
  • Log-Sobolev inequalities: Discrete log-Sobolev inequalities include a symmetric Bernoulli result with constant 1/4 and a sharpened bound relative to Ledoux’s result.
  • Transportation-cost inequalities: Transportation-cost inequalities connect relative entropy to Wasserstein distances and provide a measure-level route to concentration.
  • Transportation-cost inequalities: T2 tensorization preserves the Gaussian concentration constant independently of dimension, whereas T1 tensorization weakens it as dimension increases.
  • Transportation-cost inequalities: The chapter supplies alternative transportation-based proofs of McDiarmid’s inequality and develops product-measure extensions for T_p inequalities.

Van Trees inequality

The section proves a van Trees inequality for estimating Y from a noisy observation and characterizes equality through the Gaussian case. The proof uses score functions and Cauchy–Schwarz under differentiability and finite-information assumptions.

  • Statement: The van Trees inequality bounds the estimation error of an arbitrary Borel-measurable estimator ϕ(U) for Y observed through a Gaussian-noise channel.The model uses U = √sY + Z with independent standard Gaussian noise and assumes a differentiable, absolutely continuous density for Y with J(Y) < ∞.
  • Equality: Equality holds only when the estimator is the MMSE estimator and Y has a standard normal distribution.The equality condition is stated for the general estimator inequality and is tied to the Gaussian case.
  • Proof strategy: The proof defines paired random variables whose expectations satisfy E[∆(U, Y )Υ(U, Y )] = 1, then applies Cauchy–Schwarz.The score function is ρY(y) = d/dy ln pY(y), and the resulting second-moment relation involves s + J(Y).
  • Proof strategy: The argument uses integration by parts and Gaussian-tail decay to justify the required identities and rearrangement.Finite Fisher information implies that pY is bounded, supporting the boundary-term control used in the proof.
  • Equality: The equality analysis reduces to requiring the score ρY(y) to be affine in y, which occurs if and only if Y is Gaussian.The proof excludes the zero constant case because it would make ϕ(U) = Y, which is not a valid estimator.

3.B The proof of Theorem 3.2.3

This proof establishes the equivalence between a Rényi-divergence inequality and the Gaussian log-Sobolev inequality. Its central device is a time-dependent quantity propagated along the Ornstein–Uhlenbeck flow and shown to be non-increasing.

  • Monotonicity argument: Applying the Gaussian log-Sobolev inequality to the time-dependent density makes the derivative nonpositive because α̇(t) − 2(α(t) − 1) = 0.Positivity of the relevant density implies Ḟ(t) ≤ 0.
  • Ornstein–Uhlenbeck flow: The Ornstein–Uhlenbeck semigroup provides the flow needed to differentiate F(t) with respect to time.The proof introduces operators Kt, with K0 as the identity, and uses their channel representation.
  • Conclusion: Monotonicity of Rényi divergence then yields the target inequality for the appropriate relation between α and α(t).The proof combines monotonicity on both sides and concludes that the Gaussian log-Sobolev inequality implies the stated bound.
  • Conclusion: Conversely, selecting t = 0 and β = 2 recovers precisely the Gaussian log-Sobolev inequality.This establishes the reverse implication and completes the theorem after the remaining equality formula is supplied.

Details on the Ornstein–Uhlenbeck semigroup

The appendix develops the Ornstein–Uhlenbeck semigroup tools used in the proof, including its generator, integration-by-parts identities, stationarity, reversibility, and carré du champ operator.

  • Technical identities: Gaussian integration by parts and the OU flow establish the differential identities required later in the proof.The derivations rely on suitable smoothness and boundary decay conditions.
  • Process properties: The Ornstein–Uhlenbeck process is stationary and reversible, enabling exchange of the process coordinates in expectation identities.This reversibility yields the adjoint relation for the semigroup operator Kt.
  • Generator: The generator L is self-adjoint on L2(G), while constant functions lie in its kernel.These properties are expressed through the integration-by-parts identities for the Gaussian process.
  • Carré du champ: The operator Γ measures how far L is from satisfying the Leibniz rule and is called the carré du champ.The derivation comparison uses L(gh) = gLh + hLg as the reference Leibniz identity.

LSI for Bernoulli and Gaussian measures

This section derives a Bernoulli log-Sobolev inequality and connects it to the Gaussian version through a central-limit argument. The construction begins with a tilted function representation and then passes to the Gaussian limit.

  • Bernoulli measure: The Bernoulli log-Sobolev inequality is converted into an inequality for a function f defined by e^f = g^2.The discrete carré du champ satisfies Γf = |f(0) − f(1)|, and an elementary bound controls the resulting expression.
  • Bernoulli measure: The conversion is verified by tracking the equalities and inequalities connecting the Bernoulli functional terms to the tilted expectation.The derivation concludes that the Bernoulli inequality implies the target functional inequality.
  • Gaussian limit: Gross’s Gaussian log-Sobolev inequality is recovered from the Bernoulli version by applying the central limit theorem to normalized sums of i.i.d. Bernoulli(1/2) variables.The measures converge weakly to the standard Gaussian distribution as n → ∞.
  • Gaussian limit: For sufficiently smooth g, weak convergence allows the discrete functional expressions to converge to their Gaussian counterparts.The required smoothness ensures continuity and boundedness conditions for the limiting argument.
  • Bernoulli measure: The same technique extends the construction to an asymmetric Bernoulli measure by defining a corresponding function on {0, 1}^n.The resulting function is then inserted into the Bernoulli inequality.

Fano’s inequality for list decoding

The section derives Fano-type bounds for list decoding, relating conditional entropy to list size and decoding error. It also notes a weaker form when list size is bounded only in expectation.

  • H(X|Y) ≤ h(Pe) + (1 − Pe) ln N + Pe ln |X | when the decoding list has size at most N almost surely.
  • The derivation introduces E ≜ 1{X̸∈L(Y)} and expands H(E, X|Y) in two ways.
  • Because X and Y determine E, H(X|Y) can be bounded through H(E|Y) and H(X|E, Y), with H(E|Y) ≤ H(E).
  • Given E = 0 and Y = y, X is supported on L(y), enabling the log-cardinality entropy bound involving N.
  • If list size is bounded only in expectation through E[ln |L(Y)|] < ∞, the resulting inequality is weaker than the almost-surely bounded form.

3.F Details for the derivation of (3.6.22)

The derivation uses the memoryless, no-feedback structure of a discrete memoryless channel to establish per-symbol conditional-independence relations and rewrite channel expressions as expectations.

  • For a memoryless channel without feedback, each output symbol Yi depends only on the corresponding input symbol Xi.
  • The Markov relation i → Xi → Yi holds for every i = 1, . . . , n.
  • Positivity of PY |X(·|·) permits expressing a channel-related quantity as the logarithm of an expectation of PY |X(y|X).
  • The expectation is taken with respect to the conditional probability measure PY |X(y′|X).
  • Interchanging y and y′ yields a further implication used in the derivation.
Loading 1212.4663v8…