OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1: Complete traces and reconstruction: Randomized estimators and extended-real sample complexity for the binary deletion channel

Complete traces and uniform reconstruction.

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

Deletion traces retain the order of surviving bits, while their locations in the input are hidden. Reconstruction asks for a randomized rule whose success probability meets the same threshold for every input of a fixed length.

The Definition

Definition 1. Let n,mn,m be nonnegative integers and let q,sq,s be real numbers. A binary input word xx of length nn is an element of the set 𝒲n\mathcal W_n in (1), with positions numbered from zero: 𝒲n={0,1}{0,…,n−1}.\mathcal W_n=\{0,1\}^{\{0,\ldots,n-1\}}.(1)✦ A complete trace w∈𝒯w\in\mathcal T is a finite binary sequence together with its length, with 𝒯\mathcal T given by (2): 𝒯=⨆ℓ≥0𝒲ℓ.\mathcal T=\bigsqcup_{\ell\geq 0}\mathcal W_\ell.(2)✦

A deletion mask a∈ℳna\in\mathcal M_n is a binary sequence indexed by the input positions, with ai=1a_i=1 indicating retention✦; its weight pq(a)p_q(a) is given by (3): ℳn={0,1}{0,…,n−1},pq(a)=∏i=0n−1{1−q,ai=1,q,ai=0.\mathcal M_n=\{0,1\}^{\{0,\ldots,n-1\}}, \qquad p_q(a)=\prod_{i=0}^{n-1} \begin{cases} 1-q,&a_i=1,\\ q,&a_i=0. \end{cases}(3) The retained subsequence Rax∈𝒯R_a x\in\mathcal T of x∈𝒲nx\in\mathcal W_n under a deletion mask a∈ℳna\in\mathcal M_n is the finite binary sequence obtained by keeping the positions with ai=1a_i=1 in increasing order of ii, as in (4): Rax=(xi:0≤i<n,ai=1, in increasing order of i).R_a x=(x_i:0\leq i<n,\ a_i=1\text{, in increasing order of }i).(4)✦ The complete trace space 𝒯≤n\mathcal T_{\leq n} for inputs of length nn is the finite set in (5): 𝒯≤n=⨆ℓ=0n𝒲ℓ.\mathcal T_{\leq n}=\bigsqcup_{\ell=0}^{n}\mathcal W_\ell.(5)✦

The trace mass Dq(x)(w)D_q(x)(w) of a complete trace w∈𝒯w\in\mathcal T from an input x∈𝒲nx\in\mathcal W_n is the real number given by (6): Dq(x)(w)=∑a∈ℳnpq(a)𝟏{Rax=w}.D_q(x)(w)=\sum_{a\in\mathcal M_n} p_q(a)\,\mathbf 1_{\{R_a x=w\}}.(6)✦ The one-trace total variation distance between inputs x,y∈𝒲nx,y\in\mathcal W_n is the quantity in (7): TV⁡(Dq(x),Dq(y))=12∑w∈𝒯≤n|Dq(x)(w)−Dq(y)(w)|.\operatorname{TV}\bigl(D_q(x),D_q(y)\bigr) =\frac12\sum_{w\in\mathcal T_{\leq n}} \left|D_q(x)(w)-D_q(y)(w)\right|.(7)✦

A randomized estimator AA for length-nn inputs based on mm traces is a function A:𝒯m×𝒲n→ℝA:\mathcal T^m\times\mathcal W_n\to\mathbb R whose output weights satisfy (8) for every observation tuple z∈𝒯mz\in\mathcal T^m: A(z,x)≥0(x∈𝒲n),∑x∈𝒲nA(z,x)=1.A(z,x)\geq 0\quad(x\in\mathcal W_n), \qquad \sum_{x\in\mathcal W_n}A(z,x)=1.(8)✦ The reconstruction success Sq(A,x)S_q(A,x) of AA on an input x∈𝒲nx\in\mathcal W_n is the quantity in (9): Sq(A,x)=∑(a1,…,am)∈ℳnm(∏j=1mpq(aj))A((Ra1x,…,Ramx),x).S_q(A,x)=\sum_{(a_1,\ldots,a_m)\in\mathcal M_n^m} \left(\prod_{j=1}^{m}p_q(a_j)\right) A\bigl((R_{a_1}x,\ldots,R_{a_m}x),x\bigr).(9)✦

A sufficient sample budget mm for length-nn inputs at deletion parameter qq and threshold ss is a nonnegative integer belonging to the set ℬq,s(n)\mathcal B_{q,s}(n) in (10): $$\mathcal B_{q,s}(n)= \left\{m\in\mathbb N: \begin{array}{l} \text{there is an estimator }A\text{ satisfying }\eqref{eq:claim5}\\ \text{with }S_q(A,x)\geq s\text{ for every }x\in\mathcal W_n \end{array}\right\}.$$(10)✦ The sample complexity Tq,s(n)T_{q,s}(n) is the extended nonnegative real number in (11), with the infimum of the empty set equal to ∞\infty: Tq,s(n)=inf[0,∞]ℬq,s(n).T_{q,s}(n)=\inf_{[0,\infty]}\mathcal B_{q,s}(n).(11)✦ The minimum one-trace total variation Δq(n)\Delta_q(n) for length-nn inputs at deletion parameter qq is the minimum distance between the trace masses of distinct inputs when n≥1n\geq1, and is zero when n=0n=0, as in (12): Δq(n)={minx,y∈𝒲nx≠yTV⁡(Dq(x),Dq(y)),n≥1,0,n=0.\Delta_q(n)= \begin{cases} \displaystyle\min_{\substack{x,y\in\mathcal W_n\\x\ne y}} \operatorname{TV}\bigl(D_q(x),D_q(y)\bigr),&n\geq1,\\ 0,&n=0. \end{cases}(12)✦

In the paper, the result reads: for a binary word xx of length nn and known q∈(0,1)q\in(0,1), Dq(x)D_q(x) deletes each bit independently with probability qq, concatenating the surviving bits and reporting their length; for s∈(0,1]s\in(0,1], Tq,s(n)T_{q,s}(n) is the least nonnegative integer sample budget allowing a randomized estimator to reconstruct every length-nn input with probability at least ss, or ∞\infty if no such budget exists; total variation is one half the sum of absolute mass differences, and Δq(n)\Delta_q(n) is its minimum over distinct length-nn inputs.

What Is Checked

The definitions are stated over finite binary words and finite tuples of complete traces, with arbitrary real parameters q,sq,s and nonnegative integer lengths and sample budgets.