Coupon Collector Problem Markov Chain Interpretation

310 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.