Definition

For a discrete-time Markov chain, the $(n+m)$-step transition probability satisfies

$$ p_{ij}^{(n+m)}=\sum_{k\in S} p_{ik}^{(n)}p_{kj}^{(m)}. $$

Key identity

In matrix form,

$$ P^{n+m}=P^nP^m. $$
  • Interpretation: The probability of moving from $i$ to $j$ in $n+m$ steps is obtained by summing over all intermediate states $k$ reached after $n$ steps.
  • Linear Algebra Equivalence: The $n$-step transition matrix satisfies
$$ P^{(n)} = P^n. $$

Consequence

A path from $i$ to $j$ in $n+m$ steps can be decomposed through an intermediate state $k$: first $n$ steps from $i$ to $k$, then $m$ steps from $k$ to $j$, and summing over all possible $k$ gives the total probability.