Chernoff bound

The generic bound

The generic Chernoff bound for a random variable X is attained by applying Markov's inequality to e^tX. For every t > 0 :

Pr ( X ≥ a ) = Pr ( e t ⋅ X ≥ e t ⋅ a ) ≤ E [ e t ⋅ X ] e t ⋅ a .

When X is the sum of n random variables X₁, ..., X_n, we get for any t > 0,

Pr ( X ≥ a ) ≤ e − t a E [ ∏ i e t ⋅ X i ] .

In particular, optimizing over t and using the assumption that X_i are independent, we obtain,

Similarly,

Pr ( X ≤ a ) = Pr ( e − t X ≥ e − t a )

and so,

Pr ( X ≤ a ) ≤ min t > 0 e t a ∏ i E [ e − t ⋅ X i ]

Specific Chernoff bounds are attained by calculating E [ e − t ⋅ X i ] for specific instances of the basic variables X i .

Example

Let X₁, ..., X_n be independent Bernoulli random variables, whose sum is X, each having probability p > 1/2 of being equal to 1. For a Bernoulli variable:

E [ e t ⋅ X i ] = 1 + p ( e t − 1 ) ≤ e p ( e t − 1 )

So:

E [ e t ⋅ X ] ≤ e n ⋅ p ( e t − 1 )

For any δ > 0 , taking t = ln ⁡ ( 1 + δ ) > 0 and a = ( 1 + δ ) n p gives:

E [ e t ⋅ X ] ≤ e δ n p and e − t a = 1 ( 1 + δ ) ( 1 + δ ) n p

and the generic Chernoff bound gives:

Pr [ X ≥ ( 1 + δ ) n p ] ≤ e δ n p ( 1 + δ ) ( 1 + δ ) n p = [ e δ ( 1 + δ ) 1 + δ ] n p

The probability of simultaneous occurrence of more than n/2 of the events {X_k = 1} has an exact value:

Pr [ X > n 2 ] = ∑ i = ⌊ n 2 ⌋ + 1 n ( n i ) p i ( 1 − p ) n − i .

A lower bound on this probability can be calculated based on Chernoff's inequality:

Pr [ X > n 2 ] ≥ 1 − e − 1 2 p n ( p − 1 2 ) 2 .

Indeed, noticing that μ = np, we get by the multiplicative form of Chernoff bound (see below or Corollary 13.3 in Sinclair's class notes),

Pr ( X ≤ ⌊ n 2 ⌋ ) = Pr ( X ≤ ( 1 − ( 1 − 1 2 p ) ) μ ) ≤ e − μ 2 ( 1 − 1 2 p ) 2 = e − n 2 p ( p − 1 2 ) 2

This result admits various generalizations as outlined below. One can encounter many flavours 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).

Additive form (absolute error)

The following Theorem is due to Wassily Hoeffding and hence is called the Chernoff-Hoeffding theorem.

Chernoff-Hoeffding Theorem. Suppose X₁, ..., X_n are i.i.d. random variables, taking values in {0, 1}. Let p = E[X_i] and ε > 0. Then Pr ( 1 n ∑ X i ≥ p + ε ) ≤ ( ( p p + ε ) p + ε ( 1 − p 1 − p − ε ) 1 − p − ε ) n = e − D ( p + ε ∥ p ) n Pr ( 1 n ∑ X i ≤ p − ε ) ≤ ( ( p p − ε ) p − ε ( 1 − p 1 − p + ε ) 1 − p + ε ) n = e − D ( p − ε ∥ p ) n where is the Kullback–Leibler divergence between Bernoulli distributed random variables with parameters x and y respectively. If p ≥ 1/2, then Pr ( X > n p + x ) ≤ exp ⁡ ( − x 2 2 n p ( 1 − p ) ) .

A simpler bound follows by relaxing the theorem using D(p + ε || p) ≥ 2ε², which follows from the convexity of D(p + ε || p) and the fact that

d 2 d ε 2 D ( p + ε ∥ p ) = 1 ( p + ε ) ( 1 − p − ε ) ≥ 4 = d 2 d ε 2 ( 2 ε 2 ) .

This result is a special case of Hoeffding's inequality. Sometimes, the bound

D ( ( 1 + x ) p ∥ p ) ≥ 1 4 x 2 p , − 1 2 ≤ x ≤ 1 2 ,

which is stronger for p < 1/8, is also used.

Multiplicative form (relative error)

Multiplicative Chernoff Bound. Suppose X₁, ..., X_n 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, Pr ( X > ( 1 + δ ) μ ) < ( e δ ( 1 + δ ) ( 1 + δ ) ) μ .

