Efficiently simulating discrete-state models with binary decision trees

Stochastic simulation algorithms (SSAs) are widely used to numerically
investigate the properties of stochastic, discrete-state models. The Gillespie
Direct Method is the pre-eminent SSA, and is widely used to generate sample
paths of so-called agent-based or individual-based models. However, the
simplicity of the Gillespie Direct Method often renders it impractical where
large-scale models are to be analysed in detail. In this work, we carefully
modify the Gillespie Direct Method so that it uses a customised binary decision
tree to trace out sample paths of the model of interest. We show that a
decision tree can be constructed to exploit the specific features of the chosen
model. Specifically, the events that underpin the model are placed in
carefully-chosen leaves of the decision tree in order to minimise the work
required to keep the tree up-to-date. The computational efficencies that we
realise can provide the apparatus necessary for the investigation of
large-scale, discrete-state models that would otherwise be intractable. Two
case studies are presented to demonstrate the efficiency of the method.