The Setting
A randomly displaced window tree replaces each occurrence of an initial binary word by a leaf observation and records paired observations from the surrounding runs. The root observation is the concatenation of these emissions in their prescribed order. The oracle considered here retains the complete tree, including paths that fail to fit inside their parent windows.
Let be the requested deletion probability, so that each bit survives with probability . Set and ; the construction theorems call their working rate . The simulation statement also allows an arbitrary rate .
A binary word of length is a function assigning a bit to each position in .✦ A deletion mask retains the positions where , in their original order.✦ The mask weight of a deletion mask is its probability at deletion rate , given by (1).✦ The complete trace law is the pushforward of this mask law under the retained subsequence map, on the bounded trace space .✦ A binary trace includes its surviving length. (1)
A finite probability law on a finite set is a nonnegative mass function with ✦; for a real test function on , its expectation is .✦ Products and coordinate products describe independent draws. A mixture of laws with mixing law has mass , and their joint law has mass at .✦ Write for the pushforward under and for the point mass concentrated at .
The complete trace expectation of a test is .✦ For a finite law , a decoder into binary traces and a binary word , the simulation discrepancy at deletion rate is the supremum of the expectation differences in (2). Approximate trace simulation with error means ✦; exact trace simulation means equality of the decoded and complete trace expectations for every real trace test.✦ (2)
For finite laws on a common outcome space, total variation and overlap use the normalization in (3). For binary words , complete trace overlap uses their two trace laws in the common bounded trace space with cutoff .✦ The repeated word is the concatenation of copies of .✦ (3)
The Window Oracle
Fix a Prouhet order , integer sequences of copy counts , window counts , local trial counts and repetition counts , and initial words . For a root orientation , the recursive source words are the complementary-word substitutions in (4), where denotes the pair of source words at level , is the Prouhet binary pattern and denotes complementary-word substitution.✦ Natural subtraction means . (4)
The scheduled global trial counts and their positions are defined by (5). A global trial at level has a zero-based pair of indices with and ; its single index is .✦ Its first and second emissions occur at the indicated pre and post positions. (5)
The complete window leaf set , trial set , filler set and collection set are the recursively indexed sets in (6). Levels are numbered from the bottom, and all child and trial indices are zero-based. A collection is one vertex’s local or global trial collection.✦ Write , and for the source leaf, trial and filler counts. (6)
A window orientation assignment on is a function assigning a bit to every trial in .✦ At depth zero there is one empty assignment. Choose fixed enumerations of the finite trial, filler and leaf sets. Flattening an assignment gives an array .✦
The nominal prefix and suffix counts , trial bundle reserve and local center are defined by (7). For a depth , the source layout margins require, for every , an even window count , , , an even local trial count , and .✦ (7)
The source trial word for a root local trial at depth is for side ; for a root global trial at depth it is the same word. A trial below a child uses that child’s trial word. The source filler words at depth one are empty. At depth , the filler on side of child is the run in (8), where and denote the source prefix and suffix filler counts and , . Fillers below children use the same recursion. After enumeration, denote the trial words by and the filler words by . (8)
The recursive leaf orientation starts with a root orientation , an incoming integer shift and a sequence of integer centers. At depth zero its value is . At a nonleaf, the integer template at the source node anchor determines the orientation passed to a child; that child’s scheduled shift is its incoming shift for the next step. With centers from (7), root incoming shift zero and flattened trial assignment , write for the resulting flattened leaf orientations.
A paired mechanism on a finite side outcome space is a collection of laws and weights indexed by the trial slots, satisfying for every .✦ A paired report consists of an optional orientation flag and two chronological outcomes ; denotes a hidden flag. The oriented pair laws , hidden pair masses , flagged pair masses and report laws are defined in (9). The joint report law on arrays of paired reports is the coordinate product of the individual report laws , so reports at distinct trial slots are independent. (9)
For a report array , the joint orientation posterior is the coordinate product of the flag posteriors✦: a hidden flag gives a fair bit and a visible flag gives .✦ Given finite leaf laws on a finite space , the selected leaf law for orientations is .✦ The canonical source oracle is the joint law of reports and leaf observations with mass (10).✦ (10)
An emission slot is one side of a trial, a filler, or a leaf.✦ Trial and filler slots have outcomes in , and leaf slots have outcomes in .✦ The public emission chronology at depth zero contains the sole leaf. At depth it lists the first local trial emissions, then for each child in increasing order its first scheduled global emissions, prefix filler, child chronology, second scheduled global emissions and suffix filler, followed by the second local trial emissions. Fixed enumerations identify these positions with the flattened emission slots.✦ For decoders and , the public decoder applies to trial and filler outcomes and to leaf outcomes, then concatenates the resulting words in this chronology.✦
The fitting tail is the finite tree bound for paths that fail to fit, defined in (11).✦ For a collection , let be its trial count: at a local collection at level , at a global collection, and the corresponding recursive count below a child.✦ For an overlap threshold , the hidden metadata tail is the sum in (12); empty collections contribute zero.✦ (11)
The Numerical Schedule
Fix maximum block dimension , block count and ambient size . The warmup block count is .✦ At zero-based block index , the dimension corresponds to block number , denoted in the paper. The block gain , total score exponent , scale slack , scale exponent and window exponent are specified in (13). (13)
The scale exponent product and backwards target scale are given in (14). The zero-based nesting index uses window exponent . The integer window size and extended block windows at target scale and dimension are and in (15). Floors and ceilings with a subscript are truncated below at zero. (14) (15)
The rank Schur constant , primitive period constant , initial overlap threshold and overlap multiplier are the constants in (16), evaluated at the working rate . (16)
A block arithmetic state records its length, overlap count, copy count and trial count.✦ For initial length and overlap count , its initial state is . Write for the first two coordinates of . Let be the source root trial count at parameters , and let denote the source local trial count. The arithmetic transitions and block trial counts are those in (17). (17)
A concrete level pair at rate , scale , allowance , decay exponent , overlap threshold , count multiplier , level and half moment order consists of distinct words of a common length , finite laws with a common decoder , a nonnegative simulation error , a likelihood score and a repetition count satisfying (18).✦ Its even score exponent is ; the squared moment norm is probability-weighted, with the order-zero value defined to be one. (18)
A source level pair at index is a concrete level pair at rate with , , , and the choices in (19).✦ (19)
The degree cutoff , work size , cancellation order , moment envelope , weight envelope and cap envelope are defined by (20). (20)
A finite ordered role shape of depth and branching bound is an ordered rooted tree with at most children at each vertex and one role in on each child; depth zero has one empty shape.✦ Let be the number of these shapes.✦ The bad role factor and forced role factor are the sums in (21). (21)
For level costs , the binary tree budget is the sequence and .✦ The smoothing and skeleton prefactors are and in (22). (22)
The numerical schedule margins at scale are the inequalities in (23), with the last two required for every .✦ The tail denominator and tail exponent are given by (24). (23) (24)
The Claim
Theorem 1. Fix , a depth , and the word construction above. Assume the layout margins , the identity , an even with and , and for every . Let paired mechanisms have slots, and let be finite filler laws for . Suppose exactly simulates the trial words from , the trial words from , and the filler words from , all at rate . Suppose simulates from , respectively, with errors at most . For either root orientation , the canonical simulation satisfies (25). (25)✦
Let , , and , and let be a source level pair at index , with left word length and overlap count . Set , , and form from (15) and (17), starting from . Assume the numerical schedule margins (23) at scale and . The level tail budget is (26). (26)✦
In the paper, the result reads: for the unconditioned surrogate laws , their common projection , root words , incoming leaf error , allowance and , the distances and are each at most , uniformly in block level .
What Is Checked
The simulation is stated over finite side and leaf outcome spaces, paired mechanisms with common-submass domination, and the complete window tree with its layout margins; the tail budget is stated over a source level pair and the numerical schedule margins at its next target scale.
Deletion mask weights sum to one for every real parameter✦ and are nonnegative on .✦ For any finite laws and any real common weight, the paired report masses sum to one. With a nonnegative common weight and common-submass domination, they are also nonnegative.✦ The public chronology contains every emission exactly once, and the rectangular global trial indexing is bijective.✦