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:
“Knowledge has two extremes. The first is the pure natural ignorance in which all men find themselves at birth. The other extreme is that reached by great minds, who, having run through all that men can know, find they know nothing, and come back again to that same natural ignorance from which they set out; this is a learned ignorance which is conscious of itself.”
—Blaise Pascal (1623–1662)
“Tennis is more than just a sport. It’s an art, like the ballet. Or like a performance in the theater. When I step on the court I feel like Anna Pavlova. Or like Adelina Patti. Or even like Sarah Bernhardt. I see the footlights in front of me. I hear the whisperings of the audience. I feel an icy shudder. Win or die! Now or never! It’s the crisis of my life.”
—Bill Tilden (1893–1953)
“If some books are deemed most baneful and their sale forbid, how, then, with deadlier facts, not dreams of doting men? Those whom books will hurt will not be proof against events. Events, not books, should be forbid.”
—Herman Melville (1819–1891)
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)