Graph Transformation Method for Calculating Waiting Times in Markov Chains

Abstract

We describe an exact approach for calculating transition probabilities and waiting times in finite-state discrete-time Markov processes. All the states and the rules for transitions between them must be known in advance. We can then calculate averages over a given ensemble of paths for both additive and multiplicative properties in a non-stochastic and non-iterative fashion. In particular, we can calculate the mean first passage time between arbitrary groups of stationary points for discrete path sampling databases, and hence extract phenomenological rate constants. We present a number of examples to demonstrate the efficiency and robustness of this approach.

58 pages, 10 figures, 1 table and 3 algorithms (given in pseudocode)

References in corpus (8)

• Kinetics of protein-DNA interaction: facilitated target location in sequence-dependent potential
• A Doubly Nudged Elastic Band Method for Finding Transition States
• Monte Carlo with Absorbing Markov Chains: Fast Local Algorithms for Slow Dynamics
• The long reach of DNA sequence heterogeneity in diffusive processes
• Characterizing the network topology of the energy landscapes of atomic clusters
• Kinetic Analysis of Discrete Path Sampling Stationary Point Databases
• Mean first-passage and residence times of random walks on asymmetric disordered chains
• Multifractals of Normalized First Passage Time in Sierpinski Gasket

Cited by in corpus (7)

• Exploring the Free Energy Landscape: From Dynamics to Networks and Back
• Path Factorization Approach to Stochastic Simulations
• The Energy Landscape, Folding Pathways and the Kinetics of a Knotted Protein
• Simulating structural transitions by direct transition current sampling: the example of LJ38
• Analysing kinetic transition networks for rare events
• Constrained Approximation of Effective Generators for Multiscale Stochastic Reaction Networks and Application to Conditioned Path Sampling
• Kinetic network in Milestoning: Clustering, reduction, and transition path analysis