Markov chain

From Citizendium, the Citizens' Compendium

Jump to: navigation, search


This article is developing and not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
 
http://en.citizendium.org/wiki?title=Markov_chain&printable=yes
This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

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 \left(t + 1\right) is solely a function of the state t, and not of any previous states [2].

Contents

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 [1].

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 [2].

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[2].

References

  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.
Retrieved from "http://en.citizendium.org/wiki/Markov_chain"
Views
Personal tools