The Chapman-Kolmogorov Equations

Suppose a machine can be in one of several operating states. Each day it transitions between states according to fixed probabilities. A natural question arises: what is the probability the machine is in state jj exactly ten days from now? This is given that it starts in state ii today. Answering this directly seems to require summing over every possible ten-day itinerary. This seems to require tracking an exponentially growing number of paths. The Chapman–Kolmogorov equations give a way to sidestep this explosion entirely. They show that multi-step transition probabilities decompose cleanly through any intermediate time. This decomposition is one of the most useful computational facts in the theory of Markov Chains and Transition Matrices. It converts a combinatorial counting problem into a linear-algebraic one. The combinatorial problem is to enumerate all paths of length nn from ii to jj. The linear-algebraic version is simply: multiply matrices. The equations state how the nn-step transition probabilities are obtained. Sum, over every possible intermediate state kk, two things. First, the probability of reaching kk in mm steps. Second, the probability of then reaching jj in the remaining n−mn-m steps. This is nothing more than the law of total probability applied to the Markov property. But its consequences are far-reaching. The big picture is that this decomposition turns the entire theory of finite-state Markov chains into a chapter of matrix algebra. Transition matrices raised to powers compute long-run behavior. Eigenvalues and eigenvectors of the transition matrix govern convergence rates. The existence of a stationary distribution becomes a fixed-point equation for a matrix. Chapman–Kolmogorov is the bridge that makes all of this legitimate. It is the reason "the nn-step transition matrix equals the nn-th power of the one-step transition matrix" is a theorem. It is not merely a suggestive analogy. This article gives the precise definition of nn-step transition probabilities. It states and proves the Chapman–Kolmogorov equations in full generality. It shows how they collapse into matrix multiplication for time-homogeneous chains. Two worked examples illustrate the machinery: a three-state weather model and an asymmetric random walk on a cycle. These are followed by a counterexample showing what fails without the Markov property. Finally, there is a discussion of where these equations surface in modern applications.

Key takeaways
  • The nn-step transition probability Pij(n)P^{(n)}_{ij} is the chance of going from state ii to state jj in exactly nn steps.
  • Chapman–Kolmogorov: Pij(m+n)=∑kPik(m)Pkj(n)P^{(m+n)}_{ij} = \sum_k P^{(m)}_{ik} P^{(n)}_{kj}, decomposing any trip through an intermediate time.
  • For time-homogeneous chains this is exactly the matrix identity P(m+n)=P(m)P(n)\mathbf{P}^{(m+n)} = \mathbf{P}^{(m)}\mathbf{P}^{(n)}.
  • Consequently P(n)=Pn\mathbf{P}^{(n)} = \mathbf{P}^n, the nn-th matrix power of the one-step transition matrix.
  • The proof rests entirely on the Markov property and the law of total probability — no extra assumptions needed.
  • Key idea: summing over an intermediate state at any intermediate time turns path-counting into matrix multiplication.

Where this lives today

The Chapman–Kolmogorov equations underlie essentially every computational use of finite-state Markov models. In Google's PageRank algorithm, the nn-step transition matrix of a random surfer on the web graph converges (as n→∞n\to\infty) to a stationary distribution used to rank pages; computing that convergence relies on repeatedly applying P(n)=Pn\mathbf P^{(n)} = \mathbf P^n. In genetics and bioinformatics, hidden Markov models for DNA sequence alignment and gene prediction use the equations to compute multi-step state probabilities efficiently via the forward algorithm, which is a direct computational instance of the intermediate-state decomposition. In queueing theory and operations research, Chapman–Kolmogorov equations (in their continuous-time differential form) give the Kolmogorov forward and backward equations governing birth-death processes used to model server queues, inventory systems, and epidemics (the SIR-type continuous-time Markov chains). In statistical physics, the equations appear as a discrete-time analogue of the master equation describing the evolution of a probability distribution over microstates. In finance, discrete-time Markov chain models of credit ratings use nn-step transition matrices, computed via matrix powers justified by Chapman–Kolmogorov, to estimate multi-year default probabilities. In cryptography and pseudorandom number generation, the mixing time of a Markov chain — how quickly Pn\mathbf P^n approaches a limiting distribution — is analyzed via eigenvalues of P\mathbf P, whose relevance to nn-step probabilities is precisely guaranteed by this theorem. The equations also form the conceptual seed for the later theory of Stationary Distributions, since a stationary distribution π\pi is precisely a probability vector satisfying πP=π\pi \mathbf P = \pi, which forces πP(n)=π\pi \mathbf P^{(n)} = \pi for all nn by repeated application of Chapman–Kolmogorov.

Ask the tutor: How do the Chapman–Kolmogorov equations change if the Markov chain is time-inhomogeneous, and how would I compute nn-step probabilities in that case?

Definitionnn-step transition probabilities and the Chapman–Kolmogorov equations

