OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1: Distances and working deletion rate: Finite probability laws, their distances, and the composition of deletion channels

Distances and deletion rates for complete traces.

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

A binary word xx of length mm is a function from {0,…,m−1}\{0,\ldots,m-1\} to {0,1}\{0,1\}.✦ A binary trace is a finite list of bits, including its surviving length.✦ The complete trace space 𝒯n\mathcal T_n is the set of all binary traces of length at most nn✦, and a bounded trace of bound nn is an element of 𝒯n\mathcal T_n.✦

A deletion mask aa of length mm is a function from {0,…,m−1}\{0,\ldots,m-1\} to {0,1}\{0,1\}, with ai=1a_i=1 indicating retention.✦ The retained subsequence tr⁡(x,a)\operatorname{tr}(x,a) consists of the bits xix_i with ai=1a_i=1, listed in increasing order of ii.✦

A finite probability law PP on a finite set AA assigns real masses P(a)P(a) satisfying (1). P(a)≥0(a∈A),∑a∈AP(a)=1.P(a)\geq 0\quad(a\in A),\qquad \sum_{a\in A}P(a)=1.(1)✦ For an element aa of a finite set AA, the point mass δa\delta_a on AA is the probability law that assigns mass one to aa and zero to every other element. For a family K(a)K(a) of finite probability laws on a finite set BB, the mixture law PKP K on BB has the masses in (2). (PK)(b)=∑a∈AP(a)K(a)(b),b∈B.(P K)(b)=\sum_{a\in A}P(a)K(a)(b),\qquad b\in B.(2)✦ The pushforward f*Pf_*P under a function f:A→Bf:A\to B is the mixture with point masses K(a)=δf(a)K(a)=\delta_{f(a)}.✦

Let q∈[0,1]q\in[0,1] be the requested deletion probability, so each bit survives with probability 1−q1-q. The deletion mask law Mq,mM_{q,m} assigns to a mask aa the probability in (3). Mq,m(a)=∏i=0m−1{1−q,ai=1,q,ai=0.M_{q,m}(a)=\prod_{i=0}^{m-1} \begin{cases} 1-q,&a_i=1,\\ q,&a_i=0. \end{cases}(3)✦ For a binary list ww of length m≤nm\leq n, regarded as a word on its mm positions, the complete trace law 𝒟q,n(w)\mathcal D_{q,n}(w) on 𝒯n\mathcal T_n is the pushforward in (4). 𝒟q,n(w)=(a↦tr⁡(w,a))*Mq,m.\mathcal D_{q,n}(w) =\bigl(a\mapsto\operatorname{tr}(w,a)\bigr)_*M_{q,m}.(4)✦

For real rates r<1r<1 and qq, the additional deletion rate e(r,q)e(r,q) is the scalar in (5). e(r,q)=q−r1−r.e(r,q)=\frac{q-r}{1-r}.(5)✦

The Claim

The construction theorems call their working deletion rate qq; here qq denotes the requested deletion probability.

Definition 1 (Distances and working deletion rate). Let P,QP,Q be finite probability laws on the same finite set AA, and write TV⁡(P,Q)=12∑a∈A|P(a)−Q(a)|\operatorname{TV}(P,Q)=\frac12\sum_{a\in A}|P(a)-Q(a)| for their total variation distance. For finite probability laws P,QP,Q on the same finite set AA, the probability overlap overlap⁡(P,Q)\operatorname{overlap}(P,Q) is the real number in (6). The squared Hellinger distance H2(P,Q)H^2(P,Q) between finite probability laws P,QP,Q on the same finite set AA is the real number in (7). overlap⁡(P,Q)=∑a∈Amin⁡{P(a),Q(a)}.\operatorname{overlap}(P,Q)=\sum_{a\in A}\min\{P(a),Q(a)\}.(6)✦ H2(P,Q)=∑a∈A(P(a)−Q(a))2.H^2(P,Q)=\sum_{a\in A}\bigl(\sqrt{P(a)}-\sqrt{Q(a)}\bigr)^2.(7)✦ For a requested deletion probability qq, the working deletion rate δ\delta is defined by (8). δ=min⁡{q,1/2}.\delta=\min\{q,1/2\}.(8)✦

Theorem 1 (Working scale and further deletion). Let 0<q<10<q<1 and let L≥0L\geq0 be real. The working scale δ3L\delta^3L satisfies (9). q3L8≤δ3L≤q3L.\frac{q^3L}{8}\leq\delta^3L\leq q^3L.(9)✦ Let 0≤r<10\leq r<1 and r≤q≤1r\leq q\leq1, and let ww be a binary list of length at most nn. The deletion channels satisfy the mixture identity (10). 𝒟q,n(w)=∑z∈𝒯n𝒟r,n(w)(z)𝒟e(r,q),n(z).\mathcal D_{q,n}(w) =\sum_{z\in\mathcal T_n}\mathcal D_{r,n}(w)(z)\, \mathcal D_{e(r,q),n}(z).(10)✦

In the paper, the result reads: overlap is 1−TV⁡(P,Q)1-\operatorname{TV}(P,Q), the maximal common subprobability mass, and H2(P,Q)H^2(P,Q) is the sum or integral of (dP−dQ)2(\sqrt{dP}-\sqrt{dQ})^2; the construction uses δ=min⁡{q,1/2}\delta=\min\{q,1/2\}, Λ=δ−3\Lambda=\delta^{-3}, and Hdel=δ3log⁡nH_{\mathrm{del}}=\delta^3\log n; further deletion at rate (q−δ)/(1−δ)(q-\delta)/(1-\delta) restores the requested channel.

What Is Checked

The distance definitions concern laws on finite sets, and the channel identity concerns binary lists and complete traces with a common finite length bound. The mask weights in (3) sum to one for every real qq✦ and are nonnegative for q∈[0,1]q\in[0,1].✦ The additional rate in (5) belongs to [0,1][0,1] whenever r<1r<1 and r≤q≤1r\leq q\leq1.✦ The working scale bound concerns requested deletion probabilities 0<q<10<q<1 and nonnegative real scales LL.