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:
“Successful socialism depends on the perfectibility of man. Unless all, or nearly all, men are high-minded and clear-sighted, it is bound to be a rotten failure in any but a physical sense. Even through it is altruism, socialism means materialism. You can guarantee the things of the body to every one, but you cannot guarantee the things of the spirit to every one; you can guarantee only that the opportunity to seek them shall not be denied to any one who chooses to seek them.”
—Katharine Fullerton Gerould (1879–1944)