Let (Xt)t≥0(X_t)_{t \geq 0} be a Markov chain on a countable state space SS, meaning that for all t≥0t \geq 0 and all states i0,i1,…,it+1∈Si_0, i_1, \dots, i_{t+1} \in S with P(X0=i0,…,Xt=it)>0P(X_0 = i_0, \dots, X_t = i_t) > 0,

P(Xt+1=it+1∣X0=i0,…,Xt=it)=P(Xt+1=it+1∣Xt=it).P(X_{t+1} = i_{t+1} \mid X_0 = i_0, \dots, X_t = i_t) = P(X_{t+1} = i_{t+1} \mid X_t = i_t).

For times s≤ts \le t and states i,j∈Si,j \in S, define the (s,t)(s,t)-transition probability

Pij(s,t):=P(Xt=j∣Xs=i),P_{ij}(s,t) := P(X_t = j \mid X_s = i),

whenever P(Xs=i)>0P(X_s = i) > 0. If the chain is time-homogeneous, meaning P(Xt+1=j∣Xt=i)P(X_{t+1}=j \mid X_t = i) does not depend on tt, this quantity depends only on the elapsed time n=t−sn = t - s, and we write

Pij(n):=P(Xn=j∣X0=i),n≥0,P^{(n)}_{ij} := P(X_n = j \mid X_0 = i), \qquad n \geq 0,

with the convention Pij(0)=1[i=j]P^{(0)}_{ij} = \mathbb{1}[i=j] and Pij(1)=PijP^{(1)}_{ij} = P_{ij}, the one-step transition probability. The Chapman–Kolmogorov equations assert that for every m,n≥0m, n \geq 0 and all i,j∈Si, j \in S,

Pij(m+n)=∑k∈SPik(m) Pkj(n).P^{(m+n)}_{ij} = \sum_{k \in S} P^{(m)}_{ik}\, P^{(n)}_{kj}.

Writing P\mathbf{P} for the (possibly infinite) matrix with entries PijP_{ij}, and P(n)\mathbf{P}^{(n)} for the matrix with entries Pij(n)P^{(n)}_{ij}, this is equivalent to the matrix equation

P(m+n)=P(m)P(n),henceP(n)=Pn.\mathbf{P}^{(m+n)} = \mathbf{P}^{(m)} \mathbf{P}^{(n)}, \qquad \text{hence} \qquad \mathbf{P}^{(n)} = \mathbf{P}^n.

Intuition

Think of P\mathbf{P} as a weighted directed graph on the state space: an arrow from ii to kk carries weight PikP_{ik}, the probability of jumping there in one step. A path of length m+nm+n from ii to jj must pass through some state kk at time mm, whether or not we ever observe or record that state. The Chapman–Kolmogorov equations say the total probability of all length-(m+n)(m+n) paths from ii to jj is obtained by fixing the "waypoint" kk, multiplying the probability of getting from ii to kk in mm steps by the probability of getting from kk to jj in the remaining nn steps, and summing over all possible waypoints kk. This is exactly how matrix multiplication works: entry (i,j)(i,j) of a product ABAB sums over the shared index kk of AikBkjA_{ik}B_{kj}. The theorem says probabilistic path-counting is matrix multiplication. The figure below shows this for a simple three-state chain: to compute the probability of going from state 11 to state 33 in two steps, we sum over the three possible states occupied after step one.

Figure
Decomposing a 2-step transition through an intermediate state kk
i=1 k=1 k=2 k=3 j=3 P₁₁=0.5 P₁₂=0.3 P₁₃=0.2 P₁₃=0.2 P₂₃=0.4 P₃₃=0.6 Time 0 Time 1 Time 2 P⁽²⁾₁₃ = 0.5·0.2 + 0.3·0.4 + 0.2·0.6 = 0.34

Chapman-Kolmogorov Equations

TheoremChapman–Kolmogorov equations

Let (Xt)t≥0(X_t)_{t\geq 0} be a time-homogeneous Markov chain on a countable state space SS with one-step transition probabilities Pij=P(X1=j∣X0=i)P_{ij} = P(X_1=j\mid X_0=i). Define Pij(n)=P(Xn=j∣X0=i)P^{(n)}_{ij} = P(X_n = j \mid X_0 = i) for n≥0n \geq 0, with Pij(0)=1[i=j]P^{(0)}_{ij}=\mathbb{1}[i=j]. Then for all integers m,n≥0m,n \geq 0 and all i,j∈Si,j \in S,

Pij(m+n)=∑k∈SPik(m) Pkj(n).P^{(m+n)}_{ij} = \sum_{k \in S} P^{(m)}_{ik}\, P^{(n)}_{kj}.

Equivalently, if P\mathbf{P} and P(n)\mathbf{P}^{(n)} denote the matrices of these probabilities, then

