The Setting
A trace reconstruction experiment observes the surviving subsequence of a binary word, including its length. The requested deletion probability is ; each bit survives with probability . A supplied pair has a working deletion rate . The construction choice is , with ; the construction theorems call their working rate . The library’s restoration statement starts from a supplied level pair and permits any integer target length at least its scale .
A finite probability law on a finite set is a nonnegative mass function whose masses sum to one.✦ For a finite probability law on and a real function on , the expectation is the real number given in (1). For a finite probability law on and a probability kernel from to a finite set , the mixture is the probability law on with masses given in (1). (1) The point mass at is the probability law on that assigns mass one to and zero elsewhere. For a finite probability law on and a map from to a finite set , the pushforward is the probability law on obtained by mixing the point masses at according to .✦ For a finite probability law on and a natural sample count , the product law is the probability law on of independent samples from ; its coordinates occupy the zero-based slots , with masses given by (2). (2)✦
For finite probability laws on a common finite set, their total variation distance , probability overlap , and squared Hellinger distance are the real quantities defined in (3). (3)
A binary word assigns a bit to each zero-based position .✦ A binary trace is a finite list of bits.✦ The complete trace space is the set of finite lists of bits of lengths zero through ; a bounded trace with bound is a finite list of bits belonging to . A deletion mask retains position when .✦ The retained subsequence of a binary word under a deletion mask is the list of the bits retained by , in their original order.✦ For a binary word , the deletion mask law is the probability law on with weights given in (4). For a binary word with , the complete trace law is the probability law on with masses given in (4). (4) For a word of exact length , write .✦ For binary words , their complete trace overlap is the probability overlap of their complete trace laws with the common bound , as given in (5). (5)✦
Approximate Trace Pairs
The complete trace expectation , for a real parameter and a real function on traces, is the functional defined by (6); here prepends bit to . (6)✦ For , this is expectation under the complete trace law. An approximate trace simulation of a binary word at rate with error is a finite probability law with a decoder into traces satisfying (7) for every test taking values in . (7) An approximate Hellinger trace pair for at rate , with errors , consists of finite laws on a common outcome set and a common decoder that simulate , respectively, with error , and satisfy .✦
A concrete level pair at rate , scale , error allowance , decay exponent , overlap threshold , count multiplier , zero-based level , and half moment order consists of distinct words and finite laws with a common decoder. Their length and simulation error satisfy (8), and the laws simulate the respective words with that error at rate . (8) The likelihood score of a concrete level pair is a real function on the common outcome set of its laws satisfying the density relation and score bound in (9). The squared moment norm appearing there uses probability weights, with even score exponent . (9) The repeated word is the concatenation of copies of .✦ The pair also has a natural repetition count satisfying (10). (10)
The Claim
Theorem 1 (Approximate transfer and restoration). Let be finite laws on , let be a probability kernel into , and let be finite laws on . Suppose that and that and . For every natural sample count , the approximate transfer bound is (11). (11)✦
Let have an approximate Hellinger trace pair at rate with errors . Suppose and , and let be a natural number at least . Every natural sample count satisfies the degraded trace bound (12). (12)✦
Let be a concrete level pair at rate , with parameters and simulation error . Suppose , , and . For every natural target length , there are distinct words for which (13) holds for every natural sample count . (13)✦
In the paper, the result reads: for the global parameters there are distinct such that, for every positive integer , , and in particular .
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 ✦, and their sum over all masks of a fixed length is one for every real deletion parameter.✦