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>



Efficient computation of Markov chain transition probability matrix
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.


