# Understanding Markov Chains

Before you start, have you read the conventions page?

## Introduction

A Markov chain is a mathematical model for random processes where time is taken into consideration. For each step of time (each tick of a clock), there is a probability that some event will happen. This probability depends on what the previous event was.

For example, let’s say we built a robot that has a very simple set of instructions. It can only move 1 meter in 1 of 2 directions (forward or backwards) every second and the direction it chooses depends on the last direction it chose. If the robot moved up in the last second, it has a 75% chance of moving down in the next second (and vice-versa). If you observe and record the robot’s movement at each time step, you might get something like this:

t | movement
0 | forward
1 | backwards
2 | forward
3 | backwards
4 | backwards


etc.

This could go on for any number of time steps, generating a sequence of events. This sequence is called a Markov chain.

## A better definition

Mathematically, when a random process, $X = (X_0, X_1, X_2, ..., X_n)$, follows the following property, it is a Markov chain:

$P[X_{n+1} = s | X_n = s_n, X_{n-1} = s_{n-1}, ... , X_0 = s_0] = P[X_{n+1} = s | X_n = s_n]$

where $S$ is a set containing all the possible states (the state space). Each member of $X$ is a random variable. The above equation is stating, simply, that the future value of X ($X_{n+1}$) is dependent on the present values of X.

We can also create a diagram of the possible states and probabilities of transition in something called a state transition diagram:

This can also be described as a matrix. The same Markov chain is described below:

This matrix is called the transition matrix. Each value in the matrix must be greater than zero, and each row much sum to 1. Or in fancy latex: $P_{ij} \geq 0, \sum_{j} P_{ij} = 1$ for all i.

Storing the probabilities in a matrix allows us perform linear algebra operations on these Markov chains, which I will talk about in another blog post.

## References

Stanford Markov Chain tutorial: http://www.stanford.edu/class/stat217/New12.pdf