Markov process

A Markov process is a stochastic process whose present state contains all the information in its observed past needed to predict its future. Precisely, if ${\mathcal{F}}_s$ is the natural filtration generated by observations up to time $s$, then, for $t>s$ and any measurable set $A$ of states,The equality is between conditional probabilities and holds almost surely. It expresses the Markov property: the past and future have conditional independence given the present. It does not assert independence of consecutive states. In the sunny/rainy example below, tomorrow's sunny probability is $0.8$ after sunshine but $0.4$ after rain, so knowing today's state matters.

The memory assumption concerns the chosen state space. If an equipment model's failure probability depends on its age, recording only “working” or “failed” may lose relevant information; recording age as part of the state can retain it. Similarly, a dependence on two previous observations can sometimes be represented by using their ordered pair as the current state. Whether such a description fits observations is a modeling question.

Transition Markov kernels describe the conditional distribution of a state at a later time. Successive kernels and the initial probability distribution determine every finite-dimensional distribution, through repeated conditional probability. The time-homogeneous Markov property is an additional assumption: the kernel depends on elapsed time rather than calendar time. The attraction is compression: prediction can proceed from a current state instead of an entire recorded history. Brownian motion and continuous-time Markov chains illustrate that a Markov process need not evolve in discrete time.

A random affine recursion updates a real random variable by $X_n=A_n{X}_{n-1}+B_n$. Assume the coefficient pairs $(A_n,B_n)$ are independent and identically distributed random variables, independent of the initial value. The two coordinates within a pair may be dependent. Fresh coefficients make the recursion a time-homogeneous Markov process: its next conditional distribution depends on the current value alone.

The competition between the random multiplier and the fresh input determines whether initial conditions are forgotten. A synchronous coupling makes this particularly visible by using the same coefficient sequence for two initial values.

Let $U_n$ have the uniform distribution on $[0,1]$ and let $E_n$ have an exponential distribution of rate $\lambda >0$, with all these inputs independent. The random affine recursion $X_n=U_n(X_{n-1}+E_n)$ has an invariant exponential law of the same rate. Indeed, for independent exponential $X,E$, beta-gamma independence says that $V=X/(X+E)$ is uniform and independent of $W=X+E$. Thus an independent uniform $U$ gives $UW$ the same law as $VW=X$.

For any deterministic real initial value $c$, couple the recursion to a stationary copy. Synchronous contraction of a random affine recursion gives an expected difference $2^{-n}\mathbb{E}|c-X_0|\le 2^{-n}(|c|+{\lambda }^{-1})$. Hence the one-time laws converge to $\mathrm{Exp}(\lambda )$, independently of $c$. An invariant initialization keeps every one-time law unchanged while the chain continues to fluctuate.

Drive two copies of a random affine recursion with the same coefficient pairs, independent of their initial coupling. Then $X_n-Y_n=A_n(X_{n-1}-Y_{n-1})$. If $\rho =\mathbb{E}|A_1|<1$ and $\mathbb{E}|X_0-Y_0|<\infty$, independence of random variables givesThis proves convergence in L1 and hence convergence in probability of the difference. If one copy starts in a stationary distribution, Slutsky's theorem shows that the other copy converges to that distribution. The argument compares paths before taking their one-time probability distributions; it does not require the paths ever to become exactly equal.

A Markov process following a deterministic flow of a vector field between random jumps, with jump hazard function $\alpha (X_{t-})$ and destination transition kernel $K_t(X_{t-},dy)$. The integrated rate along the flowing path determines the next jump time. Retaining instead the holding times of a different piecewise-constant process need not yield a Markov process in the flowing state. Assume nonexplosion when describing paths at all finite times.

If the destination transition kernel has probability density function $m_t(x,y)$, the formal adjoint operator of $L_{t}f=a{f}^{\prime }+\alpha (K_{t}f-f)$ is $(L_t^{\ast }p)(x)=-{\partial }_x(a(t,x)p(x))-\alpha (x)p(x)+\int \alpha (y)m_t(y,x)p(y)dy$. Multiply by a smooth compactly supported test function, use integration by parts on transport and Fubini's theorem on the jump gain to prove the formula when the integrals are finite. The general formulation is $\frac{d}{dt}\int fd{\nu }_t=\int L_{t}fd{\nu }_t$ for probability measures ${\nu }_t$. A deterministic initial value leaves positive no-jump atomic mass at finite times, so a full smooth density cannot be assumed for that initialization.

