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

<math> 1 - \exp(-2 (p - 1/2)^2 n) \!\,<math>.

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

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

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.