A fast exact simulation algorithm for a class of Markov jump processes.
Yao Li, Lili Hu · arXiv (Cornell University) · 2015
A new stochastic simulation algorithm, named the Hashing-Leaping (HL) algorithm, for exact simulations of a class of Markov jump processes, is presented in this paper. The HL algorithm has constant computational cost per event, which is independent of the number of exponential clocks in the Markov process. The main idea of the HL algorithm is to repeatedly implement a Hash-table-like bucket sort algorithm for all times of occurrence covered by a time step with length $\tau$. This paper serves as an introduction to this new algorithm. We introduce the algorithm, demonstrate its implementation, and compare its performance with the benchmark NRM algorithm in three examples. Our performance test and CPU operation statistics show a significant advantage of the HL algorithm for large scale problems.