A Markov model is a mathematical representation of a changing system in which the current state contains the information from the past needed to describe its future probabilistically. Its defining assumption is the Markov property: conditional on the present state, earlier states provide no additional information about subsequent evolution. This does not mean that successive observations are independent, or that the past has no influence. Rather, past influences relevant to prediction are represented through the current state.
Markov models are fundamental in probability, statistics, and the study of stochastic processes. They describe systems as diverse as particles moving through space, queues of customers, sequences of biological symbols, changing equipment conditions, and decisions made under uncertainty. The term encompasses several related constructions, including observable Markov chains, continuous-time processes, hidden-state models, and controlled models. Their usefulness depends both on the mathematical structure of their transitions and on whether the chosen state captures the information required for the intended application.
State, memory, and mathematical definition
A Markov model begins with a state space , an initial probability distribution, and a rule for transitions between states. The state may be a category, such as an operating mode; a vector of real numbers, such as position and velocity; or a more complex object, such as a configuration of interacting particles. Time may be discrete, indexed by integers, or continuous. The state is therefore a modeling choice, not necessarily a directly measured quantity or a complete physical description.
For a discrete-time process , the Markov property can be written as
for every suitable set , with equality understood almost surely. This is a statement of conditional independence. It differs from ordinary statistical independence because may depend strongly on . A machine that is currently damaged, for example, may be much more likely to fail during the next interval than one that is currently functioning normally.
For a general measurable state space, transitions are described by a probability kernel
For each state , this is a probability measure over possible destinations; for each measurable set , it varies measurably with . The initial distribution and these kernels determine the finite-dimensional distributions of the model. A model is time-homogeneous when the same kernel applies at every time. Homogeneity is an additional assumption, not part of the Markov property itself. A model can be Markovian while its transitions change seasonally or with calendar time.
The familiar first-order condition can be extended to dependence on the most recent states. Such a higher-order model can be represented as a first-order model on an enlarged state,
For an alphabet of possible observations, this construction has up to states. It demonstrates that being Markovian depends on how the state is defined, but also exposes the cost of recording more history. A sufficiently rich state can simplify temporal dependence while making estimation and computation much harder.
The same distinction arises in mechanics. Position alone may not determine a particle’s future distribution, whereas position together with velocity may provide an adequate state. Conversely, aggregating several physical states into one observed category can destroy the Markov property. Thus a Markov model is best understood as a claim about a particular representation of a system at a particular temporal resolution.
Discrete-time chains and transition calculations
A discrete-time Markov chain on a finite or countable state space is specified by transition probabilities. In the time-homogeneous case these form a transition matrix , whose entries are
Every entry is nonnegative, and each row sums to one. Using row-vector notation, an initial distribution evolves according to
The choice of row vectors is conventional; column-vector formulations use transposed matrices.
Consider an illustrative two-state system with states “operational” and “unavailable”:
An operational system remains operational for one more interval with probability , while an unavailable system returns to operation with probability . If it starts operational, its probability of being operational two intervals later is
The second term accounts for an intervening unavailable state followed by recovery. This illustrates why a multi-step transition probability must include every possible intermediate route, not merely repeated persistence in the starting state.
The general composition rule is given by the Chapman–Kolmogorov equations:
For nonhomogeneous chains, the corresponding calculation uses products of successive transition matrices rather than powers of one matrix. The probability of a complete path in a homogeneous chain factors as
This factorization is the basis for likelihood calculations, simulation, and many algorithms for temporal inference.
A transition matrix can also be viewed as a weighted directed graph, with an edge from to whenever . Graph structure identifies states that communicate, inaccessible regions, and absorbing states. A state is absorbing if : once entered, it cannot be left. In a finite absorbing chain, arranging transient states first produces the block form
When eventual absorption occurs with probability one, the fundamental matrix
records expected visits to transient states before absorption. The row sums of give expected absorption times, and gives absorption probabilities. These quantities describe outcomes such as completion, failure, or arrival at a designated boundary without requiring enumeration of all possible paths.
Continuous time and infinitesimal dynamics
A continuous-time Markov chain allows transitions at arbitrary nonnegative times while retaining a discrete state space. Instead of specifying a one-step transition matrix for a fixed interval, it is usually described by a generator . For ,
These off-diagonal entries are transition rates and have units of inverse time. The diagonal entries satisfy
Thus generator rows sum to zero, unlike the rows of a transition matrix.
For a homogeneous jump process with finite exit rate , the holding time in state has an exponential distribution with rate . When , the next destination is with probability . The exponential holding-time assumption is a consequence of the memoryless property: conditional on still occupying the state, the remaining waiting-time distribution does not depend on how long the process has already remained there. It is often the most consequential substantive assumption in a continuous-time model.
For a finite homogeneous chain, the transition matrix over duration is
where the matrix exponential solves the forward and backward equations,
For a row distribution, the forward equation is
A Poisson process is a basic example: its state is the number of events so far, and each transition increases that count by one at a constant rate.
Continuous state spaces lead to other Markov processes. A Wiener process has continuous paths and independent Gaussian increments. More general diffusions can be specified by a stochastic differential equation,
Under standard existence and uniqueness conditions, this construction yields a Markov process. Its infinitesimal generator acts on suitable smooth functions as
The generator links random trajectories to deterministic differential equations for expectations and probability densities.
Infinite state spaces introduce technical issues absent from finite chains. In particular, jump rates may permit infinitely many jumps in finite time, a phenomenon called explosion. Existence, uniqueness, boundary behavior, and conservation of total probability must then be established rather than assumed. Moreover, the ordinary Markov property at deterministic times is distinct from the strong Markov property, which imposes the analogous conditional-future rule at suitable random stopping times.
Recurrence, equilibrium, and long-run behavior
Long-run analysis asks whether a model forgets its initial state, how often it returns to particular regions, and whether time averages approach stable values. A stationary distribution for a discrete-time chain is a probability vector satisfying
For a continuous-time chain, the corresponding equilibrium equation is
Starting the chain with this distribution makes its one-time marginal distributions constant. Stationarity of the initial law should not be confused with time homogeneity of the transition mechanism: a homogeneous chain can begin far from equilibrium.
A chain is irreducible if every state is reachable from every other state in some number of steps. Every finite irreducible chain has a unique stationary distribution. Convergence to it from an arbitrary initial distribution additionally requires aperiodicity in discrete time. A chain that alternates deterministically between two states has stationary distribution , but its distribution from a fixed starting state oscillates forever. Its time averages can nevertheless converge, showing that convergence of distributions and convergence of empirical occupation frequencies are different properties.
On infinite state spaces, irreducibility alone does not guarantee a stationary probability distribution. A recurrent state is returned to with probability one; a transient state has a positive probability of never being revisited. Recurrent states are positive recurrent if the expected return time is finite and null recurrent otherwise. The symmetric nearest-neighbor random walk on the integers is null recurrent: it returns to its starting point almost surely but has no stationary probability distribution. These distinctions are central to queues, where an apparent steady-state formula is meaningful only if the arrival and service dynamics actually support positive recurrence.
For many ergodic chains, averages along one long trajectory satisfy a Markov-chain analogue of the law of large numbers:
For finite irreducible chains this holds for every real-valued state function, including periodic chains. Under additional conditions, a central limit theorem describes fluctuations around the limiting mean. Serial dependence affects their variance: a trajectory of observations generally contains less information than independent draws from the same stationary distribution.
A particularly useful sufficient condition for stationarity is detailed balance,
It implies reversibility: a stationary trajectory has the same distribution when its time order is reversed. Reversibility is not necessary for stationarity, because equilibrium systems can sustain circulating probability flows. Rates of convergence are often studied through eigenvalues and eigenvectors, coupling arguments, or probability-distance bounds. For finite reversible chains, eigenvalues near one signal slowly decaying modes; nearly isolated groups of states can therefore produce very long relaxation times.
Hidden states and observation models
In a hidden Markov model, the process that satisfies the Markov property is not directly observed. A latent state evolves through a transition rule, and an observation is generated from a distribution associated with that state. The standard model assumes that observations are conditionally independent given the latent-state sequence, with each depending only on . Its joint distribution factors as
The observation distributions are often called emission distributions.
This construction separates system dynamics from measurement uncertainty. A sensor reading may be noisy even when the underlying state is stable; alternatively, the state may switch while similar observations continue to appear. The observed sequence is generally not itself a first-order Markov chain. Earlier observations can remain informative because they help identify the current hidden state. Thus a hidden Markov model does not assert that the latest observation alone is sufficient for predicting the next one.
Three inference tasks have distinct meanings. Filtering calculates , the current-state distribution using observations available so far. Prediction propagates that distribution into the future. Smoothing calculates for , allowing later observations to revise beliefs about an earlier state. For a finite-state model, filtering alternates a prediction step,
with a Bayesian update using . Forward–backward recursions perform smoothing.
Computing the most probable complete state sequence is a different task from choosing the most probable state separately at each time. The Viterbi algorithm solves the sequence problem by retaining the best partial path ending in each state. The forward algorithm instead sums over paths to compute observation probabilities. For hidden states and observations, dense implementations of these algorithms generally require operations, rather than enumeration of exponentially many state sequences.
Continuous-state models use the same separation between latent dynamics and observations. In a linear Gaussian model,
with suitable independent Gaussian noises and a Gaussian initial state, the Kalman filter computes exact filtering means and covariance matrices. Nonlinear or non-Gaussian models may require approximation. Hidden-state representations are especially useful when observation error would otherwise be mistaken for rapid state switching, but their interpretation depends on whether different latent structures can actually be distinguished from the observed data.
Estimation, uncertainty, and model comparison
For a fully observed finite-state chain, transition estimation follows directly from the path factorization. Let be the number of observed transitions from to , and let . Conditional on the starting state, the likelihood is proportional to
Maximizing each row under its probability constraints gives the maximum-likelihood estimate
provided . If no departure from a state is observed, its transition row cannot be estimated from those counts alone.
Sparse data create a distinction between an impossible transition and one that has simply not yet been observed. Unrestricted maximum likelihood assigns zero probability to an unobserved destination from a visited state. Regularization or Bayesian inference can stabilize estimates, but their assumptions affect the result. A Dirichlet prior with parameters gives the posterior mean
Known structural zeros should be represented separately rather than automatically receiving positive probability.
For a fully observed continuous-time trajectory, estimation uses both jump counts and exposure times. If is the total observed time spent in state , then an unconstrained off-diagonal rate estimate is
When states are observed only at separated sampling times, intervening jumps are unknown. The likelihood instead involves entries of . Not every discrete transition matrix is the exponential of a valid rate matrix, and some permit more than one such generator, making reconstruction from sampled observations a distinct identification problem.
In hidden-state models, transition counts and state-specific observation statistics are themselves unobserved. The expectation–maximization algorithm alternates between calculating their conditional expectations and maximizing the resulting expected complete-data log likelihood. For finite hidden Markov models this procedure is commonly called Baum–Welch estimation. It increases or preserves the likelihood under the usual exact-update conditions, but it need not find a global optimum. Different initializations can reach different solutions, and latent-state labels can be permuted without changing the observation distribution.
Uncertainty assessment must respect temporal dependence. Treating a trajectory as independent observations can understate standard errors, while random train–test splitting can leak information between adjacent observations. Suitable approaches include likelihood-based intervals, posterior distributions, dependence-aware resampling, and temporally ordered cross-validation. Model comparison may examine predictive performance, state number, transition restrictions, and observation distributions. Good predictive fit does not by itself establish identifiability, nor does an estimated transition association establish causation.
Controlled models and simulation algorithms
A Markov decision process adds actions and rewards to state dynamics. At time , an action affects the next-state distribution through , while a reward function records the value or cost of the transition. A policy specifies how actions are chosen. The controlled Markov assumption states that the next-state distribution, conditional on current state and action, does not additionally depend on the preceding history. It does not require all policies to be memoryless.
For a finite model with bounded rewards and discount factor , the optimal value function satisfies the Bellman optimality equation
Under these conditions, a stationary deterministic optimal policy exists. Algorithms such as value iteration exploit the recursive structure rather than evaluating every possible future action sequence. Average-reward and undiscounted problems require different assumptions; conclusions from the discounted finite-state case do not transfer automatically.
When the decision maker cannot observe the underlying state, the model becomes a partially observable Markov decision process. A probability distribution over hidden states—the belief state—can serve as the state of a fully observed control problem. The belief is updated from actions and observations using Bayesian filtering. Even when the underlying state space is finite, the space of beliefs is continuous, which substantially increases computational difficulty. State estimation and action selection are coupled because actions can influence both outcomes and future information.
Markov models also underlie Markov chain Monte Carlo, where a chain is constructed to sample from a target distribution rather than to represent the literal dynamics of a physical system. In the Metropolis–Hastings algorithm, a proposed move from to , drawn from , is accepted with probability
when the ratio is defined. The acceptance rule can establish detailed balance with the target . An unknown normalizing constant cancels from the ratio, enabling computation with distributions known only up to proportionality.
Having the desired stationary distribution is not enough to guarantee useful simulation. The chain must reach the relevant regions and move between them on a practical timescale. Strong autocorrelation, isolated modes, or poorly chosen proposals can make a long run contain little effective information. General Monte Carlo estimates based on Markov trajectories therefore require attention to initialization, convergence, and sampling variability. This computational use illustrates a central distinction: a Markov model may be an empirical description, a decision framework, or an intentionally designed numerical mechanism.
Applications across scientific and technical fields
Queueing systems provide a direct connection between modeling assumptions and operational quantities. In an queue, arrivals form a Poisson process with rate , service times are independent exponentials with rate , and one server handles customers. The number in the system is a continuous-time Markov chain with upward rate and downward rate whenever the queue is nonempty. When , its stationary distribution and mean are
At , there is no stationary probability distribution for this standard infinite-capacity model.
In population and molecular science, Markov models describe events that change counts or configurations. Birth–death chains represent populations with one-unit increases and decreases; chemical reaction models use state vectors of molecule counts and reaction-specific jump rates. Sequence models in genomics assign probabilities to nucleotides, coding regions, or other latent categories. Continuous-time nucleotide-substitution models describe changes along evolutionary lineages through rate matrices, explicitly allowing more than one substitution between observed endpoints. Their states and assumptions differ from hidden-state segmentation models, even though both use Markov mathematics.
Engineering reliability models represent working, degraded, failed, and repaired conditions. Their outputs can include availability, expected time to failure, and probabilities of entering hazardous configurations. Absorbing-state constructions represent irreversible failure, whereas repairable systems contain return transitions. In formal verification, probabilistic model checking evaluates properties such as the probability of eventually reaching an error state or reaching a target within a prescribed time. These calculations operate on a specified transition system; their validity as statements about equipment or software depends on the fidelity of that system.
Language and signal applications often use state to summarize recent context or an unobserved source. An -gram language model makes the next-symbol distribution depend on the preceding symbols. Hidden Markov models became important in speech recognition by separating latent acoustic-state progressions from measured speech features. In tracking, continuous-state filtering models separate motion dynamics from noisy observations. Across these applications, increasing state detail can improve representation but also enlarge the number of parameters and the computational burden.
Networks offer another prominent example. PageRank assigns scores through the stationary distribution of a random walk on a web-link graph, modified by a teleportation mechanism that permits movement independently of the current page’s outgoing links. In econometrics, regime-switching models use latent states to represent changes between different statistical dynamics, while credit-transition matrices describe movements between rating categories. Such models summarize patterns at a specified scale; stationarity and Markov assumptions must be distinguished from claims that the same patterns will persist under changed economic or institutional conditions.
Historical development
The mathematical study of Markov models originated with the Russian mathematician Andrey Andreyevich Markov. In 1906 he began publishing work on dependent random variables that became foundational for Markov-chain theory. A central issue was whether results resembling the law of large numbers could hold without independence. This motivation is important: Markov chains were introduced not as a dismissal of dependence, but as a structured way to study it.
In a 1913 analysis, Markov classified a sequence of 20,000 letters from Alexander Pushkin’s verse novel Eugene Onegin into vowels and consonants and examined their succession. The example demonstrated measurable dependence between neighboring symbols using a comparatively simple state description. It anticipated later statistical treatments of symbolic sequences, although it was not a modern hidden-state language model and should not be interpreted as a complete account of linguistic structure.
During the early twentieth century, work by mathematicians including Maurice Fréchet and Andrey Kolmogorov broadened the theory. Kolmogorov’s 1931 paper on analytical methods in probability connected transition probabilities with differential equations, helping establish the modern framework for continuous-time processes. His 1933 axiomatization of probability supplied a general measure-theoretic setting. Subsequent developments distinguished finite chains from processes on general state spaces and clarified recurrence, invariant measures, stopping times, and conditions for existence.
Several mid-century advances connected the theory to computation and control. Nicholas Metropolis and colleagues introduced a Markov-chain sampling procedure in 1953; W. K. Hastings generalized the method in 1970. Richard Bellman’s work on dynamic programming in the 1950s provided recursive methods for sequential decision problems, while Ronald Howard’s 1960 book Dynamic Programming and Markov Processes developed computational approaches to Markov decision problems. Rudolf Kalman’s 1960 filtering paper established a major state-space method for linear estimation.
Hidden Markov modeling developed through work on probabilistic functions of Markov chains and through statistical algorithms associated with Leonard Baum and collaborators in the 1960s and early 1970s. Applications in speech recognition subsequently made these methods prominent in engineering; Lawrence Rabiner’s 1989 tutorial became a widely used exposition. Later applications in biological sequence analysis, machine learning, and large-scale simulation drew on this accumulated theory. The phrase “Markov model” consequently came to designate a broad family of related representations rather than a single model introduced at one historical moment.
Model adequacy, coarse-graining, and limitations
The principal substantive question is whether the chosen state is sufficient for the predictive task. If transition probabilities depend on elapsed time in a state, unrecorded earlier events, or persistent external conditions, a first-order homogeneous model may be inadequate. For example, a component’s probability of failure may depend on age even after conditioning on a broad “working” category. Adding age, usage, or degradation measurements can improve the state representation, but changes the model’s dimension and data requirements.
Duration distributions reveal one common mismatch. In a homogeneous discrete-time chain, the number of consecutive visits to a state has a geometric distribution; in a homogeneous continuous-time jump chain, holding times are exponential. These restrictions imply memoryless persistence. A semi-Markov model separates the destination mechanism from a more general holding-time distribution, allowing transition behavior to depend on how long the current state has lasted. Another approach introduces several hidden substates whose combined residence time is more flexible than a single exponential duration.
Aggregation creates a different problem. Even if a detailed process is Markovian, grouping its states into broad categories need not preserve that property. For an aggregated finite-state chain to behave consistently as a Markov chain for every initial distribution, a standard sufficient and necessary condition is strong lumpability: any two detailed states within the same group must have the same total transition probability into each destination group. Without that condition, the next observed category can depend on the unobserved composition within the current category, which in turn can depend on earlier observations.
Temporal resolution also matters. Regular subsampling of a homogeneous discrete-time chain preserves the Markov property, with transition matrix when every th state is retained. Exact sampling of a homogeneous continuous-time chain at interval gives . However, noisy observation, state aggregation, or interval-averaged measurements may destroy the Markov property of the recorded sequence. A model that appears adequate at one sampling interval may therefore fail at another, especially when fast transitions are hidden by coarse measurements.
Adequacy can be investigated through conditional transition comparisons, residence-time distributions, multi-step predictive checks, and residual dependence. Posterior predictive checking can compare observed features with those generated by a fitted model, while temporally separated validation tests prediction under later conditions. Such checks cannot prove that no relevant memory remains: finite datasets have limited power, particularly for rare states and transitions. In high-dimensional systems, the curse of dimensionality further constrains how much historical information can be encoded explicitly. Choosing a state therefore involves a concrete trade-off between temporal sufficiency, interpretability, statistical support, and computational tractability.