Sharp Bounds for Mutual Covering

Jingbo Liu, Mohammad Hossein Yassaee, Sergio Verdú

TL;DR

This paper introduces novel, sharper bounds for the "mutual covering lemma," a crucial tool in network information theory. By employing a weighted sum trick and Talagrand's concentration inequality, the authors achieve significantly improved error exponent bounds, particularly in applications like broadcast channel coding and joint distribution simulation, leading to more efficient theoretical limits.

What Problem Does This Paper Address?

In network information theory, a fundamental challenge is to determine the conditions under which a pair of random variables can be "jointly typical" within a given set. The "covering lemma" provides a lower bound on the probability of finding such a pair among a set of independently generated candidates. However, existing bounds, particularly for the "mutual covering lemma" (which deals with multiple pairs), have been suboptimal, leading to less precise error exponents in practical applications like broadcast channel coding and simulating joint distributions. This paper aims to tighten these bounds, providing a more accurate understanding of achievable rates and error probabilities.

Methods

The core of this paper lies in developing new, sharper bounds for the mutual covering lemma. The authors introduce two key techniques:

  • Weighted Sum Trick: Instead of simply summing indicator functions of covering events, they use a weighted sum. This approach, inspired by graph theory, leads to a more compact and stronger bound.
  • Talagrand's Concentration Inequality: This powerful inequality is used to bound the deviation of the weighted sum from its mean. This is a significant improvement over previous methods that relied on Chebyshev's inequality, enabling tighter bounds on the probability of failure.

These tools are applied to derive two main lemmas: a "limited independence" version and a "full independence" version, with the latter being the main result and providing the sharpest bounds. The paper also leverages Hall's marriage theorem for one of its applications.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Doubly Exponential Convergence: For certain "typical" sets, the probability of failing to cover converges to 1 doubly exponentially fast in the blocklength. This is a significant improvement over previous exponential bounds and implies that the covering lemma itself doesn't impose penalties on error exponents in coding theorems.
  • Duality with Sampling: A key insight is the connection between mutual covering and joint distribution simulation. The paper shows that the maximum difference between the true joint distribution and a simulated one is directly related to the mutual covering error. This duality allows for deriving exact error exponents in simulation problems.
  • Sharpness in Two Regimes: The new bounds are shown to be sharp in two distinct scenarios: the "typical case F" (where the set's probability is bounded away from 0 and 1) and the "worst case F." This demonstrates the broad applicability and tightness of the new bounds.
  • Weighted Sum Advantage: The use of a weighted sum, rather than a simple sum of indicators, is crucial for achieving the tighter bounds, especially when dealing with the concentration of the sum of random variables.

Key Results

  • New Mutual Covering Bounds: The paper presents Lemma 5, a new mutual covering lemma with significantly improved bounds, particularly in terms of exponential convergence rates.
  • Doubly Exponential Error Exponents: For typical sets, the covering error is shown to decay doubly exponentially, which is crucial for achieving optimal error exponents in applications like broadcast channel coding (Theorem 1).
  • Exact Error Exponents for Distribution Simulation: Using the covering-sampling duality, the paper derives the exact error exponents for joint distribution simulation (Theorem 3 and Theorem 4).
  • Suboptimality of Weighted Samplers: The paper analyzes a "weighted sampler" inspired by likelihood encoders and shows that it achieves a strictly suboptimal error exponent compared to optimal samplers, highlighting the value of the duality approach.

Limitations and Future Work

  • Finite Alphabets for Hall's Theorem: The proof of Theorem 3, which uses Hall's marriage theorem for the distribution simulation application, assumes finite alphabets. The authors note that this assumption is required for the specific proof technique and may not be a fundamental limitation of the result itself.
  • Multivariate Extensions: The paper discusses extensions to multivariate settings (Lemma 6), suggesting that the techniques are generalizable, but the primary focus remains on the bivariate case.
  • Further Applications: While two key applications (broadcast channel and distribution simulation) are detailed, the authors imply that the new sharp bounds could be beneficial in other areas of information theory where covering lemmas are used.

Summary updated

Abstract

A fundamental tool in network information theory is the covering lemma, which lower bounds the probability that there exists a pair of random variables, among a give number of independently generated candidates, falling within a given set. We use a weighted sum trick and Talagrand's concentration inequality to prove new mutual covering bounds. We identify two interesting applications: 1) When the probability of the set under the given joint distribution is bounded away from 0 and 1, the covering probability converges to 1 \emph{doubly} exponentially fast in the blocklength, which implies that the covering lemma does not induce penalties on the error exponents in the applications to coding theorems. 2) Using Hall's marriage lemma, we show that the maximum difference between the probability of the set under the joint distribution and the covering probability equals half the minimum total variation distance between the joint distribution and any distribution that can be simulated by selecting a pair from the candidates. Thus we use the mutual covering bound to derive the exact error exponent in the joint distribution simulation problem. In both applications, the determination of the exact exponential (or doubly exponential) behavior relies crucially on the sharp concentration inequality used in the proof of the mutual covering lemma.
BibTeX
@article{liu2019sharp,
  author = {Jingbo Liu and Mohammad Hossein Yassaee and Sergio Verdú},
  title = {{Sharp Bounds for Mutual Covering}},
  journal = {IEEE Transactions on Information Theory},
  year = {2019},
  doi = {10.1109/tit.2019.2919720},
}

Loading related content...

Figure