Chernoff bound

In probability theory, the Chernoff bound, named after Herman Chernoff but due to Herman Rubin,[1] gives exponentially decreasing bounds on tail distributions of sums of independent random variables. It is a sharper bound than the known 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, the Chernoff bound requires that the variates be independent – a condition that neither Markov's inequality nor Chebyshev's inequality require, although Chebyshev's inequality does require the variates to be pairwise independent.

It is related to the (historically prior) Bernstein inequalities and to Hoeffding's inequality.

The generic bound

The generic Chernoff bound for a random variable X is attained by applying Markov's inequality to etX.[2] For every :

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

In particular, optimizing over t and assuming that Xi are independent, we obtain,

 

 

 

 

(1)

Similarly,

and so,

Specific Chernoff bounds are attained by calculating for specific instances of the basic variables .

Example

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

So:

For any , taking and gives:

and

and the generic Chernoff bound gives:

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

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

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

This result admits various generalizations as outlined below. 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).

Additive form (absolute error)

The following Theorem is due to Wassily Hoeffding[4] and hence is called the Chernoff–Hoeffding theorem.

Chernoff–Hoeffding theorem. Suppose X1, ..., Xn are i.i.d. random variables, taking values in {0, 1}. Let p = E[X]/n and ε > 0.
where
is the Kullback–Leibler divergence between Bernoulli distributed random variables with parameters x and y respectively. If p1/2, then which means

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

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

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

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

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

which follow from the inequality from the list of logarithmic inequalities. Or looser still:

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.[6]

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

Chernoff bounds are used in computational learning theory to prove that a learning algorithm is probably approximately correct, i.e. with high probability the algorithm has small error on a sufficiently large training data set.[7]

Chernoff bounds can be effectively used to evaluate the "robustness level" of an application/algorithm by exploring its perturbation space with randomization.[8] The use of the Chernoff bound permits one 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.[9] The following version of the inequality can be found in the work of Tropp.[10]

Let M1, ..., Mt be independent matrix valued random variables such that and . Let us denote by the operator norm of the matrix . 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 proportional to the logarithm of . In general, unfortunately, a dependence on is inevitable: take for example a diagonal random sign matrix of dimension . 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.[11]

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 and almost surely. Assume that each element on the support of M has at most rank r. Set

If holds almost surely, then

where M1, ..., Mt are i.i.d. copies of M.

Theorem with matrices that are not completely random

Garg, Lee, Song and Srivastava [12] proved a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to Wigderson and Xiao.

Kyng and Song [13] proved a Chernoff-type bound for sums of Laplacian matrix of random spanning trees.

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.[14]

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

Suppose we pick an integer k and a random sample SA of size k. Mark the relative size of the sub-population in the sample (|BS|/|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 / (2 r):[15]

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

Proofs

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:

Setting the equation to zero and solving, we have

so that

Thus,

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

We now have our desired result, that

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

Multiplicative form

Set Pr(Xi = 1) = pi. According to (1),

The third line above follows because takes the value et with probability pi and the value 1 with probability 1 − pi. This is identical to the calculation above in the proof of the Theorem for additive form (absolute error).

Rewriting as and recalling that (with strict inequality if x > 0), we set . The same result can be obtained by directly replacing a in the equation for the Chernoff bound with (1 + δ)μ.[16]

Thus,

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

This proves the result desired.

See also

References

  1. Chernoff, Herman (2014). "A career in statistics" (PDF). In Lin, Xihong; Genest, Christian; Banks, David L.; Molenberghs, Geert; Scott, David W.; Wang, Jane-Ling (eds.). Past, Present, and Future of Statistics. CRC Press. p. 35. ISBN 9781482204964.
  2. This method was first applied by Sergei Bernstein to prove the related Bernstein inequalities.
  3. Sinclair, Alistair (Fall 2011). "Class notes for the course "Randomness and Computation"" (PDF). Archived from the original (PDF) on 31 October 2014. Retrieved 30 October 2014.
  4. Hoeffding, W. (1963). "Probability Inequalities for Sums of Bounded Random Variables" (PDF). Journal of the American Statistical Association. 58 (301): 13–30. doi:10.2307/2282952. JSTOR 2282952.
  5. Mitzenmacher, Michael; Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 978-0-521-83540-4.
  6. Refer to this book section for more info on the problem.
  7. Kearns, M.; Vazirani, U. (1994). An Introduction to Computational Learning Theory. MIT Press. Chapter 9 (Appendix), pages 190–192. ISBN 0-262-11193-4.
  8. Alippi, C. (2014). "Randomized Algorithms". Intelligence for Embedded Systems. Springer. ISBN 978-3-319-05278-6.
  9. Ahlswede, R.; Winter, A. (2003). "Strong Converse for Identification via Quantum Channels". IEEE Transactions on Information Theory. 48 (3): 569–579. arXiv:quant-ph/0012127. doi:10.1109/18.985947.
  10. Tropp, J. (2010). "User-friendly tail bounds for sums of random matrices". Foundations of Computational Mathematics. 12 (4): 389–434. arXiv:1004.4389. doi:10.1007/s10208-011-9099-z.
  11. Magen, A.; Zouzias, A. (2011). "Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication". arXiv:1005.2724 [cs.DM].
  12. Garg, Ankit; Lee, Yin Tat; Song, Zhao; Srivastava, Nikhil (2018). A Matrix Expander Chernoff Bound. STOC '18 Proceedings of the fifty annual ACM symposium on Theory of Computing. arXiv:1704.03864.
  13. Kyng, Rasmus; Song, Zhao (2018). A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. FOCS '18 IEEE Symposium on Foundations of Computer Science. arXiv:1810.08345.
  14. Goldberg, A. V.; Hartline, J. D. (2001). "Competitive Auctions for Multiple Digital Goods". Algorithms — ESA 2001. Lecture Notes in Computer Science. 2161. p. 416. CiteSeerX 10.1.1.8.5115. doi:10.1007/3-540-44676-1_35. ISBN 978-3-540-42493-2.; lemma 6.1
  15. See graphs of: the bound as a function of r when k changes and the bound as a function of k when r changes.
  16. Refer to the proof above

Further reading

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.