Markov's and Chebyshev's Inequalities Explained

intoli.com

104 points·foob··9 comments

This Chebychev's inequality (there are several) is a simple extension of Markov (by setting phi(x) = |x|^2 - see the Wikipedia article on Markov's inequality).

There is another simple extension[0], much less known, of setting phi(x) = exp(-s*x), and taking the infimum over all s; it is often tractable and yields much, much sharper bounds.

[0] https://en.wikipedia.org/wiki/Chernoff_bound

My favorite contribution of Chernoff, however, is the Chernoff face:

https://en.wikipedia.org/wiki/Chernoff_face

Today I was one of the 10,000. This is great, amazing, hilarious, and awesome. I can't think of a great use at the moment, but I will find one.

Chernoff is good; it leads to some ridiculously strong concentration inequalities. If I recall correctly, the result that "a travelling salesperson tour on n uniformly selected points in [0,1]^2 is very, very likely to be of length very, very close to its mean" is derived using Chernoff (well, Talagrand, but Chernoff is closely related).

Yet, optimized Chebychev (using phi(x) = |x|^p, optimizing over p) beats optimized Chernoff[0].

[0] http://www.jstor.org/stable/2684633

If you have a hard time remembering exactly how Markov inequality goes (like I do), there's a great mnemonic from which you can construct the general version:

- if the average person is 6' tall, than at most 10% of the people are taller than 60'.

Is that right?

Yes! Think about it this way--the smallest height someone could be is zero. So imagine that 90% of the people are zero height, and 10% are exactly 60ft tall. What's the average height?

Yes, if more than 10% are over 60', then, even if everyone else has zero height, the average is already be over 6'.

Reply on news.ycombinator.com