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.

  • $\begingroup$ I think the simple answer is no and yes please to anyone who makes one. $\endgroup$
    – graffe
    Jun 23 '14 at 12:52

Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey available at http://projecteuclid.org/euclid.im/1175266369 or at Fan Chung Graham's web page.

  • $\begingroup$ Yes ! this is excellent ! I've read this survey before, but completely forgot about it. $\endgroup$ Jun 20 '14 at 11:04
  • 6
    $\begingroup$ It's a very nice survey, but I don't see anything like what is requested in the original post: "a convenient flowchart or decision tree describing how to choose the 'right' tail bound" for the random variables you have. $\endgroup$
    – usul
    Jun 20 '14 at 13:25
  • $\begingroup$ It's not exactly right, but there are flow charts showing how the different theorems imply each other, which is a start. $\endgroup$ Jun 23 '14 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.