Markov Chain

A Markov chain is a discrete-time stochastic process $\{X_n{\}}_{n\ge 0}$ taking values in a countable state space $S$, satisfying the Markov property: the conditional distribution of the next state given the entire past depends only on the present state. Formally, $P(X_{n+1}=j\mid X_n=i,X_{n-1},\dots ,X_0)=P(X_{n+1}=j\mid X_n=i)=p_{ij}$ for all states $i,j$ and all $n$. The collection of one-step transition probabilities $\{p_{ij}\}$ fully specifies the chain's dynamics (together with an initial distribution), and is conventionally arranged into a transition matrix. Markov chains form the foundation for a large family of models used throughout statistics and applied probability, including hidden Markov models, MCMC sampling, and queueing theory.

• The Markov property is about the present state, not about time itself, a chain can have an enormously complex state (e.g. the entire configuration of a board game) as long as that state alone, with no additional history, determines the next-step probabilities.
• Many processes that don't look memoryless at first can be turned into Markov chains by enlarging the state: for example, a process depending on the last two observations becomes Markov if the state is redefined as the pair (previous, current) observation.
• Markov chains underlie some of the most consequential algorithms in modern statistics and computing, Markov Chain Monte Carlo for Bayesian posterior sampling, Google's original PageRank algorithm, and hidden Markov models for speech recognition and genomics all build directly on this one memorylessness assumption.