main page, file list, single page HTML, source, report, wiki last updated on 06/07/23

Markov Chain

Markov chain is a relatively simple stochastic (working with probability) mathematical model for predicting or generating sequences of symbols. It can be used to describe some processes happening in the real world such as behavior of some animals, Brownian motion or structure of a language. In the world of programming Markov chains are pretty often used for generation of texts that looks like some template text whose structure is learned by the Markov chain (Markov chains are one possible model used in machine learning). Chatbots are just one example.

There are different types of Markov chains. Here we will be focusing on discrete time Markov chains with finite state space as these are the ones practically always used in programming. They are also the simplest ones.

Such a Markov chain consists of a finite number of states S0, S1, ..., Sn. Each state Si has a certain probability of transitioning to another state (including transitioning back to itself), i.e. P(Si,S0), P(Si,S1), ..., P(Si,Sn); these probabilities have to, of course, add up to 1, and some of them may be 0. These probabilities can conveniently be written as a n x n matrix.

Basically Markov chain is like a finite state automaton which instead of input symbols on its transition arrows has probabilities.


Let's say we want to create a simple AI for an NPC in a video game. At any time this NPC is in one of these states:

Now it's pretty clear this description gets a bit tedious, it's better, especially with even more states, to write the probabilities as a matrix (rows represent the current state, columns the next state):

A 0.5 0.5 0 0
B 0 0.5 0.25 0.25
C 0.1 0.1 0.7 0.1
D 0.25 0.25 0.5 0

We can see a few things: the NPC can't immediately attack from cover, it has to search for a target first. It also can't throw two grenades in succession etc. Let's note that this model will now be yielding random sequences of actions such as [cover, search, shoot, shoot, cover] or [cover, search, search, grenade, shoot] but some of them may be less likely (for example shooting 3 bullets in a row has a probability of 0.1%) and some downright impossible (e.g. two grenades in a row). Notice a similarity to for example natural language: some words are more likely to be followed by some words than others (e.g. the word "number" is more likely to be followed by "one" than for example "cat").

All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.