Theorem.
The step transition probability is the th power of the transition matrix .
Proof
:O
This is a go-to application of diagonalization and linear algebra in general, and for good reason. It shows the immense utility of being able to easily raise some matrix to the th power and why representing stochastic processes as matrices is so useful. Framing a problem in terms of linear algebra allows us to use a vast array of algorithmic and numerical tools that have been proven to work mathematically.