Edinburgh Research Explorer

Markov chain simulation with fewer random samples

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Rights statement: Elsevier Open Access paper.

    Final published version, 250 KB, PDF document

http://www.sciencedirect.com/science/article/pii/S1571066113000431
Original languageEnglish
Pages (from-to)183-197
Number of pages15
JournalElectronic Notes in Theoretical Computer Science
Volume296
DOIs
Publication statusPublished - 16 Aug 2013

Abstract

We propose an accelerated CTMC simulation method that is exact in the sense that it produces all of the transitions involved. We call our method Path Sampling Simulation as it samples from the distribution of trajectories and the distribution of time given some particular trajectory. Sampling from the trajectory space rather than the transition space means that we need to generate fewer random numbers, which is an operation that is typically computationally expensive. Sampling from the time distribution involves approximating the exponential distributions that govern the sojourn times with a geometric distribution. A proper selection for the approximation parameters can ensure that the stochastic process simulated is almost identical to the simulation of the original Markov chain. Our approach does not depend on the properties of the system and it can be used as an alternative to more efficient approaches when those are not applicable.

Download statistics

No data available

ID: 13236728