Calculate the average number of times transition states are visited given known absorption state

Question

Given a transition matrix like the one below I am trying to find out how many states it passes through given that we reach state 4 in the end. State 4 and Out are my two absorption states. Taking the upper left side as matrix Q and finding the inverse of I-Q I know I can calculate the average number of times visiting each state. However I am interested in knowing how many times I would visit each state on average given I get to stage 4. I know I can calculate it using probabilities but I was hoping to use the above method using matrix algebra. Seeing another example suggested removing the OUT column and row and rescaling the probabilities so they still sum to 1 and then applying the same method but I don't seem to be getting the correct answer.Can anyone see where I am likely to be going wrong or explain why the above method wouldn't work?

$$ \begin{matrix} 0 & .3 & .6 & 0 & 0 & .1 \\ 0 & 0 & .5 & .3 & 0 & .2 \\ 0 & 0 & 0 & 0 & .7 & .3 \\ 0 & 0 & 0 & 0 & .2 & .8 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{matrix} $$

The starting state is always 0. This is what I have done so far. There are three paths we can take that end in state 4 namely 0-1-2-4 , 0-1-3-4, 0-2-4. I am really interested in how many states we pass through before we get to before state 4. Taking the probability of getting to 4 through each route and multiply by the number of states we passed through, I then add together the probabilities of getting to 4 and divide by it. So I get 1.209 / 0.543 = 2.2265…

When calculating it in the matrix form I first remove the OUT column and row leaving the matrix below taking the steps I get the following resulting matrix, adding together the expected number of visits to each state I get an average of 2.3333…

Q = $$ \begin{matrix} 0 & 1/3 & 2/3 & 0 \\ 0 & 0 & 5/8 & 3/8 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{matrix} $$

Inverse (I-Q) = Q = $$ \begin{matrix} 1 & 1/3 & 7/8 & 1/8 \\ 0 & 1 & 5/8 & 3/8 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix} $$

Summing the first row I get 2.333... where have I gone wrong?

Answer 1

What you basically want to do is to find a pruned chain that describes the dynamics of the process conditioned on absorbing into what you called 4 rather than what you called state OUT, which I'll call state 5 instead. This cannot be done by any local modification, because there are cross-correlation effects going on. That is, when you condition on absorption into 4, individual steps of paths leading into states that ultimately absorb into 4 become more likely, even when state 4 can't actually be reached from the state in question.

In this scenario for example, starting from state 0, visiting state 2 becomes more likely than it would be otherwise, while visiting state 3 becomes less likely than it would be otherwise, because of the differing probabilities to ultimately absorb into state 4. The situation is more transparent when a state is guaranteed to go to 5, then regardless of how likely it is to go to that state in one step, you will not go to that state when you condition on going to state 4.

The correct way to prune the chain is to find the so-called committor. I'll label its values by $q_0,q_1,q_2,q_3$. These are the four nontrivial probabilities to ultimately absorb into state 4 started from each state. They satisfy the equations $q_i=p_{i,4} + \sum_{j \neq 4,5} p_{i,j} q_j$, as you can see by conditioning on one step and using the Markov property. One can also view the system as $q_i=\sum_j p_{i,j} q_j$ for $i \neq 4,5,q_4=1,q_5=0$.

The correctly pruned chain now has $\tilde{p}_{i,j}=\frac{p_{i,j} q_j}{\sum_k p_{i,k} q_k}$ for $i,j=0,1,2,3$ (i.e. the probabilities to go to $j$ are weighted by $q_j$ and then renormalized). Using this pruned chain, you could then solve your problem by computing $(I-\tilde{P})^{-1}$. Note that in this problem it is easy to calculate the committor because of the triangular structure: you have $q_3=0.2,q_2=0.7,q_1=0.5 \cdot q_2 + 0.3 \cdot q_3=0.41$ and $q_0=0.3 \cdot q_1 + 0.6 \cdot q_2 = 0.543$ (though this last number is never actually used in the calculation since all the $p_{i,0}$'s are zero). So for example $\tilde{p}_{0,1}=0.123,\tilde{p}_{0,2}=0.877$.