Before you start, have you read the conventions page?
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
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.
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.
Stanford Markov Chain tutorial: http://www.stanford.edu/class/stat217/New12.pdf
Youtube Markov Chain video: http://www.youtube.com/watch?v=uvYTGEZQTEs