Conditioning at an Intermediate Time
A chain that starts at \(i\) and is observed \(m+n\) steps later must occupy some state \(k\) after the first \(m\) steps. The possible intermediate states divide the event of ending at \(j\) into disjoint cases. The Chapman–Kolmogorov equation expresses the probability of that endpoint as a sum over those cases: each term is the probability of reaching \(k\) in \(m\) steps multiplied by the probability of going from \(k\) to \(j\) in the next \(n\) steps.
Let \((X_r)_{r\ge0}\) be a time-homogeneous Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its natural filtration is \(\mathcal{F}_r=\sigma(X_0,\ldots,X_r)\). Write \(\mathbb{P}_i\) for the law of the chain started at \(i\), and define \(p_{ij}^{(r)}=\mathbb{P}_i(X_r=j)\), with \(p_{ij}^{(0)}=\mathbf{1}_{\{i=j\}}\). The Markov property used here is that, given \(\mathcal{F}_m\), the conditional law of the future chain is the law of a chain started from its current state \(X_m\). In particular, for \(n\ge0\), its conditional probability of being at \(j\) after a further \(n\) steps is \(p_{X_mj}^{(n)}\).
Proof. Fix \(i,j,m,n\), and work under \(\mathbb{P}_i\). The events \(\{X_m=k\}\), \(k\in S\), are disjoint and together exhaust the sample space. Therefore, $$ \mathbb{P}_i(X_{m+n}=j)=\sum_{k\in S}\mathbb{P}_i(X_m=k,\ X_{m+n}=j). $$ If \(\mathbb{P}_i(X_m=k)>0\), the Markov property gives $$ \mathbb{P}_i(X_{m+n}=j\mid X_m=k)=p_{kj}^{(n)}. $$ Thus the corresponding joint probability is \(p_{ik}^{(m)}p_{kj}^{(n)}\), since \(\mathbb{P}_i(X_m=k)=p_{ik}^{(m)}\). If \(\mathbb{P}_i(X_m=k)=0\), the joint probability and the product \(p_{ik}^{(m)}p_{kj}^{(n)}\) are both zero, so no conditional probability on that null event is needed. Substituting each joint probability into the sum gives the claimed identity. The argument also covers \(m=0\) or \(n=0\), using \(p_{ij}^{(0)}=\mathbf{1}_{\{i=j\}}\). \(\square\)
The equation is a conditional-probability identity, not a statement that the chain is stationary. The transition probabilities may depend on the number of steps, and the starting distribution may be arbitrary. The time-homogeneous Markov assumption ensures that the probability of the next \(n\) steps, once the intermediate state \(k\) is known, is \(p_{kj}^{(n)}\), regardless of the earlier history.
Worked Calculations
Worked Example: Two Steps Through Three States
Consider a chain on \(S=\{1,2,3\}\) with transition matrix $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac13&\tfrac23\\ \tfrac14&\tfrac14&\tfrac12 \end{bmatrix}. $$ Before using the transition data, check the row sums: \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac13+\tfrac23=1\), and \(\tfrac14+\tfrac14+\tfrac12=1\). Find the two-step transition probabilities by conditioning after one step.
For a two-step transition from \(i\) to \(j\), the intermediate state can be \(1\), \(2\), or \(3\). For example, from \(1\) to \(3\), only the route through state \(2\) has positive probability: $$ p_{13}^{(2)} =p_{11}p_{13}+p_{12}p_{23}+p_{13}p_{33} =\tfrac12\cdot0+\tfrac12\cdot\tfrac23+0\cdot\tfrac12 =\tfrac13. $$ Applying the same sum to each entry gives $$ P^{(2)}= \begin{bmatrix} \tfrac14&\tfrac5{12}&\tfrac13\\ \tfrac16&\tfrac5{18}&\tfrac59\\ \tfrac14&\tfrac13&\tfrac5{12} \end{bmatrix}. $$ For instance, its first row is \((\tfrac12\cdot\tfrac12+\tfrac12\cdot0,\ \tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac13,\ \tfrac12\cdot0+\tfrac12\cdot\tfrac23)=(\tfrac14,\tfrac5{12},\tfrac13)\). The second row is \((0\cdot\tfrac12+\tfrac13\cdot0+\tfrac23\cdot\tfrac14,\ 0\cdot\tfrac12+\tfrac13\cdot\tfrac13+\tfrac23\cdot\tfrac14,\ 0+\tfrac13\cdot\tfrac23+\tfrac23\cdot\tfrac12)=(\tfrac16,\tfrac5{18},\tfrac59)\). The third row is \((\tfrac14\cdot\tfrac12+\tfrac14\cdot0+\tfrac12\cdot\tfrac14,\ \tfrac14\cdot\tfrac12+\tfrac14\cdot\tfrac13+\tfrac12\cdot\tfrac14,\ \tfrac14\cdot0+\tfrac14\cdot\tfrac23+\tfrac12\cdot\tfrac12)=(\tfrac14,\tfrac13,\tfrac5{12})\).
Check: The row sums are \(\tfrac14+\tfrac5{12}+\tfrac13=\tfrac3{12}+\tfrac5{12}+\tfrac4{12}=1\), \(\tfrac16+\tfrac5{18}+\tfrac59=\tfrac3{18}+\tfrac5{18}+\tfrac{10}{18}=1\), and \(\tfrac14+\tfrac13+\tfrac5{12}=\tfrac3{12}+\tfrac4{12}+\tfrac5{12}=1\). In particular, the computed value \(p_{13}^{(2)}=\tfrac13\) agrees with the only possible two-step route, \(1\to2\to3\), whose probability is \(\tfrac12\cdot\tfrac23=\tfrac13\).
Worked Example: The Same Three-Step Probability at Two Splits
On \(S=\{1,2\}\), take $$ P=\begin{bmatrix} \tfrac34&\tfrac14\\ \tfrac12&\tfrac12 \end{bmatrix}. $$ The row sums are \(\tfrac34+\tfrac14=1\) and \(\tfrac12+\tfrac12=1\). First condition after one step to find the two-step probabilities: $$ p_{11}^{(2)}=\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac12=\tfrac9{16}+\tfrac2{16}=\tfrac{11}{16},\qquad p_{12}^{(2)}=\tfrac34\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac3{16}+\tfrac2{16}=\tfrac5{16}, $$ $$ p_{21}^{(2)}=\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac12=\tfrac38+\tfrac14=\tfrac58,\qquad p_{22}^{(2)}=\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac12=\tfrac18+\tfrac14=\tfrac38. $$ The two-step row sums check: \(\tfrac{11}{16}+\tfrac5{16}=1\) and \(\tfrac58+\tfrac38=1\). Now calculate the probability of going from \(1\) to \(1\) in three steps, splitting first as \(1+2\): $$ p_{11}^{(3)} =p_{11}p_{11}^{(2)}+p_{12}p_{21}^{(2)} =\tfrac34\cdot\tfrac{11}{16}+\tfrac14\cdot\tfrac58 =\tfrac{33}{64}+\tfrac{10}{64} =\tfrac{43}{64}. $$ Splitting instead as \(2+1\) gives $$ p_{11}^{(3)} =p_{11}^{(2)}p_{11}+p_{12}^{(2)}p_{21} =\tfrac{11}{16}\cdot\tfrac34+\tfrac5{16}\cdot\tfrac12 =\tfrac{33}{64}+\tfrac{10}{64} =\tfrac{43}{64}. $$ Check: Both choices of intermediate time give exactly \(\tfrac{43}{64}\), as required for a probability defined by the same three-step event.
Worked Example: A Zero-Probability Intermediate State
Consider \(S=\{1,2,3\}\) and $$ P=\begin{bmatrix} 0&1&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}. $$ Every row sums to \(1\): the sums are \(0+1+0=1\), \(0+1+0=1\), and \(0+0+1=1\). Starting at state \(1\), after one step the chain is at state \(2\) with probability \(1\). Find \(p_{13}^{(2)}\) using the equation with intermediate time \(m=1\).
The sum over intermediate states is $$ p_{13}^{(2)} =p_{11}p_{13}+p_{12}p_{23}+p_{13}p_{33} =0\cdot0+1\cdot0+0\cdot1=0. $$ The term for intermediate state \(1\) is zero because it is impossible to be there after one step from \(1\). It is not necessary, and would not be meaningful, to calculate \(\mathbb{P}_1(X_2=3\mid X_1=1)\): the conditioning event has probability zero. The equation uses the zero product for that state instead.
Check: The only possible intermediate state is \(2\), and \(p_{23}=0\), so the chain cannot reach \(3\) on the second step. This agrees with the computed probability \(0\).
Conditioning on the Intermediate State Given the Endpoint
The same decomposition can answer a reverse question: if the starting and ending states are known, what is the distribution of the state at the intermediate time? This conditional distribution is defined only when the endpoint event has positive probability.
Proof. Since the denominator is positive, the conditional probability is defined. By the Markov property, the joint probability of \(X_m=k\) and \(X_{m+n}=j\), under \(\mathbb{P}_i\), is \(p_{ik}^{(m)}p_{kj}^{(n)}\), including when the first factor is zero. Dividing this joint probability by \(\mathbb{P}_i(X_{m+n}=j)=p_{ij}^{(m+n)}\) gives the formula. The conditional probabilities sum to \(1\), because their numerators sum to \(p_{ij}^{(m+n)}\) by the Chapman–Kolmogorov equation, and the denominator is positive. \(\square\)
For example, in the first worked example, \(p_{13}^{(2)}=\tfrac13>0\). Given that the chain started at \(1\) and is at \(3\) after two steps, the probability that it was at \(2\) after one step is $$ \mathbb{P}_1(X_1=2\mid X_2=3) =\frac{p_{12}p_{23}}{p_{13}^{(2)}} =\frac{\tfrac12\cdot\tfrac23}{\tfrac13}=1. $$ For \(k=1\) and \(k=3\), the corresponding numerators are \(p_{11}p_{13}=\tfrac12\cdot0=0\) and \(p_{13}p_{33}=0\cdot\tfrac12=0\). The conditional probabilities over the three possible intermediate states are therefore \(0,1,0\), which sum to \(1\).
Common Pitfalls and Interpretation
A frequent error is to add conditional probabilities without weighting them by the probabilities of the intermediate states. In the first worked example, the conditional probabilities of reaching \(3\) on the next step from states \(1,2,3\) are \(0,\tfrac23,\tfrac12\). Adding them gives \(\tfrac76\), which is not the two-step probability. The correct calculation weights each conditional probability by the probability of being in that intermediate state after one step: $$ \tfrac12\cdot0+\tfrac12\cdot\tfrac23+0\cdot\tfrac12=\tfrac13. $$ The weights are essential because the intermediate states do not occur equally often.
A second error is to divide by a conditioning probability that is zero. The Chapman–Kolmogorov sum does not require conditioning on every intermediate-state event separately. For a state \(k\) with \(p_{ik}^{(m)}=0\), its joint contribution is zero, and the product \(p_{ik}^{(m)}p_{kj}^{(n)}\) handles it directly.
The equation is useful whenever a transition over a longer interval can be understood by splitting the interval at a fixed time. The intermediate state need not be observed in practice; summing over its possible values accounts for all ways the chain can progress. It is important to keep the roles of the factors straight: \(p_{ik}^{(m)}\) describes the first part, from \(i\) to \(k\), and \(p_{kj}^{(n)}\) describes the remaining part, from \(k\) to \(j\).
Check Your Understanding
Use the Chapman–Kolmogorov equation and check that every conditional probability you use is defined.
- For the three-state chain in the first worked example, calculate \(p_{22}^{(2)}\) by summing over all three possible intermediate states.
- For the two-state chain in the second example, calculate \(p_{22}^{(2)}\) and verify that the second row of its two-step transition probabilities sums to \(1\).
- Why is \(\mathbb{P}_1(X_2=3\mid X_1=1)\) undefined in the third worked example, even though the Chapman–Kolmogorov equation still has a term for intermediate state \(1\)?
- State the extra condition needed to use the intermediate-state conditional-probability formula given the endpoint \(j\).
- In the two-state example, which two different intermediate times were used to compute \(p_{11}^{(3)}\), and why must the results agree?