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:
“You survived because you were the first.
You survived because you were the last.
Because alone. Because the others.
Because on the left. Because on the right.
Because it was raining. Because it was sunny.
Because a shadow fell.”
—Wislawa Szymborska (b. 1923)
“The energetic action of the times develops individualism, and the religious appear isolated. I esteem this a step in the right direction. Heaven deals with us on no representative system. Souls are not saved in bundles.”
—Ralph Waldo Emerson (1803–1882)
“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)
“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)