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 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.

For a Brownian path in the unit disc from $0$ conditioned to exit at $1$, let ${\Phi }_U:U\to D$ fix $0$ and $1$, and suppose $U$ agrees with the disc near $1$. The probability of avoiding $D\setminus U$ is the ratio of the boundary Poisson-kernel densities, hence $|{\Phi }_U^{\prime }(1)|$. Given avoidance, the conformally mapped path has the original law up to the conformal Brownian clock. There is no conformal-radius factor at the interior starting point.

A hidden Markov model is a Markov process whose state is latent and observed only through random emissions whose conditional distribution depends on the current hidden 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 harmonic function assigns a value to each state of a Markov chain such that one transition leaves its expected value unchanged. This turns a question about many possible future sample paths, such as which endpoint is reached first, into a local averaging rule. For a transition matrix $P$, a real-valued function $h$ is harmonic at state $i$ whenHere ${\mathbb{E}}_i$ means expected value conditional on starting at $X_0=i$; on a countable state space the sum must be absolutely convergent. If this holds at every state, write $Ph=h$. At an absorbing state the equation is automatic, so prescribed boundary conditions supply information that the averaging rule cannot.

For a finite Markov chain, choose a boundary set $B$ that can be reached from every state, and assign boundary values $b$. If $T_B$ is its first hitting time, the harmonic extension isChoosing $b$ to be the indicator function of one target within $B$ gives a hitting probability. This is a discrete Dirichlet problem: enforce the averaging rule outside $B$ and fix the values on $B$. See Hao Wu's MIT lecture 8, harmonic extension, slide 5. The construction extends the mean-value idea of a harmonic function; for a random walk on a graph it is a discrete harmonic function.

Take a birth-death chain on $\{0,1,2,3,4\}$. At each interior state, move up one state with probability $p=1/2$ and down one state with probability $q=1/2$. The endpoints are absorbing states: $P_{00}=P_{44}=1$. This is a small gambler's ruin model in which the state can represent capital, and reaching $4$ is success.

Let $T_a=\inf \{n\ge 0:X_n=a\}$ be the hitting time of endpoint $a$, and let $T=\min (T_0,T_4)$ be the first endpoint hitting time. The desired hitting probability is $h_i={\mathbb{P}}_i(T_4<T_0)$. First-step analysis and the Markov property giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values $0$ and $1$, soFor example, from state $2$ the hitting probability is $1/2$, and its one-step average is $\frac{1}{2}(1/4)+\frac{1}{2}(3/4)=1/2$. Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.

Now ask how long it takes to reach either endpoint. The expected hitting time $t_i={\mathbb{E}}_{i}T$ counts steps, including the transition that first reaches an endpoint. First-step analysis givesThis is a discrete Poisson equation, $(I-P)t=1$ in the interior. The extra $1$ counts the step just taken. The quadratic valuessatisfy the equations; from state $2$, $t_2=1+\frac{1}{2}(3)+\frac{1}{2}(3)=4$ steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.

For a biased random walk with $p=0.6$ upward and $q=0.4$ downward, keep the same absorbing states. The interior harmonic equation becomes $h_i=p{h}_{i+1}+q{h}_{i-1}$. Using biased gambler's ruin probability with these boundary values givesThe three interior hitting probabilities are approximately $0.415385$, $0.692308$, and $0.876923$. Thus starting at $2$ now succeeds about $69.23\%$ of the time. A direct check is $0.6(57/65)+0.4(27/65)=9/13$. The curved profile reflects the unequal transition weights: its successive increments shrink by the factor $q/p=2/3$. The formula, with the endpoint denoted $T$ there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.

Why does harmonic averaging produce the correct hitting probability? With the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property gives the conditional expectation identityFor a function harmonic everywhere, this makes $h(X_n)$ a martingale whenever it is integrable. For a function harmonic only in the interior, $M_n=h(X_{n\wedge T})$ is a stopped martingale. In either five-state example, $0\le M_n\le 1$. Also, from any interior state at most three consecutive upward steps reach $4$, with probability at least $p^3>0$. Repeated three-step blocks give ${\mathbb{P}}_i(T>3k)\le (1-p^3{)}^k$, so $T$ is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at $n\wedge T$ and then the bounded convergence theorem givesThe boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.

Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.

