Formula to determine how many quarters needed to buy remaining baseball cards in collection?

Question

I apologize in advance if I'm not explaining this well. I'm trying to solve a problem I'm having at work but I can't think of the mathematical formula needed in order to solve it. Rather than bore you with technical jargon related to my job, I've changed the scenario to a baseball card collection for simplicity sake:

Problem: I want to determine how many US quarters I will need in order to have the highest probability of completing a unique set of baseball cards. I already have 30 of the 40 cards within the set but each card I receive is randomly selected from the 40 available in the set.

1. 1 US dollar = 4 US quarters
2. I already have 30 of the 40 cards
3. Each card costs 1 dollar (i.e. 4 quarters)
4. I want a unique set of cards BUT, each time I pay 1 dollar to receive a card, it can be any one of the 40 cards within the set

So, seeing as how I have 30 of the 40 cards of the current set, my chances of receiving card #31 is 1 in 4. Therefore, I would need 4 dollars (or 16 quarters) to ensure the highest probability that I get a unique card #31.

Card #32 however, the odds would be 9/40. Card #33, the odds would be 8/40, or 1/5. Etc.

So, I'm just trying to write up a formula that would reflect the total number of US quarters needed to have the highest probability of completing a unique set of cards in this scenario.

Answer 1

Since you have 30 of the 40 possible coupons already, the probability that the next coupon you buy will be a new one is $10/40$; so the expected number of coupons you must buy before getting a new one is $40/10$.

Once you have your first new coupon, the probability that your next coupon will be one you don't have is $9/40$, so the expected number of coupons you must buy to get a second new coupon is $40/9$.

Continuing in this way, we see that the expected number of coupons you must buy in order to get one you don't already have is $40/10, 40/9, 40/8, \dots , 40/1$. So in all, you can expect to buy $$\frac{40}{10} + \frac{40}{9} +\frac{40}{8} +\dots +\frac{40}{1} = 40 \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{10} \right) = 117.1587302 $$ coupons in order to complete the set.

Answer 2

The post at the following MSE link 2720594 treats the same problem using $n$ coupons where $n'$ have already been seen and coupons have to be collected in two instances. With the present scenario we only have to see them once.

Using the notation from this MSE link 2426510 we have from first principles that

