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:
“And yet we constantly reclaim some part of that primal spontaneity through the youngest among us, not only through their sorrow and anger but simply through everyday discoveries, life unwrapped. To see a child touch the piano keys for the first time, to watch a small body slice through the surface of the water in a clean dive, is to experience the shock, not of the new, but of the familiar revisited as though it were strange and wonderful.”
—Anna Quindlen (b. 1952)
“But with one step backward taken
I saved myself from going.
A world torn loose went by me.”
—Robert Frost (1874–1963)
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)
“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)