6
$\begingroup$

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from each state, there can be transitions to 2 other states only).

Let $P_t$ be the transition probability matrix, so $P_t(j,k) = $ Prob($X_t = k | X_0 = j$).

My question is: what is the best way to quickly compute the $j$th row of $P_1$?

Solving the Kolmogorov forward equations gives $P_t = e^{Qt}$, so one method is to perform this computation explicitly in matlab: expm(Q). But I'm thinking that there is perhaps a better way, particularly given the structure of $Q$ and since I'm only interested in one row of $P_1$. The actual instance of the problem I'm solving is small (120 states, say), but I would like the computation to be very fast.

Edit: following the suggestion by @meij in the comments below, I posted this question here and received some useful answers: https://scicomp.stackexchange.com/questions/6828/efficient-computation-of-markov-chain-transition-probability-matrix

$\endgroup$
3
  • $\begingroup$ If $Q$ is diagonalizable, say $Q = V\Lambda V^{-1}$, then using $e^{tQ} = V e^{t\Lambda} V^{-1}$ seems likely to be faster than expm. You can also approximate the exponential using Krylov subspace (Lanczos or Arnoldi) techniques. $\endgroup$ Apr 11, 2013 at 12:15
  • $\begingroup$ maybe a good question for scicomp stackexchange $\endgroup$
    – meij
    Apr 11, 2013 at 18:32
  • $\begingroup$ @meij, was not aware of its existence, thanks! $\endgroup$
    – Johannes
    Apr 12, 2013 at 7:18

1 Answer 1

1
$\begingroup$

What you need is called "computing the action of the matrix exponential" (that is, computing $\exp(A)b$ without forming $\exp(A)$ explicitly. There are techniques based on complex integrals and Krylov subspaces. See http://eprints.ma.man.ac.uk/1426/ and the references included there.

$\endgroup$
1
  • $\begingroup$ This was exactly what I was looking for, thanks. The link even contains the authors' matlab code, which works very nicely. $\endgroup$
    – Johannes
    Apr 16, 2013 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.