Propagating Initial Distributions Through n Steps

How an Initial Distribution Evolves

A transition matrix describes what happens over one step when the current state is known. Often, however, the chain starts in a state that is itself random. To find the probability of each state after several steps, we combine the initial uncertainty with the one-step transition rule. The resulting calculation is compact: multiply a row distribution by the transition matrix once for each step.

Let \((X_n)_{n\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})\). Write \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) for the information observed through time \(n\). Its transition matrix is \(P=(p_{ij})\), where \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)\) when \(X_n=i\), almost surely. The transition rule is specified for every state, including states that have probability zero under a particular initial distribution. Each row of \(P\) is a probability distribution.

Keeping distributions as row vectors fixes the order of multiplication. If the chain is in state \(i\) with probability \(\mu_n(i)\), then it contributes \(\mu_n(i)p_{ij}\) to the probability of being in state \(j\) at the next step. Adding those contributions over possible current states gives the one-step update.

Proof. First consider one step. For any \(j\in S\), partition the event \(\{X_{n+1}=j\}\) according to the value \(i\) of \(X_n\). The law of total probability and the Markov property give \(\mathbb{P}(X_{n+1}=j)=\sum_{i\in S}\mathbb{P}(X_n=i)\mathbb{P}(X_{n+1}=j\mid X_n=i)=\sum_{i\in S}\mu_n(i)p_{ij}\). For countable \(S\), these are sums of nonnegative terms. This is precisely the \(j\)th coordinate of \(\mu_nP\), so \(\mu_{n+1}=\mu_nP\). At \(n=0\), the claim \(\mu_0=\mu_0P^0\) follows from \(P^0=I\). If \(\mu_n=\mu_0P^n\), then the one-step update gives \(\mu_{n+1}=\mu_nP=(\mu_0P^n)P=\mu_0P^{n+1}\). Induction proves the formula for all \(n\ge0\). \(\square\)

This calculation depends on the distribution at the current time, not just on the initial state. Each multiplication incorporates one more transition. The time-homogeneity assumption matters: it lets us use the same matrix \(P\) at each step. For a chain with a different transition matrix at each time, the update would instead multiply by the matrix for the next transition.

Proof. The events \(\{X_n=j\}\), for \(j\in A\), are disjoint and their union is \(\{X_n\in A\}\). Countable additivity therefore gives \(\mathbb{P}(X_n\in A)=\sum_{j\in A}\mathbb{P}(X_n=j)=\sum_{j\in A}\mu_n(j)\). For finite \(S\), the expectation of \(f(X_n)\) is \(\sum_{j\in S}f(j)\mathbb{P}(X_n=j)=\sum_{j\in S}\mu_n(j)f(j)\), which is the row-by-column product \(\mu_n f\). \(\square\)

The proposition shows how to extract a quantity of interest once the distribution is known. For example, the probability of a specified collection of states is found by summing its entries; the expected value of a numerical state label is found by weighting each entry by that label.

Reading and Checking the Update

The formula \(\mu_n=\mu_0P^n\) separates two ingredients: the initial distribution and the transition mechanism. The matrix \(P^n\) describes the transition probabilities over \(n\) steps, while multiplying on the left by \(\mu_0\) averages those transitions over the possible starting states. In particular, if the initial state is known to be \(i\), then \(\mu_0\) has a \(1\) in position \(i\) and zeros elsewhere, so \(\mu_n\) is row \(i\) of \(P^n\).

For a set \(A\) of states, the desired probability is \(\sum_{j\in A}\mu_n(j)\), not a matrix entry unless \(A\) contains just one state. For a finite state space and a numerical function \(f\), the expected value is the row-by-column product \(\mu_n f\). These are direct uses of the time-\(n\) distribution; they do not require a separate calculation of the full sample path.

Common mistake: multiplying on the wrong side. In the first example, treating the initial row distribution \((1,0)\) as a column and computing \(P\begin{bmatrix}1\\0\end{bmatrix}\) gives \(\begin{bmatrix}\tfrac34\\\tfrac12\end{bmatrix}\). Its entries sum to \(\tfrac54\), so it cannot be a probability distribution. The correct calculation is \((1,0)P=(\tfrac34,\tfrac14)\), whose entries sum to \(1\). With the row-vector convention, distributions multiply on the left and transition matrices on the right.

Another useful check is to verify the answer in two ways when practical: update one step at a time, or compute \(P^n\) and then multiply by \(\mu_0\). Agreement does not replace checking the inputs: first confirm that the entries of the initial vector sum to \(1\) and that each row of \(P\) sums to \(1\). Then confirm that the computed distribution has nonnegative entries summing to \(1\).