Optimal dimensionality reduction of Markov chains using graph transformation.

Area of Science:

• Computational Chemistry
• Statistical Mechanics
• Complex Systems Modeling

Background:

• Markov chains model complex system dynamics but suffer from ill-conditioned transition matrices with timescale separation.
• Continuous-time Markov chains (CTMCs) use mean first passage times (MFPTs) as dynamical observables.
• Discrete-time Markov chains (DTMCs) are often estimated from simulation data, e.g., in Markov state models.

Purpose of the Study:

• Generalize graph transformation (GT) for numerically stable computation in discrete-time Markov chains (DTMCs).
• Develop and analyze dimensionality reduction methods for both CTMCs and DTMCs.
• Propose a novel, numerically stable approach for optimal Markovian coarse-graining, particularly for systems with rare event dynamics.

Main Methods:

• Generalized the graph transformation (GT) algorithm to discrete-time Markov chains (DTMCs).
• Performed detailed numerical analysis of existing dimensionality reduction methods for CTMCs.
• Proposed an alternative GT-based approach to compute intermicrostate MFPTs and derived weighted intermacrostate MFPTs, including an approximation for the strongly metastable limit.

Main Results:

• Demonstrated that existing linear algebra-based dimensionality reduction methods encounter numerical issues due to metastability.
• The proposed GT-based method offers superior numerical stability for computing the optimal reduced Markov chain.
• The inversion of the weighted-MFPT matrix, derived from GT, is better conditioned than in alternative schemes.

Conclusions:

• The generalized GT algorithm provides a numerically stable method for analyzing DTMCs and their dimensionality reduction.
• The GT approach enables optimal Markovian coarse-graining, overcoming limitations of existing methods for systems with rare event dynamics.
• This work facilitates more accurate model interpretation and computation for complex systems exhibiting timescale separation.