The no-jump part of a piecewise-deterministic Markov process. The chain rule gives ${\partial }_t{P}_{s,t}^{\alpha }f=P_{s,t}^{\alpha }{L}_t^{\alpha }f$, where $L_t^{\alpha }f=a(t,\cdot )f^{\prime }-\alpha f$. The time subscript is essential for a time-dependent vector field.

For a piecewise-deterministic Markov process, conditional on no jump before $u$, the state is $z(u)=\phi (s,x,u)$ and the survival probability is $S(u)=\exp [-{\int }_s^u\alpha (z(r))dr]$. The first jump has probability density function $\alpha (z(u))S(u)$; conditioning on its time and its destination gives $P_{s,t}f(x)=S(t)f(z(t))+{\int }_s^t\alpha (z(u))S(u)\int P_{u,t}f(y)K_u(z(u),dy)du$. This proves the identity for bounded Borel measurable functions under nonexplosion.

A positive linear operator on bounded measurable functions that preserves the constant function one. A Markov semigroup is a time-indexed family of such operators with the semigroup law.

The transition operators of a time-homogeneous Markov process satisfy $P_{t+s}=P_t{P}_s$ by the Markov property. They preserve constants and positivity. When the generator and function domain permit differentiation, ${\partial }_t{P}_{t}g=L(P_{t}g)$ is the Kolmogorov backward equation. Transition semigroup of a continuous-time Markov chain is the discrete-state special case.

A probability measure is invariant for a Markov process with transition semigroup $P_t$ when starting with that law gives the same law at every later time. Equivalently, $\int P_{t}fd\nu =\int fd\nu$ for every bounded measurable function. Invariant laws may be constructed by weak convergence of probability measures of evolved laws when the Feller semigroup property permits passing the semigroup through the limit, as for the extremal invariant measures of the contact process.

An affine process is a time-homogeneous Markov process whose conditional moment-generating function is exponential-affine in its starting state. In discrete time one writes $\log {\mathbb{E}}_x{e}^{\theta X_1}=A(\theta )x+B(\theta )$ on the finite exponential moment domain. Continuous-time definitions allow the functions to depend also on elapsed time.

An autoregressive process of order one with independent and identically distributed random variables as innovations is an affine process when the innovation exponential moments are finite. Its one-step coefficients are $A(\theta )=a\theta$ and $B(\theta )=b\theta +\psi (\theta )$, where $\psi$ is the innovation cumulant-generating function.

For a scalar discrete-time affine process, the conditional cumulant-generating function of ${\sum }_{j=1}^t{\theta }_j{X}_j$ is affine in $X_0$. Backward effective parameters $q_t={\theta }_t$, $q_j={\theta }_j+A(q_{j+1})$ give coefficients $A(q_1)$ and ${\sum }_{j}B(q_j)$.

For a killed Markov process and a positive harmonic function $h$, its Doob h-transform weights the path law through a stopping time $\tau$ by $h(X_{\tau })/h(X_0)$, with localization when necessary. It describes conditioning on a boundary behaviour of probability zero. In the complex upper half-plane, $h(z)=\mathrm{Im}z$ conditions killed planar Brownian motion to remain in that half-plane.

If $h>0$ is smooth and $Z_t=h(X_t,t)$ is the unit-mean density martingale of a locally absolutely continuous probability measure relative to Wiener measure, then $h_t+\frac{1}{2}{h}_{xx}=0$. The Itô formula gives $Z=\mathcal{E}(\int (h_x/h)(X_s,s)d{X}_s)$ when $Z_0=1$. The true-martingale hypothesis is already supplied by the density process. On each finite horizon the Girsanov theorem makes $X-\int (h_x/h)(X_s,s)ds$ Brownian under the new measure. Positivity provides local equivalence; global infinite-horizon equivalence and the Novikov condition are not additional requirements.

