CS Paper Radar

Exact Second-Order Asymptotics for the Discrete Wyner--Ziv Problem

Lin Zhou

cs.IT ·submitted 2026-10-08 14:05 UTC · v1

Abstract

We revisit the discrete Wyner--Ziv problem and establish exact second-order asymptotics. Our main contribution is a second-order converse bound, which is derived using posterior decomposition, concentration inequalities, and a conditional Gaussian approximation for martingales. Furthermore, we extend the previous best known achievability result of Li and Li (arXiv 2025) by allowing the test channel to depend on the type of the observed source sequence. Exact second-order asymptotics are established by combining our achievability and converse bounds. In particular, we show that the achievability bound of Li and Li (arXiv 2025) is not optimal in general. Specifically, we provide two numerical examples to illustrate our results: a binary asymmetric source and a quaternary source. For the first example, the achievability bound of Li and Li (arXiv 2025) achieves the optimal second-order asymptotics. However, in the second example, we show that our achievability result is optimal, which reduces the second-order coding rate of Li and Li (arXiv 2025) by $10.77\%$ at the excess-distortion probability of $0.1$ and by $21.35\%$ at the excess-distortion probability of $0.2$.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Second-Order Asymptotics for the Gaussian Gray--Wyner Problem

cs.IT ·2026-10-28 ·Lin Zhou, Lei Yu
theory similarity 0.65
Abstract

We revisit the Gray-Wyner problem of lossy compression of bivariate Gaussian sources under the quadratic distortion measure and derive the exact second-order asymptotics. Specifically, we first identify the boundary rate tuples using the explicit first-order asymptotics by Yu (TIT 2023) and then characterize the tradeoff among three second-order coding rates subject to a constraint on the joint excess-distortion probability. Our main contribution is the achievability proof, where we derive a covariance shell covering lemma that is analogous to the type covering lemma for the discrete case. In particular, our covering lemma classifies the source sequences into power shell types via their empirical covariance matrix. For each such power shell type, we derive sufficient conditions on the compression rates so that covering within distortion levels are achievable. Finally, asymptotical analysis via the Berry-Esseen theorem yields the desired result.

0.48

Exact Rate Exponent Tradeoff for New Classes of Distributed Hypothesis Testing Problems

cs.IT ·2026-08-24 ·Zhenduo Wen, Amin Gohari, Michèle Wigger
theory similarity 0.61
Abstract

We study the optimal Stein error exponent for one-way distributed hypothesis testing under a communication rate constraint. We establish exact rate-exponent tradeoffs for new classes of finite-alphabet sources, including a complete single-letter characterization for every pair of strictly positive binary joint distributions as well as testing-against-dependence. Our converse analysis refines the auxiliary-receiver method through three complementary steps. First, we establish an information-projection identity that identifies the posterior-divergence optimization in an existing converse with Han's exponent functional. Second, we obtain an additional excess-rate branch by retaining a mutual-information term discarded in the usual rate relaxation. Third, we develop a two-telescope upper bound whose auxiliary variables are coupled through a joint rate constraint. Combining these bounds with information-geometric matching conditions yields exact exponents for three classes of sources by matching the achievable bounds of Han and Shimokawa-Han-Amari.

0.37

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.61
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16

Finite Sample Bounds for Composite Hypothesis Testing

cs.IT ·2026-08-28 ·Elías Vera-Sigüenza, Amedeo Roberto Esposito
similarity 0.60
Abstract · 5 figures, 34 pages

We investigate composite binary hypothesis testing in the finite sample regime under asymmetric error constraints. Using Rényi divergences, we derive explicit achievability and converse bounds for the optimal Type II error. When the Type I error is constrained to decay exponentially with sample size, the bounds identify a phase transition and yield a strong converse above it. In the composite problem, the phase transition threshold is given by the joint KL projection over the alternative and null classes. Achievability is obtained through a joint Rényi projection whose log likelihood ratio defines a single test with uniform error control over both hypothesis classes, without requiring the projected pair to be least favourable. For compact convex classes with full support on a finite alphabet, we determine the exact error exponents on both sides of the transition and show that the achievable exponent is attained at a unique Rényi order. The same framework recovers the fixed Type I composite Chernoff--Stein exponent and yields a polynomial refinement of the finite sample achievability result. We further identify conditions under which the projected pair is least favourable at finite sample size.

0.13

When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions

cs.IT ·2026-10-21 ·Vivian Papadopoulou, Yonatan Yehezkeally, V. Arvind Rameshwar, Antonia Wachter-Zeh
theory similarity 0.60
Abstract

