Markov chain

A Markov chain is a Markov process with a discrete time parameter . The Markov chain is a useful way to model systems with no long-term memory of previous states. That is, the state of the system at time $\left(t+1\right)$ is solely a function of the state $t$, and not of any previous states .

A Formal Model

The influence of the values of $X^{\left(0\right)},X^{\left(1\right)},\ldots ,X^{\left(n\right)}$ on the distribution of $X^{\left(n+1\right)}$ can be formally modelled as:

$P\left(x^{\left(n+1\right)}\mid x^{\left(n\right)},\left\{x^{\left(t\right)}:t\in E\right\}\right)=P\left(x^{\left(n+1\right)}\mid x^{\left(n\right)}\right)$

Eq. 1

In this model, $E$ is any desired subset of the series $\left\{0,\ldots ,n-1\right\}$. These $t$ indexes commonly represent the time component, and the range of $X^{\left(t\right)}$ is the Markov chain's state space .

Probability Density

The Markov chain can also be specified using a series of probabilities. If the initial probability of the state $x$ is $p_{\left(0\right)}\left(x\right)$, then the transition probability for state $y$ occurring at time $n+1$ can be expressed as:

$p_{\left(n+1\right)}\left(y\right)=\sum _{x}p_{\left(n\right)}\left(x\right)p\left(y\mid x\right)$

Eq. 2

In words, this states that the probability of the system entering state $y$ at time $n+1$ is a function of the summed products of the initial probability density and the probability of state $y$ given state $x$ .

Invariant Distributions

In many cases, the density will approach a limit $p\left(y\right)$ that is uniquely determined by $p\left(y\mid x\right)$ (and not $p_{\left(n\right)}\left(x\right)$). This limiting distribution is referred to as the invariant (or stationary) distribution over the states of the Markov chain. When such a distribution is reached, it persists forever.