Markov Chains Part 1

This post is an introduction to the Markov chain, a common stochastic modeling framework to simulate random phenomena.

A Motivating Example: Susceptible-Infected-Susceptible (SIS) Model

At any given time, an individual is either infected with a disease or is healthy, i.e. is susceptible to becoming infected. Over an extended period of time (e.g. a year), an individual is likely to experience both of these states. Suppose we observe an individual over a sequence of days and classify this individual on day n as:

There is some probability that an infected individual remains infected the following day; in this simple scenario, there must therefore be a probability that the individual instead transitions to the susceptible state the following day¹. Likewise, we can apply this same reasoning to deduce that a susceptible individual will remain susceptible the following day with probability or will transition to infected with probability

With fairly high accuracy, we can guess how an individual will feel tomorrow based only on how he/she feels today. In other words, there is no need to consider how an individual felt before day n in order to guess how an individual is likely to feel on day n + 1. Thus, the values of and apply regardless of the individual’s health history. We call this one-step memory property the Makrov property; it can be interpreted as “given the present, the future does not depend on the past.”

Markov chains (MCs) are a type of stochastic (random) mathematical model that allows us to describe this scenario more formally. This math is useful for many reasons; for example, we can use it to compute the percentage of days that an individual is expected to be sick, or the number of individuals sick simultaneously during an epidemic.

Mathematical Notation

Formally, a Markov chain is a stochastic process on the state space (i.e. the chain has s possible states) that has one-step memory. Importantly, the Markov chain assumes a discrete state-space². The transtion probability from state i to state j is given by:

Translating from math-speak to English: the probability that the Markov chain will be in state j at time-step n given (| is read as “given”) that the Markov chain is in state i at time-step n-1, i.e. depends only on the fact that and we can ignore all previous realizations of the Markov chain.

Back to the SIS Model: Constructing the Transition Probablity Matrix

There are two states in the SIS model: The transition probabilities are and as defined above, leading to the following transition probability matrix (TPM):

The rows of this matrix correspond to the current state (an individual’s infection status today), while the columns of this matrix correspond to the next state (an individual’s infection status tomorrow). Each entry of this matrix, therefore, represents the probability that a transition from state i to state j will occur in a single step. It is a specific example of a probabilistic matrix, which has the properties of rows that sum to 1 and entries that are bounded between 0 and 1.

Transition probability matrices are necessary for most of the “useful” math associated with MCs. As a brief example, multiplying the TPM by itself yields the 2-step transition probability matrix, which in the SIS example, represents the probability an individual has infection status j the day after tomorrow, given that the individual currently has infection status i³.

ODEs and MCs: A Comparison

Elsewhere, I have presented a very similar model for infectious diseases using ordinary differential equations (ODEs). Both frameworks are equally valid and can be used to answer many of the same questions. However, there is a notable difference between these two types of models. An ODE model is deterministic, i.e. it will always yield the same answer using the same parameters and set of initial conditions. MCs, on the other hand, are stochastic, i.e. they are based in randomness, and any values obtained using MCs must be assessed probabilistically. Therefore, before applying either framework, a modeler must decide what type of answer they hope to get for their research question(s).

¹ Recall from basic probability that if one of two events always occurs, then the probability that each of them occurs must sum to 1.

² In the context of the SIS example, this means an individual is either susceptible or infected; there is no intermediate state.

³ In a future post, I will explore how repeating this process yields the long-term probabilities associated with the Markov chain.