Accelerated Stochastic Simulation

Che-chi Shu, Vu Tran and Doraiswami Ramkrishna

Abstract

Various systems1,2 in nature are composed of a small number of molecules which inherently display a high degree of randomness in behavior. Capturing this is beyond the scope of deterministic differential equations, thus requiring the use of stochastic simulations. As a systemâ??s complexity increases, it becomes inaccessible to conventional CPU times. This paper demonstrates two strategies which can be utilized to reduce the CPU time in stochastic simulations. The so-called Tau-leap algorithm was introduced to reduce wasted simulation time steps and targeted to capture steps at which many only major events occurred. This leap was based on satisfying certain inequality assumptions which can be met only in a probabilistic
sense. To ensure the accuracy of each pick for time step, Cao et al.,2 proposed a leap check for
each simulation, but did not mathematically validate it.
Two aspects are proposed and demonstrated here to effectively improve simulation time, (1) the new selection of tau-leap, and (2) a strategy in which some outcomes can be realized earlier during the simulation. Usage of Chebyshevâ??s inequality for random variables provides a probabilistic guarantee of new tau-leap measurement. As a result of this effectiveness, the number of simulations can be reduced for a fixed accuracy. The second idea lies in the fact that some trajectories can reach the final designated time point earlier than the others. Since realization of a specific trajectory outcome requires completion of the previous simulation, the delay for this process can be observed. This algorithm allows independent calculations of time steps for different trajectories instantaneously. Thus, short simulations will be observed without having to wait for the completion of longer trajectories. A combination of these two strategies has shown a significant speed-up for CPU time, and raised the potential of application of the tau- leap algorithm.

References:

(1) Tian TH, Burrage K (2004) Binomial leap methods for simulating stochastic chemical kinetics. Journal of Chemical Physics 121: 10356-10364.
(2) Y. Cao, D. T. Gillespie and L. R. Petzold, Journal of Chemical Physics 124 (4) (2006).