$$\mathrm{P}[T = m] = \frac{1}{n^m}\times {n-n'\choose 1}\times (m-1)! [z^{m-1}] \exp(n'z) \left(\exp(z) - 1\right)^{n-n'-1}.$$

We shall see that with this closed form for the probabilities, we can not only compute the expectation of the number of draws to collect the remaining coupons but also the second factorial moment if desired, and the variance. To start verify that this is a probability distribution. We get

$$(n-n') \sum_{m\ge n-n'} \frac{1}{n^m}\times (m-1)! [z^{m-1}] \exp(n'z) \left(\exp(z) - 1\right)^{n-n'-1} \\ = (n-n') \sum_{m\ge n-n'} \frac{1}{n^m} (m-1)! [z^{m-1}] \exp(n'z) \\ \times \sum_{q=0}^{n-n'-1} {n-n'-1\choose q} (-1)^{n-n'-1-q} \exp(qz) \\ = (n-n') \sum_{m\ge n-n'} \frac{1}{n^m} \sum_{q=0}^{n-n'-1} {n-n'-1\choose q} (-1)^{n-n'-1-q} (n'+q)^{m-1} \\ = \frac{n-n'}{n} \sum_{q=0}^{n-n'-1} {n-n'-1\choose q} (-1)^{n-n'-1-q} \sum_{m\ge n-n'} \frac{1}{n^{m-1}} (n'+q)^{m-1} \\ = \frac{n-n'}{n} \sum_{q=0}^{n-n'-1} {n-n'-1\choose q} (-1)^{n-n'-1-q} \frac{(n'+q)^{n-n'-1}/n^{n-n'-1}} {1-(n'+q)/n} \\ = \frac{n-n'}{n^{n-n'-1}} \sum_{q=0}^{n-n'-1} {n-n'-1\choose n-n'-1-q} (-1)^{n-n'-1-q} \frac{(n'+q)^{n-n'-1}}{n-n'-q} \\ = \frac{1}{n^{n-n'-1}} \sum_{q=0}^{n-n'-1} {n-n'\choose n-n'-q} (-1)^{n-n'-1-q} (n'+q)^{n-n'-1} \\ = - \frac{1}{n^{n-n'-1}} \sum_{q=0}^{n-n'-1} {n-n'\choose q} (-1)^{n-n'-q} (n'+q)^{n-n'-1} \\ = 1 - \frac{1}{n^{n-n'-1}} \sum_{q=0}^{n-n'} {n-n'\choose q} (-1)^{n-n'-q} (n'+q)^{n-n'-1} \\ = 1 - (n-n'-1)! [z^{n-n'-1}] \frac{\exp(n'z)}{n^{n-n'-1}} \sum_{q=0}^{n-n'} {n-n'\choose q} (-1)^{n-n'-q} \exp(qz) \\ = 1 - (n-n'-1)! [z^{n-n'-1}] \frac{\exp(n'z)}{n^{n-n'-1}} (\exp(z)-1)^{n-n'}.$$

Note however that $\exp(z)-1=z+\cdots$ and hence $(\exp(z)-1)^{n-n'} = z^{n-n'}+\cdots$ which means the coefficient extractor $[z^{n-n'-1}]$ is zero and we are left with just the first term, which is one, and we indeed have a probability distribution.

Continuing with the expectation we evidently require

$$\sum_{m\ge n-n'} \frac{m}{n^{m-1}} (n'+q)^{m-1} \\ = \frac{(n'+q)^{n-n'-1}}{n^{n-n'-1}} \sum_{m\ge 1} \frac{m+n-n'-1}{n^{m-1}} (n'+q)^{m-1}.$$

The simple component from this is

$$(n-n'-1) \frac{(n'+q)^{n-n'-1}}{n^{n-n'-1}} \frac{1}{1-(n'+q)/n}.$$

Here we recognize a term that we have already evaluated which yields on substitution into the outer sum the value $n-n'-1.$ Evaluating the second term we get for the expectation

$$n-n'-1 - \frac{1}{n^{n-n'-1}} \sum_{q=0}^{n-n'-1} {n-n'\choose q} (-1)^{n-n'-q} \frac{(n'+q)^{n-n'-1}}{1-(n'+q)/n}$$

or

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[T] = n-n'-1 - \frac{1}{n^{n-n'-2}} \sum_{q=0}^{n-n'-1} {n-n'\choose q} (-1)^{n-n'-q} \frac{(n'+q)^{n-n'-1}}{n-n'-q}.}$$

Introducing

$$f(z) = \frac{(n-n')!}{n-n'-z} (n'+z)^{n-n'-1} \prod_{p=0}^{n-n'} \frac{1}{z-p}$$

we observe that for $0\le q\le n-n'-1$

$$\mathrm{Res}_{z=q} f(z) = \frac{(n-n')!}{n-n'-q} (n'+q)^{n-n'-1} \prod_{p=0}^{q-1} \frac{1}{q-p} \prod_{p=q+1}^{n-n'} \frac{1}{q-p} \\ = \frac{(n-n')!}{n-n'-q} (n'+q)^{n-n'-1} \frac{1}{q!} \frac{(-1)^{n-n'-q}}{(n-n'-q)!}$$

so that the expectation becomes

$$n-n'-1 - \frac{1}{n^{n-n'-2}} \sum_{q=0}^{n-n'-1} \mathrm{Res}_{z=q} f(z).$$

Now residues sum to zero and the residue at infinity is zero as well since $\lim_{R\rightarrow\infty} 2\pi R \times R^{n-n'-1}/R/R^{n-n'+1} = 0.$ So the sum is minus the residue at $z=n-n':$

$$\mathrm{Res}_{z=n-n'} \frac{(n-n')!}{z-(n-n')} (n'+z)^{n-n'-1} \prod_{p=0}^{n-n'} \frac{1}{z-p}.$$

This needs

$$(n-n')! \left. \left( (n'+z)^{n-n'-1} \prod_{p=0}^{n-n'-1} \frac{1}{z-p} \right)' \right|_{z=n-n'}$$

Note that when we are waiting for one last coupon i.e. $n=n'+1$ the sum formula yields for the expectation $0 - n \times (-1) = n$ so we may suppose that $n\gt n'+1.$ Continue with the derivative to get

$$(n-n')! \left. (n-n'-1) (n'+z)^{n-n'-2} \prod_{p=0}^{n-n'-1} \frac{1}{z-p} \right|_{z=n-n'} \\- (n-n')! \left. (n'+z)^{n-n'-1} \prod_{p=0}^{n-n'-1} \frac{1}{z-p} \sum_{p=0}^{n-n'-1} \frac{1}{z-p} \right|_{z=n-n'} \\ = (n-n'-1) n^{n-n'-2} - n^{n-n'-1} H_{n-n'}.$$

Replacing this in the main formula yields the closed form (which also produces the correct value for $n-n' = 1$ BTW)

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[T] = n \times H_{n-n'} \quad \sim \quad n \log (n-n') + \gamma n + \frac{1}{2} \frac{n}{n-n'} - \frac{1}{12} \frac{n}{(n-n')^2} +\cdots.}$$

