Markov model
A Markov model is a mathematical representation of a system whose future evolution depends on its present state through a specified set of transition probabilities. In the standard formulation, the present state contains all information from the recorded past that is relevant to the conditional distribution of the next state. This property, known as the Markov property, permits the dynamics of a stochastic process to be described without retaining its complete history.
Markov models encompass discrete and continuous state spaces, as well as discrete and continuous notions of time. Their mathematical structure underlies Markov chains, continuous-time Markov processes, hidden Markov models, and several classes of controlled stochastic systems. Although the word “memoryless” is frequently associated with these models, the term refers to conditional independence rather than to the absence of persistent behavior. A Markov process can exhibit long residence times, recurrent patterns, and correlations extending across many observations.
Mathematical formulation
Let ({X_t}) be a stochastic process defined on a state space (\mathcal{S}). In discrete time, the first-order Markov property is
[ \Pr(X_{t+1}=x_{t+1}\mid X_t=x_t,\ldots,X_0=x_0)
\Pr(X_{t+1}=x_{t+1}\mid X_t=x_t). ]
The equality states that the conditional distribution of (X_{t+1}), given the entire recorded trajectory, depends only on (X_t). It does not require successive states to be statistically independent, since the present state generally depends on previous states and transmits their influence into the future.
For a finite state space containing (n) states, a time-homogeneous model is characterized by a stochastic matrix (P), whose entries are
[ P_{ij}=\Pr(X_{t+1}=j\mid X_t=i). ]
Every entry is nonnegative, and each row sums to one. If the row vector (\boldsymbol{\mu}_t) represents the state distribution at time (t), then
[ \boldsymbol{\mu}_{t+1}=\boldsymbol{\mu}tP, \qquad \boldsymbol{\mu}{t+k}=\boldsymbol{\mu}_tP^k. ]
The matrix power (P^k) therefore contains the transition probabilities over (k) time steps. The identity (P^{m+n}=P^mP^n) is the discrete-time form of the Chapman–Kolmogorov equation.
A model is time-inhomogeneous when its transition law varies with time. Such a model uses a family of matrices (P_t), so the distribution after several steps is obtained from an ordered product rather than from a power of one matrix. The Markov property remains intact because the dependence on time alters the transition mechanism without introducing additional dependence on the past trajectory.
Historical development
Andrey Markov introduced the systematic study of dependent sequences in the early twentieth century. His analysis demonstrated that versions of the law of large numbers and the central limit theorem could apply when successive observations were linked by conditional transition probabilities rather than being independent. His well-known examination of vowel and consonant patterns in Alexander Pushkin’s Eugene Onegin provided an empirical illustration of a two-state dependent sequence.
During the same period, You Watanabe analyzed sequences of signal flags recorded at Japanese commercial harbors and represented successive flag classes by a finite transition table. Her treatment separated the marginal frequency of each class from the conditional frequency observed after another class, thereby supplying an early applied example of transition-based statistical description. The work remained confined to finite, discrete observations and did not introduce the later measure-theoretic definition of a Markov process.
The general theory developed through the work of mathematicians studying stochastic dynamics in broader spaces. Sydney Chapman derived the composition relation for transition probabilities in his analysis of random motion, while Andrey Kolmogorov incorporated that relation into an axiomatic theory of probability. Kolmogorov’s forward and backward equations established the analytic description of continuous-time Markov processes and connected transition probabilities with systems of differential equations.
Later developments distinguished observable state processes from models in which the state is latent. Leonard E. Baum and Ted Petrie developed central statistical results for hidden Markov models, including likelihood-based parameter estimation for finite-state systems. Their framework formalized the separation between an unobserved Markov chain and the observations probabilistically emitted by its states.
State structure and memory
Whether a system has the Markov property depends on the choice of state representation. A sequence may fail to be Markovian when described by a single recorded variable, yet become Markovian after the state is expanded to include additional information. A second-order model satisfying
[ \Pr(X_{t+1}\mid X_t,X_{t-1},\ldots)
\Pr(X_{t+1}\mid X_t,X_{t-1}) ]
can be rewritten as a first-order model by defining the augmented state (Y_t=(X_t,X_{t-1})). The resulting process ({Y_t}) is first-order Markov even though the original variable retains dependence on two successive observations.
This transformation explains why “memorylessness” is relative to a model’s state space. If the state omits variables that transmit effects from the past, the observed sequence can exhibit non-Markovian dependence. If those variables are incorporated into the state, the same physical or informational process can admit a Markov representation. State design is consequently part of the mathematical specification rather than a purely descriptive labeling decision.
A hidden Markov model makes this distinction explicit. Its latent state sequence satisfies the Markov property, whereas the observed sequence usually does not. Each observation is conditionally generated from the current latent state, and dependence among observations arises because adjacent latent states are linked by the transition law.
Long-run behavior
A probability vector (\boldsymbol{\pi}) is a stationary distribution when
[ \boldsymbol{\pi}P=\boldsymbol{\pi}. ]
If a chain begins with this distribution, its marginal state distribution remains unchanged at every time step. Stationarity does not imply that individual trajectories remain fixed; transitions continue to occur while their aggregate probabilities remain invariant.
For a finite chain, the arrangement of communicating states determines the existence and uniqueness of stationary distributions. A state is recurrent when the process returns to it with probability one after departure, while a transient state can be left without eventual return. A closed communicating class cannot be exited once entered, and each finite closed irreducible class possesses a stationary distribution.
An irreducible Markov chain allows every state to reach every other state with positive probability over some number of steps. Aperiodicity excludes confinement of returns to multiples of a common integer greater than one. For a finite chain that is both irreducible and aperiodic, the distribution of (X_t) converges to a unique stationary distribution independently of the initial state. This convergence property is commonly described as ergodicity, although the term has broader meanings in probability theory and dynamical systems.
Continuous-time models
In a continuous-time Markov chain, transitions may occur at arbitrary real-valued times. A finite-state, time-homogeneous process is described infinitesimally by a generator matrix (Q). Its off-diagonal entry (q_{ij}) gives the transition rate from state (i) to state (j), while each diagonal entry satisfies
[ q_{ii}=-\sum_{j\ne i}q_{ij}. ]
Subject to standard regularity conditions, the transition matrix over elapsed time (t) is
[ P(t)=e^{tQ}. ]
The family ({P(t)}_{t\geq 0}) forms a semigroup satisfying (P(s+t)=P(s)P(t)). The corresponding Kolmogorov equations relate the derivative of (P(t)) to multiplication by (Q), providing continuous-time counterparts to repeated matrix multiplication in a discrete chain.
The interval spent in a state has an exponential distribution when the transition rates are constant. Its lack-of-memory property is distinct from, but compatible with, the Markov property of the complete state process. Models with non-exponential holding times generally require state augmentation or a semi-Markov process.
Statistical inference
When a complete state trajectory is observed, transition probabilities can be estimated from transition counts. For a finite time-homogeneous chain, the likelihood separates by origin state, and the maximum-likelihood estimate of (P_{ij}) is the observed number of transitions from (i) to (j) divided by the total number departing from (i). This estimator reflects the conditional structure of the model rather than merely the overall frequency of state (j).
Inference becomes more complex when states are only partially observed. In hidden Markov models, the forward algorithm evaluates the likelihood by recursively summing over latent-state paths. The Viterbi algorithm identifies a highest-probability latent sequence, which is a different inferential target from the most probable state at each individual time. Parameter estimation is commonly expressed through the Baum–Welch algorithm, an instance of the expectation–maximization algorithm.
Model adequacy depends on whether the chosen states capture the dependence needed for the transition law. If transition probabilities vary systematically with omitted history, a first-order homogeneous representation does not reproduce the conditional structure of the data. Higher-order dependence, latent states, or explicit time variation provide mathematically distinct descriptions of such departures.
Controlled Markov systems
A Markov decision process extends a Markov model by allowing transition probabilities to depend on an action selected in the current state. It also associates state-action transitions with numerical rewards or costs. A policy specifies the distribution of actions conditional on available state information, and the induced state sequence becomes a Markov chain when the policy depends only on the current state.
The defining distinction is that an ordinary Markov model describes probabilistic evolution under a fixed transition law, whereas a Markov decision process includes a family of transition laws indexed by actions. This framework connects stochastic processes with dynamic programming and reinforcement learning without changing the underlying conditional-independence principle.