When I teach tail bounds, I use the usual progression:
- If your r.v is positive, you can apply Markov's inequality
- If you have independence and also bounded variance, you can apply Chebyshev's inequality
- If each independent r.v also has all moments bounded, then you can use a Chernoff bound.
After this things get a little less clean. For example
- If your variables have zero mean, then a Bernstein inequality is more convenient
- If all you know is that the combining function is Lipschitz, then there's a generalized McDiarmid-style inequality
- if you have weak dependence then there are Siegel-style bounds, (and if you have negative dependence, then Jansson's inequality might be your friend)
Is there a reference anywhere to a convenient flowchart or decision tree describing how to choose the "right" tail bound, (or even when you have to dive into a sea of Talagrand) ?
I'm asking partly so that I have a reference, partly so that I can point it to my students, and partly because if I'm sufficiently annoyed and there isn't one, I might try to make one myself.