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)
“In doing anything the first step is the most difficult.”
—Chinese proverb.
“The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
—H.L. (Henry Lewis)
“Firmness yclept in heroes, kings and seamen,
That is, when they succeed; but greatly blamed
As obstinacy, both in men and women,
Whene’er their triumph pales, or star is tamed —
And ‘twill perplex the casuist in morality
To fix the due bounds of this dangerous quality.”
—George Gordon Noel Byron (1788–1824)