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.
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).
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'.
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?
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