Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 36 · Applications and Simulation

Simulating Continuous-Time Chains with Gillespie's Method

Write the Gillespie algorithm from scratch, simulate an immigration-death chain, and verify it against exact stationary and transient results.

Equations such as πQ = 0 give averages. A simulation gives you actual random trajectories, which you can inspect, plot and use to estimate quantities that have no formula. For continuous-time Markov chains there is a standard exact method, usually called the Gillespie algorithm (after the physical chemist Daniel Gillespie, who popularized it for chemical reactions; it is also known as the stochastic simulation algorithm or the kinetic Monte Carlo method). It is the "wait, then jump" recipe from the holding times lesson, organized for a chain whose rates depend on the state.

The algorithm

Given the current state x and time t:

  1. List all possible events in state x, each with a rate rₖ(x) and an effect on the state. Let R = Σ rₖ(x).
  2. If R = 0, the chain is stuck: stop.
  3. Draw the waiting time Δ ~ Exponential(R). (Superposition: the earliest of independent exponential clocks is exponential with the summed rate.)
  4. Choose event k with probability rₖ(x)/R. (This is the race of exponentials.)
  5. Apply the event and set t = t + Δ. Repeat.

It is exact: no time-step error, only statistical error from using finitely many runs.

flowchart TD
  A["State x, time t"] --> B["Compute rates r_k(x), total R"]
  B --> C["Wait Δ ~ Exp(R)"]
  C --> D["Pick event k with prob r_k / R"]
  D --> E["Update x and t"]
  E --> A

One iteration of the Gillespie loop.

An example: immigration and death

Individuals (customers in a shop with many service counters, molecules in a cell, cars on a long road) arrive at rate a and each leaves at rate μ. With n present, the events are:

  • Arrival: rate a, effect n → n + 1.
  • Departure: rate n μ, effect n → n - 1.

This is a birth-death process, and its stationary distribution is Poisson(a/μ). Starting empty, the mean at time t is E[X(t)] = (a/μ)(1 - e^(-μt)), because d/dt E[X] = a - μ E[X].

Python Gillespie's algorithm for immigration-death

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The time-averaged distribution of the state lines up with Poisson(5), and mean and variance are both close to 5.

Now test the transient formula with many short independent runs.

Python Transient mean: simulation versus formula

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulated means follow the formula. The variances equal the means too: starting from empty, the state at time t is exactly Poisson distributed.

Why use it

Gillespie's method is the workhorse for:

  • Chemical kinetics: with few molecules, reactions are random events with state-dependent rates.
  • Epidemics: infection happens at a rate proportional to the number of susceptible-infectious pairs; recovery at a rate proportional to infectious numbers.
  • Queues and networks with several servers, priorities or blocking.
  • Population genetics and ecology: birth, death and migration events.

For a chain with very many fast events, Gillespie can be slow, since every event costs one loop pass. Tau-leaping approximates many events at once at the price of accuracy. For this course the exact method is the one to know.

Pitfalls

  • Using the wrong total rate. In state n the death rate is n μ, not μ. Always recompute R from the current state.
  • Comparing a single long path with the stationary distribution, but measuring by event counts instead of by time. States held longer count more; weight by durations as above.
  • Starting in a rare state and judging stationary behavior too early. Discard an initial "burn-in" period when you estimate long-run averages.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In the Gillespie algorithm, how is the waiting time to the next event drawn?

    The earliest of independent exponential clocks is exponential with the total rate.
  2. 2. Which probability picks the event that happens?

    Event k wins the race with probability r_k divided by the total rate R.
  3. 3. In an immigration-death chain with a = 6 and μ = 2, what are the stationary mean and variance?

    The stationary law is Poisson(a/μ) = Poisson(3), with mean and variance equal to 3.
  4. 4. To estimate stationary probabilities from one long simulated path, you should weight each visited state by...

    Stationary probabilities are long-run fractions of time.

Summary

  • Gillespie: compute the rates, wait Exp(R), choose event k with probability rₖ/R, update, repeat.
  • It is exact for any CTMC given as state-dependent rates.
  • Time-weighted averages estimate stationary distributions; many short runs estimate transient quantities.
  • Immigration-death is a good test case because its answers are known exactly.

Next: Simulating the M/M/1 Queue