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 \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$.
MC-diagram
Figure 11.7 - A state transition diagram.


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*}
      4. We can write \begin{align*} &P(X_0=1,X_1=2,X_2=3) \\ &\quad=P(X_0=1) P(X_1=2|X_0=1) P(X_2=3|X_1=2, X_0=1)\\ &\quad=P(X_0=1) P(X_1=2|X_0=1)P(X_2=3|X_1=2) \quad (\textrm{by Markov property}) \\ &\quad=\frac{1}{3} \cdot\ p_{12} \cdot p_{23} \\ &\quad=\frac{1}{3} \cdot \frac{1}{2} \cdot \frac{2}{3}\\ &\quad= \frac{1}{9}. \end{align*}




The print version of the book is available on Amazon.

Book Cover


Practical uncertainty: Useful Ideas in Decision-Making, Risk, Randomness, & AI

ractical Uncertaintly Cover