1

A very interesting probability problem. I don't know if it has a name, but I'm rephrasing it in terms of stacking pancakes.

Suppose there are $N$ stacks, and one places pancakes on them randomly (in that each pancake is placed on a random stack uniformly).

We say the $j$-th pancake of a stack is "buried" if all other stacks have at least $j$ pancakes as well. (e.g., the 1st pancake is buried when all stacks have one pancake.)

Now the question is, how many more pancakes does it take to bury the $k$-th pancake?

RobPratt
  • 45,619
qweruiop
  • 374

1 Answers1

0

This is equivalent to the "coupon collector's problem" or "dixie cup problem". The expected number of pancakes required to bury the $j$-th pancake is known to be asymptotic to $N \log N + N (j-1) \log \log N$. You're asking about the number of additional pancakes, after burying the $j$-th, required to bury the $k$-th. By linearity of expectation, the expected additional number is $$ N(k-j)\log \log N $$ to leading order.

mjqxxxx
  • 41,358