The Setting
An indexed family of subsets can be sampled by adjoining one of its members to independent coordinate noise and then choosing a target from the observed union. The library defines this resampling experiment and the part of the target retained outside the noise.
Let and be finite sets, and let be a family of subsets of . A finite probability law on is a collection of real weights satisfying (1).✦ (1) A finite probability law on has full support if for every .✦ For a finite law on a finite set and an event , the event probability is the real number given by the sum in (2).✦ (2)
For a real parameter and a subset , the Bernoulli subset weight of is the real number given by the product in (3).✦ For , the product law on is the finite probability law that includes each coordinate independently with probability . (3)
For a real parameter , a subset and an index , the unnormalized target weight is the real number in (4), with the convention .✦ (4)
The Claim
Definition 1. For a noise set and a source index , the planted union is the subset of in (5).✦ (5) The normalizing density of a subset is the sum in (6).✦ (6) For a real parameter , a noise set and source and target indices , the posterior target weight is the real number in (7).✦ (7)✦ For a noise set , the source and target weight of a pair is the real number in (8).✦ (8)
Suppose that has full support and . The conditional resampling law on is the finite probability law with atom weights (9).✦ (9)✦ For , the joint resampling experiment is the finite probability law on with atom weights (10).✦ (10)
For every and , the retained target fragment is the subset of defined by (11).✦ (11)
Theorem 1. Let be a finite probability law on , let be real, and let . Every pair of positive source and target weight satisfies (12).✦ (12)✦ For every target index , recovery holds in the form (13).✦ (13)✦ If has full support and , then every subset has observed mass (14) in the joint resampling experiment.✦ (14)✦
What Is Checked
The joint experiment is stated over a family of subsets of a finite ground set, a full-support probability law on the finite index set, and . For a full-support law and , the source and target weights sum to one over all ordered pairs of indices, for every noise set .✦ (15)