11.2.5 Using the Law of Total Probability with Recursion
Example
For the Markov chain given in Figure 11.12, answer the following questions: How many classes are there? For each class, mention if it is recurrent or transient.
- Solution
-
There are three classes: Class $1$ consists of one state, state $0$, which is a recurrent state. Class two consists of two states, states $1$ and $2$, both of which are transient. Finally, class three consists of one state, state $3$, which is a recurrent state.
Note that states $0$ and $3$ have the following property: once you enter those states, you never leave them. For this reason, we call them absorbing states. For our example here, there are two absorbing states. The process will eventually get absorbed in one of them. The first question that we would like to address deals with finding absorption probabilities.
-
Absorption Probabilities:
Consider the Markov chain in Figure 11.12. Let's define $a_i$ as the absorption probability in state $0$ if we start from state $i$. More specifically, \begin{align*} a_0&=P(\textrm{absorption in }0 | X_0=0), \\ a_1&=P(\textrm{absorption in }0 | X_0=1), \\ a_2&=P(\textrm{absorption in }0 | X_0=2), \\ a_3&=P(\textrm{absorption in }0 | X_0=3). \end{align*} By the above definition, we have $a_0=1$ and $a_3=0$. To find the values of $a_1$ and $a_2$, we apply the law of total probability with recursion. The main idea is the following: if $X_n=i$, then the next state will be $X_{n+1}=k$ with probability $p_{ik}$. Thus, we can write \begin{align} a_i &=\sum_{k} a_k p_{ik}, \quad \textrm{ for }i=0,1,2,3 \hspace{30pt} (11.6) \end{align} Solving the above equations will give us the values of $a_1$ and $a_2$. More specifically, using Equation 11.6, we obtain \begin{align*} a_0 &=a_0, \\ a_1 &=\frac{1}{3} a_0+ \frac{2}{3}a_2, \\ a_2 &=\frac{1}{2} a_1+ \frac{1}{2}a_3, \\ a_3 &=a_3. \end{align*} We also know $a_0=1$ and $a_3=0$. Solving for $a_1$ and $a_2$, we obtain \begin{align*} a_1 &=\frac{1}{2}, \\ a_2 &=\frac{1}{4}. \\ \end{align*} Let's now define $b_i$ as the absorption probability in state $3$ if we start from state $i$. Since $a_i+b_i=1$, we conclude \begin{align*} b_0=0, \quad b_1=\frac{1}{2}, \quad b_2= \frac{3}{4}, \quad b_3=1. \end{align*} Nevertheless, for practice, let's find the $b_i$'s directly.Example
Consider the Markov chain in Figure 11.12. Let's define $b_i$ as the absorption probability in state $3$ if we start from state $i$. Use the above procedure to obtain $b_i$ for $i=0,1,2,3$.
- Solution
- From the definition of $b_i$ and the Markov chain graph, we have $b_0=0$ and $b_3=1$. Writing Equation 11.6 for $i=1, 2$, we obtain \begin{align*} b_1 &=\frac{1}{3} b_0+ \frac{2}{3}b_2 \\ &=\frac{2}{3}b_2,\\ b_2 &=\frac{1}{2} b_1+ \frac{1}{2}b_3\\ &=\frac{1}{2} b_1+ \frac{1}{2}. \end{align*} Solving the above equations, we obtain \begin{align*} b_1 &=\frac{1}{2}, \\ b_2 &=\frac{3}{4}. \\ \end{align*}
Consider a finite Markov chain $\{X_n, n=0,1,2,\cdots\}$ with state space $S=\{0,1,2,\cdots, r\}$. Suppose that all states are either absorbing or transient. Let $l\in S$ be an absorbing state. Define \begin{align*} a_i&=P(\textrm{absorption in }l | X_0=i), \quad \textrm{ for all }i \in S. \end{align*} By the above definition, we have $a_l=1$, and $a_j=0$ if $j$ is any other absorbing state. To find the unknown values of $a_i$'s, we can use the following equations \begin{align*} a_i &=\sum_{k} a_k p_{ik}, \quad \textrm{ for }i\in S. \end{align*}
In general, a finite Markov chain might have several transient as well as several recurrent classes. As $n$ increases, the chain will get absorbed in one of the recurrent classes and it will stay there forever. We can use the above procedure to find the probability that the chain will get absorbed in each of the recurrent classes. In particular, we can replace each recurrent class with one absorbing state. Then, the resulting chain consists of only transient and absorbing states. We can then follow the above procedure to find absorption probabilities. An example of this procedure is provided in the Solved Problems Section (See Problem 2 in Section 11.2.7).
Mean Hitting Times:
We now would like to study the expected time until the process hits a certain set of states for the first time. Again, consider the Markov chain in Figure 11.12. Let's define $t_i$ as the number of steps needed until the chain hits state $0$ or state $3$, given that $X_0=i$. In other words, $t_i$ is the expected time (number of steps) until the chain is absorbed in $0$ or $3$, given that $X_0=i$. By this definition, we have $t_0=t_3=0$.
To find $t_1$ and $t_2$, we use the law of total probability with recursion as before. For example, if $X_0=1$, then after one step, we have $X_1=0$ or $X_1=2$. Thus, we can write \begin{align*} t_1 &=1+\frac{1}{3} t_0+ \frac{2}{3}t_2\\ &=1+\frac{2}{3}t_2. \end{align*} Similarly, we can write \begin{align*} t_2 &=1+\frac{1}{2} t_1+ \frac{1}{2}t_3\\ &=1+\frac{1}{2} t_1. \end{align*} Solving the above equations, we obtain \begin{align*} t_1 =\frac{5}{2}, \quad t_2=\frac{9}{4}. \end{align*} Generally, let $A \subset S$ be a set of states. The above procedure can be used to find the expected time until the chain first hits one of the states in the set $A$.Consider a finite Markov chain $\{X_n, n=0,1,2,\cdots\}$ with state space $S=\{0,1,2,\cdots, r\}$. Let $A \subset S$ be a set of states. Let $T$ be the first time the chain visits a state in $A$. For all $i \in S$, define \begin{align*} t_i&=E[T |X_0=i]. \end{align*} By the above definition, we have $t_j=0$, for all $j \in A$. To find the unknown values of $t_i$'s, we can use the following equations \begin{align*} t_i &=1+\sum_{k} t_k p_{ik}, \quad \textrm{ for }i\in S-A. \end{align*}
Mean Return Times:
Another interesting random variable is the first return time. In particular, assuming the chain is in state $l$, we consider the expected time (number of steps) needed until the chain returns to state $l$. For example, consider a Markov chain for which $X_0=2$. If the chain gets the values \begin{align*} X_0=2, \; X_1=1, \; X_2=4, \; X_3=3, \; X_4=2, \; X_5=3, \; X_6=2, \; X_7=3, \; \cdots, \end{align*} then the first return to state $2$ occurs at time $n=4$. Thus, the first return time to state $2$ is equal to $4$ for this example. Here, we are interested in the expected value of the first return time. In particular, assuming $X_0=l$, let's define $r_l$ as the expected number of steps needed until the chain returns to state $l$. To make the definition more precise, let's define \begin{align*} R_l =\min \{n \geq 1: X_n=l \}. \end{align*} Then, \begin{align*} r_l=E[R_l|X_0=l]. \end{align*} Note that by definition, $R_l \geq 1$, so we conclude $r_l \geq 1$. In fact, $r_l=1$ if and only if $l$ is an absorbing state (i.e., $p_{ll}=1$). As before, we can apply the law of total probability to obtain $r_l$. Again, let's define $t_k$ as the expected time until the chain hits state $l$ for the first time, given that $X_0=k$. We have already seen how to find $t_k$'s (mean hitting times). Using the law of total probability, we can write \begin{align*} r_l=1+\sum_{k} p_{lk}t_k. \end{align*} Let's look at an example to see how we can find the mean return time.Example
Consider the Markov chain shown in Figure 11.13. Let $t_k$ be the expected number of steps until the chain hits state $1$ for the first time, given that $X_0=k$. Clearly, $t_1=0$. Also, let $r_1$ be the mean return time to state $1$.
- Find $t_2$ and $t_3$.
- Find $r_1$.
- Solution
-
- To find $t_2$ and $t_3$, we use the law of total probability with recursion as before. For example, if $X_0=2$, then after one step, we have $X_1=2$ or $X_1=3$. Thus, we can write \begin{align*} t_2 &=1+\frac{1}{3} t_2+ \frac{2}{3}t_3. \end{align*} Similarly, we can write \begin{align*} t_3 &=1+\frac{1}{2} t_1+ \frac{1}{2}t_2\\ &=1+\frac{1}{2} t_2. \end{align*} Solving the above equations, we obtain \begin{align*} t_2 =5, \quad t_3=\frac{7}{2}. \end{align*}
- To find $r_1$, we note that if $X_0=1$, then $X_1=1$ or $X_1=2$. We can write \begin{align*} r_1 &=1+\frac{1}{2} \cdot t_1 + \frac{1}{2} t_2\\ &=1+\frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 5\\ &=\frac{7}{2}. \end{align*}
-
Here, we summarize the formulas for finding the mean return times. As we mentioned before, there is no need to memorize these formulas once you understand how they are derived.
Consider a finite irreducible Markov chain $\{X_n, n=0,1,2,\cdots\}$ with state space $S=\{0,1,2,\cdots, r\}$. Let $l \in S$ be a state. Let $r_l$ be the mean return time to state $l$. Then \begin{align*} r_l &=1+\sum_{k} t_k p_{lk}, \end{align*} where $t_k$ is the expected time until the chain hits state $l$ given $X_0=k$. Specifically, \begin{align*} t_l&=0,\\ t_k&=1+\sum_{j} t_j p_{kj}, \quad \textrm{ for } k\neq l. \end{align*}
