A space alien is doing a random walk starting at $0$ on the nonnegative number line. From $0$ the alien must take one step to the right (to $1$), but from any positive position on the line, the alien will move one step left or right with equal probability. What is the expected number of times that the alien will revisit $0$ before the first time that he visits $5$?
I set up the following equations$$E_0 = E_1, \quad E_1 = {1\over2}(E_0 + 1) + {1\over2}E_2, \quad E_2 = {1\over2}(E_1 + E_3), \quad E_3 = {1\over2}(E_2 + E_4), \quad E_4 = {1\over2}E_3 + {1\over2}$$When I solve this I get $E_0 = 5$. However, the solution at the back of my book sets up the following equations, where the last equation is different:$$E_0 = E_1, \quad E_1 = {1\over2}(E_0 + 1) + {1\over2}E_2, \quad E_2 = {1\over2}(E_1 + E_3), \quad E_3 = {1\over2}(E_2 + E_4), \quad E_4 = {1\over2}E_3$$And so the actual answer should be $E_0 = 4$. Can anyone explain why $E_4 = {1\over2}E_3$ is correct and $E_4 = {1\over2}E_3 + {1\over2}$ is wrong?
Best Answer
I assume that $E_i$ with $i \in \{0,\dots, 5\}$ denotes the expected value of visits at $i$. Then we can write down the equation for each $E_i$ using the information we know about the direct neighbours of $i$. $E_0$ and $E_4$ are special cases: $0$ has obviously only one neighbour. The neighbours of $4$ are $3$ and $5$. But since we stop the experiment when we reach $5$, the node $5$ has no impact on the expected value of its left neighbour $4$. That is why we only get $E_4=\frac{1}{2} E_3$ instead of $E_4=\frac{1}{2} E_3 + \frac{1}{2}$.