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.


2 Responses to 3B Exercise 8: Last visited points

  1. Douglas Zare says:

    You can do even less calculation than this. You can simply note that you get equivalent Gambler’s Ruin problems (after the first neighbor is hit, either the walk goes all the way around to the other neighbor before reaching the position, or not) so the probabilities are equal, even if you don’t calculate the probabilities first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: