Which Boolean functions are most informative?

Gowtham Ramani Kumar, Thomas A. Courtade

In a 2013 study, researchers at Stanford explored a fundamental question at the intersection of information theory and computer science: given a set of noisy data bits, what is the single most informative "yes/no" question one can ask? This inquiry centers on the "Most Informative Bit" conjecture, which posits that a simple "dictatorship" function—observing just one bit—is the optimal way to extract information from noisy inputs.

The Problem: Extracting Information from Noise

Consider $n$ bits of data $X^n$ passed through a Binary Symmetric Channel with flip probability $\alpha$, resulting in noisy observations $Y^n$. The goal is to find a Boolean function $b(X^n)$ that maximizes the mutual information $I(b(X^n); Y^n)$.

Conjecture 1 suggests that this mutual information can never exceed $1 - H(\alpha)$, the value achieved by simply selecting a single bit (e.g., $b(X^n) = X_1$). While intuitively simple, proving that complex logic like Majority functions cannot outperform a single bit is mathematically challenging due to the discrete nature of the problem.

Methodology: Discrete Geometry and Fractals

The authors decomposed the problem into structural and analytical components. They hypothesized that the functions minimizing uncertainty must be "lexicographical" (lex), where outputs are determined by bits in a specific order.

A significant hurdle in the analytical proof is the "oscillatory" behavior of the information ratio. As noise levels approach zero, the ratio follows a pattern related to the Takagi function (or "blancmange curve"), a fractal, nowhere-differentiable function. This complexity explains why standard calculus fails to provide a straightforward proof.

The oscillatory behavior of the information ratio $T_\alpha(p)$ compared to the smooth bound $f(p)H(\alpha)$.

To navigate this, the authors employed Compression Operators derived from Harper’s Theorem on hypercube isoperimetry. They demonstrated that "compressing" a Boolean function toward a lexicographical order increases its informativeness, allowing them to focus on a much smaller subset of candidate functions.

Computational Verification

Because the mathematical behavior is so irregular, the researchers developed a recursive algorithm (Algorithm II.1) to numerically verify the inequality across all noise levels $\alpha \in [0, 0.5]$. This approach allowed them to exhaustively test the conjecture for all Boolean functions with up to $n=7$ inputs.

The power of their compression theory is most evident in the reduction of the search space. For $n=7$, the total number of possible Boolean functions is astronomical, yet the researchers were able to isolate a manageable set of candidates for verification.

Reduction of the search space for Boolean functions using compression theory.

Key Results and Implications

The study yielded several critical insights:

  • The Dictatorship of the Bit: In noisy environments, complex logic (like XOR or Majority) tends to "wash out" information. The most robust strategy is to rely on the single most reliable source.
  • Theorem 2: The authors rigorously proved that "2-compression" never decreases mutual information, providing a formal path for simplifying complex functions.
  • Gambling and Strategy: The findings suggest that in scenarios like betting on multiple stocks with limited questions, asking about a single stock is superior to asking about a weighted combination.

While the "Most Informative Bit" conjecture remains technically open for arbitrary $n$, this work provides overwhelming evidence and a robust framework for future proofs. The connection to discrete isoperimetric inequalities suggests that a complete solution may require entirely new mathematical tools with broad applications in coding theory and computer science.

Summary updated

BibTeX
@inproceedings{kumar2013which,
  author = {Gowtham Ramani Kumar and Thomas A. Courtade},
  title = {{Which Boolean functions are most informative?}},
  booktitle = {ISIT},
  year = {2013},
  doi = {10.1109/isit.2013.6620221},
}
Figure