21

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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271

1 Answers1

11

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.

Chandra Chekuri
  • 6,999
  • 31
  • 39
  • Yes ! this is excellent ! I've read this survey before, but completely forgot about it. – Suresh Venkat Jun 20 '14 at 11:04
  • 6
    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. – usul Jun 20 '14 at 13:25
  • It's not exactly right, but there are flow charts showing how the different theorems imply each other, which is a start. – Suresh Venkat Jun 23 '14 at 16:08