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:
transitionstatediagram

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

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

Youtube Markov Chain video: http://www.youtube.com/watch?v=uvYTGEZQTEs

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s