Fisher information maximized by parity bits for correlated data
A Sharp Fisher-Information Inequality for Boolean Pairs: Proof of the Amari--Kobayashi Conjecture
Information Theory
Summary
This work addresses how to best compress two related sets of yes-or-no answers into just one yes-or-no answer each while preserving as much information as possible about their relationship. The authors prove that using a certain kind of parity check—adding up bits in a particular pattern—is the optimal way to do this for any data length and correlation level between the two sets. This confirms a long-standing guess made by Amari and Kobayashi. To prove this, they combine methods from analyzing functions on binary inputs with inequalities about special polynomials.
What this means in practice
- •For data compression engineers: Design compression schemes for correlated binary sources using parity to preserve maximal dependency information.
- •For distributed sensing teams: Optimize binary quantization rules for correlated sensor data to maximize retained Fisher information from compressed signals.
A theory result. No direct application yet.
Authors
Jun Chen, Shun Watanabe, Lei Yu
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.