Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Chernoff bound

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.

<Hide>

Topics: Chernoff Bound, Chernoff's Inequality...

Chernoff's inequalityIn probability theory, Chernoff's inequality named after Herman Chernoff, states the following. Let : be independent random variables, such that : and : for all i''. Let : and let be the variance of. Then : for any : where σ is the standard deviatio

Chernoff boundIn 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 be independent events each having probability p > 1 /2.

Non User