Kannan Deepti, Sharpe Daniel J, Swinburne Thomas D, Wales David J
Department of Chemistry, University of Cambridge, Lensfield Road, Cambridge CB2 1EW, United Kingdom.
Aix-Marseille Université, CNRS, CINaM UMR 7325, Campus de Luminy, 13288 Marseille, France.
J Chem Phys. 2020 Dec 28;153(24):244108. doi: 10.1063/5.0025174.
Markov chains can accurately model the state-to-state dynamics of a wide range of complex systems, but the underlying transition matrix is ill-conditioned when the dynamics feature a separation of timescales. Graph transformation (GT) provides a numerically stable method to compute exact mean first passage times (MFPTs) between states, which are the usual dynamical observables in continuous-time Markov chains (CTMCs). Here, we generalize the GT algorithm to discrete-time Markov chains (DTMCs), which are commonly estimated from simulation data, for example, in the Markov state model approach. We then consider the dimensionality reduction of CTMCs and DTMCs, which aids model interpretation and facilitates more expensive computations, including sampling of pathways. We perform a detailed numerical analysis of existing methods to compute the optimal reduced CTMC, given a partitioning of the network into metastable communities (macrostates) of nodes (microstates). We show that approaches based on linear algebra encounter numerical problems that arise from the requisite metastability. We propose an alternative approach using GT to compute the matrix of intermicrostate MFPTs in the original Markov chain, from which a matrix of weighted intermacrostate MFPTs can be obtained. We also propose an approximation to the weighted-MFPT matrix in the strongly metastable limit. Inversion of the weighted-MFPT matrix, which is better conditioned than the matrices that must be inverted in alternative dimensionality reduction schemes, then yields the optimal reduced Markov chain. The superior numerical stability of the GT approach therefore enables us to realize optimal Markovian coarse-graining of systems with rare event dynamics.
马尔可夫链可以精确地模拟各种复杂系统的状态间动态变化，但当动态变化具有时间尺度分离的特征时，其潜在的转移矩阵是病态的。图形变换（GT）提供了一种数值稳定的方法来计算状态之间的精确平均首次通过时间（MFPTs），这是连续时间马尔可夫链（CTMCs）中常用的动态可观测量。在这里，我们将GT算法推广到离散时间马尔可夫链（DTMCs），离散时间马尔可夫链通常是从模拟数据中估计出来的，例如在马尔可夫状态模型方法中。然后，我们考虑CTMCs和DTMCs的降维，这有助于模型解释并便于进行更昂贵的计算，包括路径采样。给定网络划分为节点（微状态）的亚稳态群落（宏观状态），我们对计算最优简化CTMC的现有方法进行了详细的数值分析。我们表明，基于线性代数的方法会遇到由必要的亚稳态引起的数值问题。我们提出了一种替代方法，使用GT来计算原始马尔可夫链中微状态间MFPTs的矩阵，从中可以获得加权宏观状态间MFPTs的矩阵。我们还提出了在强亚稳态极限下对加权MFPT矩阵的一种近似。加权MFPT矩阵的求逆比替代降维方案中必须求逆的矩阵条件更好，然后得到最优简化马尔可夫链。因此，GT方法的卓越数值稳定性使我们能够实现具有罕见事件动态的系统的最优马尔可夫粗粒化。
