## 11.2.2 State Transition Matrix and Diagram

We often list the transition probabilities in a matrix. The matrix is called the state transition matrix or transition probability matrix and is usually shown by $P$. Assuming the states are $1$, $2$, $\cdots$, $r$, then the state transition matrix is given by $$\nonumber P = \begin{bmatrix} p_{11} & p_{12} & ... & p_{1r} \\%[5pt] p_{21} & p_{22} & ... & p_{2r} \\%[5pt] . & . & . & .\\[-10pt] . & . & . & . \\[-10pt] . & . & . & . \\[5pt] p_{r1} & p_{r2} & ... & p_{rr} \end{bmatrix}.$$ Note that $p_{ij} \geq 0$, and for all $i$, we have \begin{align*} \sum_{k=1}^{r} p_{ik}&=\sum_{k=1}^{r} P(X_{m+1}=k |X_{m}=i)\\ &=1. \end{align*} This is because, given that we are in state $i$, the next state must be one of the possible states. Thus, when we sum over all the possible values of $k$, we should get one. That is, the rows of any state transition matrix must sum to one.

### State Transition Diagram:

A Markov chain is usually shown by a state transition diagram. Consider a Markov chain with three possible states $1$, $2$, and $3$ and the following transition probabilities $$\nonumber P = \begin{bmatrix} \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\[5pt] \frac{1}{3} & 0 & \frac{2}{3} \\[5pt] \frac{1}{2} & 0 & \frac{1}{2} \end{bmatrix}.$$ Figure 11.7 shows the state transition diagram for the above Markov chain. In this diagram, there are three possible states $1$, $2$, and $3$, and the arrows from each state to other states show the transition probabilities $p_{ij}$. When there is no arrow from state $i$ to state $j$, it means that $p_{ij}=0$.

Example
Consider the Markov chain shown in Figure 11.7.
1. Find $P(X_4=3|X_3=2)$.
2. Find $P(X_3=1|X_2=1)$.
3. If we know $P(X_0=1)=\frac{1}{3}$, find $P(X_0=1,X_1=2)$.
4. If we know $P(X_0=1)=\frac{1}{3}$, find $P(X_0=1,X_1=2,X_2=3)$.
• Solution
1. By definition $$P(X_4=3|X_3=2)=p_{23}=\frac{2}{3}.$$
2. By definition $$P(X_3=1|X_2=1)=p_{11}=\frac{1}{4}.$$
3. We can write \begin{align*} P(X_0=1,X_1=2) &=P(X_0=1) P(X_1=2|X_0=1)\\ &= \frac{1}{3} \cdot\ p_{12} \\ &=\frac{1}{3} \cdot \frac{1}{2}= \frac{1}{6}. \end{align*}