Killed planar Brownian motion conditioned to exit at a smooth boundary point $a$ is the Doob h-transform by its positive Poisson kernel, normalized at the starting point. Its generator is $\frac{1}{2}\Delta +\nabla \log h\cdot \nabla$. Conditioning on shrinking boundary arcs yields the same localized laws and specifies a canonical version of an otherwise probability-zero conditioning event.

Consider a path of planar Brownian motion in the unit disc $D$, started at $0$ and conditioned to exit at $1$. Let $U\subseteq D$ be a simply connected domain containing $0$ and agreeing with $D$ near $1$. Let ${\Phi }_U:U\to D$ be a conformal map normalized by ${\Phi }_U(0)=0$ and ${\Phi }_U(1)=1$. ThenThe conditional probability is the ratio of the boundary Poisson kernel densities for exit at $1$ in $U$ and in $D$. The conformal transformation rule for the Poisson kernel contributes the boundary derivative $|{\Phi }_U^{\prime }(1)|$; the normalized interior image is still $0$, so no additional conformal-radius factor appears. Given avoidance of $D\setminus U$, the mapped path has the original conditioned law, with the conformal Brownian clock accounting for its time parametrization.

A Hidden Markov model combines an unobserved Markov chain $Z_1,\dots ,Z_T$ with observations $O_1,\dots ,O_T$. Given the whole hidden-state path, the observations have conditional independence, and the conditional distribution of $O_t$ depends only on $Z_t$. The state-transition assumption and this emission assumption are separate parts of the model.^[ref]

For a time-homogeneous model with a finite hidden state space and discrete observations, write ${\pi }_i=P(Z_1=i)$, $a_{ij}=P(Z_{t+1}=j\mid Z_t=i)$ and $b_i(o)=P(O_t=o\mid Z_t=i)$ for the emission probabilities. The joint probability mass function factors asFor continuous observations, appropriate probability density functions replace the emission probability mass functions.

For example, a hidden state can describe whether a machine is working normally or has a fault, while a noisy sensor emits a positive or negative signal. Both states may emit a positive signal, with different probabilities; one observation therefore need not identify the state. Summing the factorization over hidden paths gives the observation likelihood. The forward algorithm reuses partial sums to compute it, and the backward algorithm helps infer hidden-state posterior probabilities. The observations alone need not satisfy the Markov property.

An emission probability in a Hidden Markov model is the probability of an observation conditional on its hidden state. For a finite observation alphabet, each state's emission probabilities sum to one. A match state can therefore emit several different characters, each with its own probability.

The backward algorithm computes suffix likelihoods in a Hidden Markov model. With ${\beta }_t(i)=P(o_{t+1},\dots ,o_T\mid Z_t=i)$, its recurrence is ${\beta }_t(i)={\sum }_j{a}_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)$. Together with the forward algorithm, it gives posterior state probabilities proportional to ${\alpha }_t(i){\beta }_t(i)$. The terminal condition must include any explicit End-state transition.

The forward algorithm computes sequence likelihoods by summing over all hidden paths through a Hidden Markov model. For emitting states, ${\alpha }_t(i)=P(o_1,\dots ,o_t,Z_t=i)$ obeys ${\alpha }_{t+1}(j)=b_j(o_{t+1}){\sum }_i{\alpha }_t(i)a_{ij}$. It reuses partial sums rather than enumerating exponentially many state sequences. Silent states require additional transitions without consuming an observation. Scaling or log-sum-exp prevents floating-point underflow.

An insertion state in a profile hidden Markov model emits characters between successive match states. A bypass allows zero inserted characters and a self-transition allows several. Under a fixed loop probability $r<1$, the length of an insertion run conditional on entering has a geometric distribution on positive integers with exit probability $1-r$.

A match state in a profile hidden Markov model emits one aligned character at a particular profile position whenever it is visited. “Match” names its alignment role, not a requirement to emit one deterministic character or to match another sequence exactly.

