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:
“When I received this [coronation] ring I solemnly bound myself in marriage to the realm; and it will be quite sufficient for the memorial of my name and for my glory, if, when I die, an inscription be engraved on a marble tomb, saying, “Here lieth Elizabeth, which reigned a virgin, and died a virgin.””
—Elizabeth I (1533–1603)