1
$\begingroup$

I am trying to understand the simple Coupon Collector Problem for $N$ coupon types with a single collection. Treating the expected time to get from 0 types in the collection to all $N$ types in the collection as a sum of expected times from $i$ types to $i+1$ types, and treating this time as a geometric random variable, it is easy to understand how the total expected time is calculated to be $NH_N$ where $H_N$ is the Harmonic number.

I would like to understand how to arrive at this conclusion using a Markov Chain approach. I have already read the explanation given by owen88 about exactly this problem, at the link: Coupon collector problem and Markov chains

What I do not understand is how the linear system for the expected time is deduced, i.e. how does one deduce that $E_{m,n} = 1 + \sum_{k} E_{k,n} P_{m,k}$ where $E_{m,n}$ is the expected time to go from $m$ coupons in the collection to $n$ coupons.

Any help would be greatly appreciated. This model generation has had me stumped for an entire day. Thank you.

$\endgroup$
4
  • $\begingroup$ Let $k$ be the nodes that we can visit from $m$ via a single hop, $1$ comes from that, remember that we move to a particular node $k$ via a transition probability $P_{m,k}$. Now assume that we are at node $k$ what would be the expected steps to reach to $n$, using the same definition as $E_{m,n}$ we can deduce it to be $E_{k,n}$. Simply we are conditioning our expectation to the first step to find it. $\endgroup$
    – keoxkeox
    Commented Aug 21, 2019 at 0:09
  • $\begingroup$ @keoxkeox I'd like to clarify your comment. So if K is the set of all states we can visit from m, then $k \epsilon K$. So we can go to two states from $m$, either $m$ itself or $m+1$. I can somewhat see where the summation comes from, but I still don't know how that accounts for the 1. $\endgroup$
    – arnavlohe15
    Commented Aug 21, 2019 at 1:05
  • $\begingroup$ Because you always have $1$ step. You open the box, and take the coupons out. That's one step. Then, depending on what coupons you already had and what you found in the box, you move to a new state. The summation represents the expected number of additional steps to finish from the new state. $\endgroup$
    – saulspatz
    Commented Aug 21, 2019 at 2:50
  • $\begingroup$ @arnavlohe15 $K$ is the set of all states we can visit from $m$ after 1 state transition. Note that $K$ can contain $m$ obviously, however, I believe I may have added more to your confusion. I will be talking in the context of $m \neq n$, since $E_{m,m}=0$. For $m=0$ you can only move to $m=1$, so $E_{0,1}=1$. From $m=1$ $E_{1,2}=1 \times P_{1,2} + (1+E_{1,2}) \times P_{1,1} $. You can repeat this pattern. The deduction with $k$ is for a more general approach and writing these problems in recurrence equations is a typical trick, in your problem $k$ is not an arbitrarily large set of integers. $\endgroup$
    – keoxkeox
    Commented Aug 21, 2019 at 10:18

1 Answer 1

Reset to default
1
$\begingroup$

The question has already been answered in the comments. The term $1$ accounts for the $1$ coupon that is drawn in the step under consideration. The sum accounts for the expected number of coupons to be drawn after this step, with the expected number for each state being weighted by the probability of transitioning to that state from the current state.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .