Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I'm playing the FIFA Panini Online Sticker Album, which is an Internet adaption of the classic Panini albums that are usually published for the soccer world cup, European championship, and possibly other tournaments.

The album has placeholders for 424 different stickers. The purpose of the game is to collect all 424. The stickers come in packs of 5, which can be obtained through codes found online (or, in case of the classic printed album, bought at your local newsstand).

I make the following assumptions:

  • All stickers are published in the same quantity.
  • One pack of stickers does not contain duplicates.

How can I find out how many packs of stickers I need to acquire in order to be reasonably sure (let's say 90%) that I have all 424 unique stickers?

share|improve this question
1  
A number of insights can be gained from reading other questions relating to the coupon-collector problem. –  Glen_b Jun 5 at 10:24
3  
You need 700 packs; the chance of acquiring all 424 stickers then equals 90.0024%. 761 are needed to bring the chance to 95% and 898 for a 99% chance. (On average, almost 560 packs are needed to complete the set. It is unlikely (less than once chance in a thousand) that fewer than 352 would be needed.) –  whuber Jun 5 at 11:51
1  
I'm not sure the first assumption can be made. "Shinies" tend to be rarer. –  James Jun 5 at 14:53
1  
Hmm, from what I could read from the document posted by Asuranceturix, they proved that there was no significant difference. –  Vidar S. Ramdal Jun 5 at 15:05
    
@VidarS.Ramdal I stand corrected. –  James Jun 5 at 16:05
add comment

2 Answers 2

up vote 11 down vote accepted

That is a beautiful Coupon Collector's Problem, with a little twist introduced by the fact that stickers come in packs of 5.

If the stickers were bought individually the result are known, as you can see here.

All the estimates for a 90% upper bound for individually-bought stickers are also upper bounds for the problem with a pack of 5, but a less close upper bound.

I think that getting a better 90%-probability upper bound, using the pack of 5 dependence, would get a lot more difficult and would not give you a far better result.

So, using the tail estimate $ P[T>\beta n \log n] \leq n^{-\beta+1}$ with $n=424$ and $n^{-\beta+1} = 0.1$, you'll get to a good answer.

EDIT:

The article "The collector’s problem with group drawings" (Wolfgang Stadje), a reference of the article brought by Assuranceturix, presents an exact analytical solution for the Coupon Collector's Problem with "sticker packs".

Before writing the theorem, some notation definitions: $S$ would be the set of all possible stickers, $s = |S|$. $A \subset S$ would be the subset that interests you (in the OP, $A = S$), and $l = |A|$. We're going to draw, with replacement, $k$ random subsets of $m$ different stickers. $X_{k}(A)$ will be the number of elements of $A$ that appear in at least one of those subsets.

The theorem says that:

$$ P(X_{k}(A) = n) = {l \choose n} \sum_{j=0}^{n}(-1)^j {n \choose j}[{s+n-l-j \choose m}/{s \choose m}]^k $$

So, for the OP we have $ l=s=n=424$ and $m=5$. I did some tries with values of $k$ near the estimate for the classical coupon collector's problem (729 packs) and I got a probability of 90.02% for k equals to 700.

So it was not so far from the upper bound :)

share|improve this answer
    
And this good answer would? –  ziggystar Jun 5 at 10:06
4  
About 3642 random stickers. So the upper bound for the "pack of 5 problem" would be something less than 729 packs. –  eqperes Jun 5 at 10:52
add comment

The other day I came across a paper that addresses a closely related question:

http://www.unige.ch/math/folks/velenik/Vulg/Paninimania.pdf

If I have understood it correctly, the expected number of packs you would need to buy would be:

$\binom{424}{5}\sum_{j=1}^{424}\left(-1\right)^{j+1}\frac{\binom{424}{j}}{\binom{424}{5}-\binom{424-j}{5}}$

However, as eqperes points out in the comments, the specific question the OP asks is actually covered in detail in another paper that is not open access.

Their final conclusion suggests the following strategy (for an album of 660 stickers):

  • Buy a box of 100 packs of 5 stickers (500 stickers, guaranteed to be all different)
  • Buy 40 more packs of 5 stickers and swap the duplicates until you have at most 50 missing stickers.
  • Purchase the remaining stickers directly from Panini (these cost approx. 1.5 times as much).

This is total of 140 packs + upto 15 extra packs worth of stickers (by cost) purchased in a targeted fashion, equivalent to at most 155 packs.

share|improve this answer
    
Great! It seems that the central argument of their results would be in the "The collector’s problem with group drawings" article, that is sadly not in open access. –  eqperes Jun 5 at 10:56
    
Haha, that's great! They also go into detail on how swapping affects the result (which I left out of the question). Very interesting, thanks! –  Vidar S. Ramdal Jun 5 at 10:57
3  
Can you summarize the solution to the OP's problem provided by the paper? Links sometimes expire and then this answer will become less useful. –  Andy Jun 5 at 11:15
    
@Andy: I have edited the answer to address your concern, but it is not exactly the answer to the original question. Unfortunately, the original paper that does provide that answer is too hard to read for me, sorry. –  Asuranceturix Jun 5 at 14:29
    
I am dubious about a box of 100 packs containing only distinct stickers. This seems like it would cause huge and unnecessary manufacturing complication for little benefit. –  jwg Jun 6 at 9:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.