Efficient Steady State Analysis of Multimodal Markov Chains

We consider the problem of computing the steady state distribution of Markov chains describing cellular processes. Our main contribution is a numerical algorithm that approximates the steady state distribution in the presence of multiple modes. This method tackles two problems that occur during the analysis of systems with multimodal distributions: stiffness preventing fast convergence of iterative methods and largeness of the state space leading to excessive memory requirements and prohibiting direct solutions. We use drift arguments to locate the relevant parts of the state space, that is, parts containing 1 − e of the steady state probability. In order to separate the widely varying time scales of the model we apply stochastic complementation techniques. The memory requirements of our method are low because we exploit accurate approximations based on inexact matrix vector multiplications. We test the performance of our method on two challenging examples from biology.