Question: There is a drunk man who is standing at the edge of the cliff. One step forward would send him over the edge. He takes random steps, either towards or away from the cliff. At any step, his probability of taking a step away is 2/3 and a step towards the cliff is 1/3. What is his chance of escaping the cliff?
Answer: Lets solve the general case of the problem, assuming p be the probability that the man moves away from cliff at any step.
Let P be the probability that the man falls the cliff (from current position on cliff) and P2 be the probability that he falls from cliff from one step away from the edge.
If he moves one step away (which has probability of p) he has P2 probability of falling from the cliff. And if he moves one step towards, he surely falls from the cliff. Thus,
P = (1 – p) . 1 + p . P2
In order to fall from one step away from edge, he has to overall move (overall displacement) towards cliff twice. And since P is the probability that he has an overall movement towards cliff once, P2 = P2. So,
P = (1 – p) + p . P2
(P – 1) . (p . P + p – 1) = 0
We can ignore P = 1, as there is always some chance of escaping the cliff.
P = 1 – p ⁄ p
In this specific case we have p = 2 ⁄ 3. P comes out to be 1 ⁄ 2 for this case.
Thus probability of falling from the cliff if 1 ⁄ 2.
Note: If p <= 1 ⁄ 2, P has to be 1 (as probability cannot be greater than 1). Even at a 1 ⁄ 2 chance of stepping in either direction he is guaranteed to eventually fall off the cliff! There is no escaping it. Turns out that being drunk and standing near a cliff is a mathematically bad idea to say the least 😀
Check out a similar puzzle, which involves Markov chain.