MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

share|cite|improve this question
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. – Steve Huntsman Apr 11 '13 at 12:15
maybe a good question for scicomp stackexchange – meij Apr 11 '13 at 18:32
@meij, was not aware of its existence, thanks! – Johannes Apr 12 '13 at 7:18
up vote 1 down vote accepted

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 and the references included there.

share|cite|improve this answer
This was exactly what I was looking for, thanks. The link even contains the authors' matlab code, which works very nicely. – Johannes Apr 16 '13 at 13:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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