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:

$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:

Failed to parse (syntax error): {\displaystyle 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 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 y} given 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 x} .

Invariant Distributions

In many cases, the density will approach a limit 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(y\right)} that is uniquely determined by 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(y \mid x\right)} (and not 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(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.