# Chernoff bounds - basic results

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.

-
One question: did you check the Wikipedia article on Chernoff Bound? – Apprentice Queue Mar 12 '12 at 1:49
You could perhaps looks here : eprints.pascal-network.org/archive/00002827/01/…. It contains the basics about Chernov bounds, but also much more (it contains a lot of results relating to large families of non i.i.d. processes, with some applications to graphs). – D. Thomine Mar 12 '12 at 1:53
Given your stated interests, have you looked at the Motwani and Raghavan Randomized Algorithms text, particularly Chapter 4. It may be pitched a little low for you given your background, but still might be useful. You can also look for large-deviations treatments in probability texts. – cardinal Mar 12 '12 at 1:54
@ApprenticeQueue: Yes, I checked the article - it seemed like a good starting point but I didn't think it would be quite sufficient. In addition, I may need to reference one of these later and I feel like a good book is always more well-received for a reference than Wikipedia! – Spyam Mar 12 '12 at 8:31
@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. – Spyam Mar 12 '12 at 12:39

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.

-
That looks interesting - is that Chernoff's original paper on the bounds? – Spyam Mar 12 '12 at 12:46
Looks like it is, this paper dated by 1952, he has another one from 1981 A Note on an Inequality Involving the Normal Distribution – com Mar 12 '12 at 17:32

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.

-
Excellent, I'll try and track down a copy in my library! Someone else has it reserved at the moment, popular book... – Spyam Mar 12 '12 at 12:45

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.

-