The Setting
A fixed real center reads bits from periodic dyadic grids as it follows a path through a finite router. Let . The router’s child set is , with nondefault children and default child .✦ The total number of children is , where uses the paper’s convention.
A decision node is a finite child sequence shorter than ✦, and a terminal path is a child sequence of length .✦ Their sets are (1) Choose selector resolutions and terminal resolutions on the sets in (1).
For real , the periodic mesh key is the floor of times the fractional part .✦ At level , put . The finite dyadic grid key is the integer index of the half-open cell containing : (2)
The selector address set consists of triples recording a decision node, a nondefault child and a grid entry.✦ The terminal address set consists of pairs recording a terminal path and a grid entry: (3) A Boolean selector table is a function ✦, and a terminal Boolean table is a function , on the addresses in (3).✦ The outcome space is the set of pairs consisting of a Boolean selector table and a terminal Boolean table.
For , the Bernoulli bit law assigns mass to and mass to ✦; the fair bit law is .✦ The independent fair selector law and the independent Bernoulli terminal law combine to give the independent table outcome law : (4) Probability values and their numerical expressions are taken in ; denotes a nonnegative real viewed in this interval.
For a decision node and nondefault child , the queried selector address uses the key in (2). The extended selector value is a bit defined for every finite child sequence : (5)
The first successful child of a Boolean vector is its least successful index, with the default chosen if none succeeds.✦ The center first-success rule , with fixed, and the pointwise first-success rule , with fixed, are child rules obtained by applying to the selector values in (5): (6)
For a child rule and a state , the iterated routing path starts from and successively appends the selected child.✦ For a finite child sequence and a child , write for appending to ; the iterated routing path is defined by (7) With the empty path, the rules in (6) give the center route and the pointwise route through (7). The default avoidance event consists of the table pairs whose center route takes no default child before depth : (8)✦
The Claim
Theorem 1. Let be natural numbers, let be arbitrary selector and terminal resolutions, and fix a real center . For , the outcome law (4) assigns to the event (8) the probability (9)✦ The event also has the pointwise routing description (10)✦ For any positive real , if the real power is less than , then the corresponding extended nonnegative power satisfies (11)✦
In the paper, the result reads: for every fixed real center , the probability that its route never chooses child is , with the previously chosen tree parameters and denoting its total number of children.
What Is Checked
The identities (9) and (10) are stated over arbitrary finite routers and resolution assignments, fixed real centers and the independent table laws with ; the numerical bound (11) is stated for any positive real satisfying the real inequality preceding (11).