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:

    “And Thee, across the harbor, silver-paced
    As though the sun took step of thee, yet left
    Some motion ever unspent in thy stride,—
    Implicitly thy freedom staying thee!”
    —Hart Crane (1899–1932)

    “To cease to admire is a proof of deterioration.”
    —Charles Horton Cooley (1864–1929)

    “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)