CS Paper Radar

Information Spectrum Methods for Multiple-Access Channels --Part II : $\varepsilon$-Capacity Regions in the Mixed Finite-Alphabet Case

Te Sun Han, Hideki Yagi

cs.IT ·submitted 2026-11-12 11:30 UTC · v2
theory

Abstract

In a nonergodic channel such as a slowly fading link, the channel law is drawn once and held fixed for the whole codeword, and the relevant performance measure is the $\varepsilon$-capacity. We study the $\varepsilon$-capacity regions of two-user mixed multiple-access channels (MACs) with finite alphabets, additive cost constraints and an arbitrary mixing measure. The direct parts are derived from a single information spectrum formula; the converse parts use, in addition, Fano's inequality and Ahlswede's strong converse applied to each component. Without knowledge of the realized component, we prove a single-letter inner bound for every $0\le\varepsilon<1$, in which one input serves all components; for $\varepsilon=0$ it is tight, and the capacity region is given by the essential infima of the component mutual informations. We prove a single-letter outer bound, the outage region, in which each component may use its own input; it holds with or without channel state information (CSI) at either terminal, and it is the $\varepsilon$-capacity region when the encoders know the component and the parameter space is countable. Both bounds coincide, in all four CSI scenarios, for well-ordered mixed MACs, which include degradedly ordered families and mixtures with a common optimal input, such as mixed additive MACs. Without CSI the outer bound can be strictly loose, and the no-CSI $\varepsilon$-capacity region for $0<\varepsilon<1$ remains open in general. Finally, we extend Ahlswede's strong converse to $K$ users with cost constraints and show that most of these results extend to $K$-user mixed MACs.

Comment
27 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Information Spectrum Methods for $\varepsilon$-Capacity Problems in the Theory of Mixed Multiple-Access Channels with Cost Constraint

cs.IT ·2026-09-16 ·Te Sun Han, Hideki Yagi
theory similarity 0.90
Abstract · 77 pages, 3 figures, the proof of Theorem 7 is fixed, necessary remarks are added

We study the $\varepsilon$-capacity regions of mixed multiple-access channels (MACs) with general mixture where the channel inputs are subject to a cost constraint from the information spectrum unified perspective. We first determine the $\varepsilon$-capacity results for additive MACs. We next give a single-letterized inner bound on the $\varepsilon$-capacity region for mixed memoryless MACs, and furthermore establish a single-letterized $0$-capacity region of the mixed memoryless MAC with finite alphabets in terms of the essential infimum of mutual informations for component channels. We also show that the MAC with additive Gaussian noise satisfies the strong converse property, which is stronger than the traditional strong converse theorem. We then focus on the quasi-static fading Gaussian MAC, for which we derive the $\varepsilon$-capacity region and show that it, in the case specialized to single-users, exactly coincides with the traditional $\varepsilon$-outage capacity region, thereby providing a Shannon-theoretic operational interpretation of the latter. We further verify that the $\varepsilon$-capacity regions coincide across four scenarios of CSI availability (no-CSI, CSIR, CSIT, and CSIRT). We also demonstrate that this coincidence generally fails for mixed MACs with general (not necessarily stationary or ergodic) components, and give a counter example to prove it. Finally, we extend these results to the $K$-user quasi-static fading Gaussian MAC.

0.21

Information-Spectrum General Formulas for the Capacity Region of Classical-Quantum Multiple Access Channels

cs.IT quant-ph ·2026-11-05 ·Takuya Kubo, Hiroshi Nagaoka
similarity 0.73
Abstract · 11 pages

For classical-quantum multiple access channels (cq-MACs) with two senders, we give several general expressions for the capacity region, valid for arbitrary sequences of channels. In the case of asymptotically vanishing error ($\varepsilon=0$), the capacity region is expressed in terms of spectral inf-mutual information rates. For every $0\le\varepsilon<1$, the $\varepsilon$-capacity region is expressed in terms of a quantity defined through a linear combination of three alternative hypotheses. In particular, the outer bound of Kubo and Nagaoka (2015) is tight. Our results include the quantum counterpart of the general formula of Han (1998) for the classical MAC. The most important ingredient is the one-shot inner bound of Sen (2021), which we apply to each member of an arbitrary channel sequence.

0.25

Information Spectrum Methods for MUltiple-Access Channels--Part III : The Strong Converse in the $K$-User Gaussian Case

cs.IT ·2026-11-12 ·Te Sun Han, Hideki Yagi
similarity 0.71
Abstract · 13 pages, 0 figures

