The Setting
Trace reconstruction compares the laws of the subsequences left after independent bit deletions. The induction measures this comparison at a prescribed word length, with auxiliary observations decoded into traces and with overlap between repeated words. Write for the requested deletion probability and put and ; the construction theorems call their working deletion rate by the name .
Finite Laws and Traces
A finite probability law on a finite set is a nonnegative mass function of total mass one.✦ The expectation of a real function on under a finite probability law on is the real number in (1). (1)✦ The point mass at an outcome of a finite set is the probability law on assigning mass one to and zero elsewhere. A Markov kernel from to a finite set assigns a probability law to each . For a finite probability law on , a Markov kernel from to , and a map , the mixture and the pushforward are the probability laws on in (2); the latter uses the point mass at each input. (2)
A binary word of length is a function assigning a bit to each zero-based position .✦ A deletion mask for a binary word of length is a list of decisions indexed by the positions , with retaining position and deleting it. For a deletion mask of a binary word of length and a real parameter , the deletion mask weight is the real number in (3). For and a word length , the deletion mask law is the probability law on deletion masks for a word of length that assigns mass to each mask .✦ (3)✦ A binary trace is a finite bit list, including its surviving length.✦ For a binary word and a deletion mask of its positions, the retained subsequence is the binary trace listing, in order, the bits of at retained positions.✦ For a nonnegative integer , the complete trace space is the set of binary traces of length at most , and the complete trace law of a binary word is the probability law obtained by applying the retained subsequence map to its deletion mask law, as in (4); a bounded trace of bound is an element of . (4)
Trace Comparison
For a binary word , a real parameter , and a real function on binary traces, the complete trace expectation is the real number determined recursively by (5). Here is the empty word, and prefixes the bit to the list . (5)✦ The overlap of two finite probability laws on the same outcome set is the real number in (6), where denotes their total variation distance. (6)✦ The complete trace overlap of binary words is , with both laws on . For a word and a nonnegative integer , the repeated word is the concatenation of copies of .✦
The Source Parameters
Let be nonnegative integers and a real size parameter. For a zero-based nonnegative integer block index , the warmup block count and source block dimension are the nonnegative integers in (7). The zero-based block index corresponds to block number . (7) For a nonnegative integer block dimension and a nonnegative integer number of blocks , the block gain and total score exponent are the real numbers in (8). (8) For a nonnegative integer level index , a nonnegative integer block dimension , and a zero-based nonnegative integer scale index , the scale slack , scale exponent , scale exponent product , and backwards target scale are the real numbers defined in (9). (9) The error allowance and half moment order at level are respectively the real number and nonnegative integer in (10), with even score exponent . The notation denotes the ceiling truncated below at zero; parameter quotients with denominator zero have value zero. (10)
For a real parameter , the rank Schur constant , primitive period constant , initial overlap lower bound , and source overlap constant are the real numbers defined in (11). (11)
The Definition
Definition 1 (Level pairs). Let . For a finite probability law on , a decoder into the set of all binary traces, a word , and , trace approximation is the condition (12). (12)✦ For a finite probability law on , a real function on , and a nonnegative integer , the even moment quantity is the real number in (13); for it is the squared norm, weighted by the probability law . (13)✦
Let be real parameters, and let be nonnegative integers. A concrete level pair in consists of binary words , finite probability laws on a common finite set , a common decoder , a real error , a real score , and an integer repetition count satisfying (14), where is the common word length. (14)✦ The class of source level pairs at level is the class in (15), with parameters from (7) through (11). (15)✦
In the paper, the result reads: choose and , depending only on , with and , and , depending only on , using the same choices at every level; a level- pair consists of distinct words of common length , auxiliary laws , and a common Markov kernel approximating both trace laws within with , where , the likelihood score has squared norm at most , and some integer satisfies .
What Is Checked
The level definitions are stated for binary words and finite auxiliary laws with a deterministic decoder, at a deletion rate in . The deletion mask weights satisfy (16). (16) For every real deletion parameter, the deletion mask weights sum to one; when the deletion rate lies in , every deletion mask weight is nonnegative.