# Probability of visiting all other states before return

Question (a)

Random walk on a clock. Consider the numbers $1, 2, \dots, 12$ written around a clock. Consider a Markov chain that jumps with equal probability to one of the two adjacent numbers each step.

• What is the expected number of steps that $X_n$ will will take to return to its starting position?

(My Work)

From a result in class, we know that a doubly stochastic transition matrix $p$ for a Markov Chain with $12$ states has the uniform distribution $\pi(x) = 1/12$ for all $x$ as a stationary distribution. We also know that if the chain is irreducible and there exists a stationary distribution (both hypotheses are satisfied) $\pi(y) = {1\over E_yT_y}$, so the expected time of first return ($E_yT_y$) is 12.

Question (b)

• What is the probability that $X_n$ will visit all of the other states before returning to its starting position?

My Question

I am not sure how to compute this probability. My first intuition was to consider $P(T_y > 12)$, but further considering the problem, this seems incorrect because the chain does not have to visit all states before move 12.

• I don't have a full solution, but my guess is that solving this would involving inverting the problem. Call $P_{*n}$ the probability that it will visit the same state in exactly $n$ stops. $P_{*2}$ = 1/12 $P_{*3}$ = 11/12*2/12 = 22/144 = 11/72 – Peter Flom Sep 24 '12 at 0:27
• Oh, and then, sum from $P_{*2}$ to $P_{*11}$ and subtract that from 1 to get your answer. – Peter Flom Sep 24 '12 at 0:35
• This looks equivalent to computing $1 - P(T_y > 12)$ to me? How is it different? – Moderat Sep 24 '12 at 0:56
• Hmm. Maybe it isn't different. But then why does it assume that the chain has to visit all states before move 12? I don't see that. – Peter Flom Sep 24 '12 at 1:03
• I think that is what you assume when you "sum from 2 to 11"? Why $P_{*n}$ for $n \ge 12$ not accounted for? These are the probabilities, now I think I may need to take expectations... – Moderat Sep 24 '12 at 1:05

For part (b), you definitely want to use the structure of the graph. Without loss of generality suppose you start at $12$ and your first step is to $1$. Can you say what the probability is that you hit $11$ before you hit $12$?
• I'm not sure what you mean about the probability of being at $11$. If you are at $1$ after the first step, then with probability $1$ you will get to $11$ without first returning $12$, or else you will get to $12$ without first visiting $11$. If you go from $1$ to $11$, a priori that could be two net counterclockwise steps or ten net clockwise steps, but if you know that you don't visit $12$ on the way, you can rule out one of these. – Douglas Zare Sep 24 '12 at 3:46
• So we went over Exit Distributions today, and for this problem, would I consider that the probability of going from $1$ to $11$ before $12$ equal to $g(x) = 1 + \sum_y p(x,y)g(y)$ where $g(x)$ is the expected time to complete the circuit when you are at $x$? – Moderat Sep 26 '12 at 2:15
• Once you get to $1$, think of $11$ and $12$ as absorbing states. – Douglas Zare Sep 26 '12 at 19:51