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.
 A: 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:


*

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

*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... .)
A: 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.
