Gillespie Decomposition of a Markov Chain

Goal

We will discuss a way to decompose a continuous time Markov chain (CTMC) into a product of two probability distributions:

1. The probability distribution for the waiting time until the next transition.
2. The probability distribution for which transition will occur when the transition takes place.

Gillespie used this decomposition to formulate his algorithm for simulating reaction kinetics. The concepts for this decomposition exist in most treatments of CTMCs, but are rarely put together so explicitly.We will quickly review the assumptions and properties of CTMCs. Then we will demonstrate how to achieve the decomposition just described.

Continuous Time Markov Chain

A CTMC is a mathematical model of systems that three properties:

1. The system resides in a finite number of discrete states
2. The system transitions from state to state in a particular way such that the probability of a transition in a small time interval $\Delta t$ is proportional to $\lambda \Delta t$ for some constant $\lambda$
3. Once the system is in a given a given state it retains no memory of past states or transitions (or any other aspect of its history). In other words, it is "memoryless"

CTMCs are defined by a set of transition probabilities that form a matrix $p_{i,j}$ where $j$ represents the current state of the system, and $i$ represents the new state after a transition. In a CTMC, the $p_{i,j}$ represent infinitesimal rates. Because a state must transition to somewhere the columns of $p$ must sum to 1. Thus, the rows can be considered conditional probabilities of the form:

$p_{i,j} = P[\text{in state } i \text{ at } t+\Deltat ,| \text{ in state } j \text{ at } t]$

In fact, the $p_{i,j}$ are the state-dependent $\lambda$s referred to in item (2) above. Therefore, the are all $o(\Delta t)$.

Connection to Poisson Process

Because a CTMC is based on the same fundamental assumptions as the Poisson process (which is no coincidence), they share some important features. Actually, a Poisson process is a special case of a CTMC in which the states are integer counting events.

Because of this relationship, the waiting time for every transition $i \to j$ is also an exponential distribution, as we will now derive. The Poisson process has a single parameter $\lambda$. A CTMC has an entire matrix of parameters $p_{i,j}$. We must figure out how to incorporate this into our derivation.

Just as with the Poisson process, we begin by deriving the probability of NO transition in a time interval $\tau$ (just as with the Poisson process, because of memorylessness, we are only concerned with intervals). If we are currently in state $j$, then the applicable rate (equivalent to $\lambda$ for the Poisson process) is $p_{j,j}$. Since we have already derived this result, we can immediately say that

$P[\text{still in } j \text{ at } t+\tau \,|\, \text{was in } j \text{ at } t] = e^{-p_{j,j}\,t}$