OctoInformBeta

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

Finite laws, entropy and information: Conditional entropy H(X∣Y)=H(X,Y)−H(Y)H(X \mid Y) = H(X,Y) - H(Y) and conditional mutual information, in natural logarithms, for variables with values in any set

Entropy and mutual information on finite probability spaces.

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 ZZ be a random Gaussian integer taking finitely many values, and let π\pi be a Gaussian prime of norm pp. The residue of ZZ modulo π\pi is a random class in ℤ[i]/(π)\mathbb{Z}[i]/(\pi), a group of pp elements, and the residues of ZZ modulo several Gaussian primes are random variables on one probability space. How evenly a residue is spread is measured by its entropy; how much one residue tells about another, once a third is known, by a conditional mutual information.

The library defines these quantities for random variables on a finite probability space with values in any set.

Finite Laws and Entropy

A finite probability law pp on a finite set Ω\Omega is a function p:Ω→ℝp\colon \Omega \to \mathbb{R} with p(ω)≥0p(\omega) \ge 0 for every ω∈Ω\omega \in \Omega and ∑ω∈Ωp(ω)=1.\sum_{\omega \in \Omega} p(\omega) = 1.(1)✦

A random variable XX on (Ω,p)(\Omega, p) with values in a set AA is a map X:Ω→AX\colon \Omega \to A. When AA is finite, the law of XX is the pushforward X*pX_*p of pp along XX, the finite probability law on AA given by X*p(a)=∑ω:X(ω)=ap(ω)(a∈A).X_*p(a) = \sum_{\omega \,:\, X(\omega) = a} p(\omega) \qquad (a \in A).(2)✦

The entropy H(q)H(q) of a finite probability law qq on a finite set AA is the Shannon sum H(q)=∑a∈Aη(q(a)),η(x)=−xlog⁡x,η(0)=0,H(q) = \sum_{a \in A} \eta\bigl(q(a)\bigr), \qquad \eta(x) = -x \log x, \quad \eta(0) = 0,(3)✦ with log\log the natural logarithm. The entropy H(X)H(X) of a random variable XX with values in a finite set is the entropy of its law: H(X)=H(X*p).H(X) = H(X_*p).(4)✦

The entropy Hf(X)H_f(X) of a random variable XX with values in an arbitrary set AA is the Shannon sum of the masses of its fibers, over the finitely many values xx that XX takes: Hf(X)=∑x∈X(Ω)η(p(X−1(x))),p(X−1(x))=∑ω:X(ω)=xp(ω).H_f(X) = \sum_{x \in X(\Omega)} \eta\bigl(p(X^{-1}(x))\bigr), \qquad p(X^{-1}(x)) = \sum_{\omega \,:\, X(\omega) = x} p(\omega).(5)✦

The joint variable (X,Y)(X, Y) of random variables XX and YY on (Ω,p)(\Omega, p) is the random variable ω↦(X(ω),Y(ω))\omega \mapsto (X(\omega), Y(\omega)), with values in the product of their value sets.

The Claim

Definition 1. Let pp be a finite probability law on a finite set Ω\Omega. For random variables XX and YY on (Ω,p)(\Omega, p) with values in finite sets, 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).(6)✦ For random variables XX and YY on (Ω,p)(\Omega, p) with values in arbitrary sets, the conditional entropy of XX given YY is Hf(X∣Y)=Hf(X,Y)−Hf(Y),H_f(X \mid Y) = H_f(X, Y) - H_f(Y),(7)✦ and, for XX with values in a finite set, Hf(X)=H(X).H_f(X) = H(X).(8)✦ For random variables XX, YY and OO on (Ω,p)(\Omega, p) with values in arbitrary sets, the conditional mutual information of XX and YY given OO is I(X;Y∣O)=Hf(X∣O)−Hf(X∣(O,Y)).I(X; Y \mid O) = H_f(X \mid O) - H_f\bigl(X \mid (O, Y)\bigr).(9)✦

In the paper, the result reads: H(X)H(X), H(X∣Y)H(X \mid Y) and I(X;Y∣O)I(X; Y \mid O) are the entropy, the conditional entropy and the conditional mutual information of random variables XX, YY and OO taking finitely many values.

What Is Checked

The claim is stated over finite probability laws on finite sets and their pushforwards (2) along maps into finite sets, with entropy given by the Shannon sum (3).