4 ms·
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).
by beagle3 9y ago
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 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