The First Step in The Proof of Chernoff Bounds
The Chernoff bound for a random variable X, which is the sum of n independent random variables, is obtained by applying etX for some well-chosen value of t. This method was first applied by Sergei Bernstein to prove the related Bernstein inequalities.
From Markov's inequality and using independence we can derive the following useful inequality:
For any t > 0,
In particular optimizing over t and using independence we obtain,
-
(1)
Similarly,
and so,
Read more about this topic: Chernoff Bound
Famous quotes containing the words the first, step, proof and/or bounds:
“The two great things yet to be discovered are these—The Art of rejuvenating old age in men, & oldageifying youth in books.—Who in the name of the trunk-makers would think of reading Old Burton were his book published for the first to day.”
—Herman Melville (1819–1891)
“It is a good lesson—though it may often be a hard one—for a man who has dreamed of literary fame, and of making for himself a rank among the world’s dignitaries by such means, to step aside out of the narrow circle in which his claims are recognized, and to find how utterly devoid of all significance, beyond that circle, is all that he achieves, and all he aims at.”
—Nathaniel Hawthorne (1804–1864)
“The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.”
—Raymond Chandler (1888–1959)
“Firmness yclept in heroes, kings and seamen,
That is, when they succeed; but greatly blamed
As obstinacy, both in men and women,
Whene’er their triumph pales, or star is tamed —
And ‘twill perplex the casuist in morality
To fix the due bounds of this dangerous quality.”
—George Gordon Noel Byron (1788–1824)