The Setting
For a tree with set labels on its arcs, sampling a set asks how much of each path’s label union can be removed while retaining control of the outgoing label distributions.
A finite probability law on a finite set is a family of real weights satisfying (1). (1)✦ A finite probability law on has full support if for every .✦
A probability tree on a ground set , with levels, is a rooted tree whose leaves all have depth , whose outgoing arcs at each internal node have a finite index set with a full support probability law , and whose arc labels are finite subsets of .✦ A tree with zero levels is a single leaf. A full path of is a complete history of branch choices from the root to a leaf; the leaf has one empty history.✦ The path label union of a full path of is the set in (2). (2)✦
Level capacities for are upper bounds on the sizes of its arc labels, as in (3). (3)✦ Levels are numbered here; the library’s declarations number them from zero. The tree is disjoint if the arc labels on each full path are pairwise disjoint.✦ A sequence of real numbers is a sequence of level spread parameters for the probability tree on if, at every node at level , the probability that its outgoing label contains any prescribed subset of is at most raised to the cardinality of that subset.✦
For a finite ground set and real , the Bernoulli subset weight of is given by (4). (4)✦ For , the Bernoulli law includes each element of independently with probability ; its event probabilities are given by (5). (5)✦
Good Samples and Reduction
Fix , a sequence and a finite set . At a node at level , write for the mass of successful target assignments to branch determined by its outgoing law, label family and parameters . A subtree starting at level is good for these parameters if it is a leaf, or if its children satisfy the condition in (6); write for this property. (6)✦
For , positive integer parameters and a sample such that holds, the reduced tree is the tree obtained recursively by retaining branches with good children and positive successful target mass, using the law and labels in (7), and reducing their children; a leaf remains a leaf. (7)✦
The Claim
Theorem 1 (Lemma 3.2). Let be a probability tree on with levels, let , and let be positive integers. For every finite such that holds, put . Then (8) holds. (8)✦ If is disjoint, then (9) holds. (9)✦ If for every level and has level spread parameters , then (10) holds. (10)✦ Path recovery is expressed by (11). (11)✦
Suppose further that is finite, , and is disjoint with level capacities and nonnegative level spread parameters . Assume at each level and at every pair of successive levels. The probability bounds are (12) and (13). (12)✦ (13)✦
In the paper, the result reads: for a disjoint probability tree with levels, positive integer capacities satisfying , and level spread parameters with , a deterministic procedure given succeeds with probability at least and returns a disjoint tree with the same levels, level capacities and level spread parameters , such that every full path of recovers a full path of satisfying .
What Is Checked
The probability assertions concern independent subsets of a finite ground set and disjoint probability trees satisfying the stated capacity, spread and growth hypotheses, while the deterministic assertions concern the recursive reduction of a good tree with positive integer parameters and .