dc_374

I have the following problem.

In a certain enterprise there are levels 0 through n. You start at
level 1 with the goal of advancing all the way to level n. At any
level you can either succeed and go up one level or fail and go down
one level. The probability of success on each level is the same and
equal to p. If you reach n or fall to 0, you are done.

What is the probability that you _will_ reach level n after no matter
how many failures?

Can anyone help? Thanks.

proginoskes

Search for "Gambler's Ruin Problem", or something like that, using Google.
-- Christopher Heckman

dc_374

Thanks, that turned out to be exactly what I was looking for.

macavity

This is the classic gambler's ruin problem, as noted by CH.

Let W(x) be the probability of eventual win starting from level x.
After several stages, if you are at level y, then it does not matter
how many/ what stages you passed to get there. This means that
irrespective of where you start, the probability of winning, if you
are at level x, is W(x).

Now from level x, there can be only two cases, and we get the
recurrence:
W(x) = W(x+1) p + W(x-1) (1-p)
for 0 < x < 1
[define W(0) = 0 and W(n) = 1]

The solution of the recurrence, with the required conditions, leads to

W(x) = (r^x - 1)/(r^n - 1)
where r = (1-p)/p <> 1

and W(x) = x/n when r = 1 (or p = 1/2)

So your answer is:
1/[1 + r + r^2 + ... r^(n-1)]

HTH.