Expected iterations for a finite random walk

Consider three cells as so:

A player (the blue disc) starts out in the left-most cell, and discrete time starts. At each step in time, the player has a 1/2 probability of moving left and a 1/2 probability of moving right. If the player chooses to move left but cannot because it is in the left-most cell, then it does nothing, though that still counts as a move. The game ends when the player reaches the right-most cell.

What is the expected number of moves in this game?

Let $N$ be the expected number of this game; that is $N$ is the expected number of moves required to reach the right-most cell. If the player is in the left-most cell, then there is a 1/2 probability of moving left. Since they can't actually move left, after this turn they stay in the cell but add one turn to their move. Therefore, this conditional contributes $1/2(1 + N)$ to the expected number of moves.

But suppose the player moves to the right. Then there is a 1/2 probability that they will move to the left, and 1/2 that they will move to the right. If they move to the left, then the game is back to the original condition with two moves used up, whereas if they move to the right, the game ends, which will have taken two moves.

Therefore, this conditional contributes $1/2(1/2(2 + N) + 1/2(2))$ to the expected number of moves. So, we get the formula:
$$N = 1/2(1 + N) + 1/2(1/2(2 + N) + 1/2(2))$$
The reader will verify that $N=6$ is the solution to this equation. Therefore, an average of six moves will be required to end the game.

Now, what if you try this with $k$ cells in a row instead of three? The problem is even easier with two cells, in which case the expected number of moves is two. If you try it with four cells, though, the above reasoning starts to get messy. I won't bore you with the details, but the problem is once you are reasoning along for the third cell, you can either go to the second or the fourth, but if you go to the second, why-you've already been to the second! That's not a true problem because the reasoning still works out, and it still solves the problem. But there is a neater way to solve this problem for $k$ cells that is neater, in my opinion.

Let $N_j$ be the number of expected moves to reach the right-most cell, given that you are starting from the $j$th cell. For $N_1$, we know that:
$$N_1 = 1/2(1 + N_1) + 1/2(1 + N_2)$$
If $1\lt j\lt k-1$ then
$$N_j = 1/2(1 + N_{j-1}) + 1/2(1 + N_{j+1})$$
And finally,
$$N_{k-1} = 1/2(1 + N_{k-2}) + 1/2$$
This gives us $k-1$ linear equations in $k-1$ unknowns, and now the problem is a standard linear algebra problem of matrix row reduction. Ordering the unknowns in the sensible way of $N_1,N_2,\dots$, we get an augmented matrix that looks like this:

Row-reducing this matrix is pretty simple: add the first row to the second, then the second row to the third, etc. all the way to the bottom. Then, add the last row to the second-last, the second-last to the third-last, etc. all the way to the top.

In going downwards, you change the augmented column to the numbers $1,2,3,\dots,k-1$. Going back up, you get that the first row gives the equation
$$1/2N_1 = 1 + 2 + \cdots + (k-1) = k(k-1)/2$$
Therefore, $N_1 = k(k-1)$, which also happens to work when $k=1$. So, the expected number of moves until the game ends for $k$ cells is just $k(k-1)$. Our special case of $k=3$ gives $k(k-1) = 3\times 2 = 6$.

Not only that, but because we defined the variable $N_j$, which is the expected number of moves to finish the game starting from the $j$th cell, the matrix also gives us a formula for these:
$$N_j = (k-1 + j)(k – j).$$

Also interesting is when $j = k-1$, for then $N_{k-1} = 2k – 2$. So for example, if you have a million cells and you're the player in the $k-1$ cell right next to the finishing $k$-cell, it will still take you on average 1999998 moves to get to the end, even though you have a 1/2 probability of finishing on the first move!

Exercise: Instead of the expected number of moves to get to the end, try working out the probability of finishing the game in $x$ moves.

Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.