P(n)=Pnfor every n≥0,\mathbf{P}^{(n)} = \mathbf{P}^n \quad \text{for every } n \geq 0,

where Pn\mathbf{P}^n is the ordinary nn-th matrix power of P\mathbf{P} (with P0=I\mathbf{P}^0 = I).

Proof

Technique: conditioning on the intermediate state via the law of total probability, then invoking the Markov property. Fix i,j∈Si, j \in S and m,n≥0m, n \geq 0, and suppose P(X0=i)>0P(X_0 = i) > 0 so that all conditional probabilities below are well defined. We compute Pij(m+n)=P(Xm+n=j∣X0=i)P^{(m+n)}_{ij} = P(X_{m+n} = j \mid X_0 = i). Step 1 (law of total probability over the intermediate state). The events {Xm=k}k∈S\{X_m = k\}_{k \in S} partition the sample space (since XmX_m takes exactly one value). By the law of total probability, conditioning throughout on X0=iX_0 = i,

P(Xm+n=j∣X0=i)=∑k∈SP(Xm+n=j,Xm=k∣X0=i).P(X_{m+n} = j \mid X_0 = i) = \sum_{k \in S} P(X_{m+n} = j, X_m = k \mid X_0 = i).

This step uses only countable additivity of probability and requires no property of Markov chains; it is valid for any stochastic process. Step 2 (factor each joint term using conditional probability). For each kk with P(Xm=k,X0=i)>0P(X_m = k, X_0 = i) > 0,

P(Xm+n=j,Xm=k∣X0=i)=P(Xm=k∣X0=i) P(Xm+n=j∣Xm=k,X0=i).P(X_{m+n}=j, X_m = k \mid X_0 = i) = P(X_m = k \mid X_0 = i)\, P(X_{m+n} = j \mid X_m = k, X_0 = i).

This is the definition of conditional probability applied to the events {Xm=k}\{X_m = k\} and {Xm+n=j}\{X_{m+n}=j\}, both conditioned on {X0=i}\{X_0=i\}; formally,

P(A∩B∣C)=P(B∣C)⋅P(A∣B∩C)P(A \cap B \mid C) = P(B\mid C) \cdot P(A \mid B \cap C)

whenever P(B∩C)>0P(B \cap C) > 0, which is a direct consequence of the definition P(A∣D)=P(A∩D)/P(D)P(A\mid D) = P(A\cap D)/P(D) applied twice. If P(Xm=k∣X0=i)=0P(X_m=k\mid X_0=i)=0 the corresponding summand is 00 on both sides of Step 2's identity by convention, and Step 1's identity still holds since we may simply omit terms where the joint probability is zero. Step 3 (Markov property removes the conditioning on X0X_0). By the Markov property applied at time mm (extended, by induction on nn, from one step to nn steps — see the lemma below), we have for all kk with P(Xm=k,X0=i)>0P(X_m=k, X_0=i)>0,

P(Xm+n=j∣Xm=k,X0=i)=P(Xm+n=j∣Xm=k).P(X_{m+n} = j \mid X_m = k, X_0 = i) = P(X_{m+n} = j \mid X_m = k).

Step 4 (time-homogeneity converts absolute times to elapsed times). Since the chain is time-homogeneous,

P(Xm=k∣X0=i)=Pik(m),P(Xm+n=j∣Xm=k)=Pkj(n).P(X_m = k \mid X_0 = i) = P^{(m)}_{ik}, \qquad P(X_{m+n} = j \mid X_m = k) = P^{(n)}_{kj}.

(The second equality follows because Xm+nX_{m+n} is nn steps after XmX_m, and homogeneity says the transition law over any nn consecutive steps started at state kk is the same, namely Pkj(n)P^{(n)}_{kj}.) Substituting Steps 2–4 into Step 1 gives

Pij(m+n)=∑k∈SPik(m) Pkj(n),P^{(m+n)}_{ij} = \sum_{k \in S} P^{(m)}_{ik}\, P^{(n)}_{kj},

which is the Chapman–Kolmogorov equation.

Matrix form. The right-hand side is precisely the (i,j)(i,j) entry of the matrix product P(m)P(n)\mathbf{P}^{(m)}\mathbf{P}^{(n)} (this holds verbatim for finite state spaces, and for countable state spaces the sum converges absolutely since each term is a product of probabilities and the total sum over kk of Pik(m)P^{(m)}_{ik} is 11). Hence

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

We now show P(n)=Pn\mathbf{P}^{(n)} = \mathbf{P}^n by induction on nn. The base case n=0n=0 holds since P(0)=I=P0\mathbf{P}^{(0)} = I = \mathbf{P}^0 by definition, and n=1n=1 holds since P(1)=P\mathbf{P}^{(1)} = \mathbf{P} by definition. For the inductive step, suppose P(n)=Pn\mathbf{P}^{(n)} = \mathbf{P}^n for some n≥1n \geq 1. Taking m=1m=1 in the matrix identity just proved,

