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

.

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

.

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.