Bill Cardwell wrote:

I'm looking for a simple derivation of the probability that a random walk starting at 0, with unit steps, will ever end up to the left of 0. Probability that the person goes to the left (towards the negative) at any step is p.

Dan Asimov replied:

Let L be the desired probability: that the walk ever reaches -1.

Then L = p + q*L^2

(q = 1-p), since if the first step is to the right, the probability of then ever reaching -1 requires first ever reaching 0 (prob = L by translation-invariance) and then ever reaching -1 from there (L again).

Which gives L = (1+-sqrt(1-4pq)) / 2q.

The + sign would give probabilities > 1, so the answer must be

L = (1-sqrt(1-4pq)) / 2q.

This is a nice slick way to rule down the set of possible answers, but it's not a complete analysis. In the case where p is 1/2 or less, the + sign gives (1+|2p-1|)/2(1-p) = (1+1-2p)/2(1-p) = 1, which is not > 1. So it takes a bit more work to show that when p is less than 1/2, the answer to Bill's question is p/(1-p) rather than 1. (Unless I'm missing something here.) The way I filled this gap in the probability class that I'm teaching this semester is by looking at the analogous problem on a finite interval, and asking "What's the chance that the walker falls off by going to the left of the leftmost point, as opposed to going to the right of the rightmost point?". (Of course, one also has to show that with probability 1, one of these two outcomes will occur!) Then one takes the limit as the size of the interval goes to infinity. Jim Propp