A trading card series has 200 different cards in it, which are sold in 5-card packages.

Each package has a random sampling of the cards (assume that any card of the 200 has an equal chance of being in a package).

On the average, how many packages will need to be bought to collect the complete series if...

A: all the cards in a package will always be different

B: a package can have repeats

(In reply to a method of solving problem B by Steve Hutton)

Steve Hutton's algorithm, with a couple of corrections, does indeed solve problem B. This independently corroborates the solution I previously posted using inclusion and exclusion of sets of collected card numbers.

The first correction is in the general recursion formula. Where Steve had given p(m,n) = p(m-1,n)*(n-1)/200 + p(m-1,n-1)*(201-n)/200, is SHOULD have been p(m,n) = p(m-1,n)*n/200 + p(m-1,n-1)*(201-n)/200 as exemplified by his own p(3,2) = (199/200)*(2/200) + (1/200)*(199/200).

The second correction is in the expected value. As the probability P(m,200) is the probability of having gained 200 cards BY step m, it has to be converted to an individual probability AT step m by subtracting the previous (m-1) probability, so instead of the sum of s*P(m,200) it should be the sum of s*(P(m,200)-P(m-1,200))

I ran a Basic program that implements Steve Hutton's algorithm, as modified and it produces the same 235.5212379... as the analytic method I previously posted, and a probability that 200 would have been achieved by packet 3000 (card 15000) as .9999999999999936, so we've covered most of the probabilities by packet 3000.

By the way, I think this methodology is called a Markov chain.

Posted by Charlie on 2003-02-05 08:53:56