We thus obtain for forty coupons with thirty already seen the expectation

$$\frac{7381}{63} \approx 117.1587302.$$

Moving on to conclude with the variance we now work with

$$\sum_{m\ge n-n'} \frac{m^2}{n^{m-1}} (n'+q)^{m-1} \\ = \frac{(n'+q)^{n-n'-1}}{n^{n-n'-1}} \sum_{m\ge 1} \frac{(m+n-n'-1)^2}{n^{m-1}} (n'+q)^{m-1}.$$

Here we recognize two easy pieces which are

$$(n-n'-1)^2$$

and

$$2 (n-n'-1) (n H_{n-n'} - (n-n'-1)).$$

With $\sum_{m\ge 1} m^2 w^{m-1} = (1+w)/(1-w)^3$ we have two additional sum terms:

$$- \frac{1}{n^{n-n'-3}} \sum_{q=0}^{n-n'-1} {n-n'\choose q} (-1)^{n-n'-q} \frac{(n'+q)^{n-n'-1}}{(n-n'-q)^2}$$

and

$$- \frac{1}{n^{n-n'-2}} \sum_{q=0}^{n-n'-1} {n-n'\choose q} (-1)^{n-n'-q} \frac{(n'+q)^{n-n'}}{(n-n'-q)^2}.$$

For the first of these we use $f(z)/(n-n'-z)$ and obtain five pieces:

$$(n-n'-1)(n-n'-2) n^{n-n'-3} - 2(n-n'-1) n^{n-n'-2} H_{n-n'} \\ + n^{n-n'-1} H_{n-n'}^2 + n^{n-n'-1} H^{(2)}_{n-n'}.$$

The second sum only differs in the exponent on $n'+q$ and we obtain

$$(n-n')(n-n'-1) n^{n-n'-2} - 2(n-n') n^{n-n'-1} H_{n-n'} \\ + n^{n-n'} H_{n-n'}^2 + n^{n-n'} H^{(2)}_{n-n'}.$$

Collecting everything including a factor of $1/2$ on the derivative we finally have (observe cancelation of the polynomial in $n$ and $n'$)

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[T^2] = n^2 \times H_{n-n'}^2 - n \times H_{n-n'} + n^2 \times H_{n-n'}^{(2)}.}$$

Using that

$$\mathrm{Var}[T] = \mathrm{E}[T^2] - \mathrm{E}[T]^2$$

we get

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{Var}[T] = n^2 \times H_{n-n'}^{(2)} - n \times H_{n-n'}.}$$

The dominant term here is $\sim \frac{\pi^2}{6} n^2.$

These results for the expectation and the variance are in agreement with Wikipedia on the coupon collector problem, where they are derived by probabilistic methods as opposed to the Stirling numbers used here.