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 step, proof and/or bounds:
“Perestroika basically is creating material incentives for the individual. Some of the comrades deny that, but I can’t see it any other way. In that sense human nature kinda goes backwards. It’s a step backwards. You have to realize the people weren’t quite ready for a socialist production system.”
—Gus Hall (b. 1910)
“The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
—H.L. (Henry Lewis)
“At bounds of boundless void.”
—Samuel Beckett (1906–1989)