# How is the Chapman-Kolmogorov Equation not a fancy name for matrix multiplication?

The Chapman-Kolmogorov Equation:
$$p^{m+n}(i,j)=\sum_kp^m(i,k)p^n(k,j)$$

Matrix Multiplication (with $[A]_{i,j}=a_{i,j}$ where $A$ is a linear map "" for B) $$[AB]_{i,j}=\sum_ka_{i,k}b_{k,j}$$

In this $p(i,j)$ denotes the transition probability from $i$ to $j$, $p$ is the matrix of these. So really is is just saying $A^{m+n}=A^mA^n$ surely.

I will be asked to prove these on exams (it is on every past paper) and I want to do it this way, but I've checked MANY sources and searched through many lectures notes from all corners of the globe, they all do it the conditional probability way - which I don't mind, but it is just matrix multiplication, with induction right? (I'm not sure how I'd do induction over this case, but it is still countable, so induction ought to work!) Please help me create a proof using matrix multiplication, or at least explain why it isn't a proof (or why it is avoided)

## 1 Answer

Just hit me!

We don't actually know matrix multiplication works, that's what the Chapman-Kolmogorov equation actually tells us.

So before it, we can write them as a matrix purely because it's a table, but we don't know multiplying makes sense, the equation proved without matrix multiplication that ends up being the definition of matrix multiplication is the point of the proof.

The notation is misleading, $p^m$ just means m transitions, the function p applied m times, we don't look at it as a linear map, we look at it as a table of probabilities, the equation lets us use matrices!

• So, how does this proof look like? :-) Dec 21, 2014 at 12:25
• @AnnevanRossum like how you'd fine if you put "Proof of the Chapman-Kolmogorov equation" into any search engine :) Dec 21, 2014 at 21:31