1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Markov chains are the way! $\endgroup$ – Lord Shark the Unknown Jan 19 at 5:20
  • $\begingroup$ @LordSharktheUnknown Can you elaborate in an answer how to use them in order to solve this problem? Like I said, I have a limited understanding of them. $\endgroup$ – automaticallyGenerated Jan 19 at 5:31
  • $\begingroup$ I'have taken the liberty to modifiy your title and tags (3 tags are a good average) in order more readers are directed towards this interesting question and its interesting answer $\endgroup$ – Jean Marie Feb 15 at 12:27
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the clear answer. I think that this is just a disguised Markov chain, as your "M" is the identity matrix minus the transition matrix. $\endgroup$ – automaticallyGenerated Jan 21 at 14:30
  • $\begingroup$ Not quite. The identity matrix minus the transition matrix is a singular $\ b\times b\ $ matrix. $\ M\ $ is the submatrix obtained from it by chopping off its last row and column. But you're right that there is indeed a Markov chain lurking in the shadows. $\endgroup$ – lonza leggiera Jan 21 at 23:27

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.