Reading Positive Powers as Paths

From Matrix Entries to Paths

A transition-matrix power gives probabilities after several steps, but its entries also have a concrete path interpretation. To understand whether a state can be reached in a specified number of steps, it is not enough to ask whether the states are connected somehow: the number of transitions matters. The key link is that a positive $n$-step transition probability corresponds to at least one sequence of $n$ transitions, each having positive probability.

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)$ and every row sums to $1$. For a chain started at $i$, probabilities are denoted by $\mathbb{P}_i$. Its $n$-step transition matrix is $P^n$, with entries $p_{ij}^{(n)}$. We use $P^0=I$, so $p_{ij}^{(0)}=1$ when $i=j$, and $0$ otherwise.

Definition: Draw a directed edge $i\to j$ when $p_{ij}>0$. A path of length $n$ from $i$ to $j$ is a sequence $i=i_0,i_1,\ldots,i_n=j$ for which every transition $p_{i_{r-1}i_r}$ is positive. States in a path may repeat. A path of length zero is allowed only from a state to itself.

The product of the transition probabilities along a particular path is the probability of following that sequence of states when the chain starts at its first state. Different sequences of intermediate states describe disjoint events: on any one run of the chain, the states at times $0,\ldots,n$ specify just one such sequence. Summing the path probabilities therefore gives the probability of ending at $j$ at time $n$.

Theorem (Path expansion): For $n\ge1$ and $i,j\in S$, $$ p_{ij}^{(n)} = \sum_{i_1,\ldots,i_{n-1}\in S} p_{i i_1}p_{i_1 i_2}\cdots p_{i_{n-1}j}. $$ For $n=1$, the expression is $p_{ij}$, with no intermediate states to sum over. If $S$ is countable, the sum is a countable sum of nonnegative terms.

Proof. We prove the formula by induction on $n$. For $n=1$, it is the identity $p_{ij}^{(1)}=p_{ij}$. Assume it holds for $n$. Matrix multiplication gives $p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}$. Substituting the induction formula for each $p_{ik}^{(n)}$ gives a sum over the intermediate states in a length-$n$ path from $i$ to $k$, followed by the final transition $k\to j$. Thus the terms are exactly the products associated with all length-$(n+1)$ sequences from $i$ to $j$. When $S$ is countable, all terms are nonnegative, so grouping the countable sum by the final intermediate state $k$ preserves its value. This proves the formula for $n+1$, and induction completes the proof. $\square$

Corollary (Positive power and path): For $n\ge1$, $p_{ij}^{(n)}>0$ if and only if there is a path of length exactly $n$ from $i$ to $j$. For $n=0$, $p_{ij}^{(0)}>0$ if and only if $i=j$, corresponding to the length-zero path.

Proof. For $n\ge1$, the path expansion writes $p_{ij}^{(n)}$ as a sum of nonnegative path products. If there is a path of length $n$, every factor in its product is positive, so that term is positive and the sum is positive. Conversely, if the sum is positive, at least one term must be positive: if every term were zero, their sum would be zero. A positive term has all its factors positive, so its sequence is a path of length $n$. For $n=0$, the identity matrix has a positive entry exactly on its diagonal, which is precisely the stated length-zero convention. $\square$

This result concerns an exact number of steps. The statement “there is a path of length $n$” is equivalent to “the chain can move from $i$ to $j$ in exactly $n$ steps with positive probability.” It does not by itself say that a path exists for every larger number of steps, or that the probability remains positive at other lengths. Those questions depend on which transitions can be repeated or inserted along a path.

Worked Example: Correctly Expanding a Four-State Row

Consider $S=\{1,2,3,4\}$ and the transition matrix $$ P= \begin{bmatrix} \tfrac14&\tfrac34&0&0\\ 0&0&\tfrac7{36}&\tfrac{29}{36}\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$ Before using it, check the row sums: row 1 has $\tfrac14+\tfrac34=1$; row 2 has $\tfrac7{36}+\tfrac{29}{36}=1$; row 3 sums to $1$; and row 4 sums to $1$.

Find the probability of being in each state after two steps when the chain starts at state 1. The possible first steps are to state 1 or state 2. Using the path expansion, the four entries in row 1 of $P^2$ are $$ \begin{aligned} p_{11}^{(2)}&=p_{11}p_{11}+p_{12}p_{21} =\tfrac14\cdot\tfrac14+\tfrac34\cdot0=\tfrac1{16},\\ p_{12}^{(2)}&=p_{11}p_{12}+p_{12}p_{22} =\tfrac14\cdot\tfrac34+\tfrac34\cdot0=\tfrac3{16},\\ p_{13}^{(2)}&=p_{11}p_{13}+p_{12}p_{23} =\tfrac14\cdot0+\tfrac34\cdot\tfrac7{36}=\tfrac7{48},\\ p_{14}^{(2)}&=p_{11}p_{14}+p_{12}p_{24} =\tfrac14\cdot0+\tfrac34\cdot\tfrac{29}{36}=\tfrac{29}{48}. \end{aligned} $$ Thus the row is $(\tfrac1{16},\tfrac3{16},\tfrac7{48},\tfrac{29}{48})$.

Check: With denominator $48$, the row sum is $\tfrac3{48}+\tfrac9{48}+\tfrac7{48}+\tfrac{29}{48}=\tfrac{48}{48}=1$. In particular, the path $1\to1\to1$ gives the first entry $\tfrac1{16}$; there is no length-two path $1\to2\to1$, since $p_{21}=0$.

Worked Example: A State Reached Only After Two Steps