A similar proof strategy can be used to show that

Pr ( X < ( 1 − δ ) μ ) < ( e − δ ( 1 − δ ) ( 1 − δ ) ) μ .

The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:

Pr ( X ≥ ( 1 + δ ) μ ) ≤ e − δ 2 μ 3 , 0 < δ < 1 , Pr ( X ≥ ( 1 + δ ) μ ) ≤ e − δ μ 3 , 1 < δ , Pr ( X ≤ ( 1 − δ ) μ ) ≤ e − δ 2 μ 2 , 0 < δ < 1.

Special cases

We can obtain stronger bounds using simpler proof techniques for some special cases of symmetric random variables.

Suppose X₁, ..., X_n are independent random variables, and let X denote their sum.

If Pr ( X i = 1 ) = Pr ( X i = − 1 ) = 1 2 . Then,

and therefore also

If Pr ( X i = 1 ) = Pr ( X i = 0 ) = 1 2 , E [ X ] = μ = n 2 Then,

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. Refer to this book section for more info on the problem.

Chernoff bounds are also used to obtain tight bounds for permutation routing problems which reduce network congestion while routing packets in sparse networks. Refer to this book section for a thorough treatment of the problem.

Chernoff bounds can be effectively used to evaluate the "robustness level" of an application/algorithm by exploring its perturbation space with randomization. The use of the Chernoff bound permits to abandon the strong -and mostly unrealistic- small perturbation hypothesis (the perturbation magnitude is small). The robustness level can be, in turn, used either to validate or reject a specific algorithmic choice, a hardware implementation or the appropriateness of a solution whose structural parameters are affected by uncertainties.

Matrix bound

Rudolf Ahlswede and Andreas Winter introduced a Chernoff bound for matrix-valued random variables.

If M is distributed according to some distribution over d × d matrices with zero mean, and if M₁, ..., M_t are independent copies of M then for any ε > 0,

Pr ( ∥ 1 t ∑ i = 1 t M i ∥ 2 > ε ) ≤ d exp ⁡ ( − C ε 2 t γ 2 ) .

where ∥ M ∥ 2 ≤ γ holds almost surely and C > 0 is an absolute constant.

Notice that the number of samples in the inequality depends logarithmically on d. In general, unfortunately, such a dependency is inevitable: take for example a diagonal random sign matrix of dimension d. The operator norm of the sum of t independent samples is precisely the maximum deviation among d independent random walks of length t. In order to achieve a fixed bound on the maximum deviation with constant probability, it is easy to see that t should grow logarithmically with d in this scenario.

The following theorem can be obtained by assuming M has low rank, in order to avoid the dependency on the dimensions.

Theorem without the dependency on the dimensions

Let 0 < ε < 1 and M be a random symmetric real matrix with ∥ E [ M ] ∥ 2 ≤ 1 and ∥ M ∥ 2 ≤ γ almost surely. Assume that each element on the support of M has at most rank r. Set

t = Ω ( γ log ⁡ ( γ / ε 2 ) ε 2 ) .

If r ≤ t holds almost surely, then

Pr ( ∥ 1 t ∑ i = 1 t M i − E [ M ] ∥ 2 > ε ) ≤ 1 p o l y ( t )

where M₁, ..., M_t are i.i.d. copies of M.

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 r_S.

Then, for every fraction d∈[0,1]:

P r ( r S < ( 1 − d ) ⋅ r ) < exp ⁡ ( − r ⋅ d 2 ⋅ k / 2 )

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 (r_S>0.5) by taking: d = 1 - 1 / (2 r):

P r ( r S > 0.5 ) > 1 − exp ⁡ ( − r ⋅ ( 1 − 1 2 r ) 2 ⋅ k / 2 )

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

Chernoff-Hoeffding Theorem (additive form)

Let q = p + ε. Taking a = nq in (1), we obtain:

Pr ( 1 n ∑ X i ≥ q ) ≤ inf t > 0 E [ ∏ e t X i ] e t n q = inf t > 0 ( E [ e t X i ] e t q ) n .

Now, knowing that Pr(X_i = 1) = p, Pr(X_i = 0) = 1 − p, we have

( E [ e t X i ] e t q ) n = ( p e t + ( 1 − p ) e t q ) n = ( p e ( 1 − q ) t + ( 1 − p ) e − q t ) n .

Therefore, we can easily compute the infimum, using calculus:

