Question

Random walk on a clock. 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. (a) What is the
expected number of steps that Xn will take to return to its starting position?

Answer 1

I think you can simplify your problem a bit by considering the following
13 states markov chain X:
,
i.e. both state 0 and 12 are the absorbing states


i.e. A simple random walk model

surely

Absorbing in state 0 means that you go back to the original position without
visiting all the other states, while absorbing in state 12 means you have
already visiting all the other states.

We start in state 1 as it denotes the first reached adjacent state from the
original state.

So you want to calculate the probability of absorbing in state 12.

Since now in this case ,
the required probability is simply

Answer 2

I think you can simplify your problem a bit by considering the following
13 states {0, 1, 2, ..., 12} markov chain X:

Pr{X_{k+1} = 0|X_{k} = 0} = Pr{X_{k+1} = 12|X_{k} = 12} = 1,
i.e. both state 0 and 12 are the absorbing states

Pr{X_{k+1} = i - 1|X_{k} = i} = Pr{X_{k+1} = i + 1|X_{k} = i} = frac {1} {2}, ~ i = 1, 2, ..., 11
i.e. A simple random walk model

X_{0} = 1 surely

Absorbing in state 0 means that you go back to the original position without
visiting all the other states, while absorbing in state 11 means you have
already visiting all the other states.

We start in state 1 as it denotes the first reached adjacent state from the
original state.

So you want to calculate the probability of absorbing in state 11.

Since now in this case p = 1/2
the required probability is simply=1/11

Answer 3

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 equalprobability 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, bysymmetry).

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 statej".


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...