Markov chain

# tag · @ author · ! scientist

A Markov chain is a stochastic model describing a sequence of states in which the probability of transitioning to the next state depends solely on the current state (Markov property). Formally: P(X_{n+1}=x | X_n=x_n,...,X_0=x_0) = P(X_{n+1}=x | X_n=x_n). Chains can be discrete or continuous in time, with a finite or countable number of states. Main tools: transition probability matrix, stationary distribution, Chapman–Kolmogorov equations.

History

Russian mathematician Andrey Markov in the early 20th century studied sequences of dependent random variables and introduced the concept of a chain to show that even in random texts, statistical regularities can be found.

How it works

Like in the game "Snake" on a phone, where the snake moves across cells, choosing a direction randomly, but only from the current position. If you know where it is now, it doesn't matter how it got there — this is the memoryless property.

💡 The first practical application of Markov chains was the analysis of the alternation of vowels and consonants in "Eugene Onegin" — Markov showed that it is not random and predicted future letters of the text.

A Markov chain is a random process with discrete time and a finite or countable state space, possessing the Markov property: the conditional distribution of future states depends only on the current state and not on the past trajectory. It is defined by an initial distribution and a transition probability matrix P = (p_{ij}), where p_{ij} = P(X_{n+1}=j | X_n=i). The chain is called homogeneous if p_{ij} do not depend on n. Key concepts: classification of states (recurrent, transient, periodicity), ergodicity (existence of a limiting distribution), stationary distribution π (πP = π). For irreducible aperiodic finite chains, there exists a unique stationary distribution to which the state distributions converge. Continuous-time Markov chains are described by an intensity matrix Q. Applications: Metropolis–Hastings algorithm in Monte Carlo, hidden Markov models in speech recognition, queueing theory.

History

Andrey Andreyevich Markov introduced chains in 1906 while studying the law of large numbers for dependent quantities. He was motivated by a desire to refute Nekrasov's claim that independence is necessary for statistical laws. Later, in the 1930s, Kolmogorov developed the general theory of Markov processes. In the mid-20th century, Markov chains became a central tool in operations research, physics (Ising model), and computer science (text generation, PageRank).

How it works

Mathematically, a Markov chain is defined by an initial probability vector π^{(0)} and a stochastic matrix P. Then the distribution after n steps: π^{(n)} = π^{(0)} P^n. The memoryless property means that to predict the future, it is sufficient to know only the current state. The long-term behavior is determined by the spectral decomposition of the matrix P: if there exists a unique left eigenvector with eigenvalue 1 (the stationary distribution), then π^{(n)} → π as n→∞. Chapman–Kolmogorov equations: P^{(n+m)} = P^{(n)} P^{(m)}, expressing the composition of transitions. For continuous time: dπ/dt = πQ, where Q is the transition intensity matrix.

p_{ij}^{(n+m)} = \sum_{k} p_{ik}^{(n)} p_{kj}^{(m)}

p_{ij}^{(n)} is the probability of transitioning from state i to state j in n steps; summation over all intermediate states k.

Open problems & fun facts

The problem of accelerating convergence for chains with slow mixing (e.g., in high-dimensional distributions with sharp peaks).; Development of efficient algorithms for estimating probabilities of rare events in complex systems.; Analysis of hidden Markov models with high-dimensional continuous hidden states.

💡 Markov chains underlie the PageRank algorithm that originally brought success to Google: web pages are modeled as states, transitions are hyperlinks; the page rank is the stationary probability of visiting during a random walk with return.

No articles yet

Markov chain

History

How it works

History

How it works

History

How it works

Open problems & fun facts

Related articles