Expected number of steps in a 1D random walk with reflecting edges

Question

Assume there is a row of $k$ tiles. A creature (monkey in some situations, ant in others, frog in others) lies on tile $a$. There is a 50% probability that the creature jumps to tile $a-1$ and a 50% probability that the creature jumps to tile $a+1$, unless it is on an edge tile. If it is on an edge tile, it must jump inwards, so it can't escape the system (i.e. tile 2 from tile 1 and tile $k-1$ from tile $k$). What is the expected number of steps for it to first reach tile $b$? $1<=a, b<=k$ is assumed. I feel like Markov chains might be used to get the answer, but I have a very limited understanding of them. If there is a closed form for the answer as well as a derivation for understanding, that would be perfect.

Answer 1

Amazingly (to me) there happens to be a very simple expression for the expected number of steps to reach $\ b\ $ from $\ a\ $. For $\ a < b\ $, it is: $$ \left(\,b + a -2\,\right)\,\left(\,b-a\,\right)\ . $$ Although a Markov chain is the obvious way to model the process, and I'm sure it could used to derive the above result, there turns out to be a less cumbersome way of doing it.

For each $\ i\ $ between $\ 1\ $ and $\ b\ $ inclusive, let $\ e_i\ $ be the expected number of steps the creature takes to go from $\ i\ $ to $\ b\ $. Obviously, $\ e_b\ = 0\ $.

If the creature starts from $\ 1\ $, then it has to take one step to $\ 2\ $, from which the expected number of steps to reach $\ b\ $ is $\ e_2\ $. Thus, the expected number of steps, $\ e_1\ $, to reach $\ b\ $ from $\ 1\ $ is $\ e_2 + 1\ $.

If the creature starts from $\ b-1\ $, then with probability $\ \frac{1}{2}\ $ it reaches $\ b\ $ on the very next step—that is, in just a single step—, and with probability $\ \frac{1}{2}\ $ it jumps to $\ b-2\ $, from which the expected number of steps to reach $\ b\ $ is $\ e_{b-2}\ $. Thus $\ e_{b-1} = \frac{1}{2}\left(e_{b-2} +1\right) + \frac{1}{2}\,1=\frac{1}{2}\,e_{b-2}+1\ $.

If the creature starts from any other point $\ i\ $, with $\ 2\le i\le b-2\ $, then with probability $\ \frac{1}{2}\ $ it jumps to $\ i-1\ $, from which the expected number of steps to reach $\ b\ $ is $\ e_{i-1}\ $, and with probability $\ \frac{1}{2}\ $ it jumps to $\ i+1\ $, from which the expected number of steps to reach $\ b\ $ is $\ e_{i+1}\ $. Therefore, $\ e_i = \frac{1}{2}\left(e_{i-1} +1\right) + \frac{1}{2}\left(e_{i+1} +1\right)= \frac{1}{2}\,e_{i-1} + \frac{1}{2}\,e_{i+1} +1\ $.

Putting this all together, we have

\begin{eqnarray} e_1 &=& e_2 + 1\\ e_i &=& \frac{1}{2}\,e_{i-1} + \frac{1}{2}\,e_{i+1} +1, \ \ \mbox{for } i=2,3, \dots, b-2\ \mbox{, and}\\ e_{b-1} &=& \frac{1}{2}\,e_{b-2}+1\ , \end{eqnarray} or, equivalently,

\begin{eqnarray} e_1 - e_2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ &=& 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ -\frac{1}{2}\,e_{i-1} + e_i -\frac{1}{2}\,e_{i+1} &=& 1, \ \ \mbox{for } i=2,3, \dots, b-2\ \mbox{, and}\\ -\frac{1}{2}\,e_{b-2}+e_{b-1} &=& 1\ . \end{eqnarray}

These equations can be written as: $$ M\,e = \mathbb 1\ , $$ where $\ M\ $ is the $\ \left(\,b-1\,\right)\times\left(\,b-1\,\right)\ $ matrix, and $\ \mathbb 1\ $ the $\ \left(\,b-1\,\right)\times\,1\ $ column vector, whose entries are given by: \begin{eqnarray} M_{1,2} &=& -1\\ M_{i,i} &=& 1\ \ \mbox{for } i=1,2,\dots, b-1\\ M_{i,i-1} &=& -\frac{1}{2}\ \ \mbox{for } i=2,3,\dots, b-1\\ M_{i,i+1} &=& -\frac{1}{2}\ \ \mbox{for } i=2,3,\dots, b-2\\ M_{i,\,j} &=& 0 \ \ \mbox{for all other }\ i, j\\ \mathbb 1_i &=& 1\ \ \mbox{for } i=1,2,\dots, b-1\ . \end{eqnarray} For $\ b=6\ $, the matrix $\ M\ $ looks like this: $$\left(\begin{matrix}1&-1&0&0&0 \\ -\frac{1}{2}&1&-\frac{1}{2}&0&0\\ 0&-\frac{1}{2}&1&-\frac{1}{2}&0\\ 0&0&-\frac{1}{2}&1&-\frac{1}{2}\\ 0&0&0&-\frac{1}{2}&1& \end{matrix}\right)\ ,$$ and has the following inverse: $$ M^{-1} = \left(\begin{matrix} 5&8&6&4&2\\ 4&8&6&4&2\\ 3&6&6&4&2\\ 2&4&4&4&2\\ 1&2&2&2&2\\ \end{matrix}\right)\ . $$ From this, we can conjecture that the entries of the inverse of the $\ \left(\,b-1\,\right)\times\left(\,b-1\,\right)\ $ matrix $\ M\ $, defined above, should be the matrix $\ L\ $ whose entries are given by: \begin{eqnarray} L_{i,1} &=& b-i\ \ \mbox{for } i=1,2,\dots, b-1\\ L_{1,\,j} &=& 2\,\left(b-j\right) \ \mbox{for } j=2,3,\dots, b-1\\ L_{i,\,j} &=& 2\,\min\left(b-i,b-j\right) \ \mbox{for } 2\le i\le b-1\ \ \mbox{and }\ 2\le j\le b-1\ , \end{eqnarray} and on checking the product $\ M\,L\ $, we find that it is indeed the $\ \left(\,b-1\,\right)\times\left(\,b-1\,\right)\ $ identity matrix. So, finally, we have: $$ e = M^{-1}\,\mathbb 1 = L\,\mathbb 1\ , $$ and $\ e_a\ $, the expected number of steps to get to $\ b\ $ from $\ a\ $ is the sum of the entries in the $\ a^\mbox{th}\ $ row of $\ L\ $: \begin{eqnarray} e_a &=& \left(b-a\right) + 2\,\left(\,a-1\,\right)\,\left(\,b-a\,\right) + 2\,\sum_{j=1}^{b-a-1} j\\ &=& \left(\,b + a -2\,\right)\,\left(\,b-a\,\right)\ , \end{eqnarray} as stated above.