In probability theory, the Chernoff bound, named after Herman Chernoff, 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 inequality, which only yield power-law bounds on tail decay. However, the Chernoff bound requires that the variates be independent - a condition that neither the Markov nor the Chebyshev inequalities require.
It is related to the (historically earliest) Bernstein inequalities, and to Hoeffding's inequality.
Read more about Chernoff Bound: Definition, A Motivating Example, The First Step in The Proof of Chernoff Bounds, Applications of Chernoff Bound, Matrix Chernoff Bound
Famous quotes containing the word bound:
“American families, however, without exception, experience a double message in our society, one that claims a commitment to families and stresses the importance of raising bright, stable, productive citizens, yet remains so bound by an ideal of “rugged individualism” that parents receive little support in their task from the public or private sectors.”
—Bernice Weissbourd (20th century)