STOCHASTIC PROCESSES 13

Gillespie Simulation

The Gillespie algorithm simulates an exact sample path of a continuous-time Markov chain from its transition rates.

The problem

At the current state, suppose event types have rates

\[a_1,a_2,\ldots,a_m.\]

We need to determine both when the next event occurs and which event it is.

1. Calculate the total rate

\[\boxed{a_0=\sum_{k=1}^m a_k}\]

2. Generate the waiting time

Draw \(U_1\sim U(0,1)\) and calculate

\[\boxed{\tau=-\frac{\ln U_1}{a_0}}.\]

Advance time by \(\tau\).

3. Choose the event

Event \(k\) is selected with probability

\[\boxed{\frac{a_k}{a_0}}.\]

A second uniform random number can be used to choose among the cumulative probability intervals.

4. Update the state

Apply the selected event to the state. For an SIS epidemic, an infection increases \(I\) by one and a recovery decreases \(I\) by one.

5. Recalculate rates

Because rates may depend on the state, calculate them again after every event.

6. Repeat

\[\boxed{\text{rates}\rightarrow\text{waiting time}\rightarrow\text{event}\rightarrow\text{new state}\rightarrow\text{repeat}}\]

7. Why it is called exact

For a CTMC with specified transition rates, Gillespie simulation samples from the model's jump-time and event-type distributions without imposing a fixed numerical time step.

8. One simulation is one trajectory

Repeated simulations are required to estimate quantities such as outbreak probability, expected prevalence or variance.