The Setting
For a real center and a fixed normalized scale , the points , with natural , test random selectors and terminal labels in a finite router. The estimate concerns their simultaneous local misses after all selector values at have been prescribed.
Fix natural numbers . The children are , with the default child and nondefault children.✦ A decision node is a child sequence of length ✦; a terminal path is a child sequence of length .✦ Write for the edge obtained by appending child to , and for the prefix relation. An admissible edge is a nonempty path of length at most .✦
Separated window data consist of a length function and natural-valued path functions satisfying (1). For an admissible edge , put and let be its window. The conditions involving two edges apply when both are admissible; denotes an arbitrary continuation in the last line. (1)✦
For a real mesh parameter , the periodic cell index is the floor of times the fractional part .✦ For a natural level and a real point , the dyadic cell index is the periodic cell index at mesh , as in (2). Its cells are half-open and include their left endpoints. (2)
The selector resolution is for ✦, and the terminal resolution is .✦ A selector address is a triple with ✦; a terminal address is a pair with , where is an integer.✦ The selector address set is the finite set of selector addresses, and the terminal address set is the finite set of terminal addresses. The selector table space is the set of all Boolean assignments to , and the terminal table space is the set of all Boolean assignments to ; their elements are the selector tables and terminal tables , respectively. The queried addresses are (3). (3)
The Bernoulli bit law , for , assigns masses and to and ✦; the fair bit law is .✦ The independent selector and terminal laws, and their joint outcome law, are the product measures in (4). (4)
Local Routing and Trials
The extended selector value at is when , and is zero otherwise.✦ For any list of nondefault bits, the first successful child is the least index with value one, or the default child when all values are zero.✦ For a selector table , a path , and a real point , the pointwise first-success choice is the least nondefault child whose extended selector value at and is one, or the default child when all these values are zero.✦
An iterated routing path from a path at a fixed point is a path obtained by starting at and repeatedly appending the child chosen at the current path and at .✦ After zero steps it is . Given a rule assigning a child to each path and real point, a path , a real point and a natural number with , the local routed leaf is the terminal path obtained by following for steps from at . For a decision node and , let be the local routed leaf starting at and taking further steps with choice . The local selector-terminal test is the Boolean conjunction in (5). (5)✦
A child window trial of length is a pair with and ✦; for starting indices , its index is .✦ At , the local starts are ✦ and the common length is . The local trial set, its indices, shifted points, and queried selector addresses are given in (6); in particular, its indices are at least three. (6)
The center selector exposure is the Boolean assignment over all decision nodes and nondefault children.✦ For a Boolean assignment to the pairs of decision nodes and nondefault children, the selector exposure atom is the fiber in and the center-exposure atom is the fiber in specified in (7). For a center selector assignment , the local miss event is the subset of on which all local selector-terminal tests vanish, as specified in (7). (7)
For each selector table , let be a terminal path beginning with . For a center selector assignment and a terminal-path assignment beginning with , the miss event is the subset of defined in (8). (8)
The Claim
Theorem 1. Let be separated window data, a decision node, and . Fix , , and a full center selector assignment . For any terminal-path assignment depending on the selector table and beginning with , the event in (8) satisfies (9)✦ For the routed local tests in (5), the event in (7) satisfies (10)✦
In the paper, the result reads: for a stable center and a full center-exposure atom whose first default node has height , putting , with denoting the window length at height , every fixed gives conditional probability , given , that for every and , where is the paper’s total number of children.
What Is Checked
The statements (9) and (10) are over separated window data and finite independent table laws, for arbitrary decision nodes and real centers, with normalized scale and terminal parameter . The leaf assignments in (9) may depend on the entire selector table, subject to the prescribed child prefix.
For every decision node and nondefault child , the local routing depth identity is (11). (11)✦