Markov chain

Definition

Let $S$ be a nonempty countable set. Let $(X_n)_{n \ge 0}$ be a stochastic process with values in $S$. It is a Markov chain with state space $S$ if $$P(X_{n+1} = j \mid X_0 = i_0, \dots, X_{n-1} = i_{n-1}, X_n = i) = P(X_{n+1} = j \mid X_n = i)$$ for each $n \ge 0$ and all states $i_0, \dots, i_{n-1}, i, j \in S$ with $P(X_0 = i_0, \dots, X_n = i) > 0$. The chain is time-homogeneous if $p_{ij} = P(X_{n+1} = j \mid X_n = i)$ does not depend on $n$.

Remarks

The condition is the Markov property in discrete time. For a time-homogeneous chain, the numbers $p_{ij}$ form the transition matrix $P = (p_{ij})_{i, j \in S}$. The initial distribution $\lambda_i = P(X_0 = i)$ and $P$ determine the law of the chain: $P(X_0 = i_0, \dots, X_n = i_n) = \lambda_{i_0} p_{i_0 i_1} \cdots p_{i_{n-1} i_n}$. Markov chains also exist in continuous time and on general state spaces.

Explanations

L1 human

A Markov chain has no memory beyond the present state. Consider the weather each day: if tomorrow depends only on today, the sequence of weather states is a Markov chain.