OctoInformBeta

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

Lemma 3.2: If X=X′X = X' outside an event of probability ε\varepsilon, then H(X)−H(X′)≤h(ε)+εlog⁡|α|H(X) - H(X') \le h(\varepsilon) + \varepsilon\log|\alpha|, with conditional and time-shifted analogues

Entropy gaps between random variables that rarely differ.

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 and X′X' be random variables on one finite probability space, with values in a finite set α\alpha of |α||\alpha| elements, that coincide outside an event of probability ε\varepsilon. The question is how much the entropy of XX can exceed that of X′X', in terms of ε\varepsilon and |α||\alpha|; and the same question for the entropy of XX given a second variable OO against that of X′X' given O′O', when OO and O′O', with values in a finite set β\beta, also coincide outside that event.

Along a walk z0,z1,…z_0, z_1, \dots of Gaussian integers the comparison is made for a shift in time. Quantities xkx_k and ckc_k attached to each time kk are read at a random time TT moved by an independent offset UU uniform on {0,…,n}\{0, \dots, n\}, and the conditional entropy of xx given cc at time T+UT + U is set against the one at time T+U+aT + U + a, for some a≤na \le n.

Finite 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.✦ The probability of an event E⊆ΩE \subseteq \Omega is p(E)=∑ω∈Ep(ω)p(E) = \sum_{\omega \in E} p(\omega). A random variable on Ω\Omega with values in a finite set α\alpha is a map X:Ω→αX\colon \Omega \to \alpha.

The law pXp_X of a random variable X:Ω→αX\colon \Omega \to \alpha, the pushforward of pp along XX, is the finite probability law on α\alpha that gives each point the total mass of its preimage: pX(b)=∑ω∈Ω,X(ω)=bp(ω)(b∈α).p_X(b) = \sum_{\omega \in \Omega,\ X(\omega) = b} p(\omega) \qquad (b \in \alpha).(1)✦

The entropy of a finite probability law qq on a finite set α\alpha is the Shannon sum H(q)=−∑b∈αq(b)log⁡q(b),H(q) = -\sum_{b \in \alpha} q(b) \log q(b),(2)✦ in natural logarithms and with 0log⁡0=00 \log 0 = 0. The entropy H(X)H(X) of a random variable XX is the entropy of its law pXp_X.✦ The conditional entropy H(X∣Y)H(X \mid Y) of a random variable XX given a random variable YY on Ω\Omega, with values in finite sets α\alpha and β\beta, is the difference H(X∣Y)=H(X,Y)−H(Y),H(X \mid Y) = H(X, Y) - H(Y),(3)✦ where (X,Y)(X, Y) is the random variable ω↦(X(ω),Y(ω))\omega \mapsto (X(\omega), Y(\omega)) with values in α×β\alpha \times \beta. 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 uniform law on a finite nonempty set SS is the finite probability law that gives every point of SS the mass 1/|S|1/|S|.✦ Given a finite probability law pp on a finite set II and, for each i∈Ii \in I, a finite probability law qiq_i on a finite set SS, the joint law p⊗qp \otimes q of pp and the family q=(qi)i∈Iq = (q_i)_{i \in I} is the finite probability law on I×SI \times S with masses (p⊗q)(i,s)=p(i)qi(s).(p \otimes q)(i, s) = p(i)\, q_i(s).(4)✦

The Claim

Theorem 1. Let pp be a finite probability law on a finite set Ω\Omega.

(a) Let XX and X′X' be random variables on Ω\Omega with values in a finite set α\alpha, and let EE be an event such that X(ω)=X′(ω)X(\omega) = X'(\omega) for every ω∈E\omega \in E with p(ω)>0p(\omega) > 0. If ε=1−p(E)\varepsilon = 1 - p(E) is the probability of the complement of EE, then H(X)−H(X′)≤h(ε)+εlog⁡|α|.H(X) - H(X') \le h(\varepsilon) + \varepsilon \log |\alpha|.(5)✦

(b) Let XX and X′X' be random variables on Ω\Omega with values in a finite set α\alpha, let OO and O′O' be random variables on Ω\Omega with values in a finite set β\beta, and let EE be an event such that X(ω)=X′(ω)X(\omega) = X'(\omega) and O(ω)=O′(ω)O(\omega) = O'(\omega) for every ω∈E\omega \in E with p(ω)>0p(\omega) > 0. If ε=1−p(E)\varepsilon = 1 - p(E) is the probability of the complement of EE, then H(X∣O)−H(X′∣O′)≤2h(ε)+ε(log⁡|α|+2log⁡|β|).H(X \mid O) - H(X' \mid O') \le 2h(\varepsilon) + \varepsilon\bigl(\log|\alpha| + 2\log|\beta|\bigr).(6)✦

(c) Let T:Ω→ℕT\colon \Omega \to \mathbb{N} be a random time, nn and aa natural numbers with a≤na \le n, and (xk)k≥0(x_k)_{k \ge 0} and (ck)k≥0(c_k)_{k \ge 0} sequences in finite sets α\alpha and β\beta. Give Ω×{0,…,n}\Omega \times \{0, \dots, n\} the joint law of pp and the uniform law on {0,…,n}\{0, \dots, n\}, let U(ω,s)=sU(\omega, s) = s, and write xT+Ux_{T+U} for the random variable (ω,s)↦xT(ω)+s(\omega, s) \mapsto x_{T(\omega) + s}, and likewise cT+Uc_{T+U}, xT+U+ax_{T+U+a} and cT+U+ac_{T+U+a}. Then, with ε=a/(n+1)\varepsilon = a/(n+1), H(xT+U+a∣cT+U+a)≤H(xT+U∣cT+U)+2h(ε)+ε(log⁡|α|+2log⁡|β|).\begin{aligned} H(x_{T+U+a} \mid c_{T+U+a}) \le{}& H(x_{T+U} \mid c_{T+U}) \\ &+ 2h(\varepsilon) + \varepsilon\bigl(\log|\alpha| + 2\log|\beta|\bigr). \end{aligned}(7)✦

In the paper, the result reads: if two laws of a pair of random variables on the same finite product alphabet of at most MM elements are at total variation distance at most ε≤1/2\varepsilon \le 1/2, and (X,O)(X, O) and (X′,O′)(X', O') stand for the pair under the first and the second law, then |H(X∣O)−H(X′∣O′)|≤2h(ε)+2εlog⁡M|H(X \mid O) - H(X' \mid O')| \le 2h(\varepsilon) + 2\varepsilon \log M.

What Is Checked

The claim is stated over finite probability laws on finite sets, the law (1) of a random variable, its entropy as the Shannon sum (2), conditional entropy as the difference (3), and, in its third part, the joint law (4) of pp with the uniform law on {0,…,n}\{0, \dots, n\}.