Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: http://scicomp.stackexchange.com/questions/6828/efficient-computation-of-markov-chain-transition-probability-matrix

share|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
add comment

1 Answer

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 http://eprints.ma.man.ac.uk/1426/ and the references included there.

share|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
add comment

Your Answer

 
discard

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.