Given an arbitrary but relatively large (more than 50 states) transition matrix, the goal is to find the answer to the following problem:

Assuming we start at state A and ultimately end up in (the only) absorbing state Z we are looking for a state S that follows:

A → [m steps] → S → [n steps] → Z

How can I calculate the probability of reaching S before reaching Z and the corresponding expected number of steps (n) from S to Z?

Update 24-12:

So I guess the first part is mosre doable than i thought (if my reasoning is correct). My approach:

  1. Rearrange the matrix in canonical form:

    $P = \left[\begin{matrix} Q & R \\ \mathbf{0} & I \end{matrix}\right]$

  2. Find the fundamental matrix:

    $ N = (I - Q)^{-1} $

  3. Find the transient probabilities:

    $ H = (N - I)N_{dg} $

  4. And the row of H which corresponds to starting state A. The entries in this row vector should correspond to the probabilities of reaching A before reaching Z.

** Is my thinking here correct? And how can I condition the original transition matrix P to estimate the steps (n) between A and Z? **

  • $\begingroup$ To clarify, we have a starting state A, ending state Z, and want to find a state S such that, conditioned on passing through S, the expected value of the number of steps to get to S is m, the the number of steps to get to Z is n? $\endgroup$ – Alex Dec 23 '18 at 3:10
  • $\begingroup$ Yes, exactly! I just don't exactly how to approach such calculation. $\endgroup$ – Remy Kabel Dec 23 '18 at 11:00
  • $\begingroup$ My idea would be that this problem is two-fold: 1. Find the probability of reaching S before absorption, and then 2. Transforming the matrix to the conditional probability as you say. But honestly I don't know exactly how to approach either. $\endgroup$ – Remy Kabel Dec 23 '18 at 11:06
  • $\begingroup$ Are you looking for the probability distribution of the time to absorption for finite discrete or continuous time Markov chain? $\endgroup$ – Waqas Dec 28 '18 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.