P(n+1)=P(1)P(n)=P⋅Pn=Pn+1.\mathbf{P}^{(n+1)} = \mathbf{P}^{(1)}\mathbf{P}^{(n)} = \mathbf{P}\cdot \mathbf{P}^n = \mathbf{P}^{n+1}.

By induction, P(n)=Pn\mathbf{P}^{(n)} = \mathbf{P}^n for all n≥0n \geq 0. ■\blacksquare

∎
Lemmaextended Markov property

Let (Xt)t≥0(X_t)_{t\geq 0} satisfy the Markov property as in the definition above. Then for all m,n≥0m, n\geq 0 and states i0,…,im,j∈Si_0,\dots,i_m,j\in S with P(X0=i0,…,Xm=im)>0P(X_0=i_0,\dots,X_m=i_m)>0,

P(Xm+n=j∣X0=i0,…,Xm=im)=P(Xm+n=j∣Xm=im).P(X_{m+n} = j \mid X_0=i_0,\dots,X_m=i_m) = P(X_{m+n}=j\mid X_m = i_m).
Proof

Technique: induction on nn, repeatedly applying the one-step Markov property. For n=0n=0 the statement is trivial: both sides equal 1[im=j]\mathbb{1}[i_m = j]. Suppose the claim holds for nn; we show it for n+1n+1. Write H={X0=i0,…,Xm=im}H = \{X_0=i_0,\dots,X_m=i_m\}, an event with P(H)>0P(H)>0. By the law of total probability over the value of Xm+nX_{m+n},

P(Xm+n+1=j∣H)=∑k∈SP(Xm+n=k∣H) P(Xm+n+1=j∣Xm+n=k,H),P(X_{m+n+1}=j \mid H) = \sum_{k\in S} P(X_{m+n}=k \mid H)\, P(X_{m+n+1}=j \mid X_{m+n}=k, H),

using conditional factorization as in Step 2 of the main proof (terms with P(Xm+n=k,H)=0P(X_{m+n}=k,H)=0 contribute 00). By the one-step Markov property applied at time m+nm+n (extending the conditioning event to include HH, which is measurable with respect to X0,…,XmX_0,\dots,X_m, hence a special case of the hypothesis with the longer history i0,…,imi_0,\dots,i_m, arbitrary intervening states, kk), we get

P(Xm+n+1=j∣Xm+n=k,H)=P(Xm+n+1=j∣Xm+n=k).P(X_{m+n+1}=j\mid X_{m+n}=k, H) = P(X_{m+n+1}=j \mid X_{m+n}=k).

Substituting, and using the inductive hypothesis P(Xm+n=k∣H)=P(Xm+n=k∣Xm=im)P(X_{m+n}=k\mid H) = P(X_{m+n}=k\mid X_m=i_m),

P(Xm+n+1=j∣H)=∑kP(Xm+n=k∣Xm=im) P(Xm+n+1=j∣Xm+n=k)=P(Xm+n+1=j∣Xm=im),P(X_{m+n+1}=j\mid H) = \sum_{k} P(X_{m+n}=k\mid X_m=i_m)\,P(X_{m+n+1}=j\mid X_{m+n}=k) = P(X_{m+n+1}=j \mid X_m = i_m),

where the last equality is the n=1n=1 base case of Chapman–Kolmogorov applied to the chain started at Xm=imX_m=i_m (equivalently, the same law-of-total-probability argument run in reverse). This completes the induction. ■\blacksquare

∎

Worked examples

Example 1: A three-state weather model. A city's weather each day is Sunny (S), Cloudy (C), or Rainy (R). The one-step transition matrix, with rows/columns ordered (S, C, R), is

P=(0.60.30.10.20.50.30.10.40.5).\mathbf{P} = \begin{pmatrix} 0.6 & 0.3 & 0.1 \\ 0.2 & 0.5 & 0.3 \\ 0.1 & 0.4 & 0.5 \end{pmatrix}.

Suppose today is Sunny. We want the probability it is Rainy in exactly 22 days, i.e. PS,R(2)P^{(2)}_{S,R}. By Chapman–Kolmogorov with m=n=1m=n=1,

PS,R(2)=∑k∈{S,C,R}PS,k Pk,R=PS,SPS,R+PS,CPC,R+PS,RPR,R.P^{(2)}_{S,R} = \sum_{k \in \{S,C,R\}} P_{S,k}\,P_{k,R} = P_{S,S}P_{S,R} + P_{S,C}P_{C,R} + P_{S,R}P_{R,R}.

Substituting values,

PS,R(2)=(0.6)(0.1)+(0.3)(0.3)+(0.1)(0.5)=0.06+0.09+0.05=0.20.P^{(2)}_{S,R} = (0.6)(0.1) + (0.3)(0.3) + (0.1)(0.5) = 0.06 + 0.09 + 0.05 = 0.20.

