OctoInformBeta

OpenAI preprint, September 2026 · §8. Genuine traces, exact lengths, and testing

Lemma 8.1: Approximate trace pairs control independent samples after increasing the deletion rate

Restoring exact lengths with sample bounds.

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 trace reconstruction experiment observes the surviving subsequence of a binary word, including its length. The requested deletion probability is q∈[0,1]q\in[0,1]; each bit survives with probability 1−q1-q. A supplied pair has a working deletion rate ρ\rho. The construction choice is δ=min⁡(q,1/2)\delta=\min(q,1/2), with Λ=δ−3\Lambda=\delta^{-3}; the construction theorems call their working rate qq. The library’s restoration statement starts from a supplied level pair and permits any integer target length at least its scale NN.

A finite probability law PP on a finite set Ω\Omega is a nonnegative mass function whose masses sum to one.✦ For a finite probability law PP on Ω\Omega and a real function ff on Ω\Omega, the expectation 𝔼P[f]\mathbb E_P[f] is the real number given in (1). For a finite probability law PP on Ω\Omega and a probability kernel KK from Ω\Omega to a finite set AA, the mixture PKPK is the probability law on AA with masses given in (1). 𝔼P[f]=∑a∈ΩP(a)f(a),(PK)(b)=∑a∈ΩP(a)K(a)(b),b∈A.\begin{aligned} \mathbb E_P[f]&=\sum_{a\in\Omega}P(a)f(a),\\ (PK)(b)&=\sum_{a\in\Omega}P(a)K(a)(b),\qquad b\in A. \end{aligned}(1) The point mass at a∈Ωa\in\Omega is the probability law on Ω\Omega that assigns mass one to aa and zero elsewhere. For a finite probability law PP on Ω\Omega and a map ff from Ω\Omega to a finite set AA, the pushforward f*Pf_*P is the probability law on AA obtained by mixing the point masses at f(a)f(a) according to PP.✦ For a finite probability law PP on Ω\Omega and a natural sample count mm, the product law P⊗mP^{\otimes m} is the probability law on Ωm\Omega^m of mm independent samples from PP; its coordinates occupy the zero-based slots 0,…,m−10,\ldots,m-1, with masses given by (2). P⊗m(a0,…,am−1)=∏j=0m−1P(aj).P^{\otimes m}(a_0,\ldots,a_{m-1})=\prod_{j=0}^{m-1}P(a_j).(2)✦

For finite probability laws P,QP,Q on a common finite set, their total variation distance TV⁡(P,Q)\operatorname{TV}(P,Q), probability overlap overlap⁡(P,Q)\operatorname{overlap}(P,Q), and squared Hellinger distance H2(P,Q)H^2(P,Q) are the real quantities defined in (3). TV⁡(P,Q)=12∑a|P(a)−Q(a)|,overlap⁡(P,Q)=∑amin⁡{P(a),Q(a)}=1−TV⁡(P,Q),H2(P,Q)=∑a(P(a)−Q(a))2.\begin{aligned} \operatorname{TV}(P,Q)&=\frac12\sum_a|P(a)-Q(a)|,\\ \operatorname{overlap}(P,Q)&=\sum_a\min\{P(a),Q(a)\} =1-\operatorname{TV}(P,Q),\\ H^2(P,Q)&=\sum_a\bigl(\sqrt{P(a)}-\sqrt{Q(a)}\bigr)^2. \end{aligned}(3)

