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 $X_n$ will take to return to its starting position? (b) What is the probability $X_n$ will visit all the other states before returning to its starting position?
I can see that we simply have a doubly stochastic 12×12 matrix, with $P_x(x, x+1) = P_x(x, x-1) = 1/2$ (here assuming 12 + 1 = 1). Thus, the stationary distribution $\pi[i] = 1/12$ for all $i \in [1:12]$. Then, the expected number of steps from any $i$ to $i$ is simply $1 / \pi[i] = 12$, right?
(b) is a little trickier – we know that all states here are null recurrent. However, I'm not sure how to think about this probability. Any tips?
Best Answer
For part (b), assume (without loss of generality) that from state 1 we went to state 2 and not state 12 (it does not matter, because the ring is symmetric).
Then we want to know the probability, starting at state 2, that we reach state 12 before getting to state 1.
Let $p_k$ be the probability, starting at state $k$, that we reach state 12 before getting to state 1. Then $p_1 = 0$, $p_{12} = 1$, and $p_k = \frac{p_{k+1} + p_{k-1}}{2}$ for $2 \le k \le 11$.
We can just solve this system of equations directly, getting $p_k = \frac{k-1}{11}$ for all $k$, or we can use some trickery.
Here's one "trickery" way to do it. Imagine a betting game in which you start with 2 dollars, and every time you bet you either win or lose a dollar with equal probability. If you keep playing until you get to 12 dollars or have 1 dollar left what is the expected amount of money you have at the end?
Setting these equal, we get $12p_2 + (1-p_2) = 2$, or $p_2 =\frac1{11}$.