Chapman–Kolmogorov Equations

The Chapman–Kolmogorov equations are composition identities for the transition probabilities of a stochastic process satisfying the Markov property. They state that a transition over a longer interval can be decomposed into transitions over two successive intervals, with all possible intermediate states accounted for. In a discrete state space, this involves a sum; in a general state space, it involves an integral against a transition probability measure. They provide the fundamental connection between local transition rules and evolution over longer times. (gordanz.github.io)

Discrete-state formulation

Let $X_t$ be a Markov process with a finite or countably infinite state space $S$ . Write

p_{ij}(s,t)=\Pr(X_t=j\mid X_s=i)

for its conditional probability of moving from state $i$ at time $s$ to state $j$ at time $t$ . For $s\leq u\leq t$ , the equations are

\boxed{ p_{ij}(s,t)= \sum_{k\in S}p_{ik}(s,u)\,p_{kj}(u,t). }

The intermediate state $k$ ranges over the entire state space. The identity applies whether or not the transition rules change with time. (stat.berkeley.edu)

For a time-homogeneous Markov chain, transition probabilities depend only on elapsed time. In discrete time, define

p_{ij}^{(n)}=\Pr(X_n=j\mid X_0=i).

Then, for nonnegative integers $m,n$ ,

p_{ij}^{(m+n)} =\sum_{k\in S}p_{ik}^{(m)}p_{kj}^{(n)}.

If $P^{(n)}=(p_{ij}^{(n)})$ , this becomes the matrix identity

P^{(m+n)}=P^{(m)}P^{(n)}.

Consequently, if $P$ is the one-step transition matrix, then

P^{(n)}=P^n,\qquad P^{(0)}=I,

where $I$ is the identity matrix. The superscript in $P^{(n)}$ denotes transition probabilities over $n$ steps; the right-hand side $P^n$ is ordinary matrix exponentiation. (gordanz.github.io)

Probabilistic derivation

The derivation combines the law of total probability with the Markov property. Conditioning on the state at time $u$ gives

\begin{aligned} \Pr(X_t=j\mid X_s=i) &=\sum_{k\in S} \Pr(X_t=j\mid X_u=k,X_s=i)\\ &\qquad\qquad{}\times \Pr(X_u=k\mid X_s=i). \end{aligned}

The Markov property allows the earlier condition $X_s=i$ to be removed from the first factor:

\Pr(X_t=j\mid X_u=k,X_s=i) =\Pr(X_t=j\mid X_u=k).

Substitution yields the Chapman–Kolmogorov equation. This is a statement about conditional independence: the intermediate state contains the information from the past needed to determine the future transition law. It does not assert that successive states are unconditionally independent. (gordanz.github.io)

General state spaces and transition densities

On a measurable space $(E,\mathcal E)$ , transitions are described by a Markov kernel

K_{s,t}(x,A),

where $x\in E$ and $A\in\mathcal E$ . For fixed $x$ , this is a probability distribution over possible later states; for fixed $A$ , it is measurable in $x$ . The general identity is

\boxed{ K_{s,t}(x,A) =\int_E K_{u,t}(y,A)\,K_{s,u}(x,dy). }

The integral averages the probability of reaching $A$ from each intermediate state $y$ , weighted by the probability of reaching that state from $x$ . (stat.berkeley.edu)

If the kernels have probability densities relative to a common reference measure $\mu$ , the corresponding density identity is

p(s,x;t,z) =\int_E p(s,x;u,y)\,p(u,y;t,z)\,\mu(dy),

with equality understood almost everywhere in the terminal variable unless suitably regular versions are available. The kernel formulation is more general: it also covers discrete, mixed, and singular transition laws for which an ordinary density may not exist. (stat.berkeley.edu)

For continuous states, $K_{s,t}(x,\cdot)$ is interpreted as a specified transition kernel, rather than an elementary ratio of probabilities involving the potentially zero-probability event $X_s=x$ . (stat.berkeley.edu)

Semigroup interpretation

