CS Paper Radar

A Sharp Mutual Information Bound for Binary Pairs

Qianmian Guo

cs.IT ·submitted 2026-11-02 02:08 UTC · v1
theory

Abstract

We prove a sharp upper bound on the mutual information between two binary random variables in terms of their distribution-dependent KL contraction coefficient. This resolves the binary-pair conjecture of Anantharam, Gohari, Kamath, and Nair. Equality holds if and only if the variables are independent or form a doubly symmetric binary source. The proof uses supporting tangents of an entropy curve to vary the input distribution and the channel while preserving the contraction coefficient. Together with tensorization and data processing, the result also bounds the mutual information between binary outputs obtained separately from two correlated observation sequences. When the observation pairs are independent copies of a finite-alphabet pair, this bound depends only on the law of one pair and not on the number of observations.

Closest papers

Nearest neighbours by meaning across the whole index.

A Sharp Fisher-Information Inequality for Boolean Pairs: Proof of the Amari--Kobayashi Conjecture

cs.IT ·2026-10-29 ·Jun Chen, Shun Watanabe, Lei Yu
theory similarity 0.65
Abstract

Consider two terminals that observe correlated uniform binary vectors and separately compress their observations to one bit. We prove that, for every blocklength and every correlation parameter in $(-1,1)$, the Fisher information retained by the resulting pair of bits is maximized by matching parity functions of an appropriate degree, thereby resolving a conjecture of Amari and Kobayashi. The proof combines a Fourier-based bound on the derivative of the normalized covariance with a scalar inequality for signed polynomials subject to a global range constraint.

0.15

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.65
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

Sample Complexity of Peer Prediction

cs.IT cs.GT ·2026-08-17 ·Abdellah Aznag, Robin Bowers, Rachel Cummings, Jason Hartline, Matthew vonAllmen +1 more
similarity 0.64
Abstract

Peer prediction seeks to incentivize agents to truthfully report an observed signal by rewarding joint sets of reports without observing a ground truth. Following the generalization of information-theoretic mutual information introduced in Kong and Schoenebeck (2019), we call a function of a joint distribution over signals a mutual information when it is non-negative and disincentivizes garbling reports for all information structures. An unbiased estimator for a mutual information takes some number of samples from the distribution and returns rewards for both agents, such that the expected reward is equal to the mutual information. We seek to characterize the set of mutual informations with unbiased estimators for a given number of samples. We show that for three or fewer sampled report pairs, the only mutual information with an unbiased estimator is trivially zero, and for four or five samples with a binary report space, the Determinant Mutual Information (DMI) of Kong (2024) is the unique mutual information (up to a scalar multiple). We further show that DMI ceases to be unique at six samples. We provide an improved estimator of DMI for any given number of samples and characterize its convergence rate. We also examine mutual information estimators that accept a randomized number of samples. First, we show that mutual information estimators on an ex-ante bounded number of samples (termed "stop-short estimators") can achieve a lower variance than an equivalent fixed-sample estimator (for DMI). Second, we introduce the class of scoring-rule-based mutual informations and identify in this family a mutual information that can be estimated with under three samples in expectation.

0.45

Mutual Information Constrained Chernoff Bottleneck

cs.IT cs.LGmath.OCmath.ST+1 ·2026-09-29 ·Dier Tang, Guangyue Han
similarity 0.63
Abstract · 35 pages, 4 figures, 3 tables. Feedback and comments are welcome!

The classical information bottleneck (IB) measures the relevance of a representation $U$ of $X$ to a target $Y$ by $I(U;Y)$, which does not directly characterize the error of downstream decisions. For a binary hypothesis $Y$ inferred from many separately encoded observations, the optimal error exponent is the Chernoff information between the two conditional distributions of $U$ given $Y$. We study the mutual information constrained Chernoff bottleneck, which seeks an encoder that maximizes this Chernoff information subject to a rate constraint $I(U;X) \leq R$. We show that its optimal value $C(R)$ increases strictly up to $R = H(V)$, where $V$ merges the symbols of $X$ with equal likelihood ratio, remains at the uncompressed exponent beyond, and, unlike the IB curve, need not be concave. We further show that $k+1$ outputs suffice to attain $C(R)$, where $k$ is the cardinality of $V$. We propose an alternating algorithm that updates the encoder via a generalized Blahut--Arimoto algorithm and the Chernoff parameter $s$ via a nonlinear equation, and prove that its iterates remain feasible, with nondecreasing and convergent Chernoff information. Comparing with the classical IB for $n$ samples, we show that, whenever the two objectives disagree, the IB encoder has the smaller equivocation $H(Y|U^{n})$ at $n = 1$, whereas the Chernoff bottleneck has the smaller error probability and equivocation for all large $n$. Numerical experiments confirm the theory, and on real topic-detection data from the 20 Newsgroups corpus, compressing each word to only $17\%$ of its entropy retains $90\%$ of the error exponent and nearly the accuracy of the uncompressed classifier.

0.39

Wyner's Common Information and the Common Entropy are NP-Hard to Compute

cs.IT ·2026-10-11 ·Roberto Bruno, Ugo Vaccaro
theory similarity 0.62
Abstract · A preliminary version of the manuscript

