|
|
hbghlyj
Posted at 2023-8-5 20:07:04
Markov chains - Topics in Probability
Let $\mathbf{P}$ be the transition probability transition matrix for an absorbing Markov chain. Suppose that $\mathbf{P}$ is stated as follows\[\mathbf{P}=\left[\begin{array}c Q & R \\ \mathbf{0} & I \\ \end{array}\right]\]
such that $Q$ is the submatrix of $\mathbf{P}$ that consists of the one-step transition probabilities between transient states and $R$ is the submatrix of $\mathbf{P}$ that consists of the one-step transition probabilities from transient states into absorbing states. The fundamental matrix is $W=(I-Q)^{-1}$, which is the inverse of the matrix $I-Q$ where $I$ is the identity matrix of the same size as $Q$.
We sketch an answer to two questions.
- Why each entry $W_{ij}$ in the fundamental matrix $W$ is the mean time the process spent in state $j$ given that the process starts in state $i$?
- Why the matrix $W \times R$ gives the probabilities of absorption?
Note that the entries in $Q^n$, the $n$th power of the matrix $Q$, approach zero as $n$ becomes large. This is because $Q$ contains the one-step transition probabilities of the transient states (once in a transient state, the process has to leave the transient states at some point). We have the following equality.
\[W=I+Q+Q^2+Q^3+\cdots+Q^n+\cdots \tag3\]
To see the equality (3), fix transient states $i$ and $j$ with $i \ne j$. We show the following:
\[\tag4W_{ii}=1+P_{ii}+P_{ii}^2+P_{ii}^3+\cdots+P_{ii}^n+\cdots\]
\[\tag5W_{ij}=P_{ij}+P_{ij}^2+P_{ij}^3+\cdots+P_{ij}^n+\cdots\]
Suppose the process starts at state $i$. Define the indicator variables $Y_n$ and $Z_n$ for $n \ge 1$. At time $n$, if the process is in state $i$, let $Y_n=1$. Otherwise $Y_n=0$. Likewise, at time $n$, if the process is in state $j$, let $Z_n=1$. Otherwise $Z_n=0$. By definition,\[1+Y_1+Y_2+Y_3+\cdots+Y_n+\cdots\]\[Z_1+Z_2+Z_3+\cdots+Z_n+\cdots\]are the times spent in state $i$ and in state $j$, respectively. The 1 in the first random time accounts for the fact that the process is already in state $i$ initially. Because we are dealing with transient states, only a finite number of $Y_n$ and $Z_n$ can be 1’s. So these two random time variables are well defined. Each $Y_n$ is a Bernoulli random variable with $P[Y_n=1]=P_{ii}^n$. Likewise each $Z_n$ is a Bernoulli random variable with $P[Z_n=1]=P_{ij}^n$. The following gives (4) and (5).\begin{aligned} W_{ii}&=1+E[Y_1]+E[Y_2]+\cdots+E[Y_n]+\cdots \\&=1+P_{ii}+P_{ii}^2+\cdots+P_{ii}^n+\cdots \end{aligned}\begin{aligned} W_{ij}&=E[Z_1]+E[Z_2]+\cdots+E[Z_n]+\cdots \\&=P_{ij}+P_{ij}^2+\cdots+P_{ij}^n+\cdots \end{aligned}Expressing equalities (4) and (5) in matrix form gives the equality (3). The following derivation shows that $W=(I-Q)^{-1}$.
\begin{aligned} W&=I+Q+Q^2+Q^3+\cdots+Q^n+\cdots \\&=I+Q (I+Q+Q^2+Q^3+\cdots+Q^n+\cdots) \\& = I+ Q W\end{aligned}\[W-Q W=I\]\[W (I-Q)=I\]Thus the mean times spent in the transient states are obtained by taking the inverse of the matrix $I-Q$. Based on the derivation, the sum $I+Q+Q^2+Q^3+\cdots+Q^n$ for a sufficiently large $n$ would give a good approximation of the waiting time matrix $W$. Of course, computationally speaking, it is much easier to compute the inverse matrix of $I-Q$. |
|
