CS Paper Radar

A Bayesian Proof of the Bernoulli Theorem

Jingbo Liu, Ilias Zadik

cs.IT math.PRmath.ST ·submitted 2026-08-11 15:09 UTC · v2
theory

Abstract

We give a new proof of the Bernoulli theorem, conjectured by Talagrand and proved in the seminal work of Bednorz and Latała. Our approach is based on information-theoretic ideas: lower bounds on the supremum of a Bernoulli process are translated to the fundamental limits of Bayesian estimation in a Cauchy additive channel. This leads to a new information-theoretic functional that characterizes Bernoulli-process suprema and plays a role analogous to Fernique's majorizing-measure functional for Gaussian processes. The same viewpoint yields a distributional strengthening: for any prescribed law of the index, we characterize the largest expected value attainable over all couplings of that index with the Bernoulli process. This extends to Bernoulli processes a phenomenon previously understood for Gaussian processes through the work of Fernique and Talagrand.

Comment
Added a citation to an independent and concurrent work by OpenAI

Closest papers

Nearest neighbours by meaning across the whole index.

Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta--Massey

cs.IT ·2026-08-24 ·Yihong Wu
similarity 0.59
Abstract

A textbook result in information theory is that linear encoders achieve the entropy for lossless compression of Bernoulli source with parameter $p$. For lossy compression, however, linearity is known to incur strict suboptimality compared to the rate-distortion function. Massey asked whether the optimal rate for linear encoding is achieved simply by compressing a fraction of the bits linearly and losslessly and estimating the rest by zero \cite{Massey1978}. For $p=\frac12$, Ancheta answered this question affirmatively \cite{Ancheta1978}. This note extends Ancheta's result to all $p<\frac12$. The key argument is to bound the entropy of the posterior distribution conditioned on an affine subspace in terms of its marginals. The proof was discovered by GPT-5.6 Sol in an interactive process guided by the author. The purpose of the present note is to communicate a simplified version of this proof and to make connections with the existing literature on coding theory and spin glass theory.

0.41

Functional inequalities from the fundamental limits of Bayesian estimation

cs.IT math.PRmath.ST ·2026-11-04 ·Shuchen Li, Ilias Zadik
theory similarity 0.57
Abstract

We develop a Bayesian information-theoretic framework for proving functional inequalities for log-concave measures. Motivated by Klartag and Ordentlich, we establish a unified equivalence between $Φ$-Sobolev inequalities and Bayesian estimation lower bounds: for a large class of smooth convex $Φ$, a log-concave measure $μ$ satisfies a $Φ$-Sobolev inequality with constant $C>0$ if and only if for $X\simμ$, any $t>0$, and any real-valued measurable $f$, the Bayes risk of estimating $f(X)$ under the $Φ$-Bregman loss from the Gaussian additive observation $Y_t=\sqrt tX+G, G\sim N(0,I_n)$ is at least a $1/(1+Ct)$-fraction of that of the trivial estimator. Combining it with direct information-theoretic arguments, such as testing-to-estimation reductions, we obtain old and new functional inequalities: - For the Poincaré inequality, corresponding to $Φ(x)=(x-1)^2$, we give a simple static information-theoretic proof that the Poincaré constant of an isotropic log-concave measure on $\mathbb{R}^n$ is $O(n^{1/2})$, first proven via stochastic localization in the seminal work of Lee and Vempala. - For the log-Sobolev inequality, corresponding to $Φ(x)=x\log x$, we prove that all smooth $K$-subgaussian log-concave measures $μ$ satisfy $C_{\mathrm{LS}}(μ)\lesssim K^2n^{1/4}$, surpassing the recent state-of-the-art bound of $O(K^2n^{1/2})$ by Bizeul. In parallel and independent work, OpenAI claimed the optimal bound $O(K^2)$ in their October 6, 2026 release of 722 papers. - Finally, we give a Bayesian reformulation of the common structure of the three recent proofs of the Kannan--Lovász--Simonovits conjecture, a dimension-free Poincaré bound for isotropic log-concave measures [BK26; BKL26; SZ26]. Tools from the study of the "low-degree MMSE" in computational complexity of statistical inference motivate and recast key steps and quantities of these proofs.

0.24

The marginal is pretty good

