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)
“Life begins at six—at least in the minds of six-year-olds. . . . In kindergarten you are the baby. In first grade you put down the baby. . . . Every first grader knows in some osmotic way that this is real life. . . . First grade is the first step on the way to a place in the grown-up world.”
—Stella Chess (20th century)
“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)
“Nature seems at each man’s birth to have marked out the bounds of his virtues and vices, and to have determined how good or how wicked that man shall be capable of being.”
—François, Duc De La Rochefoucauld (1613–1680)