Solving a recursive probability problem with the Markov Chain framework | Python example

Reconducting a recursive probability problem to a Markov Chain can lead to a simple and elegant solution. In this article, I first walk through the resolution “by hand” of an example problem. Then, I provide the implementation of the same process in Python.

5 min readSep 28, 2021

The Problem

There are six basketball players on a field: for convenience, we will call them A, B, C, D, E, F. When given the ball, each of them might or might not pass the ball to one of the others. If the ball is passed, the game continues, otherwise it ends.

Whether a pass is performed is not completely random. Each player follows a fixed probability scheme that determines its actions. In particular:

Player A: 1/3 chance of passing to B, 2/3 chance of passing to F
Player B: 5/10 chance of passing to A, 3/10 chance of passing to D, 2/10 chance of passing to E.
Player C: never passes the ball.
Player D: never passes the ball.
Player E: never passes the ball.
Player F: never passes the ball.

Question: if the ball is given to A, what are the probabilities that the game ends, respectively, with the ball in the ends of C, D, E and F?

Why Markov

You might be wondering why we would need such a complex theoretical model to solve a not-too-difficult problem.

The problem of the infinite number of cases introduced by the recursion generated between players A and B could in fact be solved by simply recurring to the convergence of the sum of a geometric series.

While the above solution works perfectly in this case, it hardly fits more complex scenarios with multiple loops. Markov instead, works in the exact same way also for more complex chains. This is also the reason why it is suitable for the design of a generalized solving program.

What the hell is a Markov Chain?

First of all, what is a Markov Chain? Quoting the always beloved Wikipedia:

A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.

More precisely, this is an Absorbing Markov Chain. Quoting again Wikipedia:

[…] an absorbing Markov chain is a Markov chain in which every state can reach an absorbing state. An absorbing state is a state that, once entered, cannot be left.

In simple words, the process is an Absorbing Markov Chain since:

It is a sequence of events whose probability solely depends on the last element of the chain.
There is at least one state that cannot be left if reached — the players who will not pass the ball.
From any starting point, an absorbing state can be reached in a finite number of steps.

Reconducting the problem to the Absorbing Markov Chain framework

In order to apply the properties of the Absorbing Markov Chain, the problem data should be rewritten in a way that fits the framework. In particular, we need to write the probabilities in a matrix that satisfies the following conditions:

The cell XY — where X is the row and Y the column — contains the probability of going from state X to state Y.
If a row represents a non-absorbing state, then the same is true also for all the previous rows. Thus all the stable states should be at the bottom.
The stable states should be sorted so that they form a diagonal matrix.

While the above might sound a bit intimidating, it is actually quite a simple process. In our case we obtain:

Each cell contains the probability of passing from one state to another. For the absorbing states, there is a probability of 1 that the next state will be the state itself.

Since the matrix was correctly created, we can already identify the four submatrices that will allow us to perform the desired operations. These are highlighted in the image below:

Let’s call n the number of non-stable states and s the number of stable states and quickly comment on the submatrices:

Q: is a [n x n] matrix starting from cell [1,1]. It contains the probabilities of passing from one non-stable state to the others.
R: is a [n x s] matrix starting from cell [1, n+1]. It contains the probabilities of passing from a non-stable state to a stable one.
O: is a [s x n] matrix starting from cell [n+1,1]. It always contains only zeros as it expresses the probability of passing from a stable state to a non-stable one.
I: is a [s x s] matrix starting from cell [n+1,n+1]. It contains a diagonal matrix as it contains the probabilities of passing from one stable state to the other.

Solving the problem through the chain properties

The first thing we need to do is to compute the difference between an identity matrix of dimension [n x n] and Q.

Then we take the inverse of this matrix, obtaining the matrix N:

The last operation is a matrix multiplication between N and R to obtain the final matrix B:

Each cell XY of the B matrix tells which is the probability of ending in the absorbing state Y by starting from the unstable state X.

Thus, the probabilities of ending in states C, D, E, F by starting from A are respectively: 0, 3/25, 2/25, 20/25.

Python Implementation

Now that we know what to do, the python implementation is straightforward.

Note that AbsorbingMarkovChain intakes an already sorted matrix and it is made of the following:

A utility property to find the first absorbing state, useful for the remaining computations
Four of properties to retrieve the various matrices mentioned in the article
Two methods to jump directly to the solution, either given just the start or by specifying both start and end

The script can be easily used to answer the problem’s question!

Conclusion

Recurring probabilities problems — or at least some of them — can be easily tackled by taking advantage of the Markov Chain properties.

I hope you found this article useful!