Skip to content
Last Dictionary
Plane
Mathematics & StatisticsReinforcement LearningLanguage Models & Transformers

Markov chain

nounAlso: Markov process, Markov chains, stationary distribution, transition matrix, memorylessness

In plain wordsA chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example.

  1. A sequence of random variablesrandom variable, n.: A quantity whose value depends on chance, such as the number rolled on a die or the next word a chatbot will write. X₀, X₁, X₂, … with the Markov property: once the present state is known, earlier history carries no further information about the future. It is specified by an initial distribution and transition probabilities — for finitely many states, a transition matrixmatrix, n.: A rectangular grid of numbers arranged in rows and columns. Most of what a neural network has learned is stored in large grids like this. whose rows sum to one. Under mild conditions (irreducibility and aperiodicity) a chain forgets its start and converges to a unique stationary distribution, the leading left eigenvectoreigenvector, n.: A special direction for a transformation: anything pointing that way stays on its line, only longer, shorter or reversed; the amount of stretch is the eigenvalue. Together they reveal the main axes along which data or a system varies. of the transition matrix; this is what makes Markov chain Monte CarloMarkov chain Monte Carlo, n.: A family of methods for drawing random examples from a complicated probability distribution by taking a long, carefully designed random walk that eventually visits each region in proportion to its probability. work and what Google's PageRank computed for a random web surfer. Markov chains model text in n-gram modelsn-gram model, n.: An early type of language model that predicts the next word from just the few words before it, using counts of how often each word followed those words in a large collection of text., whose state is the previous n − 1 words; with hidden states they become hidden Markov modelshidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.; with actions and rewards they become Markov decision processesMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice., the formal basis of reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time.. A transformer is Markov only if its entire context counts as the state.

    The shuffling procedure is a Markov chain, and after a few hundred steps it is close to its stationary distribution.

P(Xt+1=j∣Xt=i,Xt−1,…,X0)=P(Xt+1=j∣Xt=i)=PijP(X_{t+1} = j \mid X_t = i, X_{t-1}, \ldots, X_0) = P(X_{t+1} = j \mid X_t = i) = P_{ij}

Origin

Introduced by the Russian mathematician Andrey Markov in 1906 to extend the law of large numbers to dependent variables; in 1913 he analyzed the sequence of vowels and consonants in Pushkin's Eugene Onegin as a chain. 'Markov chain' was in English use by 1938, and Claude Shannon's 1948 Markov models of English text were ancestors of statistical language models.

Related

See also
  • Markov chain Monte CarloMarkov chain Monte Carlo, n.: A family of methods for drawing random examples from a complicated probability distribution by taking a long, carefully designed random walk that eventually visits each region in proportion to its probability.
  • Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice.
  • hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.
  • n-gram modeln-gram model, n.: An early type of language model that predicts the next word from just the few words before it, using counts of how often each word followed those words in a large collection of text.
  • stochasticstochastic, adj.: Involving chance, so the same starting point can lead to different outcomes. AI chatbots are stochastic: ask the same question twice and you may get two different answers.
  • eigenvectoreigenvector, n.: A special direction for a transformation: anything pointing that way stays on its line, only longer, shorter or reversed; the amount of stretch is the eigenvalue. Together they reveal the main axes along which data or a system varies.

Mentioned in

hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds., Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice., Markov propertyMarkov property, n.: The assumption that the future depends only on the present situation, not on how you got there — so knowing the current state is enough to predict what happens next., n-gram modeln-gram model, n.: An early type of language model that predicts the next word from just the few words before it, using counts of how often each word followed those words in a large collection of text., stochasticstochastic, adj.: Involving chance, so the same starting point can lead to different outcomes. AI chatbots are stochastic: ask the same question twice and you may get two different answers., Markov chain Monte CarloMarkov chain Monte Carlo, n.: A family of methods for drawing random examples from a complicated probability distribution by taking a long, carefully designed random walk that eventually visits each region in proportion to its probability.