Automated State-Dependent Importance Sampling for Markov Jump Processes via Sampling from the Zero-Variance Distribution. (30th January 2018)

• Record Type: Journal Article
• Authors: Grace, Adam W.; Kroese, Dirk P.; Sandmann, Werner
• Is Part Of: Journal of applied probability. Volume 51:Number 3(2014)
• Page Start: 741
• Page End: 755
• Publication Date: 2018-01-30
• Subjects: Importance sampling, -- adaptive, -- automated, -- improved cross entropy, -- state dependent, -- zero-variance distribution, -- Markov jump process, -- continuous-time Markov chain, -- stochastic chemical kinetics, -- queueing system; 60J28, -- 62M05; 519.2
• DOI: 10.1239/jap/1409932671
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract : Many complex systems can be modeled via Markov jump processes. Applications include chemical reactions, population dynamics, and telecommunication networks. Rare-event estimation for such models can be difficult and is often computationally expensive, because typically many (or very long) paths of the Markov jump process need to be simulated in order to observe the rare event. We present a state-dependent importance sampling approach to this problem that is adaptive and uses Markov chain Monte Carlo to sample from the zero-variance importance sampling distribution. The method is applicable to a wide range of Markov jump processes and achieves high accuracy, while requiring only a small sample to obtain the importance parameters. We demonstrate its efficiency through benchmark examples in queueing theory and stochastic chemical kinetics.