To check via matrix powers, compute the full matrix P2=PP\mathbf{P}^2 = \mathbf{P}\mathbf{P}. Row SS of P2\mathbf{P}^2 is (0.6,0.3,0.1)P(0.6,0.3,0.1)\mathbf{P}:

PS,S(2)=(0.6)(0.6)+(0.3)(0.2)+(0.1)(0.1)=0.36+0.06+0.01=0.43,P^{(2)}_{S,S} = (0.6)(0.6)+(0.3)(0.2)+(0.1)(0.1) = 0.36+0.06+0.01 = 0.43,
PS,C(2)=(0.6)(0.3)+(0.3)(0.5)+(0.1)(0.4)=0.18+0.15+0.04=0.37,P^{(2)}_{S,C} = (0.6)(0.3)+(0.3)(0.5)+(0.1)(0.4) = 0.18+0.15+0.04 = 0.37,
PS,R(2)=0.20 (computed above).P^{(2)}_{S,R} = 0.20 \ \text{(computed above)}.

As a consistency check, 0.43+0.37+0.20=1.000.43 + 0.37 + 0.20 = 1.00, confirming these are a valid probability distribution, as required since X2X_2 must take some value. Now use Chapman–Kolmogorov a second time to find PS,R(3)P^{(3)}_{S,R} by splitting at m=2,n=1m=2, n=1: we need row SS of P2\mathbf{P}^2, namely (0.43,0.37,0.20)(0.43, 0.37, 0.20), and column RR of P\mathbf{P}, namely (0.1,0.3,0.5)T(0.1, 0.3, 0.5)^T:

PS,R(3)=(0.43)(0.1)+(0.37)(0.3)+(0.20)(0.5)=0.043+0.111+0.100=0.254.P^{(3)}_{S,R} = (0.43)(0.1) + (0.37)(0.3) + (0.20)(0.5) = 0.043 + 0.111 + 0.100 = 0.254.

Note we could equally have split at m=1,n=2m=1,n=2, using row SS of P\mathbf{P} and column RR of P2\mathbf{P}^2; the theorem guarantees the same answer regardless of where we place the intermediate time, since both equal the (S,R)(S,R) entry of P3\mathbf{P}^3.

Example 2: An asymmetric random walk on a cycle of 4 states. Let S={0,1,2,3}S = \{0,1,2,3\} arranged on a cycle, and at each step the walker moves clockwise (to i+1  4i+1 \bmod 4) with probability 0.70.7 or counterclockwise (to i−1  4i - 1 \bmod 4) with probability 0.30.3. The one-step matrix (rows/columns 0,1,2,30,1,2,3) is

P=(00.700.30.300.7000.300.70.700.30).\mathbf{P} = \begin{pmatrix} 0 & 0.7 & 0 & 0.3 \\ 0.3 & 0 & 0.7 & 0 \\ 0 & 0.3 & 0 & 0.7 \\ 0.7 & 0 & 0.3 & 0 \end{pmatrix}.

Start at state 00. We compute P0,2(2)P^{(2)}_{0,2}, the probability of being at state 22 (the antipodal point) after 22 steps, using Chapman–Kolmogorov summing over the intermediate state kk after step 11:

P0,2(2)=∑k=03P0,kPk,2.P^{(2)}_{0,2} = \sum_{k=0}^3 P_{0,k}P_{k,2}.

From row 00 of P\mathbf{P}, the only nonzero entries are P0,1=0.7P_{0,1}=0.7 and P0,3=0.3P_{0,3}=0.3; all other P0,k=0P_{0,k}=0, so those terms vanish automatically. Thus

P0,2(2)=P0,1P1,2+P0,3P3,2=(0.7)(0.7)+(0.3)(0.3)=0.49+0.09=0.58.P^{(2)}_{0,2} = P_{0,1}P_{1,2} + P_{0,3}P_{3,2} = (0.7)(0.7) + (0.3)(0.3) = 0.49 + 0.09 = 0.58.

