Expected number of steps for reaching a specific absorbing state in an absorbing Markov chain

Question

For a finite Markov chain with one or more absorbing states there are well-known methods for determining either the probability of ending up in a specific absorbing state or the expected number of steps to end up in any absorbing state. However, I've not found a way to determine the expected number of steps to reach a specific state.

For instance, in the classic Drunkard's Walk, the drunkard is absorbed by both home and the bar. If I were looking at a Drunkard's Walk, what I would want to determine is how many steps it takes, on average, a drunkard who gets home to actually get home. Ideally so that the answer can be presented in a form like "There's an X% chance the drunkard will end up at home, taking on average Y steps, and a Z% chance the drunkard will end up at the bar after an average of W steps." or equivalent.

I've not yet found a good way to find the solution, I'm at a bit of a loss where to start, and if the answer exists out there I've not found the correct Google search terms to land me on it.

Thanks!

Answer 1

Once you have the probability at each point for ending up in your selected absorbing state, you can compute new transition probabilities everywhere that describe the behavior of exactly those drunkards who will eventually end up in that state.

Then compute the expected time to absorption for the new chain.

---

Alternatively, if you have one starting state you're interested in, first set up a system of equations that compute for each state the expected number of times one will encounter that state before being absorbed. With these numbers you can then find the coefficients for a system of equations that finds the "expected number of steps taken yet" for a uniformly selected drunkard who just reached each specific state.

This gives you the time-to-reach for all states at once, at the expense of only working for one starting state (or probability distribution for the starting state).

Answer 2

Purge the “bad” outcomes from the system: Let $S_+$ be the set of “good” absorbing states and $S_-$ the set of states that don’t communicate with $S_+$. Delete $S_-$ and update the remaining transition probabilites by conditioning them on not entering $S_-$ in one step: $$p_{ij} \to {p_{ij} \over 1-\sum_{k\in S_-}p_{ik}}.$$ You need to delete more than just the “bad” absorbing states because deleting the latter can create new recurrent states in which the system can get trapped, effectively replacing some of the deleted absorbing states with new ones. These dead-end branches also need to be pruned. The reduced system can then be analyzed as usual to find the conditional expected absorption times.