An Enhanced Method for the Computation of the Distribution of the Proportion of Time that a Continuous-Time Markov Chain is in a Subset of States in a Time Interval

We develop a new numerical method for the computation of the complementary probability distribution of the proportion of time in a time interval that a continuous-time Markov chain (CTMC) is in a subset of states. The new method is an enhanced version of a method developed by the second author (method C) based on a uniformization construct with a uniformization rate for states in the subset and a uniformization rate for states outside the subset which for large CTMCs can be much faster than a previous uniformization-based general purpose state-of-the-art method (method A) when the proportion of time is close to one and the maximum output rate from states in the subset is significantly different from the maximum output rate from states outside the subset. The enhancement consists in new truncation points, in computing with potentially better numerical stability some probabilities required by method C, and in a different computational scheme. Using reasonable estimates for the computational cost of the new method, method C, and method A, it is argued that for large enough CTMCs the new method can be expected to be less costly in both memory and CPU time that both method C and method A for many combinations of values of the maximum output rate from states in the subset, the maximum output rate from states outside the subset, the product of the maximum output rate and the width of the time interval, and the proportion of time. The actual reduction in CPU time is illustrated using two representative CTMC examples.