Recursive Relationship

Overview

Recursive relationship is another very common pattern in both probability and expected value questions. The question is normally about the probability of a player winning, given the player wins when a certain condition is met. It is solved by finding a condition where the game is essential “reset”.

When approaching this type of question, and many other probability questions, think only one step at a time. For example, if the game is tossing a coin and you’ll win after three heads are tossed, ask youself: what happened after one toss? And then go from there.

Questions

Coin Toss

DS Book

Players A and B are playing a game where they take turns flipping a biased coin, with p probability of landing on heads and winning. Player A starts the game, and then the players pass the coin back and forth until one person flips heads and wins. What is the probability that A wins?

There are three scenarios in this questions:

1. A flips a head and wins. Probability of this happening is p.
2. A flips a tail, and B flips a head and wins. Probability of this happening is (1-p)p.
3. A flips a tail, and B flips a tail. It’s now A’s turn again to flip the coin. The game is basically reset and back to square 1. Probability of this happening is (1-p)^2

Let P(A) be the probability of A wins, then using law of total probability, we have:

Solving this equation will give you P(A) in terms of p.

Coin Toss II

Green Book

Two players, A and B, alternatively toss a fair coin. The sequence of heads and tails is recorded. If there is a head followed by a tail, the game ends and the person who tosses the tail wins. What is the probability that A wins the game?

• By law of total probability, we break this problem down into P(A) = P(A|H)P(H) + P(A|T)P(T)
  • For P(A|H), we can expand it to P(A|H) = P(A|HT)P(T) + P(A|HH)P(H)
    • For HT case, A has 0% probability of winning
    • For HH case, B essential has P(A|H) probability of winning, as now he tossed the “first head”, therefore, A has P(A|HH) = 1 - P(A|H) probability of winning
    • Solving for P(A|H), we get P(A|H) = 1/3
  • For P(A|T), B becomes the first to toss. Therefore, P(A|T) = P(B’) = 1 - P(A)
• Combining all equations, we have P(A) = 1/6 + (1 - P(A))/2 = 4/9

Amoeba

Green Book

There is one amoeba in a pond. After every minute the amoeba may die, stay the same, split into two or split into three with equal probability. All its offspring, if it has any, will behave the same and independently. What is the probability the amoeba population will die out?