The Setting
A fixed occupied set determines which local resampling choices succeed at each node of a probability tree. The associated potential assigns a real value to every subtree.
Let be a ground set, and let be finite. A finite probability law on a finite set consists of weights with ✦; it has full support if every is positive.✦ A probability tree on is either a leaf, of depth zero, or a node with a finite branch set , a full-support law , finite arc labels , and children of a common depth.✦
A probability tree on has disjoint path labels if the arc labels on every full path of are pairwise disjoint.✦ Level capacities for a probability tree on form a sequence such that every arc label leaving level has cardinality at most , where the root is at level one.✦ A probability tree on satisfies the level spread condition with parameters if, at every node of level , the total weight of labels containing any fixed finite subset of is at most raised to the cardinality of that subset.✦ The declarations index these levels from zero.
Local Masses and Potentials
Fix a node with branch law and labels , and a real parameter . For a source , the planted union is .✦ At a node with branch set , law and labels , the unnormalized target weight for a branch and the normalizing density are the real numbers in (1); quotients with zero denominator are set to zero. (1) The conditional target weight and the source and target weight are the weights in (2). (2)
For an integer capacity , local success means the condition in (3), with retained fragment ; local failure is its complement.✦ (3)✦ For a real parameter , use the outgoing law and labels at a node of level with and . The local failure mass at a node for an occupied set is the sum of source and target weights over local failures in (4). (4)✦ The successful target mass at a node for a target branch and an occupied set is the sum of source and target weights over local successes with target in (5). (5)✦
For a node of a probability tree on , the fixed-input tree potential is the real-valued function on finite occupied sets defined recursively by (6), where also denotes the corresponding child. (6)✦ For the capacity sequence with entries , a leaf is good for . A branching node at level of a probability tree is good for if it satisfies (7); a node of the tree is bad for these parameters if it is not good. (7)✦
A function on finite subsets of depends only on coordinates outside a finite set if whenever .✦
The potential envelope for remaining levels, starting at level , is the number defined by (8). (8)✦
For finite , the Bernoulli subset weight and Bernoulli expectation are given by (9). For , includes coordinates independently with probability , and is expectation under . (9)
The Claim
Theorem 1. Let , let be a sequence of nonnegative integer capacities, and let be finite. A bad probability tree with root satisfies (10). (10)✦ Let the parameter be real and let the capacities be any sequence. At a branching node of a probability tree with disjoint path labels, each child potential depends only on coordinates outside its incoming label, as stated in (11) for every branch and finite . (11)✦ Suppose now that is finite, , and has depth , disjoint path labels, level capacities , and level spread parameters . If , , and for every , its root potential satisfies (12). (12)✦
In the paper, the result reads: with outgoing capacity , local failure mass and local non-failure mass with target , leaves have and branching nodes have , bad nodes have , disjointness makes depend only on outside , and , with geometric capacity growth giving .
What Is Checked
The bad-tree assertion is stated over finite subsets of an arbitrary ground set and a positive parameter; locality is stated over disjoint probability trees for any real parameter; the expectation bound is stated over a finite ground set with the level capacity and spread hypotheses in the theorem.