1
$\begingroup$

I am looking for a good reference covering Chernoff bounds for a beginner. By this I mean, a beginner on the subject of Chernoff bounds; I have taken an undergraduate and masters course in mathematics which includes some probability, but this has usually been more on the measure-theoretic side of things, and somehow I have managed to never encounter Chernoff bounds until this point.

An ideal reference would be quite short and cover the concept of Chernoff bounds from scratch (but not necessarily probability as a whole, I am comfortable with university level probability), including a fairly wide range of reasonably basic results on Chernoff bounds, proofs preferably included, but without necessarily going into particularly deep or complex applications.

If it helps to have some context, I am studying a number of almost-Ph.D level papers on random graph theory and many of them appeal to "results with Chernoff bounds" multiple times without giving much information on what these are or how they are actually being used. I don't believe the applications themselves are very deep, but they are used lots of times in different contexts, and the results actually being applied don't appear to be identical. Hence, I would like to find a source which can provide me with enough information to plausibly contain most the results being snuck into these papers, but since the applications don't seem particularly deep I don't think I want anything extraordinarily complex, particularly as I have quite a lot of other reading to do and would prefer not to cover too much irrelevant material when possible (though ascertaining which bits will be relevant is proving quite tricky given the brevity of the papers!).

If no such reference exists, then anything you could point me towards which you believe to contain a particularly well-written treatment on Chernoff bounds would be greatly appreciated. (The book/reference of course doesn't need to exclusively cover the topic of Chernoff bounds, of course.) Many thanks for your advice.

  • 0
    @Cardinal and D. Thomine: many thanks for both of those suggestions, I'll be sure to check out both of them and see what's relevant.2012-03-12

3 Answers 3

0

I used few of them, good reference for beginners Lecture 10.Chernoff Bounds. And application of the bound for more advanced reader A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations.

  • 0
    Looks like it is, this paper dated by 1952, he has another one from 1981 [A Note on an Inequality Involving the Normal Distribution](http://www.jstor.org/discover/10.2307/2243541?uid=3738240&uid=2129&uid=2&uid=70&uid=4&sid=47698748841467)2012-03-12
1

There is a great book "Probability and Computing" in computer science by Michael Mitzenmacher and Eli Upfal with whole chapter on Chernoff bounds, you could look it up on Google books.

  • 0
    Excellent, I'll try and track down a copy in my library! Someone else has it reserved at the moment, popular book...2012-03-12
0

I personally enjoy the article by T.K. Phillips and R. Nelsen, "The Moment Bound Is Tighter Than Chernoff's Bound for Positive Tail Probabilities", The American Statistician, vol 49., no. 2 (1995) pp.175-178 available from JSTOR.