Transition Semigroups and Chapman-Kolmogorov

From the Markov Property to a Semigroup

In continuous time, a transition matrix records how the state changes over a specified time interval. The time-homogeneous Markov property says that, once the current state is known, the conditional distribution of the future depends on the length of the interval—not on the earlier path. Applying that property at an intermediate time gives a composition rule: to move for \(s+t\) units, sum over the state occupied after the first \(s\) units. This is the Chapman–Kolmogorov identity, and it is the defining multiplication rule for a transition semigroup.

We make the starting-state assumption explicit. Let \(S\) be a finite or countable state space. For each \(i\in S\), let \((\Omega,\mathcal F,\mathbb P_i)\) be the path-space probability model for a process \((X_t)_{t\ge0}\) started at \(i\), so \(\mathbb P_i(X_0=i)=1\). Let \(\mathcal F_t\) be the filtration generated by the process up to time \(t\). We assume the process remains in \(S\) at every time. For \(i,j\in S\) and \(t\ge0\), define \(p_{ij}(t)=\mathbb P_i(X_t=j)\), and write \(P(t)=(p_{ij}(t))\).

The condition is required under \(\mathbb P_i\) for every starting state \(i\), not merely under one chosen initial distribution. The right side uses the transition probabilities for the process started from the state \(X_s\). That requirement ensures the identity we derive applies to every row of \(P(s+t)\). If \(S\) is countable, sums over \(S\) below are sums of nonnegative terms; conditional expectation and countable additivity justify the corresponding countable sums.

Proof. Fix \(i,j\in S\) and \(s,t\ge0\). By the definition of conditional expectation and the tower property, applied under \(\mathbb P_i\), $$ \mathbb P_i(X_{s+t}=j) =\mathbb E_i[\mathbf{1}_{\{X_{s+t}=j\}}] =\mathbb E_i\!\left[\mathbb E_i[\mathbf{1}_{\{X_{s+t}=j\}}\mid\mathcal F_s]\right]. $$ The assumed Markov property makes the last expression \(\mathbb E_i[p_{X_s,j}(t)]\). Since \(X_s\) takes values in \(S\), partitioning according to its value gives $$ \mathbb E_i[p_{X_s,j}(t)] =\sum_{k\in S}\mathbb P_i(X_s=k)p_{kj}(t) =\sum_{k\in S}p_{ik}(s)p_{kj}(t). $$ The leftmost probability is \(p_{ij}(s+t)\), proving the entrywise identity for the fixed \(i,j\). Since \(i,j,s,t\) were arbitrary, it holds for every entry and hence for the matrices. Each \(P(t)\) is stochastic because \(p_{ij}(t)\ge0\), and the disjoint events \(\{X_t=j\}\), \(j\in S\), exhaust the possible states, so \(\sum_{j\in S}p_{ij}(t)=1\). Finally, under \(\mathbb P_i\), \(X_0=i\) almost surely, so \(p_{ij}(0)=1\) if \(j=i\) and \(0\) otherwise. Thus \(P(0)=I\). \(\square\)

The formula has a direct interpretation: the factor \(p_{ik}(s)\) is the probability of being at \(k\) after \(s\) time units when starting at \(i\), and \(p_{kj}(t)\) is the probability of reaching \(j\) after a further \(t\) units from \(k\). Summing over all possible intermediate states accounts for every path from \(i\) to \(j\). Matrix multiplication performs exactly that sum, one intermediate state at a time.

Finite-State Computations

The semigroup identity is both a consequence of the Markov property and a practical consistency check. In each example, verify that every displayed transition matrix has rows summing to \(1\) before multiplying. The numbers \(s\) and \(t\) can differ; the rule uses elapsed time, not a requirement that the intervals be equal.

Proof. For each \(j\in S\), partition the event \(\{X_t=j\}\) according to \(X_0=i\). The Markov transition probabilities give \(\mathbb P(X_t=j)=\sum_{i\in S}\mathbb P(X_0=i)p_{ij}(t)=\sum_{i\in S}\mu_i p_{ij}(t)\), which is the \(j\)th component of \(\mu P(t)\). Applying the Chapman–Kolmogorov identity gives \((\mu P(s))P(t)=\mu(P(s)P(t))=\mu P(s+t)\); matrix multiplication is associative, and all entries being summed are nonnegative. \(\square\)

Why the Starting-State Condition Matters

A conditional-expectation identity asserted almost surely under one initial law only constrains the process on states that law can visit. It cannot establish transition probabilities for states outside that support. But the matrix identity claims equality in every row, including those states. Thus, to infer the full Chapman–Kolmogorov identity from the Markov property, require the property under each \(\mathbb P_i\), or separately assume that the specified kernels are genuine transition probabilities for processes started at every state and satisfy the Markov property there.

Common mistake: treating an almost-sure statement under one start as a statement for every state. Consider a process with state space \(\{0,1\}\) that is identically \(0\) under its given law. Assign row \(0\) of \(P(u)\) to \((1,0)\) for all \(u\ge0\). Assign row \(1\) of \(P(0)\) to \((0,1)\), row \(1\) of \(P(1)\) to \((0,1)\), and row \(1\) of \(P(u)\) to \((1,0)\) for \(u>0\) with \(u\ne1\). Every assigned row sums to \(1\), and \(P(0)=I\). Under the law concentrated on the constant path at \(0\), the conditional Markov property is satisfied: only row \(0\) is ever used. Yet for \(s=t=1/2\), row \(1\) of \(P(s)P(t)\) is \((1,0)\), whereas row \(1\) of \(P(s+t)=P(1)\) is \((0,1)\). The calculation is valid for the assigned matrices but those matrices are not a transition semigroup. The correction is not to infer an unvisited row from an almost-sure identity; impose and verify the Markov-kernel condition under every starting state.

The semigroup identity is a structural rule, not a claim that the process has a stationary distribution or that its state probabilities are constant in time. It describes how transition probabilities compose across intervals. Once a process has been shown to have such a family, the identity supports calculations over several time intervals and provides a basic check on any proposed transition matrices. Questions about how transition probabilities behave over very short intervals require additional assumptions and belong to the study of small-time transitions.