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:
“Without being bound to the fulfillment of promises, we would never be able to keep our identities; we would be condemned to wander helplessly and without direction in the darkness of each man’s lonely heart, caught in its contradictions and equivocalities—a darkness which only the light shed over the public realm through the presence of others, who confirm the identity between the one who promises and the one who fulfills, can dispel.”
—Hannah Arendt (1906–1975)