In probability theory, tau-leaping, or τ-leaping, is an approximate method for the simulation of a stochastic system. It is based on the Gillespie algorithm, performing all reactions for an interval of length tau before updating the propensity functions. By updating the rates less often this sometimes allows for more efficient simulation and thus the consideration of larger systems.
The algorithm is analogous to the Euler method for deterministic systems, but instead of making a fixed change
the change is
where is a Poisson distributed random variable with mean .
Given a state with events occurring at rate and with state change vectors (where indexes the state variables, and indexes the events), the method is as follows:
- Initialise the model with initial conditions .
- Calculate the event rates .
- Choose a time step . This may be fixed, or by some algorithm dependent on the various event rates.
- For each event generate , which is the number of times each event occurs during the time interval .
- Update the state by
- where is the change on state variable due to event . At this point it may be necessary to check that no populations have reached unrealistic values (such as a population becoming negative due to the unbounded nature of the Poisson variable ).
- Repeat from Step 2 onwards until some desired condition is met (e.g. a particular state variable reaches 0, or time is reached).
Algorithm for efficient step size selection
This algorithm is described by Cao et al. The idea is to bound the relative change in each event rate by a specified tolerance (Cao et al. recommend , although it may depend on model specifics). This is achieved by bounding the relative change in each state variable by , where depends on the rate that changes the most for a given change in .Typically is equal the highest order event rate, but this may be more complex in different situations (especially epidemiological models with non-linear event rates).
This algorithm typically requires computing auxiliary values (where is the number of state variables ), and should only require reusing previously calculated values . An important factor in this since is an integer value, then there is a minimum value by which it can change, preventing the relative change in being bounded by 0, which would result in also tending to 0.
- For each state variable , calculate the auxiliary values
- For each state variable , determine the highest order event in which it is involved, and obtain
- Calculate time step as
This computed is then used in Step 3 of the leaping algorithm.
- Gillespie, D. T. (2001). "Approximate accelerated stochastic simulation of chemically reacting systems" (PDF). The Journal of Chemical Physics. 115 (4): 1716–1733. Bibcode:2001JChPh.115.1716G. doi:10.1063/1.1378322.
- Erhard, F.; Friedel, C. C.; Zimmer, R. (2010). "FERN – Stochastic Simulation and Evaluation of Reaction Networks". Systems Biology for Signaling Networks. p. 751. doi:10.1007/978-1-4419-5797-9_30. ISBN 978-1-4419-5796-2.
- Cao, Y.; Gillespie, D. T.; Petzold, L. R. (2005). "Avoiding negative populations in explicit Poisson tau-leaping". The Journal of Chemical Physics. 123 (5): 054104. Bibcode:2005JChPh.123e4104C. CiteSeerX 10.1.1.123.3650. doi:10.1063/1.1992473. PMID 16108628.
- Cao, Y.; Gillespie, D. T.; Petzold, L. R. (2006). "Efficient step size selection for the tau-leaping simulation method" (PDF). The Journal of Chemical Physics. 124 (4): 044109. Bibcode:2006JChPh.124d4109C. doi:10.1063/1.2159468. PMID 16460151.
- Anderson, David F. (2008-02-07). "Incorporating postleap checks in tau-leaping". The Journal of Chemical Physics. 128 (5): 054103. arXiv:0708.0377. Bibcode:2008JChPh.128e4103A. doi:10.1063/1.2819665. ISSN 0021-9606. PMID 18266441.
- Chatterjee, Abhijit; Vlachos, Dionisios G.; Katsoulakis, Markos A. (2005-01-08). "Binomial distribution based τ-leap accelerated stochastic simulation". The Journal of Chemical Physics. 122 (2): 024112. Bibcode:2005JChPh.122b4112C. doi:10.1063/1.1833357. ISSN 0021-9606. PMID 15638577.
- Moraes, Alvaro; Tempone, Raul; Vilanova, Pedro (2014-04-24). "Hybrid Chernoff Tau-Leap". Multiscale Modeling & Simulation. 12 (2): 581–615. CiteSeerX 10.1.1.756.9799. doi:10.1137/130925657. ISSN 1540-3467.