Chernoff Bound - The First Step in The Proof of Chernoff Bounds

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:

    “I have placed slippers very carefully under my bed, only to have them crawl out during the night to a position where I will step into them the wrong way round when leaping out of bed to answer the telephone.”
    —Robert Benchley (1889–1945)

    “Right and proof are two crutches for everything bent and crooked that limps along.”
    —Franz Grillparzer (1791–1872)

    “Great Wits are sure to Madness near alli’d
    And thin Partitions do their Bounds divide;
    Else, why should he, with Wealth and Honour blest,
    Refuse his Age the needful hours of Rest?”
    —John Dryden (1631–1700)