# Expectation of collecting stickers in groups

I saw this article about the expected number of stickers required to complete the Panini Euro 2016 album, where stickers are sold in packets of 5 distinct stickers. The author presents the case where stickers are bought singly, then adds in the restriction that each 5 in a packet are distinct. For the latter case, he calculates the expected number of stickers to be the sum:

680/680 + 680/680 + 680/680 + 680/680 + 680/680
+ 680/675 + 680/675 + 680/675 + 680/675 + 680/675
+ 680/670 + . . . . . . .
+ 680/5 + 680/5 + 680/5 + 680/5 + 680/5

However, I can't see why this is the case. Surely the second sticker from the first packet has probability 679/679 of being required, because it can't be the same as the first sticker? Of course, for the first packet, this makes no difference, but come the second packet it does. In the second packet the first sticker has probability 675/680 of being required, but the second has probability 674/679. Therefore, why isn't the sum this?

680/680 + 679/679 + 678/678 + 677/677 + 676/676
+ 680/675 + 679/674 + 678/673 + 677/672 + 676/671
+ 680/670 + . . . . . . .
+ 680/5 + 679/4 + 678/3 + 677/2 + 676/1

Could somebody point out where I'm going wrong? Thanks.

• Several answers to this question are supplied in our thread at stats.stackexchange.com/questions/101255 . The formula you quote from the Web is obviously wrong, as can be determined by applying it to smaller (but verifiable) cases, such as four stickers sold in packets of two. It appears to predict an expectation of $4/4+4/4+4/2+4/2=6$ whereas, by conducting just a few trials, the actual expectation is easily seen to be less than $4$. – whuber Apr 22 '16 at 13:50
• I have seen that post and read the article by Stadje. Using his formula, for your 4 stickers, 2 per packet case, the probability of getting all 4 stickers is 0.167 after 2 packets, 0.528 after 3 and 0.755 after 4. The expectation for 2 packets is 3.0, 3 packets is 3.5 and 4 packets is 3.75. I'm not sure what you mean by "conducting just a few trials"? The 6 you calculated from the original website's formula would be stickers, so 3 packets. – Timothy Jones Apr 22 '16 at 19:15
• This simulation generates 100,000 packets. It collects them until all cards are obtained and then starts all over again with the next packet. I consistently get an expectation close to 3.80. When I generate a million packets of five cards each (chosen randomly out of 680), I succeed in making 1035 complete collections within the first 999,947 cards, for an expectation of 966. (Re-running it gives 960.) The standard error is only 5.4. The article's estimate of 747 thus is implausibly small. The simulation estimates there's only a 6.8% chance of completing the collection that quickly. – whuber Apr 22 '16 at 19:33
• Thanks, I understand now. So the paper by Stadje gives formulae for the expected number of unique stickers after k packets and also the probability of getting less than n or exactly n stickers with k packets. Can any of these be used here to help with this problem? – Timothy Jones Apr 22 '16 at 19:41
• Those formulae completely solve the problem. They do not, however, answer the question you asked, which is to point out where you (might) be going wrong. BTW, a straightforward recursive program computes $3.8$ for the case of four stickers in packets of two and $963.1617\ldots$ for $680$ stickers in packets of five. – whuber Apr 22 '16 at 19:54

## 2 Answers

Probability problems can be tricky. Whenever possible, reduce them to steps that are justified by basic principles and axioms.

Expectation problems get a little easier because you don't have to keep track of all the individual chances. This particular problem is a nice illustration.

To get going, let's establish notation. I like $n=680$ for the total number of cards to collect and $k=5$ for the packet size. After you have begun collecting cards you will keep track of how many more you need: let's call that quantity $m$ (which means you already have $n-m \ge 0$ distinct cards).

What happens when you obtain a new packet? There are up to $k+1$ possibilities, depending on whether it contains $0, 1, \ldots,$ through $k$ new cards. To keep track of these, let the expected number of packets you need to buy in addition to those you currently have be written $e(m; n,k)$. Let $X$ be the random variable giving the number of new cards you collect and let its probability distribution be given by $\Pr(X=j|m,n,k)$. Two things happen:

1. You pay for another packet: this raises the expectation by $1$.

2. You change the expectation depending on $X$. By the rules of conditional expectation, for any $j$ between $0$ and $k$, we have to weight the new expectations by the probabilities and add them up:

$$e(m;n,k) = 1 + \sum_{j=0}^k \Pr(X=j|m,n,k) e(m-j;n,k).$$

To make this practicable, we have to overcome the difficulty that $e(m;n,k)$ appears on both sides (it shows up for $j=0$ on the right hand side). Just do the usual algebra to solve:

