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

With this cumulative probability at 5-card intervals, minus the preceding result, the probability of a completion at that n is obtained, which, multiplied by n is added as a term to the expected value.

A problem in actually computing the value from this formula is that the resulting Sigma, which is a probability and so has a value between 0 and 1, is the result of adding 200 terms alternating positive and negative, and some being as large in order of magnitude as C(200,100), which has 59 digits before its decimal point. As a result 59 significant digits get lost in the addition. If we want accuracy to say 10 places after the decimal we need 69-digit precision. As a result, I wrote the program to compute this in a language called UBASIC, and set the precision to 120 significant decimal digits, which is well within its capabilities. It also has a built-in combination function, COMBI():
10 point 25 ' sets precision at 25 * 4.8 decimal places
14 ExpTot=0:PVal=0
15 for P=40 to 1000
16 N=P*5
19 Tot=0:Sg=1
20 for I=1 to 200
30 Tot=Tot+(1-((200-I)/200)^N)*combi(200,I)*Sg
40 Sg=-Sg
50 next
60 ExpTot=ExpTot+P*(Tot-PVal)
61 PVal=Tot
70 next P
80 print ExpTot:print Tot

The resulting expected value comes out to 235.521235…, and the total cumulative probability by the 1000th packet (5000th card) is .999999997…. Increasing the number of packets max to 3000 changes the expected number of packets to 235.52123792…, and the probability of a larger number of packets being needed is less than 1 in 10^30.

Posted by Charlie on 2003-01-30 10:01:13