Discrete-Time Markov Chains
A discrete-time Markov chain is a sequence of random states evolving in integer time so that the distribution of the next state depends only on the current state, not on the full past.
Definition
A discrete-time Markov chain is a stochastic process on a countable state space indexed by the non-negative integers whose conditional distribution of the next state given the entire history depends only on the present state, encoded by a one-step transition probability matrix.
Scope
This area covers the Markov property and transition matrices, the classification of states by communication, recurrence, transience, and periodicity, the existence and uniqueness of stationary and limiting distributions, convergence and mixing rates, and the principal applications including Markov chain Monte Carlo and hidden Markov models.
Sub-topics
Core questions
- What does the Markov property mean and how is it captured by a transition matrix?
- How are states classified into recurrent, transient, and periodic classes?
- When does a chain possess a unique stationary distribution and converge to it?
- How fast does a chain approach equilibrium, and how is this exploited in simulation?
Key theories
- Markov property and Chapman-Kolmogorov equations
- The future is conditionally independent of the past given the present, so multi-step transition probabilities are obtained by multiplying transition matrices, which makes the n-step behaviour computable from the one-step matrix.
- Ergodic theorem for Markov chains
- An irreducible, aperiodic, positive-recurrent chain has a unique stationary distribution to which the marginal distribution converges and against which time averages of functions converge almost surely, linking long-run frequencies to the stationary law.
Clinical relevance
Discrete-time Markov chains model random walks, queueing snapshots, population genetics, ranking algorithms such as PageRank, and economic state transitions; their convergence theory underpins Markov chain Monte Carlo, the dominant computational method for sampling from complex probability distributions across statistics, physics, and machine learning.
History
Andrey Markov introduced chains with dependent but memoryless transitions in 1906 to extend the law of large numbers beyond independence, illustrating them with letter sequences in Pushkin's poetry. Kolmogorov and Doeblin placed the convergence theory on rigorous measure-theoretic foundations in the 1930s.
Key figures
- Andrey Markov
- Andrey Kolmogorov
- Wolfgang Doeblin
Related topics
Seminal works
- norris1997
Frequently asked questions
- What makes a process a Markov chain?
- The Markov property: given the present state, the future evolution is independent of how the chain reached that state, so the entire dynamics are described by one-step transition probabilities.
- When does a Markov chain converge to a unique long-run distribution?
- When it is irreducible, aperiodic, and positive recurrent; then there is a single stationary distribution to which the chain converges regardless of its starting state.