Wyner's common information $J(p)$ and the common entropy $G(p)$ of a pair of random variables $(X,Y)$ with finite ranges and joint distribution $p$ are both defined by an optimization over the auxiliary random variables $W$ that make $X$ and $Y$ conditionally independent: $J(p)$ is the infimum of the mutual information $I(X,Y;W)$, and $G(p)$ is the infimum of the entropy $H(W)$. We prove that both quantities are NP-hard to compute. For Wyner's common information, deciding whether $J(p)$ is strictly smaller than a given integer $r$ is NP-hard, and the problem is NP-complete on tables that are uniform on their support and have the same number of positive entries in every row. The reduction is from Maximum Edge Biclique and rests on an exact criterion, in terms of rectangles in the support of $p$, for improving on the auxiliary $W=X$; every yes-instance satisfies $J(p)<r-1/(4N^2)$ and every no-instance satisfies $J(p)=r$, where $N$ is the number of positive entries of $p$. For the common entropy, deciding whether $G(p)\le r$ for a rational number $r$ is NP-hard, even for tables with at most four nonzero entries in each row, all taking one of two values. The reduction is from exact cover by $3$-sets and rests on a majorization property of the masses of the nonnegative rank-one decompositions of $p$, combined with a quantitative form of the Schur concavity of entropy. In both cases the separation between yes- and no-instances is inverse-polynomial in the size of $p$, so that approximating $J(p)$ or $G(p)$ within a suitable inverse-polynomial additive error is also NP-hard. The two mechanisms are genuinely different: we exhibit a table on which a large rectangle in the support lowers $J$ below the threshold of our first reduction while leaving $G$ on it.

0.15

Exact Common Information and Exact Channel Synthesis for Correlated Gaussian Sources

cs.IT ·2026-08-26 ·Lei Yu
similarity 0.61
Abstract · 16 pages, 2 figures

In this paper, we resolve two conjectures posed by Yu and Tan in 2020 (in two separate papers published in the IEEE Trans. Inf. Theory). Specifically, we establish that: 1) the exact common information for a pair of $ρ$-correlated Gaussian sources is given by the conjectured expression $\frac{1}{2}\log\frac{1+ρ}{1-ρ}+\fracρ{1+ρ}$; and 2) the admissible region for the shared randomness rate and the communication rate in exact channel synthesis is exactly the conjectured one. These results yield two important consequences. First, for any $ρ>0$, the exact common information of a correlated Gaussian pair strictly exceeds Wyner's common information. Second, for $ρ>0$, the exact channel synthesis of such a pair requires strictly higher rates than the total-variation version. The proof combines an exact optimal-transport representation of the worst-case Gaussian cross-entropy, Fathi's Gaussian transport inequality, and a determinant inequality arising from the covariance structure of the conditional means.

0.36

A Proof of the Most Informative Boolean Function Conjecture

cs.DS cs.IT ·2026-09-21 ·Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni +2 more
similarity 0.61
Abstract · Added links to end-to-end lean formalization, a short expository note, and discussion of concurrent work

Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade--Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H_2$ is binary entropy, with equality attained by dictator functions. The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers. The proof proceeds from a local inequality to a dimension-independent bound on entropy production. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs. The key estimate is therefore an unrestricted Bellman inequality with two mean constraints and two entropy constraints, allowing arbitrary couplings of the edge variables. This paper and its supplement provide the proofs and computational verification records. The document is lengthy because it is designed to be entirely self-contained, deriving all proofs from first principles and reproducing the proofs of cited results. We also give a self-contained expository note explaining the reduction to a low-dimensional inequality and the ideas behind the key lower bounds. The entire proof, including all numerical certificates, has been formally verified in Lean end-to-end, and is available online.

0.46

Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source

cs.IT ·2026-09-23 ·Georg Pichler
theorycode/datahot direction similarity 0.61
Abstract

We settle three conjectures concerning a doubly symmetric binary source $(X,Y)$ with crossover $p$. Consider Markov chains $U - X - Y - V$ with $U,V$ binary, and let $\mathcal{A}$ be the set of rate triples $(I(U;V),I(U;X),I(Y;V))$ attainable with arbitrary binary channels $X\to U$, $Y\to V$, and $\mathcal{B}$ the subset attainable with binary symmetric channels. The averaged BSC conjecture, Conjecture 5.2 of Pichler, Piantanida and Matz (2022), asserts $\operatorname{conv}\mathcal{A}=\operatorname{conv}\mathcal{B}$. We prove this for every $p\in[0,1]$. Two conjectures of Dikshtein, Ordentlich and Shamai (2022) concern the double-sided information bottleneck at $p=0$, where $Y=X$ and the two channels see the same source: their Conjecture 1 identifies the exact maximum of $I(U;V)$ at prescribed rates $I(U;X)$ and $I(Y;V)$, and their Conjecture 2 the exact minimum. We prove both for binary $U,V$: the two extrema are attained by the same pair of Z/S-channels, in opposite orientation for the maximum and in the same orientation for the minimum. The proofs were found with substantial AI assistance, and all three theorems are formalised in Lean 4 with Mathlib, depending only on the standard axioms. The development is available at https://github.com/g-pichler/bsc-averaging . The proof of Conjecture 1 of Dikshtein, Ordentlich and Shamai (2022) contains three certified computations, a polynomial bound, an interval sweep and a polynomial positivity certificate, all of which are checked in Lean.

0.58