Meaning of n-Step Transition Probabilities

From One Step to a Fixed Future Time

A one-step transition probability describes the next move. Many questions instead concern where a chain will be after several moves: what is the probability that tomorrow’s weather is sunny, given today’s state, or that a particle is in a particular location after four updates? The n-step transition probability answers this fixed-horizon question. Its meaning is simple, but keeping the time horizon precise prevents confusion with one-step probabilities and with the probability of having visited a state at any earlier time.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), and let \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) be its natural filtration. The chain is time-homogeneous when its one-step transition probabilities do not depend on \(n\): for every \(i,j\in S\), \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{ij}\) almost surely on \(\{X_n=i\}\). Write \(P=(p_{ij})\) for its transition matrix, with rows indexed by the current state and columns by the next state. Each row sums to \(1\).

The defining event is \(X_n=j\), not “the chain moves from \(i\) to \(j\) in one step.” Thus \(p_{ij}^{(1)}=p_{ij}\), while \(p_{ij}^{(n)}\) for \(n>1\) concerns the state at a later time. The chain may visit \(j\) before time \(n\), leave it, and end in a different state; an n-step probability does not record those visits.

Proof. Fix \(i\) and \(n\). The events \(\{X_n=j\}\), as \(j\) ranges over the finite state space \(S\), are disjoint and their union is the whole sample space under \(\mathbb{P}_i\), since \(X_n\) takes exactly one value in \(S\). Their probabilities are nonnegative and sum to \(1\). At time \(0\), a chain started in \(i\) is in \(i\) with probability \(1\), and in every \(j\ne i\) with probability \(0\), giving the identity matrix. At time \(1\), the probabilities are the one-step transition probabilities \(p_{ij}\), giving \(P^{(1)}=P\). \(\square\)

Consequently, every matrix of n-step probabilities is row-stochastic: it has nonnegative entries and each row sums to \(1\). In examples, we can calculate \(P^n\) by ordinary matrix multiplication and interpret its entries as n-step probabilities using the standard identity stated above. We will check each matrix row and the resulting probabilities directly.

Reading the Entries of a Matrix Power

Exact-Time Probabilities and Hitting Probabilities

For a set \(A\subseteq S\), the hitting time is \(T_A=\inf\{n\ge0:X_n\in A\}\), with \(\inf\varnothing=\infty\). The event \(T_A\le n\) means the chain has visited \(A\) at least once by time \(n\). By contrast, \(X_n\in A\) asks only whether it is in \(A\) at time \(n\). The events need not be equal: a chain can visit \(A\) and then leave.

Proof. If \(X_n\in A\), then the chain has been in \(A\) at some time no later than \(n\), namely at time \(n\). Hence \(\{X_n\in A\}\subseteq\{T_A\le n\}\). Taking probabilities of the two events gives the inequality. The inclusion can be strict if the chain visits \(A\) by time \(n\) but is outside \(A\) at time \(n\). \(\square\)

For example, return to the weather chain and start from \(C\), with \(A=\{H\}\) and \(n=2\). The exact-time probability is \(p_{C,H}^{(2)}=\tfrac{17}{36}\). The probability of having hit \(H\) by time \(2\) is larger: the chain can go from \(C\) to \(H\) on the first step, with probability \(\tfrac13\), or stay at \(C\) first and then move to \(H\), with probability \(\tfrac23\cdot\tfrac13=\tfrac29\). These disjoint possibilities give \(\tfrac13+\tfrac29=\tfrac59=\tfrac{20}{36}\), which exceeds \(\tfrac{17}{36}\). The difference \(\tfrac{3}{36}\) is the probability of having reached \(H\) by time \(2\) but ending at \(C\) at time \(2\).

A Common Misreading

Pitfall: squaring a one-step entry. In the weather example, an incorrect calculation for the probability of being hot after two days starting hot is \((\tfrac34)^2=\tfrac{9}{16}\). This counts only the route that is hot after the first day and hot again after the second. It omits the possibility of being cool after the first day and hot after the second. The matrix-power calculation gives \(\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac13=\tfrac{27}{48}+\tfrac{4}{48}=\tfrac{31}{48}\). Substituting into the two-step row gives \(\tfrac{31}{48}+\tfrac{17}{48}=1\), whereas the incorrect entry \(\tfrac{9}{16}\) alone is not the two-step probability.

When reading \(p_{ij}^{(n)}\), identify the starting state \(i\), the destination \(j\), and the exact time \(n\). Then check that the row of the n-step matrix gives probabilities over all possible destination states and sums to \(1\). If the question instead asks whether the chain has visited a state or set by time \(n\), it is a hitting-probability question, not merely an entry of \(P^{(n)}\).