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:
“Two principles, according to the Settembrinian cosmogony, were in perpetual conflict for possession of the world: force and justice, tyranny and freedom, superstition and knowledge; the law of permanence and the law of change, of ceaseless fermentation issuing in progress. One might call the first the Asiatic, the second the European principle.”
—Thomas Mann (1875–1955)
“And Thee, across the harbor, silver-paced
As though the sun took step of thee, yet left
Some motion ever unspent in thy stride,—
Implicitly thy freedom staying thee!”
—Hart Crane (1899–1932)
“The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
—Charles Baudelaire (1821–1867)
“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)