I have very limited probability background, but I came across a problem in an engineering application:

Is there a formula that computes the average number of steps taken for a particle beginning at the origin to return to the origin if it has equal probabilities of moving left and right on a 1d chain, given that at some point n/2 to the right the particle gets reflected (P = 1 to left), and some point -n/2 to the left the particle also gets reflected (P = 1 to the right)?

  • $\begingroup$ I will assume $n = 2m$ is even. For $k = 1,\ldots,m$, let $T_k$ be the expected time for a particle start at $k$ and return to origin. Set $T_0 = 0$. Convince yourself the time you want equals to $T_1 + 1$ and $T_k$ satisfies a recurrence relation $$T_k = \frac12(T_{k+1} + T_{k-1}) + 1\quad\text{ for } 1 \le k < m$$ with boundary condition $T_m = T_{m-1} + 1$. Solve that and you will get $T_1 + 1 = 2m$. $\endgroup$ – achille hui Apr 23 at 5:16

In a Markov chain with limiting distribution $\vec{\pi}$, it takes $\frac1{\pi_i}$ expected time to return to state $i$ starting from that state. So it's enough to compute the limiting distribution of this Markov chain.

Rather than have reflective barriers at $-\frac n2$ and $\frac n2$, it is equivalent to make the Markov chain periodic modulo $n$, so that state $n$ is the same as state $0$. When you're at state $\frac n2$ in the periodic Markov chain, you can move to $\frac n2 -1$ or $\frac n2 + 1$, but either way you get $1$ step closer to $0$ - same as in the reflective Markov chain.

In the periodic Markov chain, it is easy to see that $\pi_0 = \frac1n$ by symmetry: there are $n$ indistinguishable states. Therefore the average return time is $\frac1{\pi_0} = n$.


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.