d d t ( p e ( 1 − q ) t + ( 1 − p ) e − q t ) = ( 1 − q ) p e ( 1 − q ) t − q ( 1 − p ) e − q t

Setting the equation to zero and solving, we have

( 1 − q ) p e ( 1 − q ) t = q ( 1 − p ) e − q t ( 1 − q ) p e t = q ( 1 − p )

so that

e t = ( 1 − p ) q ( 1 − q ) p .

Thus,

t = log ⁡ ( ( 1 − p ) q ( 1 − q ) p ) .

As q = p + ε > p, we see that t > 0, so our bound is satisfied on t. Having solved for t, we can plug back into the equations above to find that

log ⁡ ( p e ( 1 − q ) t + ( 1 − p ) e − q t ) = log ⁡ ( e − q t ( 1 − p + p e t ) ) = log ⁡ ( e − q log ⁡ ( ( 1 − p ) q ( 1 − q ) p ) ) + log ⁡ ( 1 − p + p e log ⁡ ( 1 − p 1 − q ) e log ⁡ q p ) = − q log ⁡ 1 − p 1 − q − q log ⁡ q p + log ⁡ ( 1 − p + p ( 1 − p 1 − q ) q p ) = − q log ⁡ 1 − p 1 − q − q log ⁡ q p + log ⁡ ( ( 1 − p ) ( 1 − q ) 1 − q + ( 1 − p ) q 1 − q ) = − q log ⁡ q p + ( − q log ⁡ 1 − p 1 − q + log ⁡ 1 − p 1 − q ) = − q log ⁡ q p + ( 1 − q ) log ⁡ 1 − p 1 − q = − D ( q ∥ p ) .

We now have our desired result, that

Pr ( 1 n ∑ X i ≥ p + ε ) ≤ e − D ( p + ε ∥ p ) n .

To complete the proof for the symmetric case, we simply define the random variable Y_i = 1 − X_i, apply the same proof, and plug it into our bound.

Multiplicative form

Set Pr(X_i = 1) = p_i. According to (1),

Pr ( X > ( 1 + δ ) μ ) ≤ inf t > 0 E [ ∏ i = 1 n exp ⁡ ( t X i ) ] exp ⁡ ( t ( 1 + δ ) μ ) = inf t > 0 ∏ i = 1 n E [ e t X i ] exp ⁡ ( t ( 1 + δ ) μ ) = inf t > 0 ∏ i = 1 n [ p i e t + ( 1 − p i ) ] exp ⁡ ( t ( 1 + δ ) μ )

The third line above follows because e t X i takes the value e^t with probability p_i and the value 1 with probability 1 − p_i. This is identical to the calculation above in the proof of the Theorem for additive form (absolute error).

Rewriting p i e t + ( 1 − p i ) as p i ( e t − 1 ) + 1 and recalling that 1 + x ≤ e x (with strict inequality if x > 0), we set x = p i ( e t − 1 ) . The same result can be obtained by directly replacing a in the equation for the Chernoff bound with (1 + δ)μ.

Thus,

Pr ( X > ( 1 + δ ) μ ) < ∏ i = 1 n exp ⁡ ( p i ( e t − 1 ) ) exp ⁡ ( t ( 1 + δ ) μ ) = exp ⁡ ( ( e t − 1 ) ∑ i = 1 n p i ) exp ⁡ ( t ( 1 + δ ) μ ) = exp ⁡ ( ( e t − 1 ) μ ) exp ⁡ ( t ( 1 + δ ) μ ) .

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

exp ⁡ ( ( e t − 1 ) μ ) exp ⁡ ( t ( 1 + δ ) μ ) = exp ⁡ ( ( 1 + δ − 1 ) μ ) ( 1 + δ ) ( 1 + δ ) μ = [ e δ ( 1 + δ ) ( 1 + δ ) ] μ

This proves the result desired.

Additional reading

Chernoff, H. (1952). "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations". Annals of Mathematical Statistics. 23 (4): 493–507. doi:10.1214/aoms/1177729330. JSTOR 2236576. MR 57518. Zbl 0048.11804. 

Chernoff, H. (1981). "A Note on an Inequality Involving the Normal Distribution". Annals of Probability. 9 (3): 533. doi:10.1214/aop/1176994428. JSTOR 2243541. MR 614640. Zbl 0457.60014. 

Hagerup, T. (1990). "A guided tour of Chernoff bounds". Information Processing Letters. 33 (6): 305. doi:10.1016/0020-0190(90)90214-I. 

Nielsen, F. (2011). "Chernoff information of exponential families". arXiv:1102.2684 [cs.IT].