Markov chain
- Key People:
- Andrey Andreyevich Markov
- Related Topics:
- stochastic process
- Ornstein-Uhlenbeck process
Markov chain, sequence of possibly dependent discrete random variables (x1, x2, x3,…)—identified by increasing values of a parameter, commonly time—with the property that any prediction of the next value of the sequence (xn) is based on the last state (xn − 1) alone. That is, the future value of such a variable is independent of its past. The term Markov process is used for sequences in which the random variables can assume continuous values.
In mathematics, probability distributions such as Markov chains, in which the next state of the system depends only on the current state, are said to possess the Markov property and be “memoryless.” This term implies that the model has “forgotten” previous states.
Markov chains are named for the Russian mathematician Andrey Andreyevich Markov (1856–1922), who was the first to study them systematically. The first application of Markov chains was carried out by Markov himself, when he analyzed the first 20,000 characters in Aleksandr Pushkin’s novel in verse Eugene Onegin (1833). The probability of a vowel following a vowel was 0.128, and the probability of a vowel following a consonant was 0.663. Markov’s work inspired the American mathematician and electrical engineer Claude Shannon in the development of information theory, and Shannon modeled language as a Markov chain. The first Google search engine algorithm, PageRank, was a large Markov chain calculation (a 2.7 billion × 2.7 billion matrix).
Markov chains have been used in machine-learning models and studies of genes, as well as in modeling how animals choose habitats and how epidemics spread. Random walks, which describe random motions of some object, are Markov chains. Brownian motion is a random-walk phenomenon. Many economists believe that stock market fluctuations, at least over the short run, are random walks.
See also stochastic process.