The Setting
A planted set can be resampled through its posterior label while retaining only the coordinates absent from a random background. Local failure concerns the normalizing density of this posterior law and the size of the retained fragment.
A finite probability law on a finite set is a family of nonnegative weights whose sum is one.✦ A finite probability law on has full support when every weight , for , is strictly positive.✦ For a finite probability law on , the expectation of a real function on and the probability of an event are the weighted sums in (1). (1)
Let be a finite ground set, a finite label set, an indexed family of subsets of , and a finite probability law on with weights . For a real parameter , a finite probability law on is -spread for an indexed family of subsets of when every nonempty satisfies (2). (2)✦
For a subset of and a real parameter , the Bernoulli subset weight is the real number given by the product in (3). For , these weights form the law of independent coordinate inclusion with probability ; the Bernoulli expectation of a real function on subsets of is its expectation with these weights. (3)
For a background , source and target , the planted union and retained fragment are the sets in (4). (4) For a label and a set , the unnormalized target weight and normalizing density are the real numbers in (5), with the reciprocal at zero taken to be zero. (5) For a background and labels , the posterior target weight and source and target weight are the real numbers in (6); a zero denominator gives posterior weight zero. (6)
When has full support and , the resampling transition law is the finite probability law on with masses .✦ For with full support and , the joint resampling law on triples is defined by (7). (7)✦
For a nonnegative integer , local success is the condition in (8). For a nonnegative integer , a background and labels , local failure is the condition that local success does not hold.✦ (8)✦
A function on subsets of depends only on coordinates outside when, for all subsets , whenever .✦ For a real cutoff , the density cutoff target mass is the sum in (9) over sources whose planted union has density at least . (9)✦
The Claim
Theorem 1. For every real , nonnegative integer , background and labels , local failure has the real threshold description (10). (10)✦
Suppose has full support, , is a positive integer, for every , and is -spread with and . Then the joint law satisfies (11) and (12). (11)✦ (12)✦
Let , , and let be -spread with . Fix and a nonnegative integer with . For every nonnegative real function depending only on coordinates outside , the cutoff estimate (13) holds. (13)✦ When has full support, the transition law also satisfies (14), where denotes its sampled target. (14)✦
In the paper, the result reads: for an -spread indexed law with for every label, a positive integer , and , draw independently of the source and then take the specified posterior target , declare local failure when or , with , and obtain together with for every fixed target and every nonnegative real depending only on .
What Is Checked
The failure bounds are stated over the joint resampling law for a finite label law with full support and a finite indexed family under the spread, size and parameter hypotheses of (11); the size hypothesis in (13) concerns only its fixed target, and its parameter range includes and .
For every with full support, positive and background , the source and target weights satisfy the normalization identity (15). (15)✦