// Target: markov-process.bigb

Take states $0,n,n^{\prime }$ for $n\ge 1$, with $0\to 1^{\prime }$ deterministic and transitions $n\to n-1$ with probability $q$, $n\to (n+1{)}^{\prime }$ with probability $p=1-q$, $n^{\prime }\to n$ with probability $q$, and $n^{\prime }\to (n+1{)}^{\prime }$ with probability $p$. The Markov chain is transient for $q<q_c$, null recurrent for $q=q_c$, and positive recurrent for $q>q_c$. To see the Markov chain recurrence threshold, eliminate the primed-state hitting probabilities to obtain $p(1+q)a_{n+1}-(1+pq)a_n+q{a}_{n-1}=0$, with characteristic roots $1$ and $q/(1-q^2)$. Boundedness forces return with probability one when the second root is at least one. When it is below one, the minimal nonnegative solution gives return probability $q^2/p<1$ from $0$. In the positive recurrent case, put $t=(1-q^2)/q$ and $D=q^2+q-1$. The stationary distribution is ${\pi }_0=D/[q(q+2)]$, ${\pi }_n=({\pi }_0/q)t^{n-1}$ and ${\pi }_{n^{\prime }}={\pi }_0{t}^{n-1}$. It follows from balance across each level cut and sums to one; at criticality the invariant weights cannot be normalized.

For $P_{ii}<1$, observe a discrete-time Markov chain only when its state changes. The probability that its next different state is $j$ is ${\sum }_{r\ge 0}{P}_{ii}^r{P}_{ij}=P_{ij}/(1-P_{ii})$. Its holding times are finite geometric waiting times. This construction deletes self-transitions and differs from the existing continuous-time jump-chain concept.

An irreducible recurrent discrete-time Markov chain with at least two states has $P_{ii}<1$ everywhere. Removing repeated consecutive states from a positive-probability path proves irreducibility of its discrete-time jump chain. Each sojourn in a state is almost surely finite; infinitely many visits to a recurrent state therefore correspond to infinitely many distinct returning sojourns. The jump chain remains recurrent, although deleting holding times may change periodicity.

Let independent $D_n$ have $\mathbb{P}(D_n=k)=p{q}^k$, $k\ge 0$, $q=1-p$. The displayed chain has transition probabilities $P_{ij}=p{q}^{i-j+1}$ for $1\le j\le i+1$ and $P_{i0}=q^{i+1}$. Its probability of hitting zero from $i\ge 1$ is one when $p\le 1/2$ and $(q/p{)}^{i+1}$ when $p>1/2$. The first-step boundary equation at $i=1$ is essential for the extra exponent. The chain is positive recurrent for $p<1/2$, with stationary probabilities $(1-p/q)(p/q{)}^j$, null recurrent at $p=1/2$, and transient for $p>1/2$.

At a junction, let $a_j$ be the probability that one excursion leaves through branch $j$ and never returns. If $a=\sum a_j>0$, repeated returns restart the same probabilities by the Strong Markov property. Thus the probability of $m$ returns is $(1-a{)}^m$, and eventual escape through $j$ is ${\sum }_{m\ge 0}(1-a{)}^m{a}_j=a_j/a$. When the branches have outward random-walk drift, the final infinite excursion tends to the corresponding end almost surely.

A time-homogeneous Discrete-time Markov chain is a sequence of random variables $Y_0,Y_1,\dots$ indexed by nonnegative integers, with the displayed conditional probabilities. Here ${\mathcal{F}}_n$ is its natural filtration and $P$ is a row-stochastic transition matrix. The Markov property removes dependence on earlier observations once $Y_n$ is specified; the time-homogeneous Markov property makes $P$ independent of $n$.

