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

CC BY-SA 3.0
2014-06-20T11:04:30.260Z
Yes ! this is excellent !  I've read this survey before, but completely forgot about it.
Suresh Venkat
CC BY-SA 3.0
2014-06-20T13:25:59.630Z
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
CC BY-SA 3.0
2014-06-23T16:08:41.207Z
It's not exactly right, but there are flow charts showing how the different theorems imply each other, which is a start.
Suresh Venkat
CC BY-SA 3.0
2014-06-20T04:13:51.937Z
2014-06-20T04:13:51.937Z
Chandra Chekuri
<p>When I teach tail bounds, I use the usual progression: </p>

<ul>
<li>If your r.v is positive, you can apply Markov's inequality</li>
<li>If you have independence and <strong>also</strong> bounded variance, you can apply Chebyshev's inequality</li>
<li>If each independent r.v <strong>also</strong> has all moments bounded, then you can use a Chernoff bound. </li>
</ul>

<p>After this things get a little less clean. For example</p>

<ul>
<li>If your variables have zero mean, then a Bernstein inequality is more convenient</li>
<li>If all you know is that the combining function is Lipschitz, then there's a generalized McDiarmid-style inequality</li>
<li>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)</li>
</ul>

<p>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) ? </p>

<p><em>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.</em> </p>

CC BY-SA 3.0
2014-06-23T12:52:12.210Z
I think the simple answer is no and yes please to anyone who makes one.
Simd
<reference-request><pr.probability><randomized-algorithms>
A flowchart for concentration bounds
Suresh Venkat
# A flowchart for concentration bounds

(Asked by: username_0 on 2014-06-19)

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.*

**Tags:** reference-request, pr.probability, randomized-algorithms
> **Comments:**
> **username_1**: I think the simple answer is no and yes please to anyone who makes one.  

---

## 1 answers

### Answer by username_2 on 2014-06-20. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_0**: Yes ! this is excellent !  I've read this survey before, but completely forgot about it.  
> **username_3**: 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.  
> **username_0**: It's not exactly right, but there are flow charts showing how the different theorems imply each other, which is a start.  

---