A profile hidden Markov model represents the position-dependent structure of a sequence alignment using an ordered series of match states and optional insertion states, commonly with silent deletion states as well. An emitting state chooses one character from its probability mass function; transitions describe which profile position comes next. If deletion states are forbidden, an alignment column containing gaps cannot be a compulsory match state.

In a screening misclassification model, true disease states are latent and screen results are emissions. A cancer-free state may emit a positive result with a false positive rate, while a perfectly sensitive pre-clinical state always emits a positive result. Conditional independence of emissions given latent states is an additional model assumption, not a consequence of a marginal false-positive rate.

For a time-homogeneous Markov process with transition kernel $P_t(x,dy)$,When transition densities exist, this becomes

The term Markov chain commonly denotes a Markov process on a finite or countable state space. Time may be discrete, as for a daily record, or continuous, as for a continuous-time Markov chain. Some authors also use “Markov chain” for discrete-time processes on more general state spaces; specifying both time and state space avoids this ambiguity.

For a Discrete-time Markov chain, its initial probability distribution ${\mu }_0$ and transition matrix $P$ specify the probability of each finite path:This is the Markov factorization, obtained by applying conditional probability repeatedly. See Hao Wu's MIT lecture 1, definition and distribution evolution.

For the constructed sunny/rainy Markov chain below, starting sunny makes the path sunny, rainy, sunny have probability $1\times 0.2\times 0.4=0.08$. Starting instead with stationary distribution $(2/3,1/3)$ makes that path's probability $(2/3)\times 0.2\times 0.4=4/75$. The transition probabilities are identical in both experiments; the initial probability distribution distinguishes them.

A two-phase inspection model alternates between inspecting every item and inspecting each item with probability $1/r$, where $r>1$. Suppose item defects are independent with probability $p\in (0,1)$. The first phase ends after $K\ge 1$ good items have been accumulated, while the second ends upon detecting a defect. With state $i<K$ equal to the cumulative number of good items found during the current full-inspection phase, the Markov chain has transitions $P_{ii}=p$, $P_{i,i+1}=q=1-p$, $P_{K0}=p/r$, $P_{KK}=1-p/r$.

Its stationary distribution is ${\pi }_i=p/(Kp+rq)$ for $i<K$ and ${\pi }_K=rq/(Kp+rq)$. Indeed, balance gives equal mass to every phase-A state and $p{\pi }_K/r=q{\pi }_{K-1}$; normalization fixes the common mass. The finite chain is irreducible and aperiodic, so the Markov chain ergodic theorem identifies these probabilities with long-run occupation fractions. The long-run inspected fraction is $1-(1-1/r){\pi }_K=(Kp+q)/(Kp+rq)$. The fraction of all production consisting of undetected defective items is $p(1-1/r){\pi }_K=p(r-1)q/(Kp+rq)$.

An important modeling choice is whether defects during full inspection preserve accumulated good items or reset the count. Resetting produces the distinct consecutive-clearance inspection model and changes the long-run fractions.

In the consecutive-clearance inspection model, a run of $K$ consecutive good items is required to leave full inspection. With $q=1-p$, $0<p<1$, its Markov chain has transitions $P_{i0}=p$, $P_{i,i+1}=q$ for $i<K$, and $P_{K0}=p/r$, $P_{KK}=1-p/r$. Thus every defect in the clearance phase resets the count, rather than preserving the cumulative total.

Writing $D=1+(r-1)q^K$, the stationary distribution isTo prove this, balance at $i=1,\dots ,K-1$ gives ${\pi }_i=q^i{\pi }_0$, while balance at $K$ gives $(p/r){\pi }_K=q^K{\pi }_0$. Summing the geometric series and normalizing gives ${\pi }_0=p/D$; balance at zero follows as well. The inspected fraction is $1-(1-1/r){\pi }_K=1/D$. The fraction of all production that is both defective and uninspected is $p(r-1)q^K/D$; the fraction among defective items alone is $(r-1)q^K/D$. All these long-run limits follow from the Markov chain ergodic theorem and the independent inspection coins. The distinction from cumulative clearance matters already at $K=2$.

