Stochastic simulation algorithms and methods were initially developed to analyse chemical reactions involving large numbers of species with complex reaction kinetics. The first algorithm, the Gillespie algorithm

Gillespie algorithm

In probability theory, the Gillespie algorithm generates a statistically correct trajectory of a stochastic equation. It was created by Joseph L...

 was proposed by Dan Gillespie in 1977. It is an exact procedure for numerically simulating the time evolution of a well-stirred chemically reacting system.

The algorithm is a Monte Carlo

Monte Carlo method

Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...

 type method.

Discrete, exact variants

In order to determine the next event in a stochastic simulation, the rates of all possible changes to the state of the model are computed, and then ordered in an array. Next, the cumulative sum of the array is taken, and the final cell contains the number R, where R is the total event rate. This cumulative array is now a discrete cumulative distribution, and can be used to choose the next event by picking a random number z~U(0,R) and choosing the first event, such that z is less than the rate associated with that event.

In order of decreasing efficiency

Partial-propensity methods

Published in 2009, 2010, and 2011 (Ramaswamy 2009, 2010, 2011). Use factored-out, partial reaction propensities to reduce the computational cost to scale with the number of species in the network, rather than the (larger) number of reactions. Four variants exist:

• PDM, the partial-propensity direct method. Has a computational cost that scales linearly with the number of different species in the reaction network, independent of the coupling class of the network (Ramaswamy 2009).
• SPDM, the sorting partial-propensity direct method. Uses dynamic bubble sort to reduce the pre-factor of the computational cost in multi-scale reaction networks where the reaction rates span several orders of magnitude (Ramaswamy 2009).
• PSSA-CR, the partial-propensity SSA with composition-rejection sampling. Reduces the computational cost to constant time (i.e., independent of network size) for weakly coupled networks (Ramaswamy 2010) using composition-rejection sampling (Slepoy 2008).
• dPDM, the delay partial-propensity direct method. Extends PDM to reaction networks that incur time delays (Ramaswamy 2011) by providing a partial-propensity variant of the delay-SSA method (Bratsun 2005, Cai 2007).

The use of partial-propensity methods is limited to elementary chemical reactions, i.e., reactions with at most two different reactants. Every non-elementary chemical reaction can be equivalently decomposed into a set of elementary ones, at the expense of a linear (in the order of the reaction) increase in network size.

Direct and first reaction methods

Published by Dan Gillespie in 1977, and is a linear search on the cumulative array. See Gillespie algorithm

Gillespie algorithm

In probability theory, the Gillespie algorithm generates a statistically correct trajectory of a stochastic equation. It was created by Joseph L...

.

See also

• Gillespie algorithm
  Gillespie algorithm
  In probability theory, the Gillespie algorithm generates a statistically correct trajectory of a stochastic equation. It was created by Joseph L...
  
  
• Network simulation
  Network simulation
  In communication and computer network research, network simulation is a technique where a program models the behavior of a network either by calculating the interaction between the different network entities using mathematical formulas, or actually capturing and playing back observations from a...
  
  
• Network traffic simulation
  Network traffic simulation
  Network traffic simulation is a process used in telecommunications engineering to measure the efficiency of a communications network.-Overview:...
  
  
• Simulation language
  Simulation language
  A computer simulation language describes the operation of a simulation on a computer. There are two major types of simulation: continuous and discrete event though more modern languages can handle combinations. Most languages also have a graphical interface and at least simple statistical gathering...
  
  
• Queueing theory
  Queueing theory
  Queueing theory is the mathematical study of waiting lines, or queues. The theory enables mathematical analysis of several related processes, including arriving at the queue, waiting in the queue , and being served at the front of the queue...
  
  
• Software choice for discrete event simulations

External links

Software

• Cain - Stochastic simulation of chemical kinetics. Direct, next reaction, tau-leaping, hybrid, etc.
• PDM - C++ implementations of all partial-propensity methods.
• StochPy - Stochastic modelling in Python