Mr. Wilson is on a 10 meter bridge, 3 meters from the left side, moving 1 meter left or right each minute. However, Mr. Wilson refuses to get off the bridge at the right side. If he reaches the right side, on the next minute he will always move left. What is the expected number of minutes until he leaves the bridge (on the left side)?
Here's what I've done so far. We want to solve for $E_7$ given the following system of $10$ equations: $$E_0 = E_1 + 1$$ $$E_i = {1\over2}(E_{i + 1} + 1) + {1\over2}(E_{i - 1} + 1),\text{ }1 \le i \le 8$$ $$E_9 = {1\over2} + {1\over2}(E_8 + 1)$$
However, I'm not sure what to do from here. Can anyone help? Row reducing or inverting a $10 \times 10$ matrix seems like a lot of work so it seems like there should be a shortcut, given that this matrix will have a lot of $0$'s.
EDIT: Okay, I did some calculation and got $E_7 = 51$. Is that correct?
We can model this problem as an absorbing Markov chain. The standard notation is to have the absorbing state be the last, so I have written the Markov chain with transition matrix
$$ P = \left( \begin{array}{cccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ Let $Q$ denote the substochastic matrix obtained from $P$ corresponding to transitions between transient states, $R$ the substochastic matric obtained from $P$ corresponding to transitions from transient to absorbing states, $\mathbf 0$ the substochastic matrix obtained from $P$ corresponding to transitions from the absorbing state to transient states, and $I_r$ the the $r\times r$ identity matrix obtained from $P$ corresponding to transitions between absorbing states.
Now, since $Q$ is a strictly substochastic matrix, i.e. its entries are in $[0,1]$ and it has a row with an entry strictly less than one, by the well-known result on geometric series we see that $$ N := \sum_{k=0}^\infty Q^k = (I_t-Q)^{-1}, $$ where $I$ is the identity matrix with same dimensions as $Q$. Recall that the $(i,j)^{\mathsf{th}}$ entry of $Q^k$ is the probability of transitioning from state $i$ to state $j$ in exactly $k$ steps, and so indeed the $(i,j)^{\mathsf{th}}$ entry of $N$ is the expected number of times the chain visits state $j$, given that it started in state $i$. Here we have
\begin{align}\small N &= (I_t-Q)^{-1} \\&= \left(\left( \begin{array}{ccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right)-\left( \begin{array}{ccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 \\ \end{array} \right)\right)^{-1}\\ &= \left( \begin{array}{ccccccccc} 9 & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2 \\ 8 & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2 \\ 7 & 14 & 14 & 12 & 10 & 8 & 6 & 4 & 2 \\ 6 & 12 & 12 & 12 & 10 & 8 & 6 & 4 & 2 \\ 5 & 10 & 10 & 10 & 10 & 8 & 6 & 4 & 2 \\ 4 & 8 & 8 & 8 & 8 & 8 & 6 & 4 & 2 \\ 3 & 6 & 6 & 6 & 6 & 6 & 6 & 4 & 2 \\ 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 2 \\ 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ \end{array} \right) \end{align}
Since we reversed left/right at the start, the desired expected number of steps is the third entry from the right of any row of this matrix, i.e. $6$.