This makes sense: reaching the antipodal state in two steps requires two clockwise moves (0→1→20\to1\to2, probability 0.72=0.490.7^2=0.49) or two counterclockwise moves (0→3→20\to3\to2, probability 0.32=0.090.3^2 = 0.09); a clockwise-then-counterclockwise or counterclockwise-then-clockwise pair returns to 00, not 22. Indeed P0,0(2)=(0.7)(0.3)+(0.3)(0.7)=0.42P^{(2)}_{0,0} = (0.7)(0.3)+(0.3)(0.7) = 0.42, and by symmetry of the cycle's two remaining states, P0,1(2)=P0,3(2)=0P^{(2)}_{0,1}=P^{(2)}_{0,3}=0 (an odd number of net clockwise minus counterclockwise steps of size ±2\pm2 cannot land you at an odd-distance state after an even number of moves that only change position by ±1\pm 1 each — concretely, after 22 steps the walker's clockwise displacement is 2,0,2, 0, or −2(mod4)-2 \pmod 4, landing on state 2,0,2,0, or 22 again, never 11 or 33). Check: 0.58+0.42+0+0=1.000.58+0.42+0+0 = 1.00. ✓. Now extend to 33 steps: find P0,2(3)P^{(3)}_{0,2} by splitting m=2,n=1m=2,n=1 using the row of P(2)\mathbf{P}^{(2)} from state 00, which is (0.42,0,0.58,0)(0.42, 0, 0.58, 0) (filling in the zero entries found above), and column 22 of P\mathbf{P}, which is (0,0.7,0,0.3)T(0, 0.7, 0, 0.3)^T:

P0,2(3)=(0.42)(0)+(0)(0.7)+(0.58)(0)+(0)(0.3)=0.P^{(3)}_{0,2} = (0.42)(0) + (0)(0.7) + (0.58)(0) + (0)(0.3) = 0.

This is exactly right: after an odd number of ±1\pm1 steps, the walker's position has changed parity, so it cannot be at state 22 (same parity as 00) after 33 steps — it must be at an odd-labeled state. This parity structure, visible immediately from the zero pattern in P(2)\mathbf{P}^{(2)}, is a first hint of the Classification of States to come, where such periodicity is studied systematically.

Counterexampledropping the Markov property

The Chapman–Kolmogorov decomposition P(Xm+n=j∣X0=i)=∑kP(Xm=k∣X0=i)P(Xm+n=j∣Xm=k)P(X_{m+n}=j\mid X_0=i) = \sum_k P(X_m=k\mid X_0=i)P(X_{m+n}=j\mid X_m=k) can fail entirely if (Xt)(X_t) is not Markov, because Step 3 of the proof (removing the conditioning on the full past) is no longer valid. Consider a simple non-Markov process on S={0,1}S=\{0,1\}: let X0=0X_0 = 0 always. Let X1∈{0,1}X_1 \in \{0,1\} be fair coin flip, independent of everything else. Define X2=X1X_2 = X_1 (the process "remembers" and repeats X1X_1 exactly), and let all further Xt=X1X_t = X_1 for t≥1t\geq 1 as well — the chain freezes at whatever X1X_1 was. This process is not Markov: knowing X1X_1 determines X2X_2 with certainty, but if we only average over the marginal distribution of X1X_1 (forgetting we know its value), we cannot recover X2X_2. Now compute directly. We have P(X1=k∣X0=0)=1/2P(X_1 = k \mid X_0=0) = 1/2 for k=0,1k=0,1. Also P(X2=1∣X1=0)=0P(X_2 = 1\mid X_1=0)=0 and P(X2=1∣X1=1)=1P(X_2=1\mid X_1=1)=1, by construction. The "Chapman–Kolmogorov" right-hand side would give

∑k∈{0,1}P(X1=k∣X0=0) P(X2=1∣X1=k)=12⋅0+12⋅1=12.\sum_{k\in\{0,1\}} P(X_1=k\mid X_0=0)\,P(X_2=1\mid X_1=k) = \tfrac12\cdot 0 + \tfrac12\cdot 1 = \tfrac12.

This matches P(X2=1∣X0=0)=1/2P(X_2=1\mid X_0=0)=1/2 in this particular instance — so we push further to expose the real failure, by conditioning on more of the past instead of just X0X_0. Consider instead Q01:=P(X2=1∣X1=0,X0=0)Q_{01} := P(X_2 = 1\mid X_1 = 0, X_0=0). Since X2=X1X_2=X_1 deterministically, Q01=0Q_{01} = 0, not 1/21/2. But a Markov chain built from the same one-step marginal transition probabilities P^01=P(X1=1∣X0=0)=1/2\hat P_{01}=P(X_1=1\mid X_0=0)=1/2 and P^(X2=j∣X1=k)\hat P(X_2=j\mid X_1=k) estimated marginally would predict P(X2=1∣X1=0)P(X_2=1\mid X_1=0) using only the pair (X1,X2)(X_1,X_2)'s law, which here is also degenerate (=0=0) — the point is that these two "transition kernels" P(X2=⋅∣X1=0)P(X_2=\cdot\mid X_1=0) computed (a) marginally and (b) conditionally on the further past X0X_0 genuinely coincide only because the process happens to have no other history to condition on beyond X1X_1 at this depth. To see an outright numerical clash, extend the construction: let X0=0X_0=0 deterministically, let X1X_1 be a fair coin as before, and now let X2X_2 equal X1X_1 with probability 0.90.9 and 1−X11-X_1 with probability 0.10.1, but let this "flip probability" itself depend on X0X_0 having been exactly 00 two steps back in a longer chain where X−1X_{-1} existed and X0X_0 depended on it — concretely, take any process where P(X2=j∣X1=k)P(X_2=j\mid X_1=k) genuinely varies depending on which earlier state preceded X1=kX_1=k. Then the quantity ∑kP(X1=k∣X0=i)P(X2=j∣X1=k)\sum_k P(X_1=k\mid X_0=i)P(X_2=j\mid X_1=k) uses the marginal kernel P(X2=j∣X1=k)P(X_2=j\mid X_1=k) (averaged over all the ways of reaching kk), while the true conditional probability P(X2=j∣X0=i)P(X_2=j\mid X_0=i) requires the kernel specific to arriving at kk via ii. These differ whenever the transition out of kk depends on the path used to reach kk — precisely the failure of the Markov property — and no valid single matrix P\mathbf P of "transition probabilities" exists to make the two sides equal in general. This is exactly why the hypothesis that (Xt)(X_t) is Markov cannot be dropped: without it, "P(Xm+n=j∣Xm=k)P(X_{m+n}=j\mid X_m=k)" is not even well-defined independent of history, so the sum ∑kPik(m)Pkj(n)\sum_k P^{(m)}_{ik}P^{(n)}_{kj} has no reason to equal Pij(m+n)P^{(m+n)}_{ij}.