Fix $0<p<1$. The immigration chain with complete population resets has states $0,1,2,\dots$: from zero it moves to one, and from a positive state $j$ it moves to zero with Probability $p$ or to $j+1$ with Probability $1-p$. Its Stationary distribution isStationarity gives ${\pi }_1={\pi }_0$ and ${\pi }_j=(1-p{)}^{j-1}{\pi }_0$ for $j\ge 1$. Summing the geometric tail yields total mass ${\pi }_0(1+1/p)$, giving the normalization.

Every state communicates with zero, and a return from zero takes one initial step plus a positive-support geometric waiting time of mean $1/p$. Thus the chain is irreducible and positive recurrent. Return lengths two and three have positive Probability, making it aperiodic. The ergodic occupation fraction above a positive integer $K$ is the stationary tail $(1-p{)}^K/(1+p)$.

The endpoint cases have different behavior. At $p=1$, the closed class $\{0,1\}$ alternates deterministically and is periodic; the full countable chain is not irreducible. At $p=0$, the chain increases forever and the displayed zero weights do not normalize. The strict parameter interval is therefore needed for the irreducibility and aperiodicity claims.

On the finite path $\{0,\dots ,m\}$, take interior neighbor probabilities $p$, endpoint inward Probability $2p$, and holding Probability $1-2p$, with $0<p\le 1/2$. Detailed balance gives the displayed invariant distribution: endpoint weights are half the interior weights. For $p<1/2$ the chain is irreducible and aperiodic, so transition probabilities converge to it. At $p=1/2$ parity alternates and the period is two.

Let $(X_n)$ be a time-homogeneous Markov chain with transition matrix $P$, and let $d$ be a positive integer. Then $Y_n=X_{dn}$ is a Markov chain with transition matrix $P^d$ and the same initial distribution. The Markov property and the Chapman-Kolmogorov equation give $P(X_{d(n+1)}=j\mid X_0,\dots ,X_{dn})=(P^d{)}_{X_{dn},j}$. Conditioning again on the smaller history $(Y_0,\dots ,Y_n)$ leaves the right-hand side unchanged, since it is determined by $Y_n$. This proves the Markov property of the sampled sequence, rather than only identifying its marginal transition probabilities. Periodicity of the original chain may split the sampled chain into several closed classes.

The empirical occupation proportion is the fraction of the observed Markov chain states equal to $j$. These nonnegative fractions sum to one. To simulate them from a transition matrix, sample an initial state and then draw each successive state from the current state's row, accumulating visit counts. They are empirical frequencies for a finite path, whether or not the chain is already stationary. Long-run convergence to a Stationary distribution requires the corresponding recurrence and irreducibility hypotheses.

A finite stock decreases by choosing a uniformly random positive number of its remaining items at every step. The remaining stock is a Markov chain with $P(i,j)=1/i$ for $0\le j<i$ and $P(0,0)=1$. State $0$ is an absorbing state, and every positive state is a transient state. If $e_i$ denotes the expected number of positive-stock steps before absorption, a first-step decomposition gives $e_0=0$ and $i{e}_i=i+{\sum }_{j<i}{e}_j$. Subtracting consecutive equations yields $e_i-e_{i-1}=1/i$, so $e_i=H_i$, the $i$th harmonic number.

Refill the stock to a fixed positive size $N$ immediately whenever a step empties it. The resulting Markov chain has state space $\{1,\dots ,N\}$ and transitions $P(i,j)=1/i$ for $j<i$ and $P(i,N)=1/i$. It is irreducible and aperiodic, since every state reaches $N$, $N$ reaches every state, and $P(N,N)>0$. Its unique stationary distribution is ${\pi }_N=1/H_N$ and ${\pi }_k=1/((k+1)H_N)$ for $k<N$. Normalization is the harmonic number identity. For $k<N$, stationarity follows from ${\sum }_{j=k+1}^{N-1}1/(j(j+1))+1/N=1/(k+1)$; the same telescoping sum starting at $1$ gives stationarity at $N$. The finite-state convergence theorem therefore makes this stationary distribution the limiting distribution from every initial state.