Suppose there is a Markov chain with K states {1,2,...,K} arranged clockwise on a circle. $Z_0$ = 1 The probability of moving clockwise is $p$ and the probability of moving counterclockwise is $1-p$. Then what's the probability that the Markov chain complete a clockwise circle before a counterclockwise one? In addition, I'm also interested in the long run average number of loops completed, i.e., $\lim_{n\to\infty} L(n)/n = ?$, where $L(n)$ is the number of loops completed by time n.

I don't know how I should approach this question. Any help is appreciated!

  • $\begingroup$ When you talk about "number of loops" do you mean to keep track of the loop direction, so $L(n)$ is a winding number? $\endgroup$ – kimchi lover Jun 8 at 22:00
  • $\begingroup$ No just the number of loops including clockwise and counterclockwise $\endgroup$ – Chloe Jun 9 at 3:09

The first question is equivalent to a random walk on $\{-K,-(K-1),\dots,0,\dots,K-1,K\}$ starting at $0$ and taking a step to the right with probability $p$ or to the left with probability $1-p$, and asking the probability that the walk reaches $K$ before $-K$; presumably this is a standard problem that has been answered before.

For the second question, the expected number of (signed) clockwise steps per turn is $p-(1-p) = 1-2p$, and so the expected number of (signed) clockwise loops in $n$ steps is $n(1-2p)/K$. It becomes more difficult if you care about unsigned loops, "starting over" every time a loop is completed.

  • $\begingroup$ $p-(1-p) = 2p-1$. $\endgroup$ – Fabio Somenzi Jun 8 at 23:46

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.