Scope, edge cases & common traps

SituationWhat happens
Chain is time-homogeneousPij(n)P^{(n)}_{ij} depends only on elapsed time nn; Chapman–Kolmogorov becomes P(n)=Pn\mathbf P^{(n)}=\mathbf P^n.
Chain is time-inhomogeneousEquations still hold in the two-time form Pij(s,u)=∑kPik(s,t)Pkj(t,u)P_{ij}(s,u) = \sum_k P_{ik}(s,t)P_{kj}(t,u) for s≤t≤us\le t\le u; no single power of one matrix suffices.
Infinite (countable) state spaceThe sum ∑kPik(m)Pkj(n)\sum_k P^{(m)}_{ik}P^{(n)}_{kj} converges absolutely (bounded by 11), so the identity holds without extra convergence hypotheses.
Continuous state spaceSums become integrals against transition kernels/densities; same proof structure (measure-theoretic law of total probability).
Process is not MarkovEquations can fail, as shown in the counterexample; there is no single valid transition kernel to use.
m=0m=0 or n=0n=0Reduces to the trivial identity P(n)=I⋅P(n)\mathbf P^{(n)} = I\cdot \mathbf P^{(n)}, consistent but uninformative — always check base cases separately in inductive proofs.

The mathematician behind it

Origins · 1 minAndrei Andreyevich Markov and how this was discovered
AA
Andrei Andreyevich Markov
1856–1922 · Imperial Academy of Sciences, St. Petersburg

Andrei Markov was a Russian mathematician working in probability theory and number theory, a student of Pafnuty Chebyshev. He introduced what are now called Markov chains around 1906, originally to demonstrate that the law of large numbers could hold for sequences of dependent random variables, deliberately challenging the prevailing assumption that independence was essential to probabilistic limit theorems. His examples included an analysis of vowel-consonant sequences in Pushkin's poem Eugene Onegin, an early instance of what would later be called a discrete-time stochastic process with dependent structure. The equations bearing the joint name Chapman–Kolmogorov were developed independently and put on a rigorous, general measure-theoretic footing by Sydney Chapman (a British mathematician and geophysicist) in 1928 and by Andrei Kolmogorov in 1931, in the broader context of continuous-time and continuous-space Markov processes, extending Markov's original discrete framework.

History
- 1906 — Andrei Markov introduces chains of dependent random variables and proves a law of large numbers for them.
- 1913 — Markov applies his chain model to letter sequences in Eugene Onegin, an early empirical use of Markov chains.
- 1928 — Sydney Chapman derives an equation for diffusion processes equivalent to the discrete decomposition over intermediate states.
- 1931 — Andrei Kolmogorov publishes Über die analytische Methoden in der Wahrscheinlichkeitsrechnung, establishing the general Chapman–Kolmogorov equations and the analytic (differential) theory of Markov processes.
- 1930s–1950s — The matrix formulation P(n)=Pn\mathbf P^{(n)}=\mathbf P^n becomes standard in the emerging discrete-time Markov chain theory used in operations research and queueing theory.
Is the Chapman–Kolmogorov equation only true for finite state spaces?

No. The proof given uses only the law of total probability and countable additivity, both of which hold for any countable state space. The sum ∑k∈SPik(m)Pkj(n)\sum_{k\in S} P^{(m)}_{ik}P^{(n)}_{kj} converges absolutely because each Pik(m)≥0P^{(m)}_{ik} \geq 0 and ∑kPik(m)=1\sum_k P^{(m)}_{ik} = 1, so the series is dominated termwise. For uncountable (e.g. continuous) state spaces, the same identity holds with the sum replaced by an integral against a transition kernel, proved by the analogous measure-theoretic law of total probability; this is the setting Kolmogorov treated in full generality in 1931.

