Approximate computation of transient results for large Markov chains

This paper presents a new approach for the computation of transient measures in large continuous time Markov chains (CTMCs). The approach combines the randomization approach for transient analysis of CTMCs with a new representation of probability vectors as Kronecker products of small component vectors. This representation is an approximation that allows an extremely space- and time-efficient computation of transient vectors. Usually, the resulting approximation is very good and introduces errors that are comparable to those found with existing approximation techniques for stationary analysis. By increasing the space and time requirements of the approach, we can represent parts of the solution vector in detail and reduce the approximation error, yielding exact solutions in the limiting case.