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

Derive Poisson Distribution

Let's say we are observing an event that to us seems random. E.g. The number of cars passing through a road. Suppose we learn that on average, there are m cars passing the road within 1 hour. Goal: Can we make a model to suggest what is the probability of seeing exactly r cars passing the road in an hour? Let's represent one hour as a line, and on the line there are marks to represent the time on which a car passes. Let's suppose there are m marks, to represent the average case of seeing m cars on the road in an hour. Let's divide the 1 hour line into n uniform time segments, n large enough such that in one time segment there is at most 1 car. Out of the n time segments, m of them contains a car. Then it is reasonable to say that the probability of a time segment to contain a car is m/n. Let's analyse as n goes to infinity. We can say P(seeing exactly r cars in an hour) =  P(exactly r cars contained in n segments) = \( \binom{n}{r} \left( \frac{m}{n} \right)^r \left...
Post a Comment
Read more

n-th non-square

Problem: Find the n-th non-square number. (Adapted from Problem Solving Strategies, Arthur Engel ) If you have CS background, I invite you to come up with an O(log N) solution. Done? Good. Below I present the O(1) approach. Solution: The n-th non-square number is given by \( F(n) = \left \lfloor n + \sqrt{n} + 1/2  \right \rfloor \). Proof: Let G(n) be the same as F(n) except for the floor function. Investigate \( m \neq F(n) \). There is the largest \( n \) s.t. \( F(n) < m \). Hence \( m+1 \leq F(n+1) \). We conclude that \(G(n) < m \) and \(m+1 \leq G(n+1) \). Rearranging the terms and squaring the inequalities, we get: \( n < (m-n-1/2)^2 \) and \( (m-n-1/2)^2 < n+1 \), or \( n - 1/4 < (m-n)^2 - (m-n) < n + 3/4 \). Since the middle term is an integer, we see that \( (m-n)^2 - (m-n) = n \). Simplifying, we get \(m = (m-n)^2\), showing that m is a square. In other words, F(n) skips all squares. Now, we will show that F(n) is the n-th non...
Post a Comment
Read more