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:
“People named John and Mary never divorce. For better or for worse, in madness and in saneness, they seem bound together for eternity by their rudimentary nomenclature. They may loathe and despise one another, quarrel, weep, and commit mayhem, but they are not free to divorce. Tom, Dick, and Harry can go to Reno on a whim, but nothing short of death can separate John and Mary.”
—John Cheever (1912–1982)