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 step, proof and/or bounds:
“To finish the moment, to find the journey’s end in every step of the road, to live the greatest number of good hours, is wisdom. It is not the part of men, but of fanatics, or of mathematicians, if you will, to say, that, the shortness of life considered, it is not worth caring whether for so short a duration we were sprawling in want, or sitting high. Since our office is with moments, let us husband them.”
—Ralph Waldo Emerson (1803–1882)
“From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
—Johan Huizinga (1872–1945)
“Great Wits are sure to Madness near alli’d
And thin Partitions do their Bounds divide;
Else, why should he, with Wealth and Honour blest,
Refuse his Age the needful hours of Rest?”
—John Dryden (1631–1700)