TOPICS
Search

Markov Chain

A Markov chain is collection of random variables {X_t} (where the index t runs through 0, 1, ...) having the property that, given the present, the future is conditionally independent of the past.

In other words,

P(X_t=j|X_0=i_0,X_1=i_1,...,X_(t-1)=i_(t-1))=P(X_t=j|X_(t-1)=i_(t-1)).

If a Markov sequence of random variates X_n take the discrete values a_1, ..., a_N, then

P(x_n=a_(i_n)|x_(n-1)=a_(i_(n-1)),...,x_1=a_(i_1))=P(x_n=a_(i_n)|x_(n-1)=a_(i_(n-1))),

and the sequence x_n is called a Markov chain (Papoulis 1984, p. 532).

A simple random walk is an example of a Markov chain.

The Season 1 episode "Man Hunt" (2005) of the television crime drama NUMB3RS features Markov chains.

See also

Conditional Probability, Independent Events, Markov Sequence, Monte Carlo Method, Random Walk

Explore with Wolfram|Alpha

References

Gamerman, D. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference. Boca Raton, FL: CRC Press, 1997.Gilks, W. R.; Richardson, S.; and Spiegelhalter, D. J. (Eds.). Markov Chain Monte Carlo in Practice. Boca Raton, FL: Chapman & Hall, 1996.Grimmett, G. and Stirzaker, D. Probability and Random Processes, 2nd ed. Oxford, England: Oxford University Press, 1992.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 6, 1994.Kallenberg, O. Foundations of Modern Probability. New York: Springer-Verlag, 1997.Kemeny, J. G. and Snell, J. L. Finite Markov Chains. New York: Springer-Verlag, 1976.Papoulis, A. "Brownian Movement and Markoff Processes." Ch. 15 in Probability, Random Variables, and Stochastic Processes, 2nd ed. New York: McGraw-Hill, pp. 515-553, 1984.Stewart, W. J. Introduction to the Numerical Solution of Markov Chains. Princeton, NJ: Princeton University Press, 1995.

Referenced on Wolfram|Alpha

Markov Chain

Cite this as:

Weisstein, Eric W. "Markov Chain." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MarkovChain.html

Subject classifications