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:
“The moment when she crawled out onto the back of the open limousine in which her husband had been murdered was the first and last time the American people would see Jacqueline Bouvier Kennedy Onassis crawl.... She was the last great private public figure in this country. In a time of gilt and glitz and perpetual revelation, she was perpetually associated with that thing so difficult to describe yet so simple to recognize, the apotheosis of dignity.”
—Anna Quindlen (b. 1952)
“Attacking a belief can be the first step toward embracing it.”
—Mason Cooley (b. 1927)
“O, popular applause! what heart of man
Is proof against thy sweet, seducing charms?”
—William Cowper (1731–1800)
“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)