The Setting
Keep each vertex of a graph independently with probability , and fix a set of vertices. The number of kept vertices in is binomial with parameters and , so its mean is , and an argument by random sampling needs that number to stay above half its mean and below twice it. The question is how unlikely a departure from that range is, as a function of the mean alone. Splitting the edges of at random and counting the edges of a fixed set that land on one side raises the same question.
The library states the Chernoff bounds for such a count twice, with the same hypotheses and the same conclusions: once for random vertex sampling and once for random edge splitting, each time as a lower tail bound and an upper tail bound.
The Claim
Theorem 1. Let be independent random variables, each taking only the values and and each of mean , where . Let be a finite subset of , and put and . In the version for vertex sampling, (1)✦ and (2)✦ in the version for edge splitting, likewise (3)✦ and (4)✦
In the paper, the result reads: if is binomial with mean , then and .
What Is Checked
The four bounds are stated over a family of independent random variables, each with values in and mean , a finite set of its indices, and the sum of the variables indexed by , whose mean is .