I'm dealing with a very slight variation of the Coupon Collector's problem. I have four coupons, and I'm trying to find out the expected number of boxes I have to purchase to get each coupon and from this find out how many boxes I'll have to buy to get every coupon. Each box has a $\frac{1}{2}$ probability of having a coupon in it.
Here's how I see it:
This problem is clearly based on the geometric rv because it's based on waiting until successes. I define a rv $X\sim Geo(p)$. It is known that $E[X] = \frac{1}{p}$.
Now, I have a $\frac{n}{n} = 1$ probability of receiving a coupon on the first box I open. Additionally, the probability that a given box has a coupon in it is $\frac{1}{2}$. Let us designate event A to be the event in which a given box has a coupon, and event B to be the event in which a given box has a coupon which we have not yet received. As we are looking for the event where a box has a coupon and it is a coupon we have not received yet, it is the intersection of these two events. As the two events are independent of each other, we find that $P(A\cap B) = P(A)P(B)$.
In our search for the distinct coupons, the first coupon we have received must be unique as we have not received any coupons yet. Thus, the parameter $p$ of $X_1$ is defined to be $P(A)P(B) = 1*\frac{1}{2}$
So, $E[X_1] = \frac{1}{\frac{1}{2}} = 2$.
More generally, as we collect new coupons, $P(\text{Unseen Coupon}) = \frac{n-k}{k}$ for $0\le K < 4$ , where $K$ = the number of distinct coupons seen so far.
Thus...
$$E[X_2] = \frac{1}{\frac{1}{2}*\frac{3}{4}} = \frac{8}{3}$$
$$E[X_3] = \frac{1}{\frac{1}{2}*\frac{2}{4}} = 4$$
$$E[X_4] = \frac{1}{\frac{1}{2}*\frac{1}{4}} = 8$$
Now that I have the expected number of boxes for each situation, the total number of boxes I have to collect is just equal to the summation of the above events and is thus $\frac{50}{3}$.
Does this seem correct?
Answer
Community wiki answer so the question can be marked as answered:
As noted in the comments, your result, and your reasoning as far as it is clear, are correct. Also as mentioned in the comments, a more direct way would be to note that the probability of finding a new coupon is halved for each draw, hence all expected numbers of draws for finding new coupons are doubled, hence the total expected number of draws, which is their sum, is doubled.
No comments:
Post a Comment