The Setting
A nested block has a binary orientation at every leaf. After the paired reports are observed, some of the hidden orientations remain fair bits. Averaging the leaf likelihood factors over these bits gives two conditional densities, one for each initial orientation. The library bounds the signed density through its coefficient energy and specializes the resulting estimate to the prescribed block schedule.
A finite probability law on a finite space is a nonnegative mass function with .✦ For a finite probability law on a finite space and a real function on , the expectation of under is .✦ For finite probability laws on and on , the product law is the finite probability law on the Cartesian product of their spaces with mass ✦, and the coordinate product of finite laws is the finite probability law with mass ✦; denotes the product of copies of .✦ All finite slots below are numbered from zero.
A paired mechanism on a side outcome space consists, at each trial , of finite laws and a weight satisfying .✦ A report contains an optional orientation flag and two chronologically ordered side outcomes. The absent flag records a jointly hidden pair. For a single trial with initial orientation , the hidden mass, oriented pair law, flagged mass and report mass are respectively the functions in (1): (1) The joint report law of paired mechanisms is the coordinate product of their paired report laws.✦ The reported orientation posterior is a binary probability law that fixes a visible flag and assigns probability to each orientation at an absent flag.✦ The joint orientation posterior for a report array is the coordinate product of the reported orientation posteriors of its trials.
The Complete Window Tree
For child counts and local and global trial counts , the complete window tree of depth has children of depth . A window leaf index in a complete window tree is a sequence of child choices along a path to a leaf; at depth zero there is one leaf.✦ A window trial index names a root local trial, a root global trial, or a trial below one of the children; at depth zero there are no trials.✦ A window assignment on a complete window tree with values in a set is a function assigning a value in to every window trial index, including those on unoccupied paths and paths that do not fit.✦ The leaf and trial counts , and the scheduled global counts, are specified by (2): (2) Nesting levels are numbered from the bottom. The assignment bijection reads values at their window trial indices.✦ Enumerating the finite trial set then identifies nested assignments with arrays of length ✦; the inverse places the flags of a report array into the nested tree.✦ Leaf arrays use the analogous finite enumeration of the window leaf indices.
The scheduled displacement at child is zero for . At level , global trials are grouped into blocks of trials, and the trial in within-block slot has global index .✦ Let be a complete binary orientation assignment, with orientations treated as the integers zero and one. The net global displacement and the local center are given by (3): (3) Fix a nonnegative motif scale . The recursive leaf orientation starts at an initial orientation . At a nonleaf it passes the integer template orientation at the node anchor to the chosen child, with that child’s scheduled displacement as incoming shift. At depth zero it returns the incoming orientation. With centers , zero incoming shift at the root, and a flattened complete assignment , write for the flattened leaf orientation array.✦
For centers , child displacements and sets of child indices, central motif support is the following recursive condition on a complete binary assignment: at a node of depth with incoming shift , every child at which the scale- motif indicator is nonzero belongs to , and every child satisfies the same condition with incoming shift .✦ The depth-zero condition is vacuous. The central third is .✦
The window posterior law for nested optional flags is the probability law on complete assignments that fixes reported orientations and makes all unreported orientations independent fair bits, with each global orientation drawn once.✦ It is the point mass on the empty assignment at depth zero and the product of the local, global and child posterior laws at positive depth.✦ For specified centers, displacements and sets of child indices, the noncentral posterior mass is the probability under this law that central motif support fails with incoming shift .✦ For a report , write for this mass using its nested flags, the local source centers, scheduled displacements, central thirds and zero root shift.
A paired report at depth is typical metadata for common weight and fitting threshold when it has at least hidden local trials and hidden global trials at every node of depth , and satisfies .✦ Write for this set of reports and for the set of pairs with and an arbitrary complete leaf sample .✦
Coefficients and Budgets
For a binary leaf array and a selection of leaf slots, the selection coefficient is the inclusion indicator that every selected slot has orientation one.✦ For a leaf law on a finite space , a real score and a leaf sample , the selection density multiplies over the slots of orientation one.✦ For a map from complete assignments to binary leaf arrays, the averaged selection coefficient and selection density under a finite law on assignments are defined in (4): (4) The source oracle coefficients and densities are these averages with and at depth . The signed source coefficient, weighted coefficient energy at a real scale , and source reference law are defined by (5); the coefficient sum uses counting measure, whereas reference moments use the probability law . (5)
The hidden binomial cap and hidden smoothing bound are the functions in (6):
A finite ordered role shape of depth and degree bound is an ordered rooted tree with at most children per internal vertex and a role in on each child; there is one shape at depth zero.✦ The shape and role count is the number of finite ordered role shapes of depth and degree bound . For level costs , the binary tree budget has and .✦
Put and . The interior label budget , source sparsity count , and forced contribution budget are given by (7): (7) For cutoff , smoothing allowance , fitting threshold and score weight , the sharp degree budget and sharp energy budget are defined by (8): (8)
The Block Schedule
For maximum dimension and block count , the warmup count is .✦ The dimension belongs to zero-based block index , hence to block . Floors and ceilings with subscript are truncated at zero. The block gain , total score exponent , error allowance , degree cutoff , work size and cancellation order are specified in (9): (9) The source moment envelope , weight envelope and gap lower bound are the constants in (10): (10) For target scale and block dimension , the scale exponents , window exponents , integer window sizes and extended block windows are defined in (11). (11)
A block length and overlap state is a quadruple of nonnegative integers giving length, overlap count, copies and trials.✦ With overlap multiplier , initial length and initial overlap count , start from and write for the length and overlap count at level . Let be the root trial count at target , length , window and overlap count , and let be the local trial count for copies and overlap count . The nested arithmetic states use copy counts and trial counts as in (12); these two counts describe entry into state . (12) For count factor , the source arithmetic bounds at are the conditions in (13) on these states: (13)✦
For a real cap , the bad role factor and forced role factor , together with the skeleton prefactor and smoothing prefactor , are defined by (14): (14)
The Claim
Theorem 1. Let for every , let be nonnegative integers, and let be real. Suppose , , and for . For every typical report , the conditional coefficient energy satisfies (15): (15)✦
For the reference bound, take paired mechanisms on a finite side outcome space and a finite leaf law . Let be a real score with . Suppose is an integer with , and write for the even score exponent. Suppose , , , for , and . The signed reference moment satisfies (16): (16)✦
For the block schedule, let be nonnegative integers. Suppose , , and . Set and take the windows and trials of (11) and (12). Assume the source arithmetic bounds (13), , and the budget conditions (17): (17) With , , and , the level bounds are (18): (18)✦
In the paper, the result reads: for the block of Proposition 5.1 and every exact typical metadata value , if is the product of the old first laws over all leaves and are the conditional densities obtained by averaging the type-dependent product of , with the old score, over all remaining hidden bits, including failed layouts, then with the paper’s score exponent , uniformly in and block level .
What Is Checked
The conditional bound (15) is stated over complete window assignments and typical reports. The reference bound (16) is over finite paired mechanisms and a centered leaf score with an even moment bound. The scheduled bound (18) assumes the specified arithmetic and prefactor inequalities. Under nonnegative common weight and common-submass domination, the paired report masses in (1) are nonnegative✦; for every real common weight their sum is one.✦