Consider the numbers 1, 2,..., 12 written around a ring as they usually are on a clock. Consider a Markov chain that at any point jumps with equal probability to the two adjacent numbers. Let this Markov chain be denoted X_{n}.

What is the probability X_{n} will visit all the other states before returning to its starting position ?

* First approach:

I think we may assume WLOG that the starting position is 1 (for the probability we want to compute is invariant under changing the starting position, by symmetry).

Define for every state j = 1, 2,... a r.v. T_{j} := min{ n > 0 | X_{n} = j}. This is the "first time after time 0 that the Markov chain will visit state j".

I think the probability we need to compute is then

P{ max(T_{2}, T_{3},...,T_{12}) < T_1 | X_{0} = 1 }.

But how to calculate this thing ?

* Second approach (more intuitive). The asked probability is the probability that you can go "around to the right" in 12 steps (exactly 10 possibilities) + the probability that you can go around to the right in 14 steps + the probability that you can go around to the right in 16 + ...

The problem is: consider for example the case "14 steps". It's hard to calculate in how many ways this can be done if you think about it...

I therefore think my first approach is certainly best, but how do you tackle this kind of problem ?

Thanks for the work!

What is the probability X_{n} will visit all the other states before returning to its starting position ?

* First approach:

I think we may assume WLOG that the starting position is 1 (for the probability we want to compute is invariant under changing the starting position, by symmetry).

Define for every state j = 1, 2,... a r.v. T_{j} := min{ n > 0 | X_{n} = j}. This is the "first time after time 0 that the Markov chain will visit state j".

I think the probability we need to compute is then

P{ max(T_{2}, T_{3},...,T_{12}) < T_1 | X_{0} = 1 }.

But how to calculate this thing ?

* Second approach (more intuitive). The asked probability is the probability that you can go "around to the right" in 12 steps (exactly 10 possibilities) + the probability that you can go around to the right in 14 steps + the probability that you can go around to the right in 16 + ...

The problem is: consider for example the case "14 steps". It's hard to calculate in how many ways this can be done if you think about it...

I therefore think my first approach is certainly best, but how do you tackle this kind of problem ?

Thanks for the work!

Last edited: