Markov chains

In short: A Markov chain is a random process in which the next state depends only on the current state and not on the history so far.

In more detail: It is described by transition probabilities between states. Example: weather that stays the same tomorrow with 70 % probability.

In Depth

• Markov property: “memorylessness”. The future depends only on the present.
• Transition matrix: A matrix P whose row i holds the probabilities from state i to all others. Each row sums to 1.
• Stationary distribution: In the long run many chains settle on a fixed share per state. The original PageRank method (random surfer) rests on this.
• Use: Simple text generation (next word from the current one), queueing models, speech recognition (hidden Markov models), MCMC sampling.
• Limit: If the future depends on steps further back, you need larger states or other models. Modern language models go far beyond this.

See also: Monte Carlo methods