$$e(m;n,k) = \frac{1}{1 - \Pr(X=0|m,n,k)}\left(1 + \sum_{j=1}^k \Pr(X=j|m,n,k) e(m-j;n,k)\right).$$

(Notice that the sum begins at $j=1$ now.) The formula for $\Pr(X=j|m,n,k)$ is well known: it's a Hypergeometric distribution,

$$\Pr(X=j|m,n,k) = \frac{\binom{n-m}{k-j}\binom{m}{j}}{\binom{n}{k}}.$$

The initial conditions are easily determined: there's nothing more to be done once $m$ has been reduced to $0$ or less:

$$e(m;n,k) = 0\text{ if }m \le 0.$$

This algorithm finds $e(m;n,k)$ in terms of the $k+1$ preceding values. It therefore requires only $O(k)$ storage and $O(mk)$ time for the computation (assuming all those binomial coefficients can be obtained in $O(1)$ time each--which they can). To illustrate, here is R code:

n <- 680 # Distinct cards
k <- 5   # Packet size (1 or greater)

# Hypergeometric probabilities
hyper <- function(j,m,n,k) exp(lchoose(n-m, k-j) + lchoose(m,j) - lchoose(n,k))

# Initialize
e <- c(rep(0, k), rep(NA, n)) # The index offset is k!
names(e) <- paste((1-k):n)

# The algorithm
for (m in 1:n)
e[m+k] <- (1 + sum(hyper(k:1,m,n,k) * e[(m-k):(m-1) + k])) / (1 - hyper(0,m,n,k))

print(e[n+k], digits=12)


The output, $963.161719772$, errs only in the last digit (it is "2" rather than "3" due to accumulated floating point roundoff). In the case $n=4,k=2$ it yields the answer $3.8$: it can be instructive to trace through the code as it computes that answer.

As far as where the arguments went wrong,

• The argument in the article is useless because it implicitly assumes there is no overlap among packets. That's the only possible way the calculation could be broken down into multiples of five. For instance, it's possible that the second pack you buy has a card you already collected. Afterwards there will be 671 cards to collect--but that formula has no terms corresponding to this possibility.

• Your argument refers to "probabilities of being required." It's unclear what these might be. Nevertheless, let's suppose your argument is correct, at least initially. It appears to say that if you ever get to the point of needing one last card, you will expect to buy $676/1$ packets to do that. They comprise $5\times 676=3380$ cards. Now that this has been pointed out, do you really think you need to buy so many? My intuition says the value should be very close to $680$ divided by $5$, or $136$, because by then we would expect to see each card once on average--and that's exactly the right answer. (You can see it by printing out the array e in the code: it starts out

 -4       -3       -2       -1        0        1        2        3        4
0.0000   0.0000   0.0000   0.0000   0.0000   136.0000 203.7991 248.9989 282.8988


Those last few values tell you how many more packets you expect to buy when you have $4, 3, 2,$ or $1$ cards left to collect (reading from the right side in): 283, 459, 204, and 136.

One moral is, don't trust newspaper articles that describe the computations of so-called "geniuses" unless there's evidence the writer understood the procedure. (That's pretty rare.)

Another moral is revealed by inspecting all of e. Because $e(19;680,5)=481.47$ is almost exactly half of $e(680;680,5)$, you're only halfway done when you have only $19$ more cards to collect! This is characteristic of carnival games that lure suckers in by letting them score high in their first few attempts but where attaining the final few points to win a prize is almost impossible. The only thing that saves it from being a complete fraud is the possibility of trading cards. (And let's not go into the possibility that one or more cards appear with much smaller chances than the others... .)

• Thanks for the detailed explanation - it's exceptionally helpful. Note that the formula from the web article I originally linked to was written by a professor of maths at Cardiff University, so I did think the tag "genius", whilst overly hyperbolic, might be justified... – Timothy Jones Apr 23 '16 at 8:55

Suppose that you got stickers 1, 2, 3, 4, and 5 in your first packet. All guaranteed to be 1sts.

Since the next packet of 5 will not include any doubles, the odds for each of them being "new" are all the same. If the first of these is a 6 (new), that doesn't change the odds for the next four, since they can't internally conflict. Furthermore if it is a 1 (not new) that doesn't affect the odds of the other four either. So all five have odds 675/680.

However, the next step gives my intuition a bit of pause. Since each of the 5 have odds 675/680, the expected number of each card needed is 680/675. But wait, we get cards in sets of 5, not sets of 1.007. So I wonder if it makes more sense to find the expected number of new cards per set and go that way. Maybe it adds up the same? But that's a bit of a different question.

• I don't think your reasoning properly takes into account the fact that all stickers in a packet are distinct. I do take your point about their independence from each other though. Therefore isn't the probability of each card in the second packet being needed 675/676? – Timothy Jones Apr 22 '16 at 19:02