Markov chain

| Main Article
| Discussion
| Related Articles  [?]
| Bibliography  [?]
| External Links  [?]
| Citable Version  [?]

|
|
|
|
|
|
|
|

This editable Main Article is under development and subject to a disclaimer.

[edit intro]

A Markov chain is a Markov process with a discrete time parameter [1]. 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  ( t + 1 ) {\displaystyle \left(t+1\right)} is solely a function of the state  t {\displaystyle t} , and not of any previous states [2].

## Contents

* 1 A Formal Model
* 2 Probability Density
* 3 Invariant Distributions
* 4 References

## A Formal Model[edit]

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

|  P ( x ( n + 1 ) ∣ x ( n ) , { x ( t ) : t ∈ E } ) = P ( x ( n + 1 ) ∣ x ( n ) ) {\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 {\displaystyle E} is any desired subset of the series  { 0 , … , n − 1 } {\displaystyle \left\\{0,\ldots ,n-1\right\\}} . These  t {\displaystyle t} indexes commonly represent the time component, and the range of  X ( t ) {\displaystyle X^{\left(t\right)}} is the Markov chain's state space [1].

## Probability Density[edit]

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

|  p ( n + 1 ) ( y ) = ∑ x p ( n ) ( x ) p ( y ∣ x ) {\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 {\displaystyle y} at time  n + 1 {\displaystyle n+1} is a function of the summed products of the initial probability density and the probability of state  y {\displaystyle y} given state  x {\displaystyle x} [2].

## Invariant Distributions[edit]

In many cases, the density will approach a limit  p ( y ) {\displaystyle p\left(y\right)} that is uniquely determined by  p ( y ∣ x ) {\displaystyle p\left(y\mid x\right)} (and not  p ( n ) ( x ) {\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[2].

## References[edit]

1. ↑ 1.0 1.1 Neal, R.M. (1993) Probabilistic Inference using Markov Chain Monte Carlo Methods. Technical Report TR-931. Department of Computer Science, University of Toronto http://www.cs.toronto.edu/~radford/review.abstract.html
2. ↑ 2.0 2.1 2.2 Peter M. Lee (2004) Bayesian Statistics: An Introduction. New York: Hodder Arnold. 368 p.