Combining Transition Probabilities Across Time
For a time-homogeneous continuous-time Markov chain, knowing the transition probabilities over two separate intervals determines the probabilities over their combined interval. The Chapman–Kolmogorov identity expresses this principle as matrix multiplication. Each entry of the product sums over the possible state occupied at the intermediate time, so the formula also provides a direct way to check computations and to propagate an initial distribution.
Let \((X_t)_{t\ge0}\) be a time-homogeneous Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). For each starting state \(i\in S\), write \(\mathbb{P}_i\) for the law of the chain started at \(i\). Define \(p_{ij}(t)=\mathbb{P}_i(X_t=j)\) and \(P(t)=(p_{ij}(t))_{i,j\in S}\). This definition uses the law started from \(i\); it does not require the event \(X_0=i\) to have positive probability under some other initial distribution. Each \(P(t)\) is row-stochastic: its entries are nonnegative and each row sums to \(1\).
The index \(k\) represents the state at time \(s\). A path from \(i\) to \(j\) over the full interval of length \(s+t\) must occupy some state \(k\) at the split time. The Markov property says that, once that state is specified, the probabilities for the interval after \(s\) are the transition probabilities for a chain started at \(k\).
Proof. Fix starting state \(i\) and final state \(j\). The events \(\{X_s=k\}\), for \(k\in S\), are disjoint and together have probability \(1\) under \(\mathbb{P}_i\). Decomposing according to these events gives \(\mathbb{P}_i(X_{s+t}=j)=\sum_{k\in S}\mathbb{P}_i(X_s=k,\ X_{s+t}=j)\). For any \(k\) with \(\mathbb{P}_i(X_s=k)>0\), the time-homogeneous Markov property gives \(\mathbb{P}_i(X_{s+t}=j\mid X_s=k)=\mathbb{P}_k(X_t=j)=p_{kj}(t)\). If \(\mathbb{P}_i(X_s=k)=0\), the corresponding joint probability is zero, so no conditional probability on that event is needed. Thus each joint probability in the sum is \(p_{ik}(s)p_{kj}(t)\). This proves the entrywise identity. Since matrix multiplication has entries \((P(s)P(t))_{ij}=\sum_{k\in S}p_{ik}(s)p_{kj}(t)\), the matrix identity follows. \(\square\)
Because distributions are row vectors, an initial distribution \(\mu\) evolves over an interval of length \(t\) to \(\mu P(t)\). Combining this with Chapman–Kolmogorov shows that evolving first for \(s\) and then for \(t\) gives \((\mu P(s))P(t)=\mu P(s+t)\). The equality holds because the matrix product groups the same transition probabilities as the single combined interval.
Two-State Calculation
Worked Example: Survival Until Absorption
Consider a chain with states \(1\) and \(2\), where state \(2\) is absorbing and the holding time in state \(1\) is exponential with rate \(\lambda>0\). The probability of still being in state \(1\) after time \(u\) is \(e^{-\lambda u}\). Choose interval lengths \(s,t>0\) such that \(e^{-\lambda s}=\tfrac12\) and \(e^{-\lambda t}=\tfrac13\). Compute the transition matrix over the combined interval.
For any interval of length \(u\), the transition matrix has row \(1\) equal to \((e^{-\lambda u},1-e^{-\lambda u})\) and row \(2\) equal to \((0,1)\). Each row sums to \(1\). At the chosen interval lengths, the two matrices are
Multiplying gives
For example, the probability of starting in state \(1\) and ending in state \(2\) is the sum of two possibilities: move to state \(2\) during the first interval, or remain in state \(1\) at time \(s\) and move during the second. Their probabilities are \(\tfrac12\cdot1=\tfrac12\) and \(\tfrac12\cdot\tfrac23=\tfrac13\), giving \(\tfrac12+\tfrac13=\tfrac56\). The probability of remaining in state \(1\) is \(\tfrac12\cdot\tfrac13=\tfrac16\).
Check: The product's first row sums to \(\tfrac16+\tfrac56=1\), and its second row sums to \(0+1=1\). Directly over time \(s+t\), the survival probability is \(e^{-\lambda(s+t)}=e^{-\lambda s}e^{-\lambda t}=\tfrac12\cdot\tfrac13=\tfrac16\), agreeing with the product.
Three States and Intermediate-State Sums
In a three-state example, each entry of the product can contain three terms. The terms need not all be nonzero: a zero term records an impossible route in that interval. The next example uses a chain that, at the events of a Poisson clock, replaces its state by a uniformly selected state in \(\{1,2,3\}\). A replacement may select the same state, which leaves the observed state unchanged. If \(r\) is the probability that no clock event occurs during an interval, then with probability \(r\) the initial state is retained, and otherwise the state at the end is uniform. Consequently \(p_{ij}=r\mathbf{1}_{\{i=j\}}+(1-r)/3\).
Worked Example: Uniform Resampling in Three States
Let \(s,t>0\) be chosen so that the probability of no clock event is \(\tfrac12\) during the first interval and \(\tfrac13\) during the second. For an interval with no-event probability \(r\), the diagonal entries are \(r+(1-r)/3\), and the off-diagonal entries are \((1-r)/3\). Thus, for the first interval, each diagonal entry is \(\tfrac12+\tfrac{1/2}{3}=\tfrac23\), while each off-diagonal entry is \(\tfrac{1/2}{3}=\tfrac16\). For the second interval, the diagonal entries are \(\tfrac13+\tfrac{2/3}{3}=\tfrac59\), and the off-diagonal entries are \(\tfrac{2/3}{3}=\tfrac29\).
The two transition matrices are therefore
Every row of the first matrix sums to \(\tfrac23+\tfrac16+\tfrac16=1\), and every row of the second sums to \(\tfrac59+\tfrac29+\tfrac29=1\). To compute the first row of the product, include all three intermediate states. Its first entry is \(\tfrac23\cdot\tfrac59+\tfrac16\cdot\tfrac29+\tfrac16\cdot\tfrac29=\tfrac{10}{27}+\tfrac1{27}+\tfrac1{27}=\tfrac49\). Its second entry is \(\tfrac23\cdot\tfrac29+\tfrac16\cdot\tfrac59+\tfrac16\cdot\tfrac29=\tfrac4{27}+\tfrac5{54}+\tfrac2{54}=\tfrac5{18}\). The third entry has the same terms as the second, so it is also \(\tfrac5{18}\).
The matrices are symmetric under relabeling the states, so each row of their product has the same diagonal and off-diagonal values. Hence
Check: Each product row sums to \(\tfrac49+\tfrac5{18}+\tfrac5{18}=\tfrac89+\tfrac{10}{18}=1\). Over the combined interval, the no-event probability is \(\tfrac12\cdot\tfrac13=\tfrac16\). The direct formula gives diagonal entries \(\tfrac16+\tfrac{5/6}{3}=\tfrac49\), and off-diagonal entries \(\tfrac{5/6}{3}=\tfrac5{18}\), matching the product.
Propagating an Initial Distribution
Worked Example: Two Transient States and One Absorbing State
Suppose states \(1\) and \(2\) each move to absorbing state \(3\) at rate \(\lambda>0\), with no transitions between \(1\) and \(2\). Choose \(s,t>0\) with \(e^{-\lambda s}=\tfrac12\) and \(e^{-\lambda t}=\tfrac13\). Starting from \(\mu=(\tfrac12,\tfrac13,\tfrac16)\), find the distribution after both intervals.
For any interval with survival probability \(r\), the transition matrix is \(\begin{bmatrix}r&0&1-r\\0&r&1-r\\0&0&1\end{bmatrix}\). Each row sums to \(r+1-r=1\) for the first two rows and to \(1\) for the last. Therefore
Multiplication gives first row \((\tfrac12\cdot\tfrac13,\ 0,\ \tfrac12\cdot\tfrac23+\tfrac12\cdot1)=(\tfrac16,0,\tfrac56)\). The second row is \((0,\tfrac16,\tfrac56)\), and the third row remains \((0,0,1)\). Thus \(P(s+t)=\begin{bmatrix}\tfrac16&0&\tfrac56\\0&\tfrac16&\tfrac56\\0&0&1\end{bmatrix}\).
Applying the two intervals successively, the distribution after the first interval is \(\mu P(s)=(\tfrac14,\tfrac16,\tfrac7{12})\): the first coordinate is \(\tfrac12\cdot\tfrac12=\tfrac14\), the second is \(\tfrac13\cdot\tfrac12=\tfrac16\), and the third is \(\tfrac12\cdot\tfrac12+\tfrac13\cdot\tfrac12+\tfrac16=\tfrac14+\tfrac16+\tfrac16=\tfrac7{12}\). After the second interval it is \((\tfrac14,\tfrac16,\tfrac7{12})P(t)=(\tfrac1{12},\tfrac1{18},\tfrac{31}{36})\). Indeed, the first two coordinates are \(\tfrac14\cdot\tfrac13=\tfrac1{12}\) and \(\tfrac16\cdot\tfrac13=\tfrac1{18}\); the third is \(\tfrac14\cdot\tfrac23+\tfrac16\cdot\tfrac23+\tfrac7{12}=\tfrac16+\tfrac19+\tfrac7{12}=\tfrac{31}{36}\).
Check: Directly, \(\mu P(s+t)=(\tfrac12\cdot\tfrac16,\tfrac13\cdot\tfrac16,\tfrac12\cdot\tfrac56+\tfrac13\cdot\tfrac56+\tfrac16)=(\tfrac1{12},\tfrac1{18},\tfrac{31}{36})\). The entries sum to \(\tfrac3{36}+\tfrac2{36}+\tfrac{31}{36}=1\), as required for a probability distribution.
Why the Identity Is Useful—and a Common Mistake
Chapman–Kolmogorov computations are useful when a time interval is naturally divided into stages, or when probabilities over a long interval are easier to obtain by combining shorter-interval matrices. They also provide a consistency check: a proposed family of transition matrices for a time-homogeneous chain must satisfy the identity for every pair of nonnegative interval lengths. At \(s=0\) or \(t=0\), the transition matrix is the identity matrix, so the formula reduces to \(P(0)P(t)=P(t)\) or \(P(s)P(0)=P(s)\).
Common mistake: Transition probabilities across successive intervals are not added without weighting by the intermediate state. In the two-state example, the incorrect calculation \(p_{12}(s+t)=p_{12}(s)+p_{12}(t)=\tfrac12+\tfrac23=\tfrac76\) is impossible: it exceeds \(1\) and ignores whether the chain was in state \(1\) at time \(s\). The correct calculation is \(p_{12}(s+t)=p_{11}(s)p_{12}(t)+p_{12}(s)p_{22}(t)=\tfrac12\cdot\tfrac23+\tfrac12\cdot1=\tfrac56\). The intermediate-state sum is essential; it is what makes the computation a matrix product rather than a sum of entries.
Check Your Understanding
For each question, write the intermediate-state sum or matrix product before simplifying.
- If \(P(s)=\begin{bmatrix}\tfrac34&\tfrac14\\0&1\end{bmatrix}\) and \(P(t)=\begin{bmatrix}\tfrac25&\tfrac35\\0&1\end{bmatrix}\), compute \(p_{11}(s+t)\) and \(p_{12}(s+t)\). Check the row sum.
- In a three-state chain, what does the term \(p_{i2}(s)p_{2j}(t)\) represent in the formula for \(p_{ij}(s+t)\)?
- For a row distribution \(\mu\), explain why the distribution after intervals \(s\) and then \(t\) is \((\mu P(s))P(t)\), not \(P(t)(\mu P(s))\).
- Why does the definition \(p_{ij}(t)=\mathbb{P}_i(X_t=j)\) avoid requiring \(\mathbb{P}(X_0=i)>0\) under an arbitrary initial distribution?
- In the uniform-resampling example, verify the combined-interval off-diagonal probability using the no-event probability over the full interval.