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.

  • 1
    $\begingroup$ 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 $\endgroup$ – Peter Flom Sep 24 '12 at 0:27
  • $\begingroup$ Oh, and then, sum from $P_{*2}$ to $P_{*11}$ and subtract that from 1 to get your answer. $\endgroup$ – Peter Flom Sep 24 '12 at 0:35
  • $\begingroup$ This looks equivalent to computing $1 - P(T_y > 12)$ to me? How is it different? $\endgroup$ – Moderat Sep 24 '12 at 0:56
  • $\begingroup$ 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. $\endgroup$ – Peter Flom Sep 24 '12 at 1:03
  • $\begingroup$ 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... $\endgroup$ – Moderat Sep 24 '12 at 1:05

This looks like homework so I'm trying to give a hint, not a solution.

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$?

| cite | improve this answer | |
  • $\begingroup$ Would this be the probability of going from 11 to 12, times the probability of being at 11? I am unsure how to rule out being at 12... $\endgroup$ – Moderat Sep 24 '12 at 1:51
  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Sep 24 '12 at 3:46
  • $\begingroup$ 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$? $\endgroup$ – Moderat Sep 26 '12 at 2:15
  • $\begingroup$ @jmi4: I'm not sure what you mean by the time to complete the circuit. $\endgroup$ – Douglas Zare Sep 26 '12 at 2:50
  • 1
    $\begingroup$ Once you get to $1$, think of $11$ and $12$ as absorbing states. $\endgroup$ – Douglas Zare Sep 26 '12 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.