I have tried to derive a generalized answer to this question, but don't know how to check my work. To clarify, I am asking for the probability of being in each transient state of an absorbent Markov chain after an unknown, finite amount of time has passed, given that you are not in an absorbing state.
I'll start with an example to show my approach.
Start with a Markov chain with N states, where the $n^{th}$ state is absorbing ($p_{nn} = 1, p_{ni} = 0$ $\forall$ $i \not= n$). We will call the transition matrix for this Markov chain P, where each element $p_{ij}$ is the probability of transitioning from state i to state j. We want to know the probability of being in each state i given that we are not in state n after some finite, unknown amount of time has passed. Note that we are not solving for the steady state distribution, which gives you the probabilities of being in each state after an infinite amount of time has passed.
My approach from here was to construct a new transition matrix $Q$, which contains the probability of transitioning between all the transient states of this MC. To do so, we remove the $n^{th}$ row and column from $P$ to create a new matrix, say, $P(A)$. Now, we must rescale the values of $P(A)$ such that the row elements all add up to 1 for all rows. One way to do so is:
- take the dot product of $P(A)$ and a vector of ones with N-1 dimensions, and call the resulting N-1 vector $\vec S$
- diagonalize this vector into a matrix called D, so that $D_{ii} = S_i$ and $D_{ij} = 0$ $ \forall i \not = j$.
- Now, $Q = D^{-1}P(A)$
If I am not mistaken, the elements of $Q$, called $q_{ij}$, should represent the probability of transitioning from state i to state j, given that i does not transition to state n (the absorbing state). I (quite possibly mistakenly) believe that the steady state vector of Q gives the answer to my original question. Can anyone provide any insight here? I am struggling to find any resources that I can use to confirm my approach.
Best Answer
Your approach will not work.
Suppose we have the following $3$-state Markov chain. States $1$ transitions to itself with probability $0.99$, and to state $2$ with probability $0.01$. State $2$ always goes to state $3$, and state $3$ is absorbing. We start in state $1$.
Then at any time $t>0$, the probability of being in state $2$, given that you're not in state $3$, is $0.01$ exactly. Being told that you're not in state $3$ tells us that we stayed put in state $1$ for the first $t-2$ transitions, and in particular that we were in state $1$ at time $t-1$ (if we went to state $2$ earlier, we'd be in state $3$ by now). Then we have a $0.99$ chance of being in state $1$ at time $t$, and a $0.01$ chance of being in state $2$.
On the other hand, the approach of deleting state $n$ (state $3$ in this case) and rescaling will make state $2$ absorbing, which means the probability of ending up in state $2$ will only grow.
Instead, to solve the problem for a known time $t$, compute the row vector $\vec w = \vec v P^t$, where $\vec v$ is the row vector of the initial probabilities. In other words, find the probability vector at time $t$. Then, set $w_n$ to $0$ and rescale the rest of $\vec w$ to add up to $1$. That's what conditioning on an event is.
You cannot solve this problem for a totally unknown time $t$. Even if you can't say what $t$ is for certain, you should have a probability distribution on $t$; in this case, compute the expected value $\vec w = \mathbb E[\vec v P^t]$, and use that instead.