Tuesday, January 26, 2010


This post is a fairly basic review of common probability notions. Things will get more interesting in future posts. Somebody who wants to do TCS but has not studied probability yet can read this post carefully and reach about the same level of formal training that I've had :)

Say we distribute n items into b bins randomly. Fixing our attention on one bin (e.g. the first), how can be bound the number of items landing there?

The expected number of items is n/b. Thus, by the Markov bound, we get:

Pr[bin contains ≥ 2n/b items] ≤ 1/2

To strengthen the bound, we may look at the variance and apply the Chebyshev bound. Let X be the number of elements in the first bin. Also let μ=E[X]=n/b. The variance of X is defined as E[(X-μ)2], and this is exactly what we need to compute for Chebyshev.

How can we compute the variance? We let Xi be the indicator for whether the i-th item falls in our bin (indicator means the variable is 1 if the event happens, and 1 otherwise). Then, X=X1+...+Xn.

Since we are interested in X-μ, not X, it is more convenient to define Yi = Xi-(1/b). With this definition, X-μ=Y1+...+Yn. Observe that E[Yi] = 0.

We can not break up the variance:
Var[X] = E[(X-μ)2] = E[( ΣYi )2] = Σ E[YiYj]
We are down to analyzing E[YiYj], which is simple. If i≠j, Yi and Yj are independent random variables. Thus, the expectation commutes with the product:
E[YiYj] = E[Yi] E[Yj] = 0
In the case i=j, we use brute force calculation. Yi=-1/b with probability 1-(1/b), and equals 1-(1/b) with probability 1/b. Thus, E[(Yi)2] = O(1/b).

We have found the variance to be E[(X-μ)2]=O(n/b)=O(μ). Then:
Pr[X ≥ 2n/b] = Pr[X-μ ≥ μ] ≤ Pr[(X-μ)2 ≥ μ2] ≤ O(μ) / μ2 = O(1/μ)
Observe that the Chebyshev bound is nothing more than Markov on the variable (X-μ)2.

Third moment. If stronger bounds are required, we can try to look at higher moments, E[(X-μ)k]. Unfortunately, moving to the 3rd moment (or any other odd moment) does not really help: the variable (X-μ)3 is no longer positive, so Markov cannot apply.

One way to fix this is to look at the absolute third moment: E[|X-μ|3]. It is no longer easy to compute this moment, since we cannot break up |ΣYi|3 into components, due to the absolute value. Thus, we do not commonly use absolute moments.

However, I have come across absolute moments once, in the following interesting application. The central limit theorem states that the average of N i.i.d. variables tends to the normal distribution as N→∞. The Berry-Esseen theorem quantifies this phenomenon: it gives a fairly strong bound on the speed of the convergence, assuming the third absolute moment of the summands is bounded.

Fourth moment. To strengthen the variance bound, one most commonly looks at the 4th moment. To get a feeling for it, let's see how we can bound the 4th moment in the balls and bins case:
E[(X-μ)4] = E[( ΣYi )4] = Σijkl E[ YiYjYkYl ]
We can understand the terms generated by an (i,j,k,l) tuple by case analysis:
  1. If one of the elements appears exactly once, the term is zero. For instance, let's say i∉ {j,k,l}. Then Yi is independent of the rest, so the expectation commutes with product: E[YiYjYkYl] = E[Yi] E[YjYkYl] = 0.

  2. If all elements are equal (i=j=k=l), E[(Yi)4] = O(1/b).

  3. If the tuple consists of two equal pairs, for instance (i,i,j,j), we have E[(Yi)2 (Yj)2] = E[(Yi)2] E[(Yj)2] = O(1/b2).
We have n terms of type 2, and O(n2) terms of type 3. Thus, the fourth moment is O(n2 / b2) = O(μ2).

To bound the bin size, we can now apply Markov on the fourth moment:
Pr[X ≥ 2n/b] = Pr[X-μ ≥ μ] ≤ Pr[(X-μ)4 ≥ μ4] ≤ O(μ2) / μ4 = O(1/μ2)
Thus, our bounds have improved from 1/2 for Markov, to O(1/μ) for Chebyshev, and to O(1/μ2) for the 4th moment. Going to the 6th, 8th, etc yields the predictable improvement.

Chernoff. The next step to improving our bounds is to go to the Chernoff bound. This bound has many forms, in particular two rather different instantiations for additive and relative error.

Let me quote an uncommon, but nifty version of the theorem:

Let X1, ..., Xn be independent random variables bounded in [0,1]. Let X=ΣXi and μ=E[X].
If Z≥μ, then Pr[X≥Z] ≤ eZ-μ (μ/Z)Z.
If Z≤μ, then Pr[X≤Z] ≤ eZ-μ (μ/Z)Z.
In our case, we are interested in Z=2μ. Thus, the upper bound on the probability is eμ / 2 ≈ 1 / 1.47μ. We have obtained an exponential bound, instead of the polynomial bound possible by constant moments.

If we have been interested in showing that the bin gets at least Z=μ/2 elements, the second part of the theorem gives a probability bound of e-μ/2 2μ/2 ≈ 1 / 1.17μ. Note how the two terms of the bound trade places: eZ-μ is pushing the probability down in the second case, while (μ/Z)Z is making sure it is small in the first case.

The proof of Chernoff is a bit technical, but conceptually easy. As before, we define Yi = Xi - E[Xi], so that X-μ=ΣYi. Instead of looking at E[(X-μ)k], we will not look at E[αX-μ] (where α>1 is a parameter than can be optimized at the end). This quantity is easy to compute since E[αΣYi] = E[Π αYi] = Π E[αYi]. At the end, we can just apply Markov on the positive variable αX-μ.

High probability. In TCS, we are passionate about bounds that hold "with high probability" (w.h.p.), which means probability 1 - 1/nc, for any constant c. For instance,
Algorithm A runs in O(n) time w.h.p.
formally means the following:
There exists a function f(.) such that, if you choose any constant c, I can prove that algorithm A runs in time f(c)·n with probability 1 - 1/nc.
While such bounds may seem weird at first, they do make a lot of sense: think of applying some randomized procedure a polynomial number of times. Also, these bounds make a lot more sense when dealing with many experiments over huge data sets (the essence of Computer Science) than adopting the convention from statistics, which asks for bounds that hold with 95% probability.

Since we are usually happy with whp bounds, one often hears that Chernoff is morally equivalent to O(lg n)-moments. Indeed, such a moment will give us a bound of the form 1/μO(lg n), which is high probability even in the hardest case when μ is a constant.

The paper of [Schmidt, Siegel, Srinivasan SODA'93] is often cited for this. Their Theorem 5 shows that you can get the same bounds as Chernoff (up to constants) if you look at a high enough moment.


Anonymous said...


Anonymous said...

I don't get it. This is all in Mitzenmacher's book and all much better written. Besides regurgitating Mitzenmacher's textbook, what is really the point of this post?

Mihai said...

I'm trying to get Mitz's book out of print and bankrupt him.

Gabi said...

I like the reply to the second Anonymous!

kryptos said...

nice post; more concise than in mitzenmacher's book; just on another note, i read in your earlier posts, you applied to schools in US for Professorship, did you apply to Cornell?Just curious since i am a grad student there!would be nice to see you here

Mihai said...

I did apply to Cornell, but didn't interview there. Now that I live in NYC, it should be easy for me to come up and give a talk at Cornell (one day...)

Anonymous said...

Very complete excellent post.
Thank you so much.

Anonymous said...

Great and Thanks, I am waiting for the following post!