One-Step Transition Laws Can Change with Time
A Markov chain has a one-step rule: given its current state, the distribution of its next state does not depend on the earlier path. But that rule may itself change from one time to another. A weather model might use one set of transition probabilities in winter and another in summer; a treatment model might use different probabilities at different stages of follow-up. The distinction is between dependence on the past states and dependence on the time index.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\). Use the natural filtration \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\), the information available through time \(n\). For each time \(n\), suppose a transition kernel is specified for every state \(i\in S\). Its entries are \(p_{ij}(n)\), the conditional probability of moving from \(i\) at time \(n\) to \(j\) at time \(n+1\). When \(\mathbb P(X_n=i)>0\), this is the ordinary conditional probability \(\mathbb P(X_{n+1}=j\mid X_n=i)\); for a state with probability zero at that time, the specified kernel supplies a version of the transition rule.
Both kinds of chain can satisfy the Markov property. That property concerns which information is needed to predict the next state; homogeneity concerns whether the prediction rule changes with the time index. Neither term describes whether the distribution of \(X_n\) stays the same as \(n\) changes. In particular, a homogeneous chain can have a changing marginal distribution.
Composing Transitions Across Several Steps
Write \(P_n\) for the transition matrix from time \(n\) to time \(n+1\). For integers \(r<s\), define \(P(r,s)\) to be the transition matrix from time \(r\) to time \(s\); its \((i,j)\) entry is the probability of being at \(j\) at time \(s\), given state \(i\) at time \(r\). As usual, a conditional probability given \(X_r=i\) is directly determined by the probability law when \(\mathbb P(X_r=i)>0\). The specified transition kernels also define the transition rule for other states.
Proof. Fix \(r<s\) and states \(i,j\). For \(s=r+1\), the formula is the definition of \(P_r\). For a longer interval, condition on the state \(X_{s-1}\) immediately before time \(s\). The Markov property gives $$ \mathbb P(X_s=j\mid X_r=i) =\sum_{k\in S}\mathbb P(X_{s-1}=k\mid X_r=i)\,p_{kj}(s-1). $$ This is the \((i,j)\) entry of \(P(r,s-1)P_{s-1}\). Repeating this argument, starting from the one-step case, gives \(P_rP_{r+1}\cdots P_{s-1}\). The sum is valid for a countable state space because its terms are nonnegative and the intermediate-state probabilities sum to \(1\). When \(r=s\), the state has not changed, so the transition matrix is the identity. In the homogeneous case every factor is \(P\), leaving \(s-r\) copies of \(P\), which is \(P^{s-r}\). \(\square\)
The order in the product matters: the leftmost matrix acts first on a row distribution. If \(\mu_r\) is the distribution at time \(r\), written as a row vector, then \(\mu_s=\mu_rP(r,s)\). In the homogeneous case this becomes \(\mu_s=\mu_rP^{s-r}\); in the inhomogeneous case the matrices generally cannot be replaced by a single power.
Worked Example: A Homogeneous Chain with a Changing Distribution
Let \(S=\{1,2\}\), with the same transition matrix at every time: $$ P=\begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ The first row sums to \(\tfrac23+\tfrac13=1\), and the second sums to \(\tfrac14+\tfrac34=1\). Start from \(\mu_0=(1,0)\).
One step gives $$ \mu_1=\mu_0P=(1,0) \begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac14&\tfrac34\end{bmatrix} =(\tfrac23,\tfrac13). $$ A second step gives $$ \mu_2=\mu_1P =(\tfrac23,\tfrac13) \begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac14&\tfrac34\end{bmatrix} =(\tfrac49+\tfrac1{12},\tfrac29+\tfrac14) =(\tfrac{19}{36},\tfrac{17}{36}). $$ The entries of \(\mu_1\) sum to \(1\), and those of \(\mu_2\) sum to \(\tfrac{19}{36}+\tfrac{17}{36}=1\). The transition law is homogeneous, but the distribution changes: \(\mu_0\ne\mu_1\). This illustrates why homogeneity and stationarity are different properties.
Worked Example: Alternating Transition Matrices
Let \(S=\{1,2\}\) and use the matrices $$ P_0=\begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix}, \qquad P_1=\begin{bmatrix}1&0\\[2pt]\tfrac13&\tfrac23\end{bmatrix}, $$ with \(P_0\) used from time \(0\) to time \(1\), \(P_1\) from time \(1\) to time \(2\), and the two matrices then repeated in that order. The row sums of \(P_0\) are \(\tfrac12+\tfrac12=1\) and \(0+1=1\). The row sums of \(P_1\) are \(1+0=1\) and \(\tfrac13+\tfrac23=1\). Start from \(\mu_0=(1,0)\).
After the first step, $$ \mu_1=\mu_0P_0=(1,0) \begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix} =(\tfrac12,\tfrac12). $$ After the second step, $$ \mu_2=\mu_1P_1 =(\tfrac12,\tfrac12) \begin{bmatrix}1&0\\[2pt]\tfrac13&\tfrac23\end{bmatrix} =(\tfrac12+\tfrac16,0+\tfrac13) =(\tfrac23,\tfrac13). $$ Each resulting distribution sums to \(1\). The one-step transition from state \(1\) is \((\tfrac12,\tfrac12)\) at time \(0\), but \((1,0)\) at time \(1\). Thus the transition law is time-inhomogeneous.
Worked Example: Why the Chronological Order Matters
Use the same two matrices, each of which has row sums \(1\) as checked in the preceding example. Start instead from \(\mu=(0,1)\). If \(P_0\) acts first and \(P_1\) second, then $$ \mu P_0=(0,1) \begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix} =(0,1), \qquad \mu P_0P_1=(0,1) \begin{bmatrix}1&0\\[2pt]\tfrac13&\tfrac23\end{bmatrix} =(\tfrac13,\tfrac23). $$ If \(P_1\) acts first and \(P_0\) second, then $$ \mu P_1=(0,1) \begin{bmatrix}1&0\\[2pt]\tfrac13&\tfrac23\end{bmatrix} =(\tfrac13,\tfrac23), $$ and $$ \mu P_1P_0=(\tfrac13,\tfrac23) \begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix} =(\tfrac16,\tfrac16+\tfrac23) =(\tfrac16,\tfrac56). $$ Both final vectors sum to \(1\), but they differ. The transition matrices must therefore be multiplied in their actual time order.
Homogeneity and Strict Stationarity
Strict stationarity is a property of the joint distributions of the process: shifting all observation times by the same amount leaves those distributions unchanged. A homogeneous transition law alone does not guarantee this property, as the first example showed. If the initial distribution is stationary for the homogeneous transition matrix, however, the resulting chain is strictly stationary.
Proof. First, the distribution at each time is \(\pi\). At time \(0\) this is the assumption. If the distribution at time \(n\) is \(\pi\), the one-step transition rule gives distribution \(\pi P=\pi\) at time \(n+1\). Induction proves the claim for every \(n\).
Now fix times \(0\le t_1<\cdots<t_k\) and states \(i_1,\ldots,i_k\). The probability of this state sequence is $$ \pi_{i_1}\,p^{(t_2-t_1)}_{i_1i_2}\cdots p^{(t_k-t_{k-1})}_{i_{k-1}i_k}, $$ where \(p^{(m)}_{ij}\) is the \((i,j)\) entry of \(P^m\). This follows by applying the Markov property successively between the specified times and summing over any intermediate states. The first factor is \(\pi_{i_1}\) because the distribution at \(t_1\) is \(\pi\); every other factor depends only on the gap between observation times because the chain is homogeneous. Shifting all \(t_\ell\) by the same nonnegative integer leaves the first factor and every gap unchanged, so the joint probability is unchanged. These probabilities determine the finite-dimensional distributions, proving strict stationarity. \(\square\)
The stationary initial distribution is essential to this conclusion. For example, in the first worked example the transition matrix is homogeneous, but the initial distribution is \((1,0)\), not a distribution that remains unchanged after multiplication by \(P\). The computed distributions \((1,0)\) and \((\tfrac23,\tfrac13)\) differ, so the process is not strictly stationary.
A Common Calculation Error
A tempting shortcut for a time-inhomogeneous chain is to average its matrices and then use the average as if it were the transition matrix at every time. This generally gives the wrong multi-step law. For the matrices \(P_0,P_1\) above, their average is $$ \overline P=\tfrac12(P_0+P_1) =\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac16&\tfrac56\end{bmatrix}. $$ Its rows sum to \(\tfrac34+\tfrac14=1\) and \(\tfrac16+\tfrac56=1\). The incorrect calculation from initial distribution \((0,1)\) would be $$ (0,1)\overline P^2 =(\tfrac16,\tfrac56) \begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac16&\tfrac56\end{bmatrix} =(\tfrac18+\tfrac5{36},\tfrac1{24}+\tfrac{25}{36}) =(\tfrac{19}{72},\tfrac{53}{72}). $$ The correct chronological calculation for \(P_0\) followed by \(P_1\) is \((0,1)P_0P_1=(\tfrac13,\tfrac23)\), as computed earlier. Both vectors sum to \(1\), but they are not equal: \(\tfrac{19}{72}\ne\tfrac13=\tfrac{24}{72}\). Averaging the matrices changes the transition rule; it does not preserve the original time-varying model.
For a problem involving transition laws, first identify whether the one-step matrix depends on time. If it does, keep the sequence \(P_r,\ldots,P_{s-1}\) and multiply in chronological order. If it does not, use powers of the common matrix. Separately check whether the distribution of the chain is stationary; that requires an appropriate initial distribution, not merely a homogeneous transition law.
Check Your Understanding
Use the definitions and calculations above to answer these questions.
- A chain uses the same transition matrix at every step, but its initial distribution changes after one transition. Is the transition law homogeneous? Must the process be strictly stationary?
- For a chain with matrices \(P_0\) and \(P_1\), write the matrix giving the transition from time \(0\) to time \(2\). Which matrix acts first on a row distribution?
- Using the matrices in the alternating-matrix example, compute the distribution at time \(2\) from initial distribution \((0,1)\), with \(P_0\) followed by \(P_1\).
- What additional condition on the initial distribution, beyond time homogeneity, ensures strict stationarity in the theorem?
- Explain why replacing a sequence of time-varying transition matrices by their average need not give the correct multi-step transition law.