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:
“Nature in darkness groans
And men are bound to sullen contemplation in the night:
Restless they turn on beds of sorrow; in their inmost brain
Feeling the crushing wheels, they rise, they write the bitter words
Of stern philosophy & knead the bread of knowledge with tears & groans.”
—William Blake (1757–1827)