The Collector's Problem

Suppose there exist n (maybe 100) baseball players, each of whom 
has his face on baseball cards.  A fan can buy cards, one at a 
time.  Each purchase has an equal chance of being any of the 
players (no matter how many cards are bought).  How many cards 
must the fan buy in order to have a complete set with probability 
p (say, 0.99)?

This is related to the well-known problem of determining the 
*expected* number of purchases necessary to acquire a complete set 
of cards, i.e., at least one of each of the n available types.  The 
expected number of purchases is

         E(n)  =  n(1 + 1/2 + 1/3 + ... + 1/n)

as discussed in the note Collecting k Complete Sets of Coupons.
However, it's somewhat more difficult to determine the number of 
purchases necessary to give a certain probability of having a 
complete set.  In a sense, this is a variation of the generalized 
"birthday problem", with 100 possible baseball cards instead of 
365 possible birthdays.  In general terms, if there are L distinct 
possible outcomes (each assumed to be equally probable), the problem 
is to determine the probability of a particular set of outcomes in 
N trials.

If N is small, then the "brute force" method can be used to compute 
the exact answer.  To take a simple example, suppose N=5.  The seven 
possible partitions of 5 are

                     5  = [5]
                        = [4+1]
                        = [3+2]
                        = [3+1+1]
                        = [2+2+1]
                        = [2+1+1+1]
                        = [1+1+1+1+1]

These partitions correspond to all possible outcomes.  The first
represents the cases when all 5 trials have the same outcome.  The
second represents the case when four of the five outcomes were the 
same and one was different.  The third represents the case when three 
of the trials had one outcome and the other two trials had another 
outcome, and so on.

Each of these seven outcomes has a definite probability.  For example,
the probability of outcome [5] is simply (1/L)^4, and the probability
of outcome [1+1+1+1+1] is given by (L-1)!/((L-5!)*(L)^4).  Let s(N,k) 
denote the number of components in the kth partition.  The kth partition 
of N will consist of a certain number of 1s  (i.e., unique outcomes), a 
certain number of 2s (i.e., "doubles"), a certain number of 3s (i.e., 
"triples"), and so on.  Let  a_t  denote the number of t-tuples in the 
kth partition.  Then define function

                               N!
       M(N,k)   =    ---------------------------
                        N
                     PROD  ((t!)^(a_t))*((a_t)!)
                       t=1

This is called the M_3 multinomial coefficient in "The Handbook of 
Mathematical Functions" by Abramowitz and Stegun (chapter 24 on 
Combinatorial Analysis).  Then I believe the exact probability of 
Q[N,k] (the kth partition of N) is given by

                              M(N,k) L!
       Pr{Q[N,k]} =    -----------------------
                           (L-s(N,k))! L^N

Once we have computed the probability of each partition, we can then
add up the probabilities for the partitions having any particular
property of interest, such as those for which all possible outcomes
occurred at least once during the N trials (e.g., you have at least
one of the 100 available basaeball cards).  

This approach is easy if N is small.  The difficulty is that the number 
of possible partitions of N (of L or fewer components) increases very 
rapidly as N gets larger.  For example, p(180) = 684,957,390,936.
Therefore, computing the EXACT rational answers for large values of N 
may be computationally intractable, although you could probably derive 
some good asymptotic formulas.  Feller's "Introduction to Probability" 
discusses approximate solutions of this general problem.

Notice that the solution of the "standard" birthday problem (to find
the probability of NO duplicate results) is a special case of the above
formula.  In this case we want the probability of the single partition 
consisting of all 1s.  Here we have M(N,k)=1 and s(N,k)=N, so the answer 
to the standard birthday problem reduces to the well-known formula
Pr{no duplicates} = L!/[(L-N)!*L^N].

To answer the more specialized question of the probability of at least
one of each possible outcome, a Markov model is convenient.  The states
can be distinguished by a single number, the number of outcomes that
have occurred so far.  The 100x100 transition matrix is
                                                 
      0.01     0      0      0      0   . . .    0      0     0
      0.99   0.02     0      0      0   . . .    0      0     0
        0    0.98   0.03     0      0   . . .    0      0     0
        0      0    0.97   0.04     0   . . .    0      0     0
        0      0      0    0.96   0.05  . . .    0      0     0
        .      .      .      .      .            .      .     .
        .      .      .      .      .            .      .     .
        .      .      .      .      .            .      .     .
        0      0      0      0      0          0.98     0     0
        0      0      0      0      0          0.02   0.99    0
        0      0      0      0      0            0    0.01   1.00

The probability of having seen all possible outcomes after n trials
is the [100,1] component of M^n.  For n=2^k I get the following
results
                   n           Pr

                    1        0.000000
                    2        0.000000
                    4        0.000000
                    8        0.000000
                   16        0.000000
                   32        0.000000
                   64        0.000000
                  128        0.000000
                  256        0.000137
                  512        0.556018
                 1024        0.996647
                 2048        0.999999
                 4096        1.000000
                 8192        1.000000

With this method you can determine the precise value of n for which the
probability first exceeds any specific value.