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 r
Given N people, what is the number of birthday celebrations on average in a year? Solution The quick solution is: the probability of having a celebration in a particular day is 1 - (364/365)^N. So the average is 365(1 - (364/365)^N). (Linearity if expectation) I wonder if someone tries to solve this problem directly, i.e. compute the number of ways to assign birthdays to N people to have k celebrations, call this B(N, k), then the average number of celebrations = sum k B(N, k). Turns out B(N, k) is very similar to something called Stirling number of second kind, which computes the number of ways to partition N labelled objects into k non-empty unlabelled groups. One can come up with the recurrence relation quite easily, but to directly compute it is interesting and relies on principle of exclusion and inclusion. The PIE for B(N, k) goes like this: let A_d be the set containing all assignments of birthdays where birthday d is unused. Then the answer is k^N - | A_1 union A_2 union ... u