Editing Chernoff bound (section)

==Sampling variant==

The following variant of Chernoff's bound can be used to bound the probability that a majority in a population will become a minority in a sample, or vice versa.<ref>{{Cite book | doi = 10.1007/3-540-44676-1_35| chapter = Competitive Auctions for Multiple Digital Goods| title = Algorithms — ESA 2001| volume = 2161| pages = 416| series = Lecture Notes in Computer Science| year = 2001| last1 = Goldberg | first1 = A. V. | last2 = Hartline | first2 = J. D. | isbn = 978-3-540-42493-2| citeseerx = 10.1.1.8.5115}}; lemma 6.1</ref>

Suppose there is a general population ''A'' and a sub-population ''B''&nbsp;⊆&nbsp;''A''. Mark the relative size of the sub-population (|''B''|/|''A''|) by&nbsp;''r''.

Suppose we pick an integer ''k'' and a random sample ''S''&nbsp;⊂&nbsp;''A'' of size ''k''. Mark the relative size of the sub-population in the sample (|''B''∩''S''|/|''S''|) by ''r<sub>S</sub>''.

Then, for every fraction ''d''&nbsp;∈&nbsp;[0,1]:

:<math>\Pr\left(r_S < (1-d)\cdot r\right) < \exp\left(-r\cdot d^2 \cdot \frac k 2\right)</math>

In particular, if ''B'' is a majority in ''A'' (i.e. ''r''&nbsp;>&nbsp;0.5) we can bound the probability that ''B'' will remain majority in ''S''(''r<sub>S</sub>''&nbsp;>&nbsp;0.5) by taking: ''d''&nbsp;=&nbsp;1&nbsp;−&nbsp;1/(2''r''):<ref>See graphs of: [https://www.desmos.com/calculator/eqvyjug0re the bound as a function of ''r'' when ''k'' changes] and [https://www.desmos.com/calculator/nxurzg7bqj the bound as a function of ''k'' when ''r'' changes].</ref>

:<math>\Pr\left(r_S > 0.5\right) > 1 - \exp\left(-r\cdot \left(1 - \frac{1}{2 r}\right)^2 \cdot \frac k 2 \right)</math>

This bound is of course not tight at all. For example, when ''r''&nbsp;=&nbsp;0.5 we get a trivial bound Prob&nbsp;>&nbsp;0.