Markov Chain

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

For a countable state space, this means that, for ,

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)),

whenever the conditioning event has positive probability.

If a Markov sequence of random variates takes the discrete values , ..., , then, for and conditioning histories of positive probability,

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 is called a Markov chain (Papoulis 1984, p. 532).

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

A finite chain with time-independent transition probabilities is an absorbing Markov chain when it has at least one absorbing state and every other state can reach an absorbing state with positive probability. The expected number of steps to absorption can then be calculated from a matrix inverse (Grinstead and Snell 1997, pp. 416-420).

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

See also

Conditional Probability, Detailed Balance, Glauber Dynamics, Independent Events, Markov Bridge, Markov Chain Cutoff, Markov Order, Markov Sequence, Markov Type, Mixing Time, Monte Carlo Method, Probability Vector, Random Walk, Stationary Distribution

Explore with Wolfram|Alpha

More things to try:

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.Grinstead, C. M. and Snell, J. L. Introduction to Probability, 2nd rev. ed. Providence, RI: American Mathematical Society, 1997. https://chance.dartmouth.edu/teaching_aids/books_articles/probability_book/Chapter11.pdf.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.Numberphile. Featuring M. du Sautoy. "The Game of Risk." Feb. 6, 2024. https://www.youtube.com/watch?v=RdooKXXcWWc.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.Veritasium. "The Strange Math That Predicts (Almost) Anything." Jul. 25, 2025. https://www.youtube.com/watch?v=KZeIEiBrT_w.

Referenced on Wolfram|Alpha

Cite this as:

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

Subject classifications