Markov chain

A Markov chain is a sequence of random variables X₀, X₁, X₂, … whose values belong to a set of possible states. In a discrete-time chain, the Markov property says that, once the current state is known, the probability distribution of the next state does not depend on earlier states: the conditional probability of moving to state j at the next step, given the current state i and any earlier states, equals the conditional probability of moving to j given only the current state i, whenever these conditional probabilities are defined. The word “memoryless” refers to this conditional transition rule; it does not mean the process has no history, or that the present state must summarize history in every real-world model. A modeler may need to define a richer state so that the assumption is reasonable.

The state space is the set of possible values of the process. For a time-homogeneous chain, the probability of moving from state i to state j is a fixed transition probability pᵢⱼ, independent of the step number. These probabilities form a transition matrix P: entries are non-negative, and the probabilities in each row sum to one. The chain also needs an initial distribution describing the probabilities assigned to its starting states. A transition diagram can represent states as nodes and possible moves as directed edges labeled with their probabilities.

If the current state distribution is a row vector μ, then after one step it is μP; after n steps it is μPⁿ. The entry (i, j) of Pⁿ gives the probability of being in state j after n steps when starting in state i. The Chapman–Kolmogorov equations express how multi-step probabilities combine over intermediate states. These calculations provide distributions of possible future states, not a guarantee that any single trajectory follows an average or most likely path.

Some chains have a stationary distribution π satisfying πP = π. If the chain begins with this distribution, its state distribution remains π after every step. Under additional conditions—such as irreducibility, aperiodicity and suitable recurrence conditions—the distribution from other starting states can converge to a unique stationary distribution. These conditions matter: a chain may have multiple stationary distributions, or its step-by-step distribution may oscillate instead of converging. For an irreducible, positive recurrent chain, the stationary probabilities also describe the long-run fractions of time spent in its states under the usual ergodic result.

Markov chains are used to model systems in which transitions between defined states can be described probabilistically. Examples include queues, random walks on networks, board games, reliability analysis and methods for sampling from probability distributions. Their simplicity makes them useful for calculation and simulation, but the Markov assumption and the choice of states, transition probabilities, and time scale must be justified for each application. A poorly specified state representation or transition model can yield misleading forecasts, and a stationary distribution should not be confused with a causal explanation or a guarantee about an individual outcome.