This paper, Part III of a series, treats $K$-user multiple-access channels (MACs). Its starting point is a pair of fundamental lemmas, a random-coding lemma of Feinstein type and a converse lemma of Verdú--Han type, which are the $K$-user extensions of the two lemmas underlying Han's information spectrum approach to the general two-user MAC. From them we derive the capacity region of the general $K$-user MAC with cost constraint and show that it contains the polymatroid capacity region of the $K$-user Gaussian MAC. We then prove, by an elementary information spectrum calculation that adapts a diffuse--exceptional subspace decomposition used in recent second-order converses for the Gaussian MAC, that for every subset $\cS$ of users and every independent input satisfying the power constraints, the conditional information spectral-sup rate of the $K$-user Gaussian MAC does not exceed $\frac12\log(1+P_\cS/N)$, where $P_\cS$ is the total power of the users in $\cS$, with a probability bound that does not depend on the input. Consequently, the strong converse for the $K$-user Gaussian MAC, in the sense that the error probability tends to one for every rate tuple outside the capacity region, follows directly from the converse lemma, without the wringing technique and without hypothesis-testing meta-converses. This strong converse was first established by Fong and Tan, whose per-blocklength bounds yield it, through wringing and quantization. It is the key ingredient in the converse parts of the coding theorems for mixed Gaussian MACs in Part I, where the $\varepsilon$-strong converse would not suffice.

0.37

The Capacity Region of the Multiple Access Channel with Non-Signaling Assistance

cs.IT quant-ph ·2026-08-14 ·Yuhang Yao, Syed A. Jafar
theory similarity 0.67
Abstract

The capacity region of the $K$-sender discrete memoryless multiple access channel (MAC) is fully characterized when non-signaling (NS) assistance is available to all $K$ transmitters and the receiver. It is shown to have the same form as the classical capacity region of the MAC, except that the input distribution is allowed to be arbitrarily dependent across the senders. In particular, the NS-assisted capacity region matches the natural generalization to $K$ senders of an outer bound that was previously established by Fawzi and Fermé for $K=2$ senders. Additionally, we provide examples of $K$-sender MACs where the multiplicative gain in capacity from NS-assistance is arbitrarily close to $K$. Combined with an upper bound from prior work, this establishes $K$ as the extremal value of the multiplicative gain from NS-assistance across all $K$-sender MAC settings.

0.32

A Tight Second-Order Converse Bound for Variable-Length Feedback Codes

cs.IT ·2026-09-10 ·Recep Can Yavas
similarity 0.65
Abstract · 26 pages, submitted to Information Theory Transactions

We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verdú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $ε$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.

0.11

Second-Order Asymptotics for the Gaussian MAC on the Relative Interior of the Sum-Rate Face

cs.IT ·2026-09-16 ·Vincent Y. F. Tan
similarity 0.65
Abstract · 37 pages; 9 figures

We completely characterize the second-order coding rate region of the two-user Gaussian multiple-access channel at points in the relative interior of the sum-rate face, under maximal per-codeword power constraints. For any fixed average error probability $0 < \varepsilon < 1/2$, a nontrivial mixture of power splits reduces the sum-rate dispersion and strictly improves upon standard inner bounds based on a constant power split. Thus, a constant power split, although sufficient to attain the first-order capacity region, is insufficient for second-order optimality in this regime. Our achievability proof builds on the constant composition and coded time-sharing framework of Scarlett, Martinez, and Guillén i Fàbregas, with an optimization over admissible power splits. A matching second-order converse establishes the optimality of the resulting coded time-sharing strategy.

0.44

Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

cs.IT ·2026-11-04 ·Neri Merhav
theory similarity 0.64
Abstract · 31 pages; submitted for publication

We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.

0.22

Monotonicity of the Rényi channel capacity under non-signaling assisted channel simulation

cs.IT quant-ph ·2026-09-28 ·Tina Shariat, Matt Hoogsteder-Riera, Marco Tomamichel
similarity 0.62
Abstract · 25 pages, 1 figure

We give an alternative variational proof that non-signaling correlations shared between the sender and receiver cannot increase the Rényi capacity of a classical channel. This monotonicity follows from the data-processing inequality for channel divergences established by Oufkir, Yao and Berta. Our approach works directly with the information-radius representation of the capacity. The constraints defining non-signaling boxes are linear in the box, while the Rényi capacity depends on the channel nonlinearly. We use a Legendre transform to express the capacity as an extremum over a family of affine functionals in which the channel appears linearly. Combining this method with separate arguments for the Shannon capacity and endpoint orders, we recover monotonicity at every order from zero to infinity. We then derive consequences for standard coding exponent functions: non-signaling simulation cannot increase the random-coding or sphere-packing exponent below capacity, or decrease the strong-converse exponent above capacity.

0.35