The Setting
Successive choices of finite subsets of a ground set may depend on earlier choices. A probability tree describes such choices with a prescribed number of steps.
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 .✦
The Claim
Definition 1. A probability tree of depth over is a rooted tree whose leaves all have distance from its root .✦ At each internal vertex , the outgoing arcs are indexed by a finite set , have finite labels , and are assigned a probability law with full support. A tree of depth zero consists of a single leaf.
A full path of a probability tree is a choice of an outgoing arc at each successive vertex until a leaf is reached. Writing for the child subtree reached by root arc , the set of full paths has the recursive description (2); denotes the empty path. (2)✦ The path labels of form the ordered list , where is the label of its th arc.✦ The path union is the finite subset of defined in (3), with the empty union equal to . (3)✦
For a probability tree rooted at , let be the set of vertices of at distance from . Arc levels are numbered here; the declarations number these levels from zero. For a sequence of nonnegative integers, level capacities for are upper bounds on label cardinalities as specified in (4). (4)✦ Spread is a condition on the probabilities that an outgoing label contains a prescribed finite subset of . For a sequence of real numbers, level spread for requires this condition with parameter at every vertex at distance from the root, as specified in (5). (5)✦
A finite set covers when the condition in (6) holds. (6)✦
A probability tree is recursively disjoint if every root arc label is disjoint from the union of all labels in its chosen child subtree, and each child subtree is recursively disjoint.✦ A leaf is recursively disjoint.
Theorem 1. Let be a probability tree of depth . Recursive disjointness and the criterion of path disjointness are related by (7). (7)✦
What Is Checked
The definitions and the disjointness equivalence concern trees of a common finite depth, with finite subset labels over an arbitrary set and laws with full support on finite sets of outgoing arcs.