🚀 go-pugleaf

JohnHanna@aol.com asks:
------------------------------------------------------------
   Who can help with the following problem...

   SOGGIE, breakfast of chumps, is having a special promotion. They are packing
   a special 'prize' in each box of SOGGIES. There are three different prizes
   in the collection, distributed uniformly among the boxes, and each box
   contains one prize.
   You, constant reader, buy one box at a time.

       a. What is the probability of getting all three prizes in exactly three
   boxes? That is, after buying three boxes, each box contains a different
   prize.

       b. What is the probability of getting all three prizes in exactly four
   boxes?

       c. What is the probability of getting all three prizes in exactly K
   boxes?

       d. What is the average (expected) number of boxes needed to get all
   three prizes?

       e. If the number of prizes in the collection is N, find a function E(N),
   the expected number of boxes required to get all N prizes in the collection.
------------------------------------------------------------

RWW Taylor (rwtnts@rit.edu) responds:
============================================================
    >     c. What is the probability of getting all three prizes in
    >        exactly K boxes?

    Offhand inspection (confirmed by a few back-of-the-envelope calculations)
    suggests that the probability that a third variety of prize will be
    found for the first time in the Kth box is (2^(K-1) - 2)/3^K.  There is,
    after all, a 1/3 chance that the Kth box will contain a sample of the
    third prize, if the first K-1 boxes each contain one or the other of the
    other two prizes.  But we have to exclude the two cases where the first
    K-1 boxes all contain exactly the same prize!  This generalizes neatly,
    of course, to the case of N different prizes.

============================================================

I'm not sure the generalization to N prizes is so neat, but here's a stab
at it, from the back of my envelope...

Think of it as counting the number of distinct permutations of length k
of n types of objects, with one object occurring only in the last place.
If this number is N(k, n) then if X gives the number of draws required
to first achieve all n objects, we have
Prob{X = k} = N(k,n) / n^k, since there are n^k possibilities.

So what is N(k,n)?  To avoid writing a lot n-1's, let m = n-1.

The number of distinct permutations of k-1 objects, of which
r_1 are of type 1, r_2 of type 2, ..., r_m of type m,
where the objects of any given type are indistinguishable, is
(k-1)! / r_1! r_2! ... r_m!.
This will give us the number of outcomes of our first k-1 draws, where
we get at least one of each of n-1 of the objects. (recall m = n-1).

But we have to sum over all appropriate choices of r_1, r_2,...,r_m.

N(k,n) = n * SumOver{r_1 + r_2 + ... r_m = k-n : each r_i >= 0}
         (k-1)! / (r_1 + 1)! (r_2 + 1)! ... (r_m + 1)!

The r_i + 1 guarantees that we have at least one object of each type.
The sum could also be written as:
N(k,n) = n * Sum{r_1 = 0 to k - n} Sum{r_2 = 0 to k - n - r_1} ...
             Sum{r_m = 0 to k - n - r_1... - r_(m-1)}
             (k-1)! / (r_1 + 1)! (r_2 + 1)!...(r_m + 1)!

The first factor of n is because we have n choices for the object in the
kth place.  The other factor is the number of arrangements of the m = n-1
objects in places 1 to k-1.

Then Prob{X = k} = N(k,n) / n^k     (note we could divide top & bottom by n)
and E(X) = Sum{k = n to infinity} k * Prob{X = k}.

Sorry I don't have a nice closed form here.  Perhaps my envelope was too small
and another reader will have a larger envelope.