Strong diffusion formulation of Markov chain ensembles and its optimal weaker reductions

Two self-contained diffusion formulations, in the form of coupled stochastic differential equations, are developed for the temporal evolution of state densities over an ensemble of Markov chains evolving independently under a common transition rate matrix. Our first formulation derives from Kurtz's strong approximation theorem of density-dependent Markov jump processes [Stoch. Process. Their Appl. 6, 223 (1978)] and, therefore, strongly converges with an error bound of the order of $lnN/N$ for ensemble size $N$. The second formulation eliminates some fluctuation variables, and correspondingly some noise terms, within the governing equations of the strong formulation, with the objective of achieving a simpler analytic formulation and a faster computation algorithm when the transition rates are constant or slowly varying. There, the reduction of the structural complexity is optimal in the sense that the elimination of any given set of variables takes place with the lowest attainable increase in the error bound. The resultant formulations are supported by numerical simulations.

Figure 1

State transition diagram used in the demonstrations and simulations. State 0 is the relevant state.

Figure 2

A sample time course of the relevant state density for an ensemble of 300 Markov chains each evolving independently under the state transition diagram in Fig. 1. A randomly generated transition rate matrix was used. Time courses are for (a) the microscopic Markov simulation, (b) the strong formulation, and, (c) the reduced formulation with six retained states. The deterministic state density value in this particular case is 0.31.

Figure 3

Expectation value of the relevant state density (denoted $\langle {\psi }_{0C}\rangle$), measured using (a) the strong diffusion formulation, (b) the reduced formulation with six retained states, and (c) the reduced formulation with three retained states, relative to the standard deviation obtained from the exact microscopic Markov simulation (denotedy $\langle {\psi }_{0S}\rangle$). An ensemble of 300 Markov chains, each evolving independently under the state transition diagram given in Fig. 1, was used. One hundred sets of standard deviation measurements were performed using a different transition rate matrix, with every matrix element being randomly and independently generated within the range of (0–0.5), in each set. The horizontal axis in each plot gives the measurement set number. The straight line, a guide for the eyes in each plot, indicates the situation of a perfect match between the formulation and the microscopic simulation.

Figure 4

Standard deviation of the relevant state density (denoted ${\sigma }_C$), measured using (a) the strong diffusion formulation, (b) the reduced formulation with six retained states, and (c) the reduced formulation with three retained states, relative to the standard deviation obtained from the exact microscopic Markov simulation (denoted ${\sigma }_S$). An ensemble of 300 Markov chains, each evolving independently under the state transition diagram given in Fig. 1, was used. One hundred sets of standard deviation measurements were performed using a different transition rate matrix, with every matrix element being randomly and independently generated within the range of 0–0.5, in each set. The horizontal axis in each plot gives the measurement set number. The straight line, a guide for the eyes in each plot, indicates the situation of a perfect match between the formulation and the microscopic simulation.

Figure 5

Autocorrelation time of the relevant state density (denoted ${\tau }_C$), measured using (a) the strong diffusion formulation, (b) the reduced formulation with six retained states, and (c) the reduced formulation with three retained states, relative to the standard deviation obtained from the exact microscopic Markov simulation (denoted ${\tau }_S$). An ensemble of 300 Markov chains, each evolving independently under the state transition diagram given in Fig. 1, was used. One hundred sets of standard deviation measurements were performed using a different transition rate matrix, with every matrix element being randomly and independently generated within the range of 0–0.5, in each set. The horizontal axis in each plot gives the measurement set number. The straight line, a guide for the eyes in each plot, indicates the situation of a perfect match between the formulation and the microscopic simulation.

Figure 6

Plot of the exponential decay function, given by Eq. (35), using (i) the worst-case autocorrelation time in the reduced formulation with three retained states (RF3) and (ii) the corresponding microscopic Markov simulation (Mic.) autocorrelation time.

Figure 7

Numerical experiments performed over an ensemble of 300 potassium channels, each characterized by the state transition diagram in Fig. 8. Measurements for the reduced formulation with two retained states (indicated by subscript “C”) are presented relative to the corresponding exact microscopic Markov simulation results (indicated by subscript “S”). (a) Expectation values, (b) standard deviations, and (c) autocorrelation times, over the density of the relevant state 4. A set of 30 randomly and independently generated rate values in the space of $\{\alpha \in (0$:1); $\beta \in (0$:0.5)} was used.

Figure 8

Potassium channel state transition diagram. State 4 is the relevant state.