切尔诺夫约束

The bound is commonly named after Herman Chernoff who described the method in a 1952 paper, though Chernoff himself attributed it to Herman Rubin. In 1938 Harald Cramér had published an almost identical concept now known as Cramér's theorem.

It is a sharper bound than the first- or second-moment-based tail bounds such as Markov's inequality or Chebyshev's inequality, which only yield power-law bounds on tail decay. However, when applied to sums the Chernoff bound requires the random variables to be independent, a condition that is not required by either Markov's inequality or Chebyshev's inequality.

The Chernoff bound is related to the Bernstein inequalities. It is also used to prove Hoeffding's inequality, Bennett's inequality, and McDiarmid's inequality.

Generic Chernoff bounds

The generic Chernoff bound for a random variable X is attained by applying Markov's inequality to e^(tX) (which is why it is sometimes called the exponential Markov or exponential moments bound). For positive t this gives a bound on the right tail of X in terms of its moment-generating function M(t)=E (e^(tX)): P (X≥ a)=P (e^(tX)≥ e^(ta))≤ M(t)e^(-ta) (t>0)

Since this bound holds for every positive t, we may take the infimum: （公式略）

Performing the same analysis with negative t we get a similar bound on the left tail: P (X≤ a)=P (e^(tX)≥ e^(ta))≤ M(t)e^(-ta) (t<0)

and （公式略）

The quantity M(t)e^(-ta) can be expressed as the expected value E (e^(tX))e^(-ta), or equivalently E (e^(t(X-a))).

Sums of independent random variables

When X is the sum of n independent random variables X1,..., Xn, the moment generating function of X is the product of the individual moment generating functions, giving that:

and: （公式略）

Specific Chernoff bounds are attained by calculating the moment-generating function E [e⁻t· Xᵢ] for specific instances of the random variables Xᵢ.

When the random variables are also identically distributed (iid), the Chernoff bound for the sum reduces to a simple rescaling of the single-variable Chernoff bound. That is, the Chernoff bound for the average of n iid variables is equivalent to the nth power of the Chernoff bound on a single variable (see Cramér's theorem).

Sums of independent bounded random variables

Chernoff bounds may also be applied to general sums of independent, bounded random variables, regardless of their distribution; this is known as Hoeffding's inequality. The proof follows a similar approach to the other Chernoff bounds, but applying Hoeffding's lemma to bound the moment generating functions (see Hoeffding's inequality).

Hoeffding's inequality. Suppose X1,..., Xn are independent random variables taking values in [a,b]. Let X denote their sum and let μ = E[X] denote the sum's expected value. Then for any t>0, （公式略）

（公式略）

Sums of independent Bernoulli random variables

The bounds in the following sections for Bernoulli random variables are derived by using that, for a Bernoulli random variable Xᵢ with probability p of being equal to 1, E [e^(t)· Xᵢ]=(1-p)e⁰+pe^(t)=1+p(e^(t)-1)≤ e^(p)(e^(t)-1).

One can encounter many flavors of Chernoff bounds: the original additive form (which gives a bound on the absolute error) or the more practical multiplicative form (which bounds the error relative to the mean).

Multiplicative form (relative error)

Multiplicative Chernoff bound. Suppose X1,..., Xn are independent random variables taking values in {0, 1}. Let X denote their sum and let μ = E[X] denote the sum's expected value. Then for any δ > 0, （公式略）

A similar proof strategy can be used to show that for 0 < δ < 1 （公式略）

Applications

Chernoff bounds have very useful applications in set balancing and packet routing in sparse networks.

The set balancing problem arises while designing statistical experiments. Typically while designing a statistical experiment, given the features of each participant in the experiment, we need to know how to divide the participants into 2 disjoint groups such that each feature is roughly as balanced as possible between the two groups.

Chernoff bounds are also used to obtain tight bounds for permutation routing problems which reduce network congestion while routing packets in sparse networks.

Chernoff bounds are used in computational learning theory to prove that a learning algorithm is probably approximately correct, i.e.

Matrix Chernoff bound

Rudolf Ahlswede and Andreas Winter introduced a Chernoff bound for matrix-valued random variables. The following version of the inequality can be found in the work of Tropp.

Let M1,..., Mt be independent matrix valued random variables such that Mᵢ∈ C ^(d)₁× d₂ and E [Mᵢ]=0.

Let us denote by （公式略） the operator norm of the matrix M. If （公式略） holds almost surely for all （公式略）, then for every ε > 0 （公式略）

Notice that in order to conclude that the deviation from 0 is bounded by ε with high probability, we need to choose a number of samples t proportional to the logarithm of d₁+d₂. In general, unfortunately, a dependence on log(min(d₁,d₂)) is inevitable: take for example a diagonal random sign matrix of dimension d× d.

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.

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

Suppose we pick an integer k and a random sample S ⊂ A of size k. Mark the relative size of the sub-population in the sample (|B∩S|/|S|) by rS.

Then, for every fraction d ∈ [0,1]: （公式略）

In particular, if B is a majority in A (i.e. r > 0.5) we can bound the probability that B will remain majority in S(rS > 0.5) by taking: d = 1 − 1/(2r): （公式略）

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

Proofs

Multiplicative form

Following the conditions of the multiplicative Chernoff bound, let X1,..., Xn be independent Bernoulli random variables, whose sum is X, each having probability pi of being equal to 1. For a Bernoulli variable: E [e^(t)· Xᵢ]=(1-pᵢ)e⁰+pᵢe^(t)=1+pᵢ(e^(t)-1)≤ e^(p)ᵢ(e^(t)-1)

So, using (1) with a=(1+δ)μ for any δ >0 and where μ =E [X]= ∑ ᵢ₌₁ⁿpᵢ, （公式略）

If we simply set t = log(1 + δ) so that t > 0 for δ > 0, we can substitute and find （公式略）

This proves the result desired.

Chernoff–Hoeffding theorem (additive form)

Let q = p + ε. Taking a = nq in (1), we obtain: （公式略）

Now, knowing that Pr(Xi = 1) = p, Pr(Xi = 0) = 1 − p, we have （公式略）

Therefore, we can easily compute the infimum, using calculus: d/dt(pe^((1-q)t)+(1-p)e^(-qt))=(1-q)pe^((1-q)t)-q(1-p)e^(-qt)

Setting the equation to zero and solving, we have （公式略）