5 ms·
Markov's and Chebyshev's Inequalities Explained
- beagle3 9y agoThis 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 https://en.wikipedia.org/wiki/Chernoff_bound
- tnecniv 9y agoMy favorite contribution of Chernoff, however, is the Chernoff face: https://en.wikipedia.org/wiki/Chernoff_face https://en.wikipedia.org/wiki/Chernoff_face
- jfoutz 9y agoToday 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.
- Smaug123 9y agoChernoff 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).
- randva 9y agoYet, optimized Chebychev (using phi(x) = |x|^p, optimizing over p) beats optimized Chernoff[0]. [0] http://www.jstor.org/stable/2684633 http://www.jstor.org/stable/2684633
- cscheid 9y agoIf 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'.
- j88439h84 9y agoIs that right?
- arglebarnacle 9y agoYes! 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?
- deleted 9y ago[deleted]
- lkozma 9y agoYes, if more than 10% are over 60', then, even if everyone else has zero height, the average is already be over 6'.