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:
“Three elements go to make up an idea. The first is its intrinsic quality as a feeling. The second is the energy with which it affects other ideas, an energy which is infinite in the here-and-nowness of immediate sensation, finite and relative in the recency of the past. The third element is the tendency of an idea to bring along other ideas with it.”
—Charles Sanders Peirce (1839–1914)
“We are only what we are; not what we would be; nor every thing we hope for. We are but a step in a scale, that reaches further above us than below.”
—Herman Melville (1819–1891)
“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)
“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)