Go away and read about the coupon collector's problem, or what follows will make less than no sense.

OK, glad to have you back. What's the expected number of boxes of nutritious GlobalEvilCorpTM breakfast cereal you have to buy in order to get at least one picture of each of the N E2 noders?

Well, let's use conditional expectation (which sounds a lot worse than it really is; just use your common sense in what follows, and you'll be fine). Let's say I already have pictures of j different E2 noders. What's the expected number of boxes I need to buy before I get a new picture? Well, on each box, the probability is (N-j)/N, so the expected number of boxes before it actually happens is the inverse N/(N-j).

Using the fact that expectation is linear, and breaking the time to collect the whole set into the sum of the times to collect the first, then to collect the second, then to collect the third, ..., then to collect the N'th, it turns out the expected number of boxes is

N * (1/(N-1) + 1/(N-2) + ... + 1/2 + 1 =
  = N * HN
where HN = ln(N)+γ+O(1/N2) is the N'th harmonic sum; γ is the mysterious Euler's constant, approximately 0.5772.

So the answer to our question is (for large N) approximately N*(ln N + 0.5772...).

Log in or register to write something here or to contact authors.