21
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ I think the simple answer is no and yes please to anyone who makes one. $\endgroup$
    – Simd
    Commented Jun 23, 2014 at 12:52

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes ! this is excellent ! I've read this survey before, but completely forgot about it. $\endgroup$
    – Suresh Venkat
    Commented Jun 20, 2014 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
    Commented Jun 20, 2014 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$
    – Suresh Venkat
    Commented Jun 23, 2014 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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