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 .