We consider the problem of binary sequence reconstruction where a sequence is transmitted multiple times over a channel, and each undergoes substitution errors by an arbitrary error vector of Hamming weight exactly $t$. We determine $N_{\mathrm{wc}}$, the minimum number of distinct channel output observations guaranteeing unique reconstruction by an optimal decoder, and show that the bit-wise majority-vote decoder, which was proved by Levenshtein (2001) to be optimal for channels corrupting up to $t$ bits, is in fact suboptimal here. Despite this suboptimality, we prove a condition that admits a practical early-termination rule, necessary for every decoder at any number of outputs $N$, and sufficient for bit-wise majority-vote even below $N_{\mathrm{wc}}$. We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below $N_{\mathrm{wc}}$ when the block-length $k>2t+1$. Finally, we propose an alternative algorithm aimed at guaranteeing unique reconstruction with fewer observations than bit-wise majority-vote, and demonstrate through exhaustive enumeration that it successfully decodes channel output-sets where bit-wise majority-vote fails.

0.11

Third-Order Asymptotics for Fixed-Length Lossy Compression of Discrete Memoryless Sources

cs.IT ·2026-11-10 ·Vincent Y. F. Tan
similarity 0.59
Abstract · 16 pages, 2 figures

This paper determines the third-order asymptotics of the logarithm of the minimum codebook size for fixed-length lossy compression of discrete memoryless sources. For an excess-distortion probability constraint $\varepsilon\in(0,1)$ and every interior distortion level, we establish a third-order correction of $\frac12\log n+O(1)$, where $n$ is the blocklength. This sharpens the general bounds of Kostina and Verdú [IEEE Trans. Inf. Theory, 2012]. The main technical innovation lies in the converse for positive dispersion. Under a reverse change of measure, we retain the exponential weights associated with tilted information and distortion slack and control them jointly using the multivariate weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [Proc. IEEE ISIT, 2015]. A pairing argument verifies the required covariance nondegeneracy uniformly over all reconstruction words whose distortion balls meet a typical set, yielding the matching converse.

0.31

Exact Second-Order Asymptotics for the Wyner--Ahlswede--Körner Problem

cs.IT ·2026-08-22 ·Daming Cao
similarity 0.59
Abstract · Draft manuscript

We determine the exact local second-order rate region of the finite-alphabet Wyner--Ahlswede--Körner problem under full support, at informative boundary points exposed by a finite supporting slope. The characterization permits nonunique optimizing test channels with unequal information variances and requires no neighborhood smoothness of the optimized first-order value. The optimal success function is a conditional Gaussian envelope averaged over the fluctuation of the helper's observed source type. For each type, the helper selects the minimum or maximum conditional variance according to the remaining description budget, while preserving both first-order rates. The converse follows from a uniform Gaussian bound for ordinary channel images. An exact posterior score decomposition separates a common source score, a nonnegative optimality gap, a negligible source residual on low-cost histories, and a conditionally independent channel fluctuation. Conditional-type covering with two endpoint optimizers and one common binning map attains the bound. Under a strict first-order benefit from the helper, a separate limiting-rate argument also gives the unrestricted weighted second-order optimum. A strictly positive finite source exhibits a strict gain over every fixed-optimizer Gaussian expression, and an exact binary image calculation illustrates the limiting coefficient.

0.48

Learning Finite-Memory Binary Sources

cs.IT math.PR ·2026-10-29 ·Maciej Skorski
similarity 0.59
Abstract

Estimating biased finite-memory sources from a single trajectory is a fundamental problem with practical impact, for example in estimating entropy for cryptography. We study order-$d$ binary sources whose conditional probabilities have bias at most $ε$, and establish *sharp* sample complexity bounds: relative accuracy $γ$ with confidence $1-δ$ needs $γ^{-2}\,(\tfrac12-ε)^{-d}\,(\log d+\log\tfrac1δ)$ samples up to constants depending on $ε$, with matching upper and lower bounds and no dependence on mixing time or spectral gap. The proof rests on a sharp bound on expected hitting times of the sliding-window (de Bruijn) chain, which stay of order $1/π(w)$ uniformly in $d$ exactly when $ε<\tfrac3{10}$, and on majorization of the window masses by those of independent biased coins. Applied to published entropy-source validations, the bounds show that their trace lengths may be underpowered: $10^6$ bits cannot resolve all transitions of an $8$-bit model to better than about $4.5\%$ relative error.

0.17