From a Single Path to an Endpoint Probability
An \(n\)-step transition from \(i\) to \(j\) can occur through many different sequences of intermediate states. Each sequence describes one possible path, and the event of reaching \(j\) after \(n\) steps is the union of the events corresponding to those paths. Because distinct paths specify different values of at least one intermediate state, these events are disjoint. This gives a direct way to build an endpoint probability from probabilities of individual paths.
Let \((X_n)_{n\ge0}\) be a time-homogeneous discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition probabilities are \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), with the transition rule understood to apply at every time. Write \(P=(p_{ij})\), where \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). For a chain started at state \(i\), use \(\mathbb{P}_i\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\); the Markov property says that, for every \(j\), \(\mathbb{P}_i(X_{n+1}=j\mid\mathcal{F}_n)=p_{X_nj}\) almost surely.
The order matters: the path \((i,k,\ell,j)\) is generally different from \((i,\ell,k,j)\). The probability of one specified path is the product of the transition probabilities along its successive edges. The endpoint probability is obtained only after accounting for every possible sequence of intermediate states.
Proof. For \(n=1\), the statement is the definition of the one-step transition probability. Suppose the chain has followed a specified prefix through time \(r\), ending at \(x_r\). If that prefix has positive probability, the Markov property gives conditional probability \(p_{x_r x_{r+1}}\) for the next specified state \(x_{r+1}\). Thus extending the prefix multiplies its probability by \(p_{x_r x_{r+1}}\). If the prefix has probability zero, the extended path event also has probability zero, and the product for the prefix already contains a zero factor. Starting with probability \(1\) at \(X_0=i\) and applying this argument successively for each of the \(n\) transitions gives the stated product, including paths with zero-probability prefixes. \(\square\)
Proof. Fix \(i\) and \(j\). For each ordered tuple \((x_1,\ldots,x_{n-1})\in S^{n-1}\), let its path event be the event \(X_1=x_1,\ldots,X_{n-1}=x_{n-1},X_n=j\), under \(\mathbb{P}_i\). Every outcome for which \(X_n=j\) has exactly one such tuple, namely its actual states at times \(1,\ldots,n-1\). Consequently, these path events are pairwise disjoint and their union is \(\{X_n=j\}\). Since \(S\) is countable, there are at most countably many tuples. Countable additivity therefore expresses \(\mathbb{P}_i(X_n=j)\) as the sum of the probabilities of these events. By the proposition, each summand is the product of the one-step probabilities along its path. This proves the formula. Its terms are nonnegative, and their sum is a probability, so the countable sum is well-defined and at most \(1\). For \(n=1\), there is one empty tuple of intermediate states, corresponding to the single transition \(i\) to \(j\), giving \(p_{ij}\). \(\square\)
For two steps, the only intermediate state is \(x_1\), so each term represents a path \(i\to x_1\to j\). For three steps, there are two intermediate states, and a term represents \(i\to x_1\to x_2\to j\). These are sums over all states, not just over states different from the endpoints: a path may revisit its starting state or pass through its ending state before the final step.
Worked Two-Step Decompositions
Worked Example: Two Steps from a State Back to Itself
Consider \(S=\{A,B,C\}\) with transition matrix $$ P= \begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac14&\tfrac12&\tfrac14\\ \tfrac13&\tfrac13&\tfrac13 \end{bmatrix}. $$ Before using it, check the rows: for \(A\), \(\tfrac12+\tfrac13+\tfrac16=1\); for \(B\), \(\tfrac14+\tfrac12+\tfrac14=1\); and for \(C\), \(\tfrac13+\tfrac13+\tfrac13=1\).
Find \(p_{AA}^{(2)}\). The possible paths are \(A\to A\to A\), \(A\to B\to A\), and \(A\to C\to A\). Their probabilities are, respectively, $$ \tfrac12\cdot\tfrac12=\tfrac14,\qquad \tfrac13\cdot\tfrac14=\tfrac1{12},\qquad \tfrac16\cdot\tfrac13=\tfrac1{18}. $$ Adding the disjoint path probabilities gives $$ p_{AA}^{(2)}=\tfrac14+\tfrac1{12}+\tfrac1{18} =\tfrac9{36}+\tfrac3{36}+\tfrac2{36} =\tfrac{14}{36}=\tfrac7{18}. $$
Check: The total is between \(0\) and \(1\), as an endpoint probability must be. The path probabilities also sum to \(\tfrac14+\tfrac1{12}+\tfrac1{18}=\tfrac9{36}+\tfrac3{36}+\tfrac2{36}=\tfrac{14}{36}=\tfrac7{18}\), confirming that all three possible intermediate states have been included.
Worked Example: A Two-Step Transition with Three Possible Routes
Use the same chain to find \(p_{BA}^{(2)}\). The possible intermediate states are \(A,B,C\), so the paths are \(B\to A\to A\), \(B\to B\to A\), and \(B\to C\to A\). The one-step entries used are \(p_{BA}=\tfrac14\), \(p_{AA}=\tfrac12\), \(p_{BB}=\tfrac12\), \(p_{BC}=\tfrac14\), and \(p_{CA}=\tfrac13\). Thus $$ p_{BA}^{(2)} =\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac13 =\tfrac18+\tfrac18+\tfrac1{12} =\tfrac3{24}+\tfrac3{24}+\tfrac2{24} =\tfrac8{24}=\tfrac13. $$
Check by listing the events: From \(B\), the chain can be at \(A\), \(B\), or \(C\) after one step. If it is at \(A\), the probability of then moving to \(A\) is \(\tfrac12\), giving the first contribution \(\tfrac14\cdot\tfrac12=\tfrac18\). If it is at \(B\), the probability of then moving to \(A\) is \(\tfrac14\), giving \(\tfrac12\cdot\tfrac14=\tfrac18\). If it is at \(C\), the probability of then moving to \(A\) is \(\tfrac13\), giving \(\tfrac14\cdot\tfrac13=\tfrac1{12}\). The total is \(\tfrac18+\tfrac18+\tfrac1{12}=\tfrac13\), as above.
Three Steps: Two Intermediate States
Worked Example: Enumerating Three-Step Paths
Let \(S=\{0,1,2\}\) and use $$ P= \begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ \tfrac12&0&\tfrac12 \end{bmatrix}. $$ Each row sums to \(1\): the row for \(0\) has sum \(\tfrac12+\tfrac12+0=1\), the row for \(1\) has sum \(0+\tfrac12+\tfrac12=1\), and the row for \(2\) has sum \(\tfrac12+0+\tfrac12=1\).
Find \(p_{02}^{(3)}\). A path is determined by its first intermediate state \(x_1\) and second intermediate state \(x_2\), and its probability is \(p_{0x_1}p_{x_1x_2}p_{x_2 2}\). First take \(x_1=0\). The choices \(x_2=0,1,2\) give $$ \tfrac12\cdot\tfrac12\cdot0=0,\qquad \tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18,\qquad \tfrac12\cdot0\cdot\tfrac12=0. $$ Next take \(x_1=1\). The choices \(x_2=0,1,2\) give $$ \tfrac12\cdot0\cdot0=0,\qquad \tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18,\qquad \tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18. $$ Finally, \(x_1=2\) contributes zero for every \(x_2\), because \(p_{02}=0\). Summing all nine terms, $$ p_{02}^{(3)}=0+\tfrac18+0+0+\tfrac18+\tfrac18+0+0+0=\tfrac38. $$
Check by identifying the positive-probability paths: The three nonzero paths are \(0\to0\to1\to2\), \(0\to1\to1\to2\), and \(0\to1\to2\to2\). Each has probability \(\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18\). Their sum is \(3\cdot\tfrac18=\tfrac38\), matching the full enumeration. All other paths have at least one transition of probability zero.
What the Decomposition Does—and Does Not—Count
A path term is the probability of one specific ordered sequence of states. It is not generally the probability of the endpoint event by itself: the endpoint event can be reached along many paths, and those disjoint possibilities must be added. In a countable state space, the same rule applies, with a countable sum. Nonnegativity of the terms and the disjoint-event interpretation ensure that the sum cannot exceed \(1\).
Common mistake. In the first example, counting only the path \(A\to A\to A\) gives \(\tfrac12\cdot\tfrac12=\tfrac14\). This is the probability of that one path, not the probability of being at \(A\) after two steps. The missing paths contribute \(\tfrac13\cdot\tfrac14=\tfrac1{12}\) and \(\tfrac16\cdot\tfrac13=\tfrac1{18}\). The corrected endpoint probability is \(\tfrac14+\tfrac1{12}+\tfrac1{18}=\tfrac7{18}\). Multiplying transition probabilities along a path and adding probabilities across different paths are separate operations: multiply within each path, then sum across the disjoint paths.
A reliable calculation therefore has two checks. First, ensure the transition probabilities in each row sum to \(1\), so the data define a transition matrix. Second, list the intermediate-state choices in order and account for each once, including zero-probability paths if they help confirm that the enumeration is complete. The resulting sum is an endpoint probability; each individual product remains a path probability.
Check Your Understanding
For each question, distinguish the probability of a specified path from the probability of the endpoint event.
- In a two-state chain with \(p_{00}=\tfrac34\) and \(p_{01}=\tfrac14\), what is the probability of the two-step path \(0\to0\to1\)?
- For the matrix in the first worked example, list all paths contributing to \(p_{AC}^{(2)}\) and calculate their total probability.
- In a three-step transition, how many intermediate states specify a path, and how is the path probability formed?
- Why can probabilities of distinct paths be added to obtain the probability of reaching a fixed endpoint at a fixed time?
- Give one reason a term in the path-decomposition sum can be zero.