OctoInformBeta

OpenAI preprint, September 2026 · §3. Arithmetic, walks, and entropy

Lemma 3.3: For XX with aa values, confined to at most bb candidates given YY on an event of probability ρ\rho: H(X∣Y)≤h(ρ)+ρlog⁡b+(1−ρ)log⁡aH(X\mid Y)\le h(\rho)+\rho\log b+(1-\rho)\log a

A short list of candidates bounds conditional entropy.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let XX be a random variable taking values in a finite set 𝒳\mathcal{X} of aa elements, and YY a second random variable, the data from which XX is to be recovered. Suppose a list ℒ(y)⊆𝒳\mathcal{L}(y) \subseteq \mathcal{X} of candidates is attached to each value yy of YY, and that on an event of probability ρ\rho the list ℒ(Y)\mathcal{L}(Y) has at most bb entries and contains XX. The lemma bounds the conditional entropy H(X∣Y)H(X \mid Y), the uncertainty left in XX once YY is known, in terms of aa, bb and ρ\rho alone, and bounds from below the deficit log⁡a−H(X∣Y)\log a - H(X \mid Y).

Laws and Entropy

A finite probability law pp on a finite set Ω\Omega is a function p:Ω→ℝp \colon \Omega \to \mathbb{R} that is nonnegative at every point and whose values sum to one: p(ω)≥0(ω∈Ω),∑ω∈Ωp(ω)=1.p(\omega) \ge 0 \quad (\omega \in \Omega), \qquad \sum_{\omega \in \Omega} p(\omega) = 1.(1) The points of Ω\Omega are the outcomes, a random variable is a map from Ω\Omega to a finite set, and an event E⊆ΩE \subseteq \Omega has probability p(E)=∑ω∈Ep(ω)p(E) = \sum_{\omega \in E} p(\omega).

The pushforward of pp along a map ff from Ω\Omega to a finite set SS is the finite probability law f*pf_*p on SS that gives each point the total mass of its preimage: (f*p)(s)=∑ω:f(ω)=sp(ω)(s∈S).(f_*p)(s) = \sum_{\omega \,:\, f(\omega) = s} p(\omega) \qquad (s \in S).(2)✦ The law of a random variable XX is its pushforward X*pX_*p.

The entropy of a finite probability law qq on a finite set SS is its Shannon sum, in natural logarithms and with 0log⁡0=00 \log 0 = 0: H(q)=−∑s∈Sq(s)log⁡q(s).H(q) = -\sum_{s \in S} q(s) \log q(s).(3)✦ A random variable XX on Ω\Omega has entropy H(X)=H(X*p)H(X) = H(X_*p), the entropy of its law.✦ For random variables XX and YY on Ω\Omega, the pair (X,Y)(X, Y) is the random variable ω↦(X(ω),Y(ω))\omega \mapsto (X(\omega), Y(\omega)), and the conditional entropy of XX given YY is H(X∣Y)=H(X,Y)−H(Y).H(X \mid Y) = H(X, Y) - H(Y).(4) The binary entropy of ε∈[0,1]\varepsilon \in [0, 1] is h(ε)=−εlog⁡ε−(1−ε)log⁡(1−ε)h(\varepsilon) = -\varepsilon \log \varepsilon - (1 - \varepsilon) \log (1 - \varepsilon).

The Claim

Theorem 1. Let pp be a finite probability law on a finite set Ω\Omega, and let XX and YY be random variables on Ω\Omega with values in finite sets 𝒳\mathcal{X} and 𝒴\mathcal{Y}, where 𝒳\mathcal{X} has aa elements. Let ℒ\mathcal{L} assign to each y∈𝒴y \in \mathcal{Y} a subset ℒ(y)\mathcal{L}(y) of 𝒳\mathcal{X}, let b≥1b \ge 1 be a real number, and let E⊆ΩE \subseteq \Omega be an event of probability ρ=p(E)\rho = p(E) such that at every outcome ω∈E\omega \in E with p(ω)>0p(\omega) > 0 the list ℒ(Y(ω))\mathcal{L}(Y(\omega)) has at most bb elements and contains X(ω)X(\omega). Then H(X∣Y)≤h(ρ)+ρlog⁡b+(1−ρ)log⁡a,H(X \mid Y) \le h(\rho) + \rho \log b + (1 - \rho) \log a,(5)✦ and the deficit of H(X∣Y)H(X \mid Y) from log⁡a\log a is bounded below: ρ(log⁡a−log⁡b)−h(ρ)≤log⁡a−H(X∣Y).\rho (\log a - \log b) - h(\rho) \le \log a - H(X \mid Y).(6)✦

In the paper, the result reads: if XX has at most aa values, YY is finite data and ℒ(Y)\mathcal{L}(Y) is a list of possible values of XX with Pr⁡{X∈ℒ(Y),|ℒ(Y)|≤b}=ρ\Pr\{X \in \mathcal{L}(Y),\ |\mathcal{L}(Y)| \le b\} = \rho for some 1≤b≤a1 \le b \le a, then log⁡a−H(X∣Y)≥ρlog⁡(a/b)−h(ρ)\log a - H(X \mid Y) \ge \rho \log(a/b) - h(\rho).

What Is Checked

The claim is stated over finite probability laws (1), their pushforwards (2), the entropy of a law as its Shannon sum (3), the entropy of a random variable as the entropy of its law, and the conditional entropy (4), with the binary entropy hh.