Cargando…

Analysing ill-conditioned Markov chains

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-con...

Descripción completa

Detalles Bibliográficos
Autores principales: Woods, Esmae J., Kannan, Deepti, Sharpe, Daniel J., Swinburne, Thomas D., Wales, David J.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: The Royal Society 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10200351/
https://www.ncbi.nlm.nih.gov/pubmed/37211032
http://dx.doi.org/10.1098/rsta.2022.0245
_version_ 1785045112656494592
author Woods, Esmae J.
Kannan, Deepti
Sharpe, Daniel J.
Swinburne, Thomas D.
Wales, David J.
author_facet Woods, Esmae J.
Kannan, Deepti
Sharpe, Daniel J.
Swinburne, Thomas D.
Wales, David J.
author_sort Woods, Esmae J.
collection PubMed
description 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’.
format Online
Article
Text
id pubmed-10200351
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher The Royal Society
record_format MEDLINE/PubMed
spelling pubmed-102003512023-05-22 Analysing ill-conditioned Markov chains Woods, Esmae J. Kannan, Deepti Sharpe, Daniel J. Swinburne, Thomas D. Wales, David J. Philos Trans A Math Phys Eng Sci Articles 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’. The Royal Society 2023-07-10 2023-05-22 /pmc/articles/PMC10200351/ /pubmed/37211032 http://dx.doi.org/10.1098/rsta.2022.0245 Text en © 2023 The Authors. https://creativecommons.org/licenses/by/4.0/Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, provided the original author and source are credited.
spellingShingle Articles
Woods, Esmae J.
Kannan, Deepti
Sharpe, Daniel J.
Swinburne, Thomas D.
Wales, David J.
Analysing ill-conditioned Markov chains
title Analysing ill-conditioned Markov chains
title_full Analysing ill-conditioned Markov chains
title_fullStr Analysing ill-conditioned Markov chains
title_full_unstemmed Analysing ill-conditioned Markov chains
title_short Analysing ill-conditioned Markov chains
title_sort analysing ill-conditioned markov chains
topic Articles
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10200351/
https://www.ncbi.nlm.nih.gov/pubmed/37211032
http://dx.doi.org/10.1098/rsta.2022.0245
work_keys_str_mv AT woodsesmaej analysingillconditionedmarkovchains
AT kannandeepti analysingillconditionedmarkovchains
AT sharpedanielj analysingillconditionedmarkovchains
AT swinburnethomasd analysingillconditionedmarkovchains
AT walesdavidj analysingillconditionedmarkovchains