A Second-Order Converse Bound for the Multiple-Access Channel via Wringing Dependence

Oliver Kosut

Abstract

A new converse bound is presented for the two-user multiple-access channel under the average probability of error constraint. This bound shows that for most channels of interest, the second-order coding rate -- that is, the difference between the best achievable rates and the asymptotic capacity region as a function of blocklength $n$ with fixed probability of error -- is $O(1/\sqrt{n})$ bits per channel use. The principal tool behind this converse proof is a new measure of dependence between two random variables called wringing dependence, as it is inspired by Ahlswede's wringing technique. The $O(1/\sqrt{n})$ gap is shown to hold for any channel satisfying certain regularity conditions, which includes all discrete-memoryless channels and the Gaussian multiple-access channel. Exact upper bounds as a function of the probability of error are proved for the coefficient in the $O(1/\sqrt{n})$ term, although for most channels they do not match existing achievable bounds.

Introduction

In information theory, the "first-order" result is the capacity—the maximum rate of reliable communication as the blocklength $n$ goes to infinity. "Second-order" analysis looks at how quickly we approach that capacity for a finite $n$ and a fixed error probability $\epsilon$.

For simple point-to-point channels, it has long been known that the back-off from capacity is on the order of $O(1/\sqrt{n})$. However, the Multiple-Access Channel (MAC)—where two independent senders transmit to one receiver—proved much more difficult. Because the senders are independent, standard proof techniques (like "expurgating" bad codewords) often accidentally introduce dependencies between the users. Previous "converse" bounds (which set upper limits on what is possible) could only prove a slower approach to capacity, specifically $O(\frac{\log n}{\sqrt{n}})$. This paper closes this significant gap by proving that the second-order coding rate for a two-user MAC scales as $O(1/\sqrt{n})$, matching the order of known achievable rates.

Methodology: Wringing Dependence

The core innovation of this work is the introduction of wringing dependence, a new mathematical measure denoted as $\Delta(X; Y)$. Unlike mutual information, which measures total shared information, wringing dependence specifically quantifies how much "dependence" is introduced when we restrict a code to a subset of its possible inputs. It is defined through a convex optimization problem over auxiliary distributions.

Behavior of wringing dependence as a function of probability $p$ for a binary random variable.

The author develops a "Wringing Lemma" (Lemma 3), which is a more efficient version of a classic tool by Ahlswede. It allows a researcher to find a large subset of codewords where the transmitters remain "nearly independent" according to the new $\Delta$ measure. The paper first proves a "one-shot" converse bound (Theorem 6) that doesn't depend on blocklength. It then uses tools like the Berry-Esseen theorem and Augustin-type converse arguments to extend this to the asymptotic $O(1/\sqrt{n})$ regime for both discrete-memoryless and Gaussian channels.

Key Insights

  • Efficiency Matters: Previous wringing techniques were too "expensive" in terms of how much probability mass they sacrificed to restore independence. Wringing dependence provides a more "surgical" way to measure and bound this cost.
  • Axiomatic Strength: The author proves that wringing dependence satisfies six of the seven axioms Rényi proposed for any good measure of dependence (and the seventh for Gaussian variables). This suggests it is a fundamental tool, not just a trick for one proof.
  • Hypercontractivity Connection: The paper establishes a deep link between wringing dependence and "hypercontractivity ribbons," a concept from functional analysis. This connects network information theory to broader mathematical fields.

Results

The paper successfully proves that for most MACs of interest (including all discrete-memoryless and Gaussian MACs), the achievable rate region is bounded by $C + O(1/\sqrt{n})$. This improves the previous state-of-the-art converse bound from $O(\frac{\log n}{\sqrt{n}})$ to $O(1/\sqrt{n})$, finally matching the scaling law of point-to-point channels.

For the Binary Additive Erasure Channel (BAEC), the author provides explicit numerical upper and lower bounds on the second-order coefficient (the "dispersion"), showing that while the order is now known, the exact constant still has a small gap.

Conclusion and Future Work

While the paper settles the $1/\sqrt{n}$ scaling, the constant coefficient (the dispersion) in the converse bound does not yet perfectly match the achievable bounds for most channels. Finding the exact "dispersion" of the MAC remains an open problem. Furthermore, the current proof is specifically tailored to the two-user case. Extending "wringing dependence" to $K$ users or more complex network topologies (like interference channels) is a suggested next step. Finally, while the proof holds for common channels, verifying the required "regularity conditions" (like finite second moments of information density) for more exotic continuous channels remains a challenge.

Summary updated

Abstract

A new converse bound is presented for the two-user multiple-access channel under the average probability of error constraint. This bound shows that for most channels of interest, the second-order coding rate -- that is, the difference between the best achievable rates and the asymptotic capacity region as a function of blocklength $n$ with fixed probability of error -- is $O(1/\sqrt{n})$ bits per channel use. The principal tool behind this converse proof is a new measure of dependence between two random variables called wringing dependence, as it is inspired by Ahlswede's wringing technique. The $O(1/\sqrt{n})$ gap is shown to hold for any channel satisfying certain regularity conditions, which includes all discrete-memoryless channels and the Gaussian multiple-access channel. Exact upper bounds as a function of the probability of error are proved for the coefficient in the $O(1/\sqrt{n})$ term, although for most channels they do not match existing achievable bounds.
BibTeX
@article{kosut2022second,
  author = {Oliver Kosut},
  title = {{A Second-Order Converse Bound for the Multiple-Access Channel via Wringing Dependence}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=O9fHXumviE},
}
Figure