cs.IT quant-ph ·2026-09-04 ·Lukas Schmitt, Gui-Long Jiang, Shi-Bing Li, Joseph M. Renes
theory similarity 0.56
Abstract · 12 pages, Gui-Long Jiang and Shi-Bing Li added as authors, Theorem 3.1 now holds for $α\in(0,1)$ (instead of $[1/2,1)$), Theorem 4.1 and 4.2…

One-shot information theory measures often require an optimization over states, but the form of these optimizers can be complicated or depend on the initial problem in nonlinear ways. In this note, we show that in many instances using the marginal instead of the optimal state is sufficiently good and only changes the result by a small factor. We prove that for the Petz--Rényi and sandwiched--Rényi divergences of order $α\in(0,1)$, replacing the optimizing state on $B$ by the marginal $ρ_B$ results in a multiplicative overhead of at most $1/α$.

0.28

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

cs.IT ·2026-10-08 ·Lin Zhou
similarity 0.56
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$.

0.43

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

A Poisson Transition and Bias Law for KSG Mutual-Information Estimation

cs.IT ·2026-10-27 ·Abhiram Gorle, Tsachy Weissman
theory similarity 0.54
Abstract

We quantify the error of the strict-radius Kraskov--Stögbauer--Grassberger (KSG-1) mutual-information estimator on a Gaussian channel as the sample size \(n\) grows and the channel becomes nearly deterministic. For fixed dimension \(p\) and neighbor index \(k\), we define the resolution parameter \(u_n=ne^{-I_n}\), where \(I_n\) is the true mutual information in nats. When \(u_n\to u\in(0,\infty)\), we prove that the estimation error converges in mean square to a computable deterministic bias \(B_{p,k}(u)\). Sampling fluctuations therefore vanish, while an additive bias can persist. We derive this bias from an explicit marked-Poisson law for the neighborhood counts, characterize its small-\(u\) asymptotics, and show that it tends to zero as \(u\to\infty\). The same law describes how often neighborhoods saturate, meaning that they make the largest possible contribution to the estimate. The limiting saturation probability decreases continuously and strictly from one to zero, allowing a Gaussian-model bias correction on fixed critical intervals. Finite-sample experiments show substantial bias even when the true information lies below the estimator's logarithmic ceiling and saturated neighborhoods are rare. Saturation-based correction reduces estimation error in these experiments, though recovering the resolution parameter from the observed saturation fraction can remain difficult when saturation is rare.

0.23

Recursive overlap Bernoulli distributions and an entropy concavity conjecture

cs.IT math.DS ·2026-09-02 ·Jörg Neunhäuserer
similarity 0.54
Abstract

We introduce a family of recursively generated finite probability distributions obtained from left and right embeddings with overlaps. The construction interpolates between the classical binomial distribution and the non-overlapping Bernoulli product distribution. We derive explicit formulas for the expectation, variance, and the generating function of higher moments, and formulate a conjecture asserting that the Shannon entropy is concave. The conjecture is proved in the two extremal cases and supported by symbolic computations for numerous overlap sequences.

0.26

The Information Bottleneck and the Privacy Funnel are NP-hard

cs.IT ·2026-10-15 ·Roberto Bruno, Ugo Vaccaro
similarity 0.54
Abstract · Updated version of the manuscript with additional results. Submitted for publication

Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. In both scenarios $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value $\operatorname{IB}(P_{XY},R) = \sup_T \{ I(Y;T) : I(X;T) \le R \}$ of the information bottleneck problem, as well as its Lagrangian relaxation $L_β(P_{XY}) = \sup_T [ I(Y;T) - βI(X;T) ]$, is NP-hard. Moreover, unless $\mathrm{P} = \mathrm{NP}$, neither $\operatorname{IB}(P_{XY},R)$ nor $L_β(P_{XY})$ can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-(1+α)}$, for every fixed $α> 0$. We also prove that computing the privacy funnel $\operatorname{PF}(P_{XY},r) = \inf_T \{ I(Y;T) : I(X;T) \ge r \}$ and its Lagrangian relaxation $Λ_β(P_{XY}) = \inf_T [ I(Y;T) - βI(X;T) ]$ is NP-hard, and that, unless $\mathrm{P} = \mathrm{NP}$, neither can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-2}$.

0.24