Chernoff bound

In probability theory, a Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its moment generating function. The minimum of all such exponential bounds forms the Chernoff or Chernoff-Cramér bound, which may decay faster than exponential (e.g. sub-Gaussian).[1][2] It is especially useful for sums of independent random variables, such as sums of Bernoulli random variables.[3][4]

The bound is commonly named after Herman Chernoff who described the method in a 1952 paper,[5] though Chernoff himself attributed it to Herman Rubin.[6] 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.

  1. ^ Boucheron, Stéphane (2013). Concentration Inequalities: a Nonasymptotic Theory of Independence. Gábor Lugosi, Pascal Massart. Oxford: Oxford University Press. p. 21. ISBN 978-0-19-953525-5. OCLC 837517674.
  2. ^ Wainwright, M. (January 22, 2015). "Basic tail and concentration bounds" (PDF). Archived (PDF) from the original on 2016-05-08.
  3. ^ Vershynin, Roman (2018). High-dimensional probability : an introduction with applications in data science. Cambridge, United Kingdom. p. 19. ISBN 978-1-108-41519-4. OCLC 1029247498.{{cite book}}: CS1 maint: location missing publisher (link)
  4. ^ Tropp, Joel A. (2015-05-26). "An Introduction to Matrix Concentration Inequalities". Foundations and Trends in Machine Learning. 8 (1–2): 60. arXiv:1501.01571. doi:10.1561/2200000048. ISSN 1935-8237. S2CID 5679583.
  5. ^ Chernoff, Herman (1952). "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations". The Annals of Mathematical Statistics. 23 (4): 493–507. doi:10.1214/aoms/1177729330. ISSN 0003-4851. JSTOR 2236576.
  6. ^ 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. Archived from the original (PDF) on 2015-02-11.