>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(a)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
