Probability Recursion Question for DS/ML Interviews (Step-by-Step Simple Solution)

What is a Recursion Relationship?

The recursion relationship is very common in both probability and expected value questions for ML or DS interviews. The question is normally about calculating the probability of a player winning, given the probability of an event happening when a certain condition is met. The game may come into a state that it is never over if a certain condition is not met. In other words, the game will be recursive to its “beginning state” and repeat, repeat again. For example, in a game, two players A and B take turns flipping a coin, and the person who flips the Head and gets a sequence of two heads wins the game. A sequence of two Heads here means that if A

to the Head and B flips to the Head, the game is over as B wins the game immediately. There are three different states during the game:

1) A wins

2)B wins

3) No one wins so the game will continue until one person gets a sequence of two heads.

Although there is a formal way to apply Markov Chains to solve this type of problem, In this article, I want to introduce a much more straightforward solution by drawing graphs and applying a recursion pattern.

Law of the Total Probability

Before we dive deep into the questions, let’s first warm up our math knowledge of the “Law of the Total Probability”.

The total probability rule (also known as the “Law of Total Probability”) breaks up probability calculations into distinct parts. It’s used to find the probability of an event – A when you don’t know enough about A’s probabilities to calculate it directly. Instead, you take a related event, B, C, or D.. and use that to calculate the probability for A.

The formula is expressed below:

or you can write it in the way below:

P(A) = P(A|B1)*P(B1)+P(A|B2)*P(B2)+P(A|B3)*P(B3)+…

This is all you need to know in order to solve this problem and now let’s take a look at the problem.

Question 

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?

Thought Process

To begin with, let’s enumerate all the states and consequences during the game:

1. A flips to the Head and A wins immediately;
2. If A flips Tail, it is B’s turn to flip the coin. B flips to Head. B wins the game.
3. From 2, If B  flips to Tail. The game is basically reset and back to the beginning. It starts to get into a recursion pattern.

We can draw a diagram like below to help visualize and analyze the problem.

At this point, we can break down the total probability P(A) from distinct nodes.

• For node 1: A flips the Head and A wins immediately. The probability of this happening is p. The formal calculation using Bayer’s Theorem is:  P(A)=P(A|H)*P(H)=1*p)
• For node 2: A flips the Tail and then B flips to the Head. The probability of this happening is (1-p)*p. The probability of A winning at this point is 0 because when B wins the game, A has 0 chances to win. The formal calculation using Bayer’s Theorem is: P(A)=P(A|TH)*P(TH)=0*(1-p)*p=0.
• For node 3: A flips the Tail and then B flips to the Tail. We notice the game can infinitely continue if no one flips to the Head (lower branch in the graph). The probability of this happening is (1-p)*(1-p). How do we express the probability of A winning at this point? The trick is to use a recursion relationship. At this point, the game is getting into the beginning state as the starting point. We use “X” to denote the probability of A winning. Probability of A wins P(A) = P(A|TT)*P(TT)=X*(1-P)*(1-p).

The diagram below is revised to show the recursion pattern relationship – we just need to have the node pointed back to the starting point.

Sum up the three discrete parts together and we should get the equation below. X = 1/(1-p)

X=P(A|H)*P(H)+P(A|TH)*P(TH)+P(A|TT)*P(TT)=1*p+(1-p)*0+(1-p)(1-p)*X

X=p+(1-p)*(1-p)X

Solve the X and X=1/(1-p)

Conclusion

As you see, the solution only utilized basic probability and simple algebra knowledge. The key to solving this type of problem is to understand the recursive nature of the sequence of the events (drawing a graph helps all the time!) and use a simple algebra equation to present the equilibrium. Click here for an explanation from the Youtube video and check the list of more probability questions with simple solutions.