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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(t + 1\right)} is solely a function of the state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} , and not of any previous states .

A Formal Model

The influence of the values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X^{\left(0\right)}, X^{\left(1\right)}, \ldots, X^{\left(n\right)}} on the distribution of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X^{\left(n+1\right)}} can be formally modelled as:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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$ occuring 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 <mat>n + 1</math> 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.