Consider the random walk on in which the steps have equal probability and we start at . Let be the probability that is the last point to be visisted. Remarkably is the same for all non-zero .

The book suggests that a calculation-free proof is possible. First of all consider . Suppose that a walk visits before . Then all the points of have been visited, except for . Conversely, if the walk visits before then must be the last unvisited point. It follows that is the probability that a symmetric random walk on the integers starting at visits before .

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

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

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Friday, November 19th, 2010 at 12:23 pm and is filed under Diaconis book. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

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.

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.

Yes, good point!