Probability Puzzles 1

Below are some probability puzzles.

1. There are 6 players, numbered 1 to 6. Player 1 rolls a die. If Player 1 rolls a 1, he wins and the game ends.

   If Player 1 rolls any other number, the die is passed to the player corresponding to the rolled number, and the game continues with that player rolling. The game ends when a player rolls their own number.

   Solution

   $$p = \frac{1}{6} + \frac{5}{6} \frac{1 - p}{5}$$

2. A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. For convenience, let's say that the n th passenger in line has a ticket for seat number 'n'. Being drunk, the first person in line picks a random seat (equally likely for each seat). All of the other passengers are sober, and will go to their assigned seats unless it is already occupied; If it is occupied, they will then find a free seat to sit in, at random. What is the probability that the last (100th) person to board the plane will sit in their own seat (#100)?

   Solution

   $$p = 1 / 100 + 99 / 100 * (1 / 99 + 98 / 99 * (1 / 98 + \cdots ))$$$$p = 1 / 100 + 1 / 100 + 98 / 100 * (1 / 98 + 97 / \cdots)$$$$p = 1 / 100 + 1 / 100 + \cdots + 1 / 100$$$$p = 1 / 100 + 1 / 100 + \cdots + 1 / 100$$$$p = 1 / 2$$

3. Expected number of flip to get 2 heads in a row.

   Solution

   The answer is simple, let say the expected number is $x$.

   1. If we first flip the first tail, we need $x + 1$ flips to get two heads, with prob = $\frac{1}{2}$.

   2. If we first flip the first head ($p=\frac{1}{2}$):

      1. $1/2$ probability to get a head. Than the total number of flips is $2$.

      2. $1/2$ probability to get a tail. Than the total number of flips is $x + 2$ as we already wasted two flips.

   $$x = \frac{1}{2} (x + 1) + \frac{1}{2} \left( \frac{1}{2} \cdot 2 + \frac{1}{2} (x + 2) \right)$$

   Hance, $x = 6$.

4. Generalie to question 3, what if $n$ heads in a row?

   Solution

   Inspired by reference 2.

   Denot $E_n$ as the expected number of flips to get $n$ heads in a row.

   When we need to get 1 more head from $E_{n-1}$, we have two cases:

   1. We flip a head then we need $1$ more flips.

   2. We flip a tail then we need $E_n + 1$ more flips (One for the current useless flip)

   $$E_n = \frac{1}{2} (E_{n - 1} + 1) + \frac{1}{2} (E_{n - 1} + E_n + 1)$$

   Rearranging gives:

   $$E_n = 2 E_{n - 1} + 2$$

   Let $f(n) = E_n + 2$, we have $2 f(n - 1) = 2 E_{n - 1} + 4 = f(n)$. Hance

   $$f(n) = 2^{n + 1}$$

   and

   $$E_n = 2^{n + 1} - 2$$

5. Expected number of steps for a drunk man to reach one end of the bridge.

   Question from A Practical Guide to Quantitative Finance Interviews.

   The drunk man initially stands as $p$-th meter of a 100m long bridge, and it have 1/2 probability to move 1 meter left or right. What is the expected number of steps for him to reach either end of the bridge?

   Solution

   Observed that

   $$E(S_n) = 1 / 2 (E(S_{n - 1}) + 1) + 1 / 2 (E(S_{n + 1}) - 1) = E(S_{n - 1}) = 0$$

   Hence it is a martingale, and we can use the optional stopping theorem.

   Let $E_n$ be the expected number of steps to reach either end of the bridge from $n$-th meter, let $P_p$ be the probability of reaching the left end first.

   $$E(S_n) = P_p (p) + (1 - P_p) (100 - p) = 0$$

   Rearranging gives:

   $$P_p = \frac{100 - p}{100}$$

   Using another martingale

   $$E(S_n ^ 2 - n) = 0$$

   gives

   $$P_p (p^2) + (1 - P_p) ((100 - p)^2) - n = 0$$

   Rearranging gives:

   $$n = P_p p^2 + (1 - P_p) (100 - p)^2$$

References

1. CodeChef - Mathematical Expectation

2. Math Stack Exchange - Probability Puzzles