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 be nonnegative integers and let be real numbers. A binary input word of length is an element of the set in (1), with positions numbered from zero: (1)✦ A complete trace is a finite binary sequence together with its length, with given by (2): (2)✦
A deletion mask is a binary sequence indexed by the input positions, with indicating retention✦; its weight is given by (3): (3) The retained subsequence of under a deletion mask is the finite binary sequence obtained by keeping the positions with in increasing order of , as in (4): (4)✦ The complete trace space for inputs of length is the finite set in (5): (5)✦
The trace mass of a complete trace from an input is the real number given by (6): (6)✦ The one-trace total variation distance between inputs is the quantity in (7): (7)✦
A randomized estimator for length- inputs based on traces is a function whose output weights satisfy (8) for every observation tuple : (8)✦ The reconstruction success of on an input is the quantity in (9): (9)✦
A sufficient sample budget for length- inputs at deletion parameter and threshold is a nonnegative integer belonging to the set 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 is the extended nonnegative real number in (11), with the infimum of the empty set equal to : (11)✦ The minimum one-trace total variation for length- inputs at deletion parameter is the minimum distance between the trace masses of distinct inputs when , and is zero when , as in (12): (12)✦
In the paper, the result reads: for a binary word of length and known , deletes each bit independently with probability , concatenating the surviving bits and reporting their length; for , is the least nonnegative integer sample budget allowing a randomized estimator to reconstruct every length- input with probability at least , or if no such budget exists; total variation is one half the sum of absolute mass differences, and is its minimum over distinct length- inputs.
What Is Checked
The definitions are stated over finite binary words and finite tuples of complete traces, with arbitrary real parameters and nonnegative integer lengths and sample budgets.