Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta--Massey
2026-08-24 • Information Theory
Information Theory
AI summaryⓘ
The authors discuss how to compress data made of random bits. While it's known that simple linear methods work perfectly for lossless compression, they aren't usually the best for lossy compression where some errors are allowed. Massey asked if a mixed approach—compressing some bits exactly and guessing the rest as zero—could be optimal for linear encoding. Ancheta confirmed this for perfectly random bits, and the authors extend this result to cases where bits are biased. Their proof uses mathematical tools from coding and spin glass theory and was partially discovered with AI help.
linear encodinglossless compressionlossy compressionBernoulli sourcerate-distortion functionentropyaffine subspacecoding theoryspin glass theory
Authors
Yihong Wu
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.