---

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 \begin{equation} \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}. \end{equation} 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 \begin{equation} \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}. \end{equation} 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)$.

---