# A flowchart for concentration bounds

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.

• I think the simple answer is no and yes please to anyone who makes one.
– Simd
Commented Jun 23, 2014 at 12:52