# Homework Help: Coupon collector problem

1. Oct 18, 2012

### CAF123

1. The problem statement, all variables and given/known data
Suppose that you continually collect coupons and that there are m different types. Suppose also that each time a new coupon is obtained, it is a type i coupon with probability $p_{i}$, i = 1,.. m. Suppose you have just collected your n th coupon. What is the probability that it is a new type?
Hint: condition on the type of coupon

3. The attempt at a solution
I said that after (n-1) collected coupons, the prob that you collected a specific coupon is (1/m)^(n-1) => the prob that you didn't collect a specific coupon was (1-(1/m))^(n-1).

I also let $A_{i}$ be the event that a new coupon was collected on collection i and I wanted to determine $P(A_{n})$ but I ddn't get very far with this approach.
I am unsure of what to try next.
Thanks
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Oct 18, 2012

### tiny-tim

Hi CAF123!
Since the probability is ∑ pi for the types so far,

but even if you know which types so far, you don't know how many of them,

i'd try 1 - ∑ pi for the types not so far (since you know there's exactly 0 of them!).

3. Oct 18, 2012

### Ray Vickson

The question is somewhat ambiguous, but I interpret "collected your nth coupon" to mean that you finally have n different types in your collection, but you may have purchased many more and thrown many away because they were not different from one you had already. (That is the standard interpretation in the so-called coupon collector's problem.)

Your proposed solution does not account properly for the fact that n (different) types have been collected already. For example, in the classical problem we have all p_i = 1/m for i = 1,2, ..., m. If n = 1 the probability that the next purchased coupon is the same as the first one is 1/m, so the probability that it is different is 1-1/m. By the time you have collected n = m-1 different coupons, the probability that the next purchased coupon is different is 1/m. Things to the power of n do not come into it.

However, what is worse is that your solution does not account for the fact that different coupons have different probabilities p_i. I will just look at the second coupon. After collecting 1 coupon, what is the probability that your second purchased coupon is different from it? Look instead at the probability it is the same. If we don't observe exactly what the first collected coupon is (say a friend is collecting coupons for us in another room and we don't see what is happening---all we get is a signal saying "same" or "different"). In that type of scenario, the probability of S (same) given the first is of type i (event Fi) is
$$P\{S\} = \sum_{i=1}^m P(S|F_i) P(F_i) = \sum p_i \cdot p_i = \sum p_i^2.$$ So, the probability your next purchased coupon is different from the first one is $1 - \sum p_i^2.$ This is the result you want if n = 1.

Things start to get complicated if you have already collected n = 2 different coupons, and they are even worse for n = 3, etc.

However, maybe the problem assumes you _do_ know what coupons have already been collected. By relabelling if necessary, assume you already have coupons 1,2, ...,n and want to know the probability of collecting coupon n+1 or n+2 or ..., or coupon m on the next purchase. Can you see how to compute that?

RGV

Last edited: Oct 19, 2012
4. Oct 19, 2012

### CAF123

I think the problem assumes you know what coupons have been collected before the nth collection (at least that is what i understood). I don't see how to compute what you have suggested. Can you give some hints?

5. Oct 19, 2012

### Ray Vickson

I have edited my original message; refer to the revised version.

RGV

6. Oct 19, 2012

### CAF123

I don't quite see how to compute this. Any hints?