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, , follows the following property, it is a Markov chain:

where is a set containing all the possible states (the state space). Each member of is a random variable. The above equation is stating, simply, that the future value of X () 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: 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