A binary word w∈{0,1}Lw\in\{0,1\}^L assigns a bit to each zero-based position 0,…,L−10,\ldots,L-1.✦ A binary trace is a finite list of bits.✦ The complete trace space 𝒯≤M\mathcal T_{\le M} is the set of finite lists of bits of lengths zero through MM; a bounded trace with bound MM is a finite list of bits belonging to 𝒯≤M\mathcal T_{\le M}. A deletion mask a∈{0,1}La\in\{0,1\}^L retains position jj when aj=1a_j=1.✦ The retained subsequence t(w,a)t(w,a) of a binary word ww under a deletion mask aa is the list of the bits retained by aa, in their original order.✦ For a binary word w∈{0,1}Lw\in\{0,1\}^L, the deletion mask law WqW_q is the probability law on {0,1}L\{0,1\}^L with weights given in (4). For a binary word w∈{0,1}Lw\in\{0,1\}^L with L≤ML\le M, the complete trace law 𝒟q≤M(w)\mathcal D_q^{\le M}(w) is the probability law on 𝒯≤M\mathcal T_{\le M} with masses given in (4). Wq(a)=∏j=0L−1{1−q,aj=1,q,aj=0,𝒟q≤M(w)(t)=∑a:t(w,a)=tWq(a),t∈𝒯≤M.\begin{aligned} W_q(a)&=\prod_{j=0}^{L-1} \begin{cases}1-q,&a_j=1,\\ q,&a_j=0,\end{cases}\\ \mathcal D_q^{\le M}(w)(t)&= \sum_{a:\,t(w,a)=t}W_q(a),\qquad t\in\mathcal T_{\le M}. \end{aligned}(4) For a word of exact length LL, write 𝒟q(w)=𝒟q≤L(w)\mathcal D_q(w)=\mathcal D_q^{\le L}(w).✦ For binary words u,vu,v, their complete trace overlap ov⁡q(u,v)\operatorname{ov}_q(u,v) is the probability overlap of their complete trace laws with the common bound M=max⁡{|u|,|v|}M=\max\{|u|,|v|\}, as given in (5). ov⁡q(u,v)=overlap⁡(𝒟q≤M(u),𝒟q≤M(v)).\operatorname{ov}_q(u,v)=\operatorname{overlap} \bigl(\mathcal D_q^{\le M}(u),\mathcal D_q^{\le M}(v)\bigr).(5)✦

Approximate Trace Pairs

The complete trace expectation ℰθ(w;f)\mathcal E_\theta(w;f), for a real parameter θ\theta and a real function ff on traces, is the functional defined by (6); here b::wb\mathbin{::}w prepends bit bb to ww. ℰθ(⌀;f)=f(⌀),ℰθ(b::w;f)=θℰθ(w;f)+(1−θ)ℰθ(w;t↦f(b::t)).\begin{aligned} \mathcal E_\theta(\varnothing;f)&=f(\varnothing),\\ \mathcal E_\theta(b\mathbin{::}w;f) &=\theta\mathcal E_\theta(w;f) +(1-\theta)\mathcal E_\theta \bigl(w;t\mapsto f(b\mathbin{::}t)\bigr). \end{aligned}(6)✦ For θ∈[0,1]\theta\in[0,1], this is expectation under the complete trace law. An approximate trace simulation PP of a binary word ww at rate θ\theta with error EE is a finite probability law with a decoder dd into traces satisfying (7) for every test ff taking values in [0,1][0,1]. |𝔼P[f(d(a))]−ℰθ(w;f)|≤E.\left|\mathbb E_P[f(d(a))]-\mathcal E_\theta(w;f)\right|\le E.(7) An approximate Hellinger trace pair for u,vu,v at rate θ\theta, with errors E,VE,V, consists of finite laws P,QP,Q on a common outcome set and a common decoder that simulate u,vu,v, respectively, with error EE, and satisfy H2(P,Q)≤VH^2(P,Q)\le V.✦

A concrete level pair UU at rate ρ∈[0,1]\rho\in[0,1], scale NN, error allowance Δ\Delta, decay exponent dd, overlap threshold ω\omega, count multiplier AA, zero-based level ii, and half moment order kk consists of distinct words u,vu,v and finite laws P,QP,Q with a common decoder. Their length and simulation error EUE_U satisfy (8), and the laws simulate the respective words with that error at rate ρ\rho. N2≤|u|=|v|≤N,EU≥0,EU|u|≤(i+1)Δ.\frac N2\le |u|=|v|\le N,\qquad E_U\ge0,\qquad \frac{E_U}{|u|}\le(i+1)\Delta.(8) The likelihood score ss of a concrete level pair UU is a real function on the common outcome set of its laws P,QP,Q satisfying the density relation and score bound in (9). The squared L2k(P)L^{2k}(P) moment norm appearing there uses probability weights, with even score exponent ri=2kr_i=2k. Q(a)=P(a)(1+s(a)),∥s∥L2k(P)2:=(𝔼P[|s|2k])1/k≤N−d.Q(a)=P(a)(1+s(a)),\qquad \|s\|_{L^{2k}(P)}^2 :=\left(\mathbb E_P[|s|^{2k}]\right)^{1/k}\le N^{-d}.(9) The repeated word uℓu^\ell is the concatenation of ℓ\ell copies of uu.✦ The pair also has a natural repetition count ℓ\ell satisfying (10). |u|≤ℓ≤A|u|,ω≤ov⁡ρ(uℓ,uℓ+1).|u|\le\ell\le A|u|,\qquad \omega\le\operatorname{ov}_\rho(u^\ell,u^{\ell+1}).(10)

The Claim

Theorem 1 (Approximate transfer and restoration). Let P,QP,Q be finite laws on Ω\Omega, let KK be a probability kernel into AA, and let R,SR,S be finite laws on AA. Suppose that H2(P,Q)≤VH^2(P,Q)\le V and that TV⁡(R,PK)≤E\operatorname{TV}(R,PK)\le E and TV⁡(S,QK)≤E\operatorname{TV}(S,QK)\le E. For every natural sample count mm, the approximate transfer bound is (11). TV⁡(R⊗m,S⊗m)≤mV+2mE.\operatorname{TV}(R^{\otimes m},S^{\otimes m}) \le\sqrt{mV}+2mE.(11)✦

Let u,vu,v have an approximate Hellinger trace pair at rate ρ\rho with errors E,VE,V. Suppose 0≤ρ<10\le\rho<1 and ρ≤q≤1\rho\le q\le1, and let nn be a natural number at least max⁡{|u|,|v|}\max\{|u|,|v|\}. Every natural sample count mm satisfies the degraded trace bound (12). TV⁡(𝒟q≤n(u)⊗m,𝒟q≤n(v)⊗m)≤mV+2mE.\operatorname{TV}\!\left( \mathcal D_q^{\le n}(u)^{\otimes m}, \mathcal D_q^{\le n}(v)^{\otimes m}\right) \le\sqrt{mV}+2mE.(12)✦

Let UU be a concrete level pair at rate ρ\rho, with parameters N,Δ,d,ω,A,i,kN,\Delta,d,\omega,A,i,k and simulation error EUE_U. Suppose 0≤ρ<10\le\rho<1, ρ≤q≤1\rho\le q\le1, and k≥1k\ge1. For every natural target length n≥Nn\ge N, there are distinct words x,y∈{0,1}nx,y\in\{0,1\}^n for which (13) holds for every natural sample count mm. TV⁡(𝒟q(x)⊗m,𝒟q(y)⊗m)≤mN−d+2mEU.\operatorname{TV}\!\left( \mathcal D_q(x)^{\otimes m},\mathcal D_q(y)^{\otimes m}\right) \le\sqrt{mN^{-d}}+2mE_U.(13)✦

In the paper, the result reads: for the global parameters D,dD,ΔD,d_D,\Delta there are distinct x,y∈{0,1}nx,y\in\{0,1\}^n such that, for every positive integer mm, TV⁡(𝒟q(x)⊗m,𝒟q(y)⊗m)≤mn−dD+2mn(D+1)Δ\operatorname{TV}(\mathcal D_q(x)^{\otimes m}, \mathcal D_q(y)^{\otimes m})\le\sqrt{mn^{-d_D}}+2mn(D+1)\Delta, and in particular TV⁡(𝒟q(x),𝒟q(y))≤n−dD/2+2n(D+1)Δ\operatorname{TV}(\mathcal D_q(x),\mathcal D_q(y)) \le n^{-d_D/2}+2n(D+1)\Delta.

What Is Checked

The statements range over finite probability laws and their mixtures and products; the trace statements use complete traces in a common bounded trace space and supplied approximate Hellinger or concrete level pairs. Deletion mask weights are nonnegative for parameters in [0,1][0,1]✦, and their sum over all masks of a fixed length is one for every real deletion parameter.✦