The Ultimate Chernoff bound - American History Information Guide and Reference

In probability theory, the Chernoff bound, named after Herman Chernoff, gives a lower bound for the success of majority agreement for n independent, equally likely events. More precisely let E₁, ..., E_n be independent events each having probability p > 1 /2. Then the probability of simultaneous occurrence of more than n/2 of the events E_k exceeds

$1 - \exp(-2 (p - 1/2)^2 n) \!\,$ .

The Chernoff bound is used in probabilistic algorithms (or in computational devices such as quantum computers) to determine a bound on the number of runs necessary to determine a value by majority agreement, up to a specified probability. Thus suppose an algorithm (or machine) A computes the correct value of a function f with probability at least p > 1/2. Then to compute f correctly with probability at least 1 − ε, it suffices to take n runs of the machine, provided

$n \geq \frac{1}{(p -1/2)^2} \ln \frac{1}{\sqrt{\epsilon}}$ .

In this case the probability that a majority exists and is equal to the correct value is at least 1 − ε.

The Chernoff bound is a special case of Chernoff's inequality.

Your American History Reference Guide! - Chernoff bound

Chernoff bound

Your American History Reference Guide!
- Chernoff bound