A Gillespie algorithm for non-Markovian stochastic processes

DOI10.1137/16M1055876zbMATH Open1405.60003arXiv1601.01490MaRDI QIDQ3133144FDOQ3133144

Authors: Naoki Masuda, Luis E. C. Rocha 

Publication date: 13 February 2018

Published in: SIAM Review (Search for Journal in Brave)

Abstract: The Gillespie algorithm provides statistically exact methods for simulating stochastic dynamics modelled as interacting sequences of discrete events including systems of biochemical reactions or earthquake occurrences, networks of queuing processes or spiking neurons, and epidemic and opinion formation processes on social networks. Empirically, the inter-event times of various phenomena obey long-tailed distributions. The Gillespie algorithm and its variants either assume Poisson processes (i.e., exponentially distributed inter-event times), use particular functions for time courses of the event rate, or work for non-Poissonian renewal processes, including the case of long-tailed distributions of inter-event times, but at a high computational cost. In the present study, we propose an innovative Gillespie algorithm for renewal processes on the basis of the Laplace transform. The algorithm makes use of the fact that a class of point processes is represented as a mixture of Poisson processes with different event rates. The method is applicable to multivariate renewal processes whose survival function of inter-event times is completely monotone. It is an exact algorithm and works faster than a recently proposed Gillespie algorithm for general renewal processes, which is exact only in the limit of infinitely many processes. We also propose a method to generate sequences of event times with a tunable amount of positive correlation between inter-event times. We demonstrate our algorithm with exact simulations of epidemic processes on networks, finding that a realistic amount of positive correlation in inter-event times only slightly affects the epidemic dynamics.

Full work available at URL: https://arxiv.org/abs/1601.01490

Recommendations

• Gillespie algorithms for stochastic multiagent dynamics in populations and networks
• Optimized Gillespie algorithms for the simulation of Markovian epidemic processes on large and heterogeneous networks
• A first step to implement Gillespie's algorithm with rejection sampling
• A multi-stage representation of cell proliferation as a Markov process

zbMATH Keywords

Laplace transformnetworkpoint processnumerical simulation

Mathematics Subject Classification ID

Computational methods for problems pertaining to probability theory (60-08) Renewal theory (60K05)

Cites Work

• Self-exciting point process modeling of crime
• Title not available (Why is that?)
• Title not available (Why is that?)
• Self-exciting hurdle models for terrorist activity
• Modelling security market events in continuous time: intensity based, multivariate point process models
• Title not available (Why is that?)
• Mixtures of exponential distributions
• Waiting-times and returns in high-frequency financial data: An empirical study
• The dynamic nature of contact networks in infectious disease epidemiology
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mittag-Leffler functions, related topics and applications
• Title not available (Why is that?)
• Superstatistics
• On Cox processes and gamma renewal processes
• The Fourier-series method for inverting transforms of probability distributions
• The Markov-modulated Poisson process (MMPP) cookbook
• A simple method for generating gamma variables
• Weibull renewal processes
• Title not available (Why is that?)
• Testing the Mixture of Exponentials Hypothesis and Estimating the Mixing Distribution by the Methods of Moments
• Title not available (Why is that?)
• The stochastic evolution of a protocell: the Gillespie algorithm in a dynamically varying volume
• A guide to temporal networks
• Exponential approximation to Weibull renewal with decreasing failure rate

Cited In (14)

• Protein pattern formation induced by the joint effect of noise and delay in a multi-cellular system
• Reduction from non-Markovian to Markovian dynamics: the case of aging in the noisy-voter model
• A first step to implement Gillespie's algorithm with rejection sampling
• A Hierarchical Model of Nonhomogeneous Poisson Processes for Twitter Retweets
• Temporal scaling theory for bursty time series with clusters of arbitrarily many events
• Effects of concurrency on epidemic spreading in Markovian temporal networks
• Modeling stochastic gene expression: from Markov to non-Markov models
• The stochastic evolution of a protocell: the Gillespie algorithm in a dynamically varying volume
• An exact stochastic simulation method for fractional order compartment models
• A multi-stage representation of cell proliferation as a Markov process
• Noise-induced entrainment of the circadian clock by thermoperiods in tomato: a computational approach
• A network epidemic model for online community commissioning data
• A map of approaches to temporal networks
• Bursty time series analysis for temporal networks

This page was built for publication: A Gillespie algorithm for non-Markovian stochastic processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133144)