Analysing ill-conditioned Markov chains

• DOI: 10.1098/rsta.2022.0245
• Publication Date: 2023-05-21T23:05:16Z
• Authors: Esmae J. Woods; Deepti Kannan; Daniel J. Sharpe; Thomas D. Swinburne; David J. Wales
• Keywords: graph transformation; Markov chains; energy landscapes; Articles; dimensionality reduction; rare events

Discrete state Markov chains in discrete or continuous time are widely used to model phenomena in the social, physical and life sciences. In many cases, the model can feature a large state space, with extreme differences between the fastest and slowest transition timescales. Analysis of such ill-conditioned models is often intractable with finite precision linear algebra techniques. In this contribution, we propose a solution to this problem, namely partial graph transformation, to iteratively eliminate and renormalize states, producing a low-rank Markov chain from an ill-conditioned initial model. We show that the error induced by this procedure can be minimized by retaining both the renormalized nodes that represent metastable superbasins, and those through which reactive pathways concentrate, i.e. the dividing surface in the discrete state space. This procedure typically returns a much lower rank model, where trajectories can be efficiently generated with kinetic path sampling. We apply this approach to an ill-conditioned Markov chain for a model multi-community system, measuring the accuracy by direct comparison with trajectories and transition statistics.This article is part of a discussion meeting issue ‘Supercomputing simulations of advanced materials’.