1

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

Drew Lilley
  • 13
  • 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$. – achille hui Apr 23 '19 at 05:16

1 Answers1

3

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

Misha Lavrov
  • 142,276