Magic Tricks with Markov Chains

Stochastic Modelling

Calculate Hitting Times, Absorption Probabilities, and more

18 Jan 2021 — 12 min read Image by Pete Linforth from Pixabay.

If you’re unfamiliar with Stochastic processes, then I would suggest that you read my introductory article on the topic, as it covers all the background needed to understand this next tutorial. If you’re already familiar with the topic, please read on.

This tutorial focuses on using matrices to model multiple, interrelated probabilistic events. As you read this article, will learn how calculate the expected number of visits, time to reach, and probability of reaching states in a Markov chain, and a thorough mathematical explanation of the application of these techniques.

Let’s start with a simple probability question:

Q: What is the expected number of tosses to get 3 heads in a row with a fair coin?

You can solve this using prior knowledge of probability and geometric series but using a Markov chain will give you the answer to this question and more, in a way that is not only quick, but also generalizable to other problems with the same basic idea that are much messier than this one. Let’s start by constructing a transition probability matrix for this question:

coins