Markov chain

A Markov chain is a stochastic process in which the conditional probability of future states depends on the present state rather than on the complete history. Named after the mathematician Andrey Markov, it provides a framework for studying sequences of dependent random outcomes. The standard discrete-time formulation describes transitions between states at successive steps; continuous-time chains describe transitions occurring at random times. Markov chains connect probabilistic modeling with matrix methods and the analysis of long-run behavior. (math.dartmouth.edu)

Definition and the Markov property

A discrete-time Markov chain is a sequence of random variables $X_0,X_1,\ldots$, taking values in a state space $S$, usually finite or countably infinite. Its defining Markov property is

whenever the conditioning event has positive probability. This expresses conditional independence: once the current state is known, earlier states supply no additional information about the next state. It does not mean that successive states are independent, nor that the process must remain unchanged over time. (math.dartmouth.edu)

A chain is time-homogeneous when its transition probabilities do not depend on $n$. Otherwise, it is time-inhomogeneous. Homogeneity concerns the transition rule, whereas stationarity concerns the distribution of the process; a homogeneous chain need not begin in a stationary distribution. The chosen state must summarize the information needed for prediction, so the Markov assumption depends on how the system is represented. (see.stanford.edu)

Transition matrices and an example

For a homogeneous chain, define $p_{ij}=\Pr(X_{n+1}=j\mid X_n=i)$. These probabilities form a transition matrix $P=(p_{ij})$, a matrix with nonnegative entries whose rows each sum to one. Together with an initial distribution $\mu_0$, it specifies the chain’s law. Using row vectors,

The entry $(P^n)_{ij}$ gives the probability of reaching $j$ after $n$ steps from $i$. The Chapman–Kolmogorov equations express composition of transitions: $P^{m+n}=P^mP^n$. (web.stanford.edu)

As an illustrative calculation, suppose a simplified weather model has states sunny and rainy, with

Starting from sunny weather, the probability of rain two steps later is $0.8(0.2)+0.2(0.6)=0.28$, accounting for both possible intermediate states. This is a hypothetical model, not an empirical weather forecast.

State classification and long-run behavior

States communicate when each can be reached from the other with positive probability. A chain is irreducible if all its states communicate. The period of a state is the greatest common divisor of its possible positive return times; an irreducible chain is aperiodic when this period is one. A deterministic alternation between two states, for example, has period two. (ocw.mit.edu)

A state is recurrent if, starting there, the chain eventually returns with probability one; otherwise, it is transient. A recurrent state is positive recurrent when its expected return time is finite. An absorbing state cannot be left once entered. For a finite absorbing Markov chain, with transient-state block $Q$ and eventual absorption guaranteed, the fundamental matrix $N=(I-Q)^{-1}$ records expected visits to transient states before absorption. (math.dartmouth.edu)

A stationary distribution is a probability vector satisfying

Thus, starting with $\pi$ preserves the same state distribution at every step. In linear algebra terms, it is a normalized nonnegative left eigenvector associated with eigenvalue one. (ocw.mit.edu)

Every finite irreducible chain has a unique stationary distribution. If it is also aperiodic, $\mu_0P^n$ converges to that distribution from every initial distribution. Aperiodicity is not required for long-run empirical state frequencies to converge. For an irreducible countably infinite chain, positive recurrence is required for a stationary probability distribution to exist. These distinctions prevent stationarity, recurrence, and convergence from being treated as interchangeable. (web.mit.edu)

In the illustrative weather model, solving $\pi=\pi P$ gives $\pi=(2/3,1/3)$. The model’s long-run rainy-state frequency is therefore one third, rather than its one-step probability from either particular state.

Reversibility and computation

A stationary chain is reversible when its probabilistic behavior is unchanged by reversing time. For discrete states, detailed balance,

characterizes reversibility and implies stationarity. It equates probability flow between each pair of states, a stronger condition than balancing total incoming and outgoing flow. (ocw.mit.edu)

Markov chain Monte Carlo constructs transitions whose stationary distribution is a desired target distribution. Its algorithms generate dependent samples for estimating distributional quantities. Detailed balance is a common design device, but is not necessary for every valid sampler. Successive samples can remain strongly correlated, so computational accuracy depends on exploration and correlation as well as sample count. (arxiv.org)

Extensions and applications

A continuous-time Markov chain on a finite state space is described by a generator $G$, with nonnegative off-diagonal transition rates and rows summing to zero. Its transition matrix at elapsed time $t$ is $e^{tG}$, and a stationary distribution satisfies $\pi G=0$. Such models describe systems whose transitions need not follow a fixed observation clock. (statslab.cam.ac.uk)

A random walk on a graph is a Markov chain whose states are vertices. Graph walks support network analysis, including PageRank. A hidden Markov model adds observations generated from unobserved Markov states, supporting applications such as speech recognition. A Markov decision process further introduces actions that influence transition probabilities, extending the framework from passive evolution to controlled systems. (ocw.mit.edu)