# How to prove Markov Chain formula?

I saw an question about how often should I roll a 6-face dice to get every number at least once.

I have read a lot of interesting answers but one of them caught my attention. It is one which imples Markov Chain.

Acording to the author

ThePawn has the right idea to attack the problem with a recurrence relationship. Consider a Markov chain with states ${0,…,6}$ corresponding to the count of the number of distinct dice rolls that have happened. State 0 is the start state, and state 6 is the finish state. Then, the probability of transition from state $i$ to itself is $\frac{i}{6}$. The probability of transition from state $i$ to state $i+1$ is $\frac{6-i}{6}$. Therefore the hitting time of the finish state is

$$\sum_{i=0}^5 \frac{6}{6-i} = 14.7$$

I would like to know which steps with more details that I need to develop in order to prove that summation formula.

What if I change the dice for a 8-faces dice or even if I put 2 6-dices rolling at the same time?

Thank you, guys! Luis P.

The expected hitting time is equal to the amount of time it takes to get from 0 to 6. At every jump of the Markov chain, you can either remain at the same state, i.e. you've thrown a number you already got before, or jump to the next state, meaning that you've collected a new number. Thus if $\tau$ is the total time it takes to get from 0 to 6 and $\tau_i$ is the time it took to get from $i$ to $i+1$, you want to calculate:

$$E[\tau]=E[\sum_{i=0}^{5}\tau_i]=\sum_{i=0}^5E[\tau_i],$$

by linearity of expectation.

Jumping from i to i+1 has has expected time:

$$E[\tau_i]=\sum_{k=0}^\infty k(i/6)^k (1-i/6),$$

i.e. the expected value of a geometric distribution with success probability $p=1-i/6$, which has expected value $6/(6-i)$. This is how you arrive at:

$$E[\tau]=\sum_{i=0}^5\frac{6}{6-i}$$

The generalized form of this problem is known as the coupon-collector problem.

• Beautiful! XXX Alex R. – Luis P. Feb 29 '16 at 21:33