Markov chain

A Markov chain is a stochastic process that evolves over time according to a sequence of random states, where the probability of moving to the next state depends only on the current state, not on the past history. This property is called the Markov property. So in particular is a Markov process.

A Markov chain is given by:

A state space $S = s_{1}, s_{2}, \dots$ (finite or countable).
A transition probability matrix $P = (p_{i j})$ , where

p_{i j} = Pr (X_{n + 1} = s_{j} ∣ X_{n} = s_{i}), \sum_{j} p_{i j} = 1.

Key Ideas

Markov property:

Pr (X_{n + 1} = s_{j} ∣ X_{n}, X_{n - 1}, \dots, X_{0}) = Pr (X_{n + 1} = s_{j} ∣ X_{n}) .

The distribution of states after $n$ steps is given by matrix powers:

π^{(n)} = π^{(0)} P^{n},

where $π^{(0)}$ is the initial distribution.

Examples

Random walk on integers: move left or right with given probabilities.
Weather model: states = {sunny, rainy}; transitions encode probabilities of changing weather.