Transition Probabilities by Path Enumeration

From One-Step Moves to Multi-Step Probabilities

A transition probability over several steps collects the probabilities of all possible ways the chain can travel between its starting and ending states. The calculation is finite when the state space is finite, and it can be organized even when the state space is countable: specify the intermediate states, multiply the one-step probabilities along each path, and add the results. Keeping the paths visible is especially useful when different routes contribute substantially or when some routes have probability zero.

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})\). Write \(P=(p_{ij})\) for its row-stochastic transition matrix, so \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\) under the Markov transition rule and \(\sum_{j\in S}p_{ij}=1\) for each \(i\in S\). Let \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The Markov property means that, conditional on \(\mathcal{F}_n\), the distribution of \(X_{n+1}\) depends on the past only through \(X_n\), with \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{X_nj}\) almost surely. We use \(\mathbb{P}_i\) for probabilities when \(X_0=i\).

For instance, in two steps from \(i\) to \(j\), the only intermediate state is the state \(k=X_1\). In three steps, there are two intermediate states, \(k=X_1\) and \(\ell=X_2\). The path formula gives the contributions \(p_{ik}p_{kj}\) and \(p_{ik}p_{k\ell}p_{\ell j}\), respectively. These are not probabilities of the same event: each product corresponds to one particular sequence of states. The endpoint probability is obtained only after all possible intermediate states have been accounted for.

Two Results That Justify Enumeration

Proof. Fix a path \(i_0,\ldots,i_n\), and let \(A_m=\{X_1=i_1,\ldots,X_m=i_m\}\) for \(1\le m\le n\), with \(A_0=\Omega\) under \(\mathbb{P}_{i_0}\). We prove successively that \(\mathbb{P}_{i_0}(A_m)=\prod_{r=1}^{m}p_{i_{r-1}i_r}\). The claim holds for \(m=0\) using the empty-product convention. For \(m\ge0\), \(A_m\) is measurable with respect to \(\mathcal{F}_m\). By conditional expectation and the Markov property,

The last equality holds because \(X_m=i_m\) on \(A_m\). It does not require conditioning on \(A_m\), so it remains valid when \(\mathbb{P}_{i_0}(A_m)=0\). Induction gives the stated product for every \(m\le n\). \(\square\)

Proof. Under \(\mathbb{P}_i\), the event \(\{X_n=j\}\) is the disjoint union over all sequences \((i_1,\ldots,i_{n-1})\in S^{n-1}\) of the events \(\{X_1=i_1,\ldots,X_{n-1}=i_{n-1},X_n=j\}\). Each such event has probability equal to its path product by the path formula. Adding the probabilities of these disjoint events gives the result by finite or countable additivity. For \(n=1\), the event is simply \(\{X_1=j\}\), whose probability is \(p_{ij}\); this also covers the case with no intermediate states. \(\square\)

For a finite state space, the theorem gives a practical procedure: list the intermediate-state sequences, calculate each product, and add. For a countable state space, the same decomposition is valid, but there may be infinitely many paths; the resulting sum is understood as a nonnegative series. The examples below use finite state spaces so that every contributing path can be displayed explicitly.

Reading and Checking a Path Enumeration

For a fixed starting state and endpoint, every intermediate-state sequence contributes exactly one path event. The events are mutually exclusive because a chain cannot have two different values at the same intermediate time; together they exhaust the event of ending at the specified endpoint. This is why the calculation uses a sum, not a product of the path probabilities. Within each path, the one-step probabilities are multiplied because the Markov path formula gives the probability of that complete sequence.

Two checks help catch errors. First, confirm that every row of \(P\) sums to 1 before interpreting its entries as transition probabilities. Second, check whether the listed intermediate-state sequences cover all possibilities. For a finite state space of size \(r\), there are \(r^{n-1}\) sequences of intermediate states for an \(n\)-step probability, though many may have zero contribution. A compact calculation may omit zero terms only after identifying why those paths have zero probability.

Common mistake: conditioning on an impossible prefix. In the three-state example, the path \(0\to2\to1\to2\) has first transition probability \(p_{02}=0\). It is invalid to write a conditional probability “given \(X_1=2\)” under \(\mathbb{P}_0\), because that conditioning event has probability zero. The product for the full path is nevertheless \(0\cdot\tfrac12\cdot\tfrac12=0\). The path formula proof uses conditional expectation given \(\mathcal{F}_n\), not conditioning on the path event, and therefore covers this case without assigning meaning to a conditional probability on a null event.

Path enumeration is most useful when only a few entries of \(P^{(n)}\) are needed, when a model has a clear set of possible routes, or when the contributions of different routes have separate interpretations. For large \(n\) or a large state space, writing every path may become unwieldy; the enumeration identity still explains the probability, while matrix multiplication or other methods can organize the arithmetic more efficiently. At this stage, the key discipline is to distinguish the complete path from its endpoint event and to account for every intermediate possibility exactly once.