Random walk by the cliff

You are one step away from falling down a cliff. In each step, you have 1/3 chance of moving towards the cliff, 2/3 chance of moving away from the cliff. What is the probability you fall down the cliff?

Solution

It is 1/2, and there are 3 ways to approach this.

Let's say we are at position 0, and the cliff is at position -1. We go +1 with probability p, and go -1 with probability 1-p.

Approach 1.

Catalan number: All paths that end with falling down the cliff can be broken down to two parts: 0 -> ... -> 0 and 0 -> -1. The path 0 -> ... -> 0 is Catalan; if we fix the path length to 2n, then the number of paths would be C_n. What we want to compute is the total probability = (1-p) sum { C_n (p(1-p))^n }. We can use the generating function for Catalan to arrive at: if p <= 1/2, probability = 1; if p > 1/2, probability = 1/p - 1.

Approach 2.

Let P(i) be the probability of reaching -1 from position i. 

P(0) = 1-p + pP(1)

Also, P(1) can be derived as follows: can we reuse P(0) to compute P(1)? Yes.

The path 1->...->-1 can be broken down to:

1 -> ... -> 0 (for the first time) : this is equivalent to P(0)

0 -> ... -> -1: this is the definition of P(0)

So P(1) = P(0)*P(0).

We can solve for P(0). The difficulty here is in deciding whether P(0) is 1 or 1/p-1 and when (not clear).

Approach 3. (Fun approach)

Telescoping. If we assume the sum P(i) is convergent then we can add the equations P(i) = (1-p) P(i-1) + p P(i+1)

Add them up, and cancel things out, we will derive P(0) = 1/p - 1. But we know this doesn't work for p < 1/2.

Follow up question: what if we stop taking steps when we are far away enough from the cliff, i.e. if we are n steps away from the cliff, what is the probability of falling off?

In this case we have to solve for the system of linear equations. However one trick is to either guess the closed form of the recurrence or by using generating function as a mid-step to realise that P(n) = P(0) * (1/p-1)^n + P(n-1), which can be used to solve for P(n). We can than use this to compute P(0) at the terminating condition.