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:
“What in fact have I achieved, however much it may seem? Bits and pieces ... trivialities. But here they won’t tolerate anything else, or anything more. If I wanted to take one step in advance of the current views and opinions of the day, that would put paid to any power I have. Do you know what we are ... those of us who count as pillars of society? We are society’s tools, neither more nor less.”
—Henrik Ibsen (1828–1906)
“The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.”
—Charles Baudelaire (1821–1867)
“At bounds of boundless void.”
—Samuel Beckett (1906–1989)