Does Chapman–Kolmogorov require the chain to be time-homogeneous?

No, though the compact matrix-power form P(n)=Pn\mathbf P^{(n)} = \mathbf P^n does require it. In general, for s≤t≤us \le t \le u, the equations hold in the form Pij(s,u)=∑kPik(s,t)Pkj(t,u)P_{ij}(s,u) = \sum_k P_{ik}(s,t) P_{kj}(t,u), where the transition probabilities may depend on the actual times s,t,us,t,u, not merely on elapsed time. Time-homogeneity is what lets us collapse this two-time-parameter family into a single-parameter family Pij(n)P^{(n)}_{ij} and hence into powers of a single fixed matrix P\mathbf P.

Why is this useful if I can already simulate the chain forward step by step?

Simulation gives you one sample path at a time and requires many repetitions to estimate a probability accurately, with statistical error shrinking only like 1/number of simulations1/\sqrt{\text{number of simulations}}. Chapman–Kolmogorov gives the exact probability via a finite, deterministic linear-algebra computation: raise a matrix to a power. For a chain with NN states, computing Pn\mathbf P^n costs roughly O(N3log⁡n)O(N^3 \log n) operations via repeated squaring, far cheaper and exact compared to Monte Carlo simulation for a fixed accuracy target.

How does this relate to eigenvalues and long-run behavior?

Because P(n)=Pn\mathbf P^{(n)} = \mathbf P^n, the long-run behavior of the chain as n→∞n \to \infty is governed by the spectral decomposition of P\mathbf P. If P\mathbf P is diagonalizable with eigenvalues λ1=1≥∣λ2∣≥…\lambda_1=1 \geq |\lambda_2| \geq \dots, then Pn\mathbf P^n can be written in terms of these eigenvalues, and Pn→1πT\mathbf P^n \to \mathbf 1 \pi^T (a matrix with every row equal to the stationary distribution π\pi) at a rate governed by ∣λ2∣n|\lambda_2|^n, under suitable conditions such as irreducibility and aperiodicity. This spectral analysis is only possible because Chapman–Kolmogorov identifies nn-step probabilities with matrix powers in the first place.

Can I split the nn steps at any intermediate point, or only at the midpoint?

Any intermediate point works, and this is precisely the content of the theorem: for any 0≤m≤m+n0 \le m \le m+n, Pij(m+n)=∑kPik(m)Pkj(n)P^{(m+n)}_{ij} = \sum_k P^{(m)}_{ik}P^{(n)}_{kj}. You may choose m=1m=1 (peel off one step), m=m+n−1m = m+n-1 (peel off the last step), or any split in between; associativity of matrix multiplication guarantees P(m)P(n)\mathbf P^{(m)}\mathbf P^{(n)} gives the same matrix Pm+n\mathbf P^{m+n} regardless of how m+nm+n is partitioned, since matrix multiplication is associative.

What goes wrong in continuous time — do the equations look different?

The same underlying idea holds: for a continuous-time Markov process with transition functions Pij(t)=P(Xs+t=j∣Xs=i)P_{ij}(t) = P(X_{s+t}=j\mid X_s=i), the Chapman–Kolmogorov equations read Pij(s+t)=∑kPik(s)Pkj(t)P_{ij}(s+t) = \sum_k P_{ik}(s)P_{kj}(t), i.e., P(s+t)=P(s)P(t)\mathbf P(s+t) = \mathbf P(s)\mathbf P(t), so {P(t)}t≥0\{\mathbf P(t)\}_{t\geq 0} forms a matrix semigroup. Differentiating this semigroup property at t=0t=0 (under regularity conditions) yields the Kolmogorov forward and backward differential equations, which are the continuous-time analogues used to derive generators QQ with P(t)=eQt\mathbf P(t) = e^{Qt}.

Is the converse true: if a process satisfies Chapman–Kolmogorov, is it necessarily Markov?

Not in general — this converse is false without further conditions, and we do not claim it. A process can satisfy the two-time consistency identity Pij(s,u)=∑kPik(s,t)Pkj(t,u)P_{ij}(s,u)=\sum_k P_{ik}(s,t)P_{kj}(t,u) for a family of transition functions while the underlying process itself fails to be Markov, if that family was not actually derived as the process's true conditional probabilities. Chapman–Kolmogorov as stated here is a consequence of the Markov property for the process's own transition probabilities; establishing sufficient conditions under which a consistent family of kernels satisfying these equations defines a genuine Markov process is a separate construction (Kolmogorov extension theorem) and is beyond the scope of this article.

Before this

Where this leads