The Setting
Let be a finite ground set. A rooted tree whose arcs are labelled by subsets of gives a family of sets, one for each full path. A random subset covers a path when it contains every label along that path.
A finite probability law on a finite set is a family of real weights satisfying (1); it has full support if for every .✦ (1)✦ A probability tree of depth over is a finite rooted tree with all leaves at depth , in which each internal vertex has a finite set of outgoing branches, a probability law of full support on , and a label on each outgoing arc.✦ A probability tree of depth zero consists of a single leaf.✦
A full path in starts at the root and chooses one outgoing branch at each internal vertex until it reaches a leaf.✦ The label union of a full path in a probability tree over is the subset of defined by (2), where are the successive arc labels and the empty union equals . (2) The path covering event is the family of subsets of in (3). (3)✦
For , let be the probability law on subsets of under which coordinates are included independently with probability . Its mass at a subset and its probability of an event are given by (4). (4)
Disjointness, Capacities and Spread
A probability tree is disjoint if the arc labels on every full path are pairwise disjoint.✦ Level capacities for are nonnegative integers such that every arc label at level has cardinality at most .✦ Levels are numbered from one here, while the declarations index them from zero.
For , an indexed family of labels with probability law is -spread if it satisfies (5). Level spread parameters for a probability tree of depth are numbers such that the outgoing labels at each vertex of depth , with that vertex’s probability law, are -spread.✦ (5) A probability tree is -spread when all its level spread parameters equal . Write for the base-two logarithm.
The Claim
Theorem 1. Let be a disjoint probability tree of positive depth over a finite ground set . Suppose that is -spread for some , and that it has positive integer level capacities satisfying for . Then (6)✦
What Is Checked
The estimate (6) is stated over finite ground sets and probability trees of positive depth, with full support at every internal vertex, disjoint path labels, a common positive spread parameter, and positive level capacities growing by a factor of at least sixteen.