## 3B Exercise 8: Last visited points

Consider the random walk on $\mathbf{Z}/p\mathbf{Z}$ in which the steps $\pm 1$ have equal probability $1/2$ and we start at $0$. Let $q_r$ be the probability that $r$ is the last point to be visisted. Remarkably $q_r$ is the same for all non-zero $r$.

The book suggests that a calculation-free proof is possible. First of all consider $q_{-1}$. Suppose that a walk visits $p-2$ before $-1$. Then all the points of $\mathbf{Z} / p\mathbf{Z}$ have been visited, except for $-1 = p-1$. Conversely, if the walk visits $p-2$ before $-1$ then $-1$ must be the last unvisited point. It follows that $q_{-1}$ is the probability that a symmetric random walk on the integers starting at $0$ visits $p-2$ before $-1$.

This probability appears in the famous ‘Gambler’s Ruin’ problem: what is the chance that a gambler starting with a stake of $m$ units can bust a bank owning $n$ units playing a fair game for stakes of one unit each time? The probability is proportional to the stakes, so is $m/(m+n)$. (This can be proved more rigorously by solving a simple recurrence relation.) In our case the stakes are $1$ and $p-2$, so $q_{-1} = 1/(p-1)$.

In general, let $r$ be a non-zero point. Suppose we visit $r-1$ before $r+1$. Then $r$ is the last unvisited point if and only if, as the walk continues, it visits $r+1$ before $r-1$. As before, this event has probability $1/(p-1)$. A similar argument applies if the walk visits $r+1$ before $r-1$. Since the walk cannot visit $r$ without passing through either $r-1$ or $r+1$. this shows that $q_r = 1/(p-1)$ for all non-zero $r$.