# Mathematics Prelims

## December 20, 2008

### The Chapman-Kolmogorov Equations

Filed under: Probability Theory,Stochastics — cjohnson @ 12:46 pm

Supposing we’re given each $P_{ij}$ for a Markov chain, we have all of the one-step transition probabilities.  Calculating the $n$-step transition probabilities, we arrive at the Chapman-Kolmogorov equations.  We will let $P_{ij}^(n)$ denote the probability that we arrive at state $j$ after $n$ transitions, given that we start in $i$:

$\displaystyle P_{ij}^(n) = P(X_n = j | X_0 = i)$

We begin by considering $n = 2$.  If $X_0 = i$, we find the chance of $X_2 = j$ by considering all the paths that start at $i$ and end at $j$; that is, we look at all posibilities of $X_1$.  Since we have each $P_{ik}$, we just look at the chance we first transition to state $k$, then from $k$ transition to $j$.  This gives

$\displaystyle P_{ij}^(2) = \sum_k P(X_2 = j \cap X_1 = k | X_0 = i)$

$\displaystyle \, \, = \sum_k P(X_2 = j| X_1 = k) P(X_1 = k | X_0 = i)$

$\displaystyle \, \, = \sum_k P(X_1 = j | X_0 = k) P(X_1 = k | X_0 = i)$

$\displaystyle \, \, = \sum_k P_{kj} P_{ik}$

$\displaystyle \, \, = \sum_k P_{ik} P_{kj}$

Note this gives the two-step transition probabilities form the matrix $P^2$.  We can extend this result inductively, then we have that the $n$-step transition probability matrix is simply $P^n$.

Continuing with the weather example from last time, we have that the two-step probability transition matrix is

$\displaystyle \left[ \begin{array}{ccc} 1/2 & 1/4 & 1/4 \\ 1/8 & 1/2 & 3/8 \\ 1/4 & 0 & 3/4 \end{array} \right]^2 = \left[ \begin{array}{ccc} 11/32 & 1/4 & 13/32 \\ 7/32 & 9/32 & 1/2 \\ 5/16 & 1/16 & 5/8 \end{array}\right]$

And so, according to our model, if it’s rainy today, there is an 11/32 chance it will be rainy two days from now, 1/4 chance it snows two days from now, and 13/32 chance it’s sunny.