Graph transformation and shortest paths algorithms for finite Markov chains

The graph transformation (GT) algorithm robustly computes the mean first-passage time to an absorbing state in a finite Markov chain. Here we present a concise overview of the iterative and block formulations of the GT procedure and generalize the GT formalism to the case of any path property that is a sum of contributions from individual transitions. In particular, we examine the path action, which directly relates to the path probability, and analyze the first-passage path ensemble for a model Markov chain that is metastable and therefore numerically challenging. We compare the mean first-passage path action, obtained using GT, with the full path action probability distribution simulated efficiently using kinetic path sampling, and with values for the highest-probability paths determined by the recursive enumeration algorithm (REA). In Markov chains representing realistic dynamical processes, the probability distributions of first-passage path properties are typically fat-tailed and therefore difficult to converge by sampling, which motivates the use of exact and numerically stable approaches to compute the expectation. We find that the kinetic relevance of the set of highest-probability paths depends strongly on the metastability of the Markov chain, and so the properties of the dominant first-passage paths may be unrepresentative of the global dynamics. Use of a global measure for edge costs in the REA, based on net productive fluxes, allows the total reactive flux to be decomposed into a finite set of contributions from simple flux paths. By considering transition flux paths, a detailed quantitative analysis of the relative importance of competing dynamical processes is possible even in the metastable regime.

Figure 1

Disconnectivity graph [114] representing the energy landscape of the model eight-state CTMC, at a threshold energy increment of $\mathrm{\Delta }E=2$. The branches of the tree terminate at the energies of the corresponding nodes. A fork indicates that there exists a path between the corresponding sets of nodes via a highest-energy transition state that lies in between the neighboring energy thresholds. The branches corresponding to the absorbing and initial nodes, which constitute the sets $\mathcal{A}$ and $\mathcal{B}$, are colored red and blue, respectively.

Figure 2

Variation in the $\mathcal{A}\leftarrow \mathcal{B}$ mean first-passage time, ${\mathcal{T}}_{\mathcal{A}\mathcal{B}}$, and the steady-state $\mathcal{A}\leftarrow \mathcal{B}$ reactive flux, ${\mathcal{J}}_{\mathcal{A}\mathcal{B}}$, with inverse temperature, for the eight-state CTMC (Fig. 1).

Figure 3

Probability distribution of the path action for the ensemble of $\mathcal{A}\leftarrow \mathcal{B}$ first-passage paths, obtained from 100 000 kinetic path sampling [68] iterations, and mean path action obtained using the generalized GT algorithm (pink), for the eight-state CTMC (Fig. 1) at an inverse temperature of $1/T=2$. At this temperature, the CTMC is strongly metastable.

Figure 4

Values of the path action (blue) and cumulative pathwise sum [Eq. (15)] for the MFPT (pink) for the 100 000 highest-probability $\mathcal{A}\leftarrow \mathcal{B}$ first-passage paths in the eight-state CTMC (Fig. 1) at an inverse temperature of $1/T=2$. At this temperature, the CTMC is strongly metastable. The value of the MFPT, computed using GT, is indicated by a dashed pink line. The paths were determined using the recursive enumeration algorithm (Algorithm 1) [70]. Note the small scale for the path action axis.

Figure 5

Cumulative sum of $\mathcal{A}\leftarrow \mathcal{B}$ first-passage path probabilities at varying temperature for the eight-state CTMC (Fig. 1), accounting for an increasing number of the highest-probability paths determined by the recursive enumeration algorithm (Algorithm 1) [70]. The annotations denote the value of the inverse temperature, i.e., $1/T$.

Figure 6

Cumulative sum of relative contributions [cf. Eq. (16)] to the total $\mathcal{A}\leftarrow \mathcal{B}$ steady-state reactive flux, ${\mathcal{J}}_{\mathcal{A}\mathcal{B}}$, from alternative simple flux paths, for the eight-state CTMC (Fig. 1) at varying temperature. There are 36 simple flux paths in total, but no more than 15 transition flux paths are required to account for the vast majority ($>99\%$) of the total reactive flux for all temperatures shown. The annotations denote the value of the inverse temperature, i.e., $1/T$. The flux paths were determined using the recursive enumeration algorithm [70] (Algorithm 1) with edge costs based on net reactive fluxes [Eq. (18)].