Tagged: problem

May 3, 2014

How Many Purchasing do You Need to Gather All Collection of Gifts?

We often find interesting marketing strategy of some cereal manufacture, that is providing some “action figures” in the box wrap. Of course there are many collection of the figure gifts, and yet you can not confirm what kind of figure you will get whenever you buy a box until you purchase it and open the seal. Suppose there are 10 kinds of figure collection. If you are lucky enough, you may gather all of the collection in 10 purchasing in a row, or that means that you always get a different collection every time you buy a cereal! What a lovely event! However, you may also experience some frustrating moment where you have gather 9 collections and you never get the 10th, although you have purchased a numerous cereals (and unfortunately, the cereal is never get eaten!). You buy a cereal and you think that this time you must get the 10th one, but that is not happening! Damn! The company is cheating me! How many more I should buy to get the 10th one? Does that 10-different-gifts-in-row event that rare? Can I be that lucky one?

These questions give us a very interesting mathematical problem, namely coupon collector problem. Suppose there are $d$ collection of figure. How many purchasing do you expect to collect all the $d$ collection? In the calculation of the expectation, we may find many interesting combinatorial properties involving in the progress. OK, let us start!

First, we define a sequence of event $\{A_n\}_1^\infty$ for each $n, A_n$ represent an event of in the n-th purchasing, for the first time you gather every $d$ collections. Let $p_n$ be the probability of the event $A_n$ , which is $p_n=P(A_n)$ . Well, the event $A_n$ is completely the event you really want to experience. Clearly that if we have the event $A_n$ , then the number of purchasing we need is $n$ . It would be very nice if $n$ is as small as possible. However, we are about to calculate for which value of $n$ in which most likely everybody experience the event $A_n$ ? By the basic statistics, we have the expectation of the number of purchasing needed to collect all the collection is $\mu=\sum\limits_{n\geq 1} np_n$ .

Next, how would we calculate the value of $p_n$ ? To begin this, we introduce the notion $\begin{Bmatrix} n \\ k \end{Bmatrix}$ , which denote the Stirling number of the second kind.

$\begin{Bmatrix} n \\ k \end{Bmatrix}$ = number of partitions of $\{1,2,\dots, n,\}$ into exactly $k$ class.

For example, if $n=4$ and $k=2$ , then we are about to collect every possible partitions of $\{1,2,3,4\}$ into exactly 2 class. Below is the lists of every possible partitions:

$\{ \{1,2\}, \{3,4\} \}$

$\{ \{1,3\}, \{2,4\} \}$

$\{ \{1,4\}, \{2,3\} \}$

This means that $\begin{Bmatrix} 4 \\ 2 \end{Bmatrix}=3$ . Note that the order of the classes in the partition is not considered significant. Well, now we are ready to calculate the value of $p_n$ .

The sample space of the event in this context is the set of all possible outcomes in the sequence of $n$ purchasing. For every purchase, we have $d$ possibilities of outcomes. Therefore the size of the sample space is $d^n$ . Now we move into how many possible outcomes in which the event $A_n$ happen. Suppose we have the event $A_n$ occurred, means that when you purchase the n-th cereal, for the first time, you get the last collection (one thing you’d die for) which you have not owned yet before. Surely this must be the very condition, right? So, we can partition the times of purchasing, $\{1,\dots,n\}$ , into exactly $d$ classes, which means that if $k$ belongs to the class $j$ , then in the purchasing of $k$ , you got the collection number $j$ . Of course you can not have a class of size zero, since you have to gather every collection in the $n$ purchasing. And also, $n$ must be in a class having no other else in that class, i.e $\{n\}$ must be a single class. This means, we should not worry about the class of $n$ , since it always to be solitary. However, we still deal with those $n-1$ purchasing before the last one over the $d-1$ choices of collectibles. So in order to produce the partition, we have $\begin{Bmatrix} n-1 \\ d-1 \end{Bmatrix}$ types of partitions. Moreover, since the order of the partition is such a matter for us, we multiply again this number to $d!$ , as we have $d$ classes in the partition.

Therefore, $p_n=\dfrac{d!\begin{Bmatrix} n-1 \\ d-1 \end{Bmatrix}}{d^n}$

However, how would we calculate the mean of number of purchasing? First we define a probability generating function of $p_n$ , which is

$P(x)=\sum\limits_{n\geq 1} p_n x^n$

By some combinatorial analysis, (I wouldn’t talk about this in this post, maybe later :D), we can get the formula of the GF:

$P(x)=\dfrac{x^d(d-1)!}{(x-d)(x-2d)\dots (x-(d-1)d)}$

However, we can compute the expectation by $\mu=P'(1)$ . Therefore, by differentiating the generating function, we can get

$\mu =d H_d$ where $H_d$ is the harmonic number $H_d=1+\frac{1}{2}+\dots + \frac{1}{d}$ and therefore the average number of purchasing so that you can collect every $d$ collectibles is $d\left(1+\frac{1}{2}+\dots + \frac{1}{d}\right)$ . (You could check by yourself if you want!) Seems not friendly enough to understand? Okay, let say $d=10$ . Then the average number is 10(1+1/2+1/3+…+1/10)=29.2897. This means most people complete the collections after the 29th purchasing. So, if you have bought 20 boxes, and you still have 7 collection, that’s fine. Everybody experience the same, you should ‘try’ harder! So, hey, what if the number of collectibles is not 10? Yes, you can compute the expected number by yourself. It’s easy enough to do naive computation by calculator. So, are you hunting for those gifts? You’d better check your lucky number!