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. In this article, we will review the statistics 101 knowledge together, use a thought template and chart to crack problem like this.

Let's get started. Here is the game background:

In a game, two players A and B take turns to flip a coin, the person who gets a sequence of two heads wins the game.

Let's stop here to think for seconds. 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.

One can argue that there is a formal way to apply Markov Chains to solve this type of problem. However, 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 question, we will firstly warm up our statistics 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 rewrite it as:

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

Question

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

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, we will enumerate all the states and consequences during the game

A flips to the Head and A wins immediately;
If A flips Tail, it is B’s turn to flip the coin. B flips to Head. B wins the game.
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 to visualize and analyze the problem.

The graph shows clearly that we can break down the total probability P(A) from distinct nodes.

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)
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.
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).

Now the question comes to that how do we express the probability of A winning at Node 3? The trick is to use a recursion relationship. At this point, the game is getting into the beginning state as the starting point. We can use “X” to denote the probability of A winning. Probability of A wins for node 3 is: 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.

The graph shows clearly that we can break down the total probability P(A) from distinct nodes.

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)
Node 2: A flips the Tail and B flips the head. B wins. 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.
Node 3: A flips the Tail and then B flips to the Tail. The game continues. If B flips a Tail. The probability of this happening is (1-p)*(1-p). Probability of A wins is same as the beginning state, which is X. Thus the probability of this happening is (1-p)*(1-p)*X.

Sum up the three discrete parts together and we should get the equation below.

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)

Recap

As you see, the solution only utilizes the 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. Hope you enjoy the journey of learning this method. Click here for an explanation from the YouTube video and check the list of more probability questions with simple solutions.