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 the first, step, proof and/or bounds:

    “Behind every individual closes organization; before him opens liberty,—the Better, the Best. The first and worse races are dead. The second and imperfect races are dying out, or remain for the maturing of the higher. In the latest race, in man, every generosity, every new perception, the love and praise he extorts from his fellows, are certificates of advance out of fate into freedom.”
    —Ralph Waldo Emerson (1803–1882)

    “There was never a man born so wise or good, but one or more companions came into the world with him, who delight in his faculty, and report it. I cannot see without awe, that no man thinks alone and no man acts alone, but the divine assessors who came up with him into life,—now under one disguise, now under another,—like a police in citizen’s clothes, walk with him, step for step, through all kingdoms of time.”
    —Ralph Waldo Emerson (1803–1882)

    “When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.”
    —Stephanie Martson (20th century)

    “What comes over a man, is it soul or mind
    That to no limits and bounds he can stay confined?
    You would say his ambition was to extend the reach
    Clear to the Arctic of every living kind.
    Why is his nature forever so hard to teach
    That though there is no fixed line between wrong and right,
    There are roughly zones whose laws must be obeyed?”
    —Robert Frost (1874–1963)