6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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
    Commented Sep 24, 2012 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
    Commented Sep 24, 2012 at 0:35
  • $\begingroup$ This looks equivalent to computing $1 - P(T_y > 12)$ to me? How is it different? $\endgroup$
    – Moderat
    Commented Sep 24, 2012 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
    Commented Sep 24, 2012 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
    Commented Sep 24, 2012 at 1:05

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\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
    Commented Sep 24, 2012 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
    Commented Sep 24, 2012 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
    Commented Sep 26, 2012 at 2:15
  • $\begingroup$ @jmi4: I'm not sure what you mean by the time to complete the circuit. $\endgroup$
    – Douglas Zare
    Commented Sep 26, 2012 at 2:50
  • 1
    $\begingroup$ Once you get to $1$, think of $11$ and $12$ as absorbing states. $\endgroup$
    – Douglas Zare
    Commented Sep 26, 2012 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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