Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

641 | 2^32 + 1

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED
Post a Comment
Read more

sum of 3 out of 5 is divisible by 3

Problem: Among 5 integers, there are always 3 with sum divisible by 3. (From Problem Solving Strategies, Arthur Engel) Solution: Proof by Pigeon Hole Principle. An integer is either 0, 1 or 2 \( \pmod 3 \). Imagine placing 5 integers into those 3 boxes. If we have at least one in each, then we can pick one from each, with sum divisible by 3. Otherwise, we'll have at least 3 integers in one of the boxes. Pick those 3. QED
Post a Comment
Read more

2n+1 3n+1 squares then 5n+3 not prime

Problem: Prove that if \( 2n+1 \) and \( 3n+1 \) are both squares, then \( 5n+3 \) is not a prime. Solution: Proof by contradiction. Suppose that there is n such that 5n+3 is prime. Note that \( 4(2n+1) - (3n+1) = 5n+3 \). Let \( 2n+1 = p^2 \) and \( 3n+1 = q^2 \), where \( p, q > 0 \). We have \( (2p-q)(2p+q) = 5n+3 \). Since RHS is a prime, we must have \(2p - q = 1 \) and \( 2p + q = 5n+3 \). Solving for \( q \) we get \( 2q = 5n + 2 \). Substituting, we get \( 2q = q^2 + 2n + 1 \), or \( -2n = (q-1)^2 \). Since RHS is \( \geq 0 \), we can only have equality when \( n= 0 \) and \( q = 1 \). In this case, we have \( 5n + 3 = 8 \) not a prime. QED.
Post a Comment
Read more