Conditional Markov Chain I am interested in a method of how to compute the expected number of steps for absorpion in a Markov Chain with only one absorption node and given the starting and pre-final node (before absorption).
So, if the transition probability matrix is given, for example by:
$P = \begin{bmatrix}
0 & 1/5 & 2/5 & 1/5 & 1/5\\
1/5 & 0 & 1/5 & 1/5 & 2/5\\
2/5 & 0 & 1/5 & 1/5 & 1/5\\
1/5 & 1/5 & 0 & 1/5 & 2/5\\
0 & 0 & 0 &0 & 1
\end{bmatrix}$
what will be the expected number of steps for being absorbed given that we start in node 1 (first line) and the last state before absorption is node 2 (second line) ?
So what I tried so far... I know the very known technique of using the fundamental matrix $N$ and then computing $N = (I-Q)^{-1}$ where $Q$ is the recurrent probabilities matrix (from the canonical form of $P$) and the expected number of steps would be the first entry of the vector $(I-Q)^{-1}1$, where $1$ is the five dimensional vector with all entries equal to $1$, in the case where we dont know the information about where we are absorbed.
Then, as we know that we are absorbed from node two, I tried to replace all the probabilties of the last columns by $0$ (execept for line $2$ and for the aborption node that I kept $2/5$ and $1$, respectively), then I am not pretty sure of how re-normalizing all the others...
Thank you very much!
 A: Let $S := \{1,2,3,4,5\}$ be the state space of this homogeneous Markov chain (MC) and $\xi_n$ be the random state at time $n \in \mathbb{N}_0$. Let $\mathbb{P}_s$ be the joint distribution of $\xi_0,\xi_1,\ldots$ if the MC start in $s \in S$,  $(\Omega,\mathcal{A},\mathbb{P}_s)$ be the underlying probability space and $\tau$ be the entrance time in $s_a = 5$. Let $A := \{\xi_{\tau-1} = 2\}$ be the event that immediately before stopping the state is $2$ (with $\xi_{-1} := 5$). Of interest are $$\mathbb{E}_s[\tau ~|~ A] = \frac{g(s)}{f(s)}$$
with $f_s = \mathbb{P}_s(A)$ and $g(s) = \mathbb{E}_s Y$ with $Y = \tau \cdot 1_A$ ($1_A$ the indicator function of $A$) for $s \not= s_a$.
Let $P = (p_{si})_{s,i \in S}$ be the transition matrix of the MC. By the Markov property (here we don't need the strong Markov property) we get
$$\mathbb{P}_s(A) = 2/5 \cdot \delta_{s2} + \sum_{i=1}^5 p_{si} \cdot \mathbb{P}_i(A)$$
resp. $f = Pf + (0,2/5,0,0,0)'$. Since $f(5) = 0$ we can omit the state $s = 5$ and with $\tilde P := (p_{si})_{s,i \not= 5}$ we have to solve the equation
$$(\mathbb{1} - \tilde P) \tilde f = (0, 2/5, 0, 0)'$$. We get
$$\tilde f = (0.1897, 0.5, 0.1379, 0.1724)'$$
Similarly for $g$ we get
$$\mathbb{E}_s Y = \sum_{i \in S} p_{si} \mathbb{E}_i [Y ~|~ \xi_1 = i, \xi_0 = s]$$
with $\mathbb{E}_i [Y ~|~ xi_1 = i, \xi_0 = s] = 1$, if $s = 2, i = 5$, $ = 0$, if $s \not=2, i = 5$ or $s = 5$ and $= g_i+1$, else. Thus
$$g_s = (\tilde P (g+1))_s + 2/5 \cdot \delta_{s2}$$
resp. with $x = (g_1,\ldots,g_4)'$
$$x = \tilde P (x+1) + (0,2/5,0,0)' = \tilde P x + \tilde P (1,1,1,1)' + (0,2/5,0,0)'$$
with the solution $x = (2.9612, 2.6250, 3.0172, 2.1466)'$. In particular we get the solution $x(1)/f(1) = 15.6136$.
A: I'm slightly correcting my comments, and turning it into an answer. Let $P$ be the Markov chain you're interested in. Write $j_i$ for the initial state, $j_f$ for the last state before absorption, and $j_a$ for the absorption state. Write $P'$ for the sub-Markov chain consisting of all states except $j_a$. If $i$ and $j$ are states in a Markov chain, write $\mu(i,j)$ for the expected amount of steps needed to reach $j$ given that you start at $i$.
To find the expected amount of time to reach absorption given that you're in state $j_f$ right before that, what you'll want to do is make a summation over the amount of times that you've passed through $j_f$ before landing in $j_a$. With probability $P_{j_f,j_a}$, you'll need to pass through $j_f$ only once. With probability $(1 - P_{j_f,j_a}) P_{j_f,j_a}$, you'll need to pass through $j_f$ twice. And so on. Given that you pass through $j_f$ precisely $n+1$ times, the expected amount of time that you'll need to reach $j_a$ is
$$\mu(j_i,j_f) + n \cdot\mu(j_f,j_f) + 1,$$
where $\mu$ is computed in $P'$ (not in $P$; this is because we assume that on our path from $j_f$ back to itself, we don't get absorbed along the way). Now it's a matter of appropriate summation. Modulo errors I think the answer will be
$$E(T) = \sum_{n = 0}^\infty P_{j_f,j_a} (1 - P_{j_f,j_a})^{n} \big(\mu(j_i,j_f) + n \cdot \mu(j_f,j_f) + 1\big)$$
which can be simplified to
$$E(T) = \mu(j_i,j_f) + 1 + \sum_{n = 0}^\infty n P_{j_f,j_a} (1-P_{j_f,j_a})^{n} \mu(j_f,j_f),$$
and yet further to
$$E(T) = \mu(j_i,j_f) + \frac{1-P_{j_f,j_a} }{P_{j_f,j_a}}\mu(j_f,j_f) + 1.$$
Here's an approach for finding $\mu$. In a general Markov chain $Q$, the expected amount of time needed to pass from state $i$ to state $j$ satisfies the recurrence relation
$$\mu(i,j) = 1 + \sum_{k \neq j} Q_{i,k} \mu(k,j),$$
where the sum is taken over all states $k$ not equal to $j$. This formula should be enough to find $\mu(j_i,j_f)$ and $\mu(j_f,j_f)$ in $P'$ numerically.
