Gillespie algorithm
The Gillespie stochastic simulation algorithm generates exact sample paths of a CTMC when the model is specified by discrete events and their current rates.
Step 1: calculate rates
For event rates \(a_1,\ldots,a_m\), calculate the total
\[a_0=\sum_{k=1}^m a_k.\]Step 2: sample the waiting time
\[\tau=-\frac{\ln U_1}{a_0},\qquad U_1\sim U(0,1).\]Step 3: choose the event
Event \(k\) is selected with probability \(a_k/a_0\). A second uniform random number can select among the cumulative probabilities.
Step 4: update
Advance time by \(\tau\), update the state according to the chosen event, recalculate rates, and repeat.
Key idea. Gillespie simulation randomises both when the next event occurs and which event occurs, according to the CTMC rates.