Consider states $S$ (sunny) and $R$ (rainy), with the constructed transition matrixRows give today's state and columns tomorrow's, in order $S,R$. These numbers define an illustrative model, with one step interpreted as one day; they are not estimates of real weather. Let $q_n=\mathbb{P}(Y_n=S)$. The law of total probability gives the recurrence relationSubtracting $2/3$ makes the deviation multiply by $0.4$ at each step. ThusStarting sunny gives $q_0=1$, $q_1=0.8$, $q_2=0.72$ and $q_3=0.688$; starting rainy gives $q_0=0$ and $q_2=0.56$. The two predictions approach the same stationary distribution while retaining a shrinking trace of the initial probability distribution.

An expected hitting time answers a different question. Starting sunny, let $T_R=\inf \{n\ge 0:Y_n=R\}$. Every day before the first rain remains sunny, soThis geometric distribution has finite expected value. A first-step calculation gives $h_S=1+0.8h_S+0.2h_R$, with $h_R=0$, hence $h_S=5$ days. The same result follows from the geometric series ${\mathbb{E}}_S{T}_R={\sum }_{n\ge 0}0.8^n=5$. This is a mean waiting time, not a prediction that rain first occurs exactly five days later.

A probability row vector $\pi$ is a stationary distribution when $\pi P=\pi$. The Markov chain is reversible in that law when detailed balance holds: ${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$. Multiplying those equations along a finite path gives equal forward and reversed stationary path probabilities.

An adapted process on a finite or countable state space has the Markov chain transition matrix $P$ exactly when the displayed process is a martingale for every bounded test function $f$. The forward implication follows by taking the conditional expectation of its increment. Conversely, the martingale property gives $\mathbb{E}[f(X_{n+1})\mid {\mathcal{F}}_n]=(Pf)(X_n)$; testing individual-state indicators recovers the entire conditional transition law. Stopping these martingales turns equations $(P-I)h=0$ and $(P-I)v=-1$ into hitting probabilities and expected hitting times.

For a transition matrix $P$, a finite-valued function on its state space is nonnegative superharmonic when $g\ge Pg\ge 0$. Thus $g\ge 0$ and its expected value cannot increase after one step. Replacing transitions on a target set by identity rows preserves $g\ge \tilde{P}g$. Iterating this inequality gives $g\ge {\tilde{P}}^{n}g$, a useful bound for hitting probabilities without a separate optional-stopping theorem.

An irreducible Markov chain is recurrent exactly when every nonnegative superharmonic function for a Markov chain is constant. In the recurrent case, absorb the chain at $j$. The inequality $g_i\ge ({\tilde{P}}^{n}g{)}_i\ge g_j{\mathbb{P}}_i({\tau }_j\le n)$ and almost-sure hitting give $g_i\ge g_j$; exchange $i,j$. In the transient case, the hitting probability of a state $j$ is one there and satisfies the superharmonic inequality, but its one-step average at $j$ is the strictly smaller return probability. It is a nonconstant example.

A nonnegative row vector $x$, not necessarily of total mass one, is an invariant measure for a Markov chain if $x_j={\sum }_i{x}_i{p}_{ij}$. On an irreducible Markov chain, every nonzero invariant measure has positive coordinates: iterate stationarity and use a positive transition probability along a path.

For a recurrent Markov chain, start at $k$ and stop at its first positive return $T_k$. The expected visits to each state before that return form the excursion occupation measure. Its $k$th coordinate is one. Counting the return endpoint instead of the start gives the same measure. It is invariant by shifting the occupation sum one time step and using the Markov property. Any Markov chain invariant measure normalized by $x_k=1$ dominates it: iterate the stationarity equations on the state space with $k$ removed, then retain the nonnegative excursion-path terms.

On the nonnegative integers, every positive state decreases by one, while zero jumps to $j\ge 1$ with probability $p{q}^{j-1}$, $p=1-q\in (0,1)$. Its return time from zero is one plus this geometric jump, so it has mean $(1+p)/p$. Return lengths two and three occur, establishing aperiodicity; deterministic downward motion and positive jumps establish irreducibility.

For the geometric-jump countdown Markov chain, regeneration at zero givesA cycle visits positive state $j$ precisely when its jump reaches at least $j$, with probability $q^{j-1}$. Dividing this expected occupation by the mean cycle length proves the formula. Mean recurrence times are $1/{\pi }_j$, and the limiting probability away from zero is $1/(1+p)$.

A partition of a Markov chain state space is strongly lumpable when, for every target block $C$, the sum ${\sum }_{j\in C}{p}_{ij}$ is identical for all source states $i$ in a given source block. These sums define the transition matrix of the block-valued Markov chain, independently of the initial law. Failure of this condition means the projection is not guaranteed to be a homogeneous Markov chain for every initial law, although special initial laws may still produce a Markov process.

A phi-irreducible Markov chain is Harris recurrent when every set of positive irreducibility measure is hit almost surely from every state. With an invariant probability, it becomes a positive Harris recurrent Markov chain.

A discrete-time model describes individual transitions between states at successive steps. State occupancy counts, first-entry counts and transition counts are distinct quantities, especially when a state has a self-loop. With independent individuals and fixed transition probabilities, destination counts conditional on the source count have a multinomial distribution.

With a one-step early state, early diagnosis probability $a$, and non-early diagnosis probability $b$ per subsequent step, mean infections $h_i$ yield early diagnoses $e_k=a{h}_{k-1}$ and late diagnoses $n_k=b(1-a){\sum }_{i\le k-2}{h}_i(1-b{)}^{k-i-2}$. The early intensity fraction is $e_k/(e_k+n_k)$ when positive. Initial infections and endpoint conventions determine the index limits.

A Harris recurrent chain visits every measurable set of positive irreducibility measure almost surely. Positive Harris recurrence additionally supplies an invariant probability measure. The ergodic theorem for a positive Harris recurrent Markov chain gives consistency of time averages of integrable functions.

For a positive Harris recurrent Markov chain with invariant probability $\pi$ and $\int |h|d\pi <\infty$, its time average converges almost surely to the invariant expectation:This is the consistency result for Markov chain Monte Carlo averages. Independent-observation variance formulas do not follow from this theorem.

The Ehrenfest urn model moves one uniformly chosen ball between two boxes at each step. For $k\ge 1$ balls, the count in one box is a Markov chain on $\{0,\dots ,k\}$. Its stationary distribution is $2^{-k}\left(\genfrac{}{}{0ex}{}{k}{i}\right)$, and detailed balance makes it a reversible Markov chain. The chain has period two, but its mean recurrence time to the all-in-one-box state is still $2^k$.

Choose two positions independently and uniformly from $\{1,\dots ,n\}$ and swap them. This Markov chain on the symmetric group holds with probability $1/n$ and assigns probability $2/n^2$ to each unordered transposition. Its stationary distribution is uniform, and its ordinary spectral gap is $2/n$ for $n\ge 2$. The latter follows from the Aldous spectral gap theorem: the single-label continuous-time Markov chain has rate $2/n^2$ between every pair of positions, whose mean-zero eigenvalues are all $-2/n$.

In a random transposition shuffle on a six-cycle, the shorter circular distance between two distinguished labels takes values $1,2,3$. The symmetry of the cycle and exchangeability of other labels make this a lumped Markov chain. Counting the fifteen possible transpositions gives transition matrix $P=\frac{1}{15}\left(\begin{array}{ccc}9& 4& 2\\ 4& 9& 2\\ 4& 4& 7\end{array}\right)$. Its stationary distribution is $(2/5,2/5,1/5)$ and $P=\frac{1}{3}I+\frac{2}{3}\Pi$, where each row of $\Pi$ is this stationary distribution. Consequently the probability of opposite labels after $n$ steps from adjacent labels is $(1-3^{-n})/5$.

On the symmetric group $S_n$, this Markov chain chooses uniformly from the identity and the $n-1$ adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities $1/n$ to existing neighbours.