Bill Cordwell asks: 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.
From: Dan Asimov <dasimov@earthlink.net>
Let L be the desired probability: that the walk ever reaches -1.
Then L = p + (1-p) L^2 [...] L = (1-sqrt(1-4p(1-p))) / 2(1-p),
which simplifies to
L = (1-|2p-1|) / 2(1-p).
Considering the cases p >= 1/2 and p <= 1/2 separately: ------------------------------- L(p) = 1 if p >= 1/2, and L(p) = p/(1-p) if p <= 1/2. -------------------------------
When I see a solution to a problem, I would like to figure out the way to look at it that leads to the solution "obviously". I have this half-Pascal's-triangle in my mind and Dan's rationale...
...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).
...doesn't immediately dispel it or show me how to fix it. But... ARGUMENT 1: the probability of eventually going left, L = is the probability that you will... p go left or + qL p right, then eventually left, then left, or + (qL)^2 p right, eventually left, right, eventually left, left, or + (qL)^3 p ... = p + qL( p + qLp + (qL)^2 p ... ) = p + qL^2 ARGUMENT 2: L is the probability that this procedure will terminate: def getLeftOf(x): while rnd() >= p: getLeftOf(x+1) The while loop can be written tail-recursively: def getLeftOf(x): if rnd() >= p: // escape probability p // else (1-p) getLeftOf(x+1) // x L getLeftOf(x) // x L Dan's solution and my embellishments are examples of dealing with infinity by mapping a set one-to-one with a subset of itself ;-) --Steve