Adaptive uniformization

Uniformization has been shown to be, in many cases, a good method to compute transient state probabilities of a continuous-time Markov chain. However, two issues limit its use: uniformization can be computationally very intensive, for instance, on stiff models, and uniformization cannot be used for all model classes, e.g., models with not uniformly bounded transition rates. In this paper we introduce adaptive uniformization, a variation on standard uniformization, which can overcome these problems for some models. Adaptive uniformization differs from standard uniformization in that it uses a uniformization rate that adapts depending on the set of states that the process can be in after a particular number of jumps. Doing this can sometimes significantly reduce the computational cost required to obtain a solution. A formal definition of adaptive uniformization is first given, along with a proof that adaptive uniformization yields correct results. Characteristics of models that can facilitate solution and alternative methods for computing the required “jump probabilities” are then discussed. Finally, the computational cost of adaptive uniformization (relative to standard uniformization) is illustrated, through its application to an extended machine-repairman model.