Let $S=\{1,2,3\}$, with transition matrix $$ P= \begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac13&\tfrac23\\ 1&0&0 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac12=1$, $\tfrac13+\tfrac23=1$, and $1=1$, so these are valid transition probabilities.

From state 1, the one-step probability of reaching state 3 is $p_{13}=0$. In two steps, the only positive-probability path from 1 to 3 is $1\to2\to3$, with probability $$ p_{12}p_{23}=\tfrac12\cdot\tfrac23=\tfrac13. $$ Therefore $p_{13}^{(2)}=\tfrac13>0$. For a fuller check, the entire first row of $P^2$ is $\tfrac12$ times row 1 of $P$ plus $\tfrac12$ times row 2 of $P$: $$ \left(\tfrac14,\tfrac14+\tfrac16,\tfrac13\right) = \left(\tfrac14,\tfrac5{12},\tfrac13\right). $$ Its entries sum to $\tfrac3{12}+\tfrac5{12}+\tfrac4{12}=1$. The zero one-step entry and positive two-step entry illustrate why the length must be specified.

Worked Example: Paths of Several Exact Lengths

Take $S=\{1,2\}$ and $$ P= \begin{bmatrix} \tfrac12&\tfrac12\\ 0&1 \end{bmatrix}. $$ Both rows sum to $1$. Starting from 1, calculate the probabilities of ending at 1 and 2 after exactly three steps by listing the paths.

To end at 1 after three steps, all three transitions must be $1\to1$. This path has probability $\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18$. To end at 2, the chain must first move from 1 to 2 at one of the three steps. The three possible paths are $1\to2\to2\to2$, $1\to1\to2\to2$, and $1\to1\to1\to2$. Their probabilities are respectively $\tfrac12$, $\tfrac14$, and $\tfrac18$. Hence $$ p_{12}^{(3)}=\tfrac12+\tfrac14+\tfrac18=\tfrac78. $$ The resulting first row of $P^3$ is $(\tfrac18,\tfrac78)$, whose entries sum to $1$.

There is also a length-zero path from 1 to 1, but none from 1 to 2. At length three, both destinations have positive probabilities. This example shows that the meaning of a positive entry depends on the exponent: it certifies a path with that exact length, not just an unspecified connection.

Using the Path Interpretation

For a fixed $n$, the test is direct: inspect $P^n$, or enumerate paths of length $n$, and ask whether the relevant entry is strictly positive. A zero entry means there is no sequence of $n$ transitions whose individual probabilities are all positive. A positive entry means at least one such sequence exists. If several paths are possible, their probabilities add; the entry is not generally the probability of any one particular path.

To ask whether $j$ can be reached from $i$ in some number of steps, look for a positive entry $p_{ij}^{(n)}$ for at least one $n\ge0$. This statement is about existence across lengths, whereas the corollary gives the exact-length test for each individual $n$. A self-transition $p_{ii}>0$, for example, can extend a path by one step at a time. Without such a transition, an existing path need not automatically yield paths of every longer length.

The path formula also gives a useful way to read calculations. Each summand in a matrix-power entry corresponds to one intermediate-state sequence. A term vanishes if any factor in its product is zero; only sequences using positive-probability transitions contribute. For a finite state space there are finitely many sequences of a fixed length, while for a countable state space there may be countably many. In either case, nonnegativity ensures that a positive sum has at least one positive contributing term.

A Common Calculation Pitfall

When expanding a matrix product, a frequent error is to assign a contribution to an endpoint without checking the last transition in the proposed path. In the four-state example, the first entry of row 1 of $P^2$ is sometimes mistakenly reported as $\tfrac3{16}$. That value is actually the probability of ending at state 2: it comes from $1\to1\to2$, with probability $\tfrac14\cdot\tfrac34=\tfrac3{16}$.

For the first entry, the only candidate intermediate states are 1 and 2. The two contributions are $p_{11}p_{11}=\tfrac1{16}$ and $p_{12}p_{21}=\tfrac34\cdot0=0$. Thus $p_{11}^{(2)}=\tfrac1{16}$, not $\tfrac3{16}$. Replacing the correct first entry by $\tfrac3{16}$ would produce a row sum of $\tfrac9{48}+\tfrac9{48}+\tfrac7{48}+\tfrac{29}{48}=\tfrac{54}{48}=\tfrac98$, contradicting the fact that a row of a transition-matrix power sums to $1$. The correction restores the row sum: $\tfrac3{48}+\tfrac9{48}+\tfrac7{48}+\tfrac{29}{48}=1$.

A reliable procedure is to fix the initial and final states, list each possible intermediate sequence, multiply the transition probabilities along that sequence, and then add the contributions. Finally, check that the entries in the computed row sum to $1$. The row-sum check can expose an arithmetic error, while the path list identifies which entry or transition caused it.

Check Your Understanding

For each question, pay attention to whether the requested path length is exact. When a transition matrix is given, first verify its row sums.

If $p_{ij}^{(4)}>0$, what can be concluded about paths from $i$ to $j$, and what cannot be concluded about length 5?
Suppose a length-three path from $i$ to $j$ uses transitions with probabilities $\tfrac12$, $0$, and $\tfrac34$. Does it contribute a positive term to $p_{ij}^{(3)}$? Explain.
For $P=\begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix}$, list the paths of length two from state 1 to state 2 and compute $p_{12}^{(2)}$.
Why does a positive countable sum of nonnegative path probabilities guarantee at least one path with positive probability?
What does $p_{ii}^{(0)}=1$ represent under the length-zero path convention?

Reading Positive Powers as Paths

What You'll Learn