And there's actually plenty of practical applications where we want to know

the answer to this problem as well.

I have a 20-sided die, this is, again, just another illustration.

You keep rolling the die, and every time you get a new value,

you check off the value.

So how many times, you're going to have to roll the die,

so because of the birthday problem, after not too many rolls, you get a repeat.

So not new, and then after a while you start to get into plenty of repeats.

But the question is how many times do you have to roll it untill you get all

possible values?

So in this case now we're still looking for just two more possibilities.

Finally we get the 4, and

then after 37 rolls we have all possibilities For a 20 sided die.

So in general, if given M,

how many times you have to throw to get all different M values.

That's the coupon collector problem.

Now, with classical probability, this problem is actually not too difficult.

And so I'll give a classical analysis.

Actually, the analytic combinatorics is more complicated than this.

But it's still worth doing because the classical analysis just gives the average.

And if you want to study variants of a problem, or

other properties of the distribution,

you're going to need the structure that we get from analytic combinatorics.

But anyway, here's the classical analysis.

So, first thing is the probability that you need more than j

rolls to get the k+1st coupon is k/M to the j.

That's the probability that the first j rolls are all from the same k values.