For a time-homogeneous process, write $K_t$ for the transition kernel over duration $t$ . Then

K_{s+t}(x,A) =\int_E K_t(y,A)\,K_s(x,dy).

Define operators on bounded measurable functions by

(T_tf)(x)=\int_E f(y)\,K_t(x,dy).

These operators satisfy

T_{s+t}=T_sT_t,\qquad T_0=I.

Thus the Chapman–Kolmogorov equations express the defining composition law of a Markov semigroup. Probabilistically, $T_tf(x)$ is the expected value of $f(X_t)$ when the process starts at $x$ . Strong continuity on a chosen function space is an additional analytical condition, not part of the composition identity alone. (numerik.mi.fu-berlin.de)

Relation to the Kolmogorov differential equations

For a finite-state, time-homogeneous continuous-time Markov chain, let $P(t)$ be its transition matrix. The composition law is

P(s+t)=P(s)P(t).

Its infinitesimal generator is the rate matrix

Q=\lim_{h\downarrow0}\frac{P(h)-I}{h}.

Differentiating the composition identity gives the Kolmogorov forward and backward equations:

P'(t)=P(t)Q \quad\text{and}\quad P'(t)=QP(t),

respectively, with $P(0)=I$ . Their unique finite-state solution is the matrix exponential

P(t)=e^{tQ}.

The forward equation isolates a short interval at the end of the transition; the backward equation isolates one at the beginning. (mpaldridge.github.io)

The Chapman–Kolmogorov equations themselves are composition identities, not differential equations. Passing to differential equations requires appropriate limiting and regularity assumptions. In infinite state spaces, interchanging limits with infinite sums requires justification, and explosion—infinitely many jumps in finite time—introduces additional complications. (metaphor.ethz.ch)

Examples

For the two-state transition matrix

P= \begin{pmatrix} 0.8&0.2\\ 0.3&0.7 \end{pmatrix},

direct multiplication gives

P^2= \begin{pmatrix} 0.70&0.30\\ 0.45&0.55 \end{pmatrix}.

For example, the two-step probability of moving from state $1$ to state $2$ is

0.8(0.2)+0.2(0.7)=0.30.

The two terms correspond to intermediate states $1$ and $2$ .

For standard one-dimensional Brownian motion, the transition density over duration $t>0$ is

g_t(y-x)= \frac{1}{\sqrt{2\pi t}} \exp\!\left[-\frac{(y-x)^2}{2t}\right].

Its Chapman–Kolmogorov identity is

g_{s+t}(z-x) =\int_{\mathbb R} g_s(y-x)\,g_t(z-y)\,dy.

This is a convolution identity for normal distributions: independent Gaussian increments with variances $s$ and $t$ combine into an increment with variance $s+t$ . The same transition density is the fundamental solution of the heat equation with diffusion coefficient $1/2$ . (math.ucdavis.edu)

Uses and scope

The equations propagate state distributions. With the row-vector convention, an initial distribution $\mu_0$ for a homogeneous discrete-time chain evolves according to

\mu_n=\mu_0P^n.

They therefore connect a one-step model to predictions over many steps. (gordanz.github.io)

They also supply consistency conditions for constructing Markov processes from transition kernels: inserting or removing intermediate observation times must produce compatible finite-dimensional distributions. Under the appropriate state-space assumptions, these distributions can be used with the Kolmogorov extension theorem to construct a process. Such a construction does not, by itself, guarantee continuous sample paths; path regularity requires further arguments. (users.math.msu.edu)

References

Chapter 5 Markov Chains — Lecture notes for “Introduction to Stochastic Processes”gordanz.github.io
A guide to Brownian motion and related stochastic processesstat.berkeley.edu
Lecture notes for Numerik IVc — Numerics for Stochastic Processesnumerik.mi.fu-berlin.de
Section 18 Forward and backward equations — MATH2750 Introduction to Markov Processesmpaldridge.github.io
Lecture notes on stochastic processesmetaphor.ethz.ch
Lecture Notes on Applied Mathematicsmath.ucdavis.edu