Finding metastabilities in reversible Markov chains based on incomplete sampling

Konstantin Fackeldey, Amir Niknejad, and Marcus Weber. "Finding metastabilities in reversible Markov chains based on incomplete sampling." Special Matrices 5.1 (2017): 73-81. <http://eudml.org/doc/288148>.

@article{KonstantinFackeldey2017,
abstract = {In order to fully characterize the state-transition behaviour of finite Markov chains one needs to provide the corresponding transition matrix P. In many applications such as molecular simulation and drug design, the entries of the transition matrix P are estimated by generating realizations of the Markov chain and determining the one-step conditional probability Pij for a transition from one state i to state j. This sampling can be computational very demanding. Therefore, it is a good idea to reduce the sampling effort. The main purpose of this paper is to design a sampling strategy, which provides a partial sampling of only a subset of the rows of such a matrix P. Our proposed approach fits very well to stochastic processes stemming from simulation of molecular systems or random walks on graphs and it is different from the matrix completion approaches which try to approximate the transition matrix by using a low-rank-assumption. It will be shown how Markov chains can be analyzed on the basis of a partial sampling. More precisely. First, we will estimate the stationary distribution from a partially given matrix P. Second, we will estimate the infinitesimal generator Q of P on the basis of this stationary distribution. Third, from the generator we will compute the leading invariant subspace, which should be identical to the leading invariant subspace of P. Forth, we will apply Robust Perron Cluster Analysis (PCCA+) in order to identify metastabilities using this subspace.},
author = {Konstantin Fackeldey, Amir Niknejad, Marcus Weber},
journal = {Special Matrices},
keywords = {Markov State Models; sampling strategy; transition matrix; molecular simulation},
language = {eng},
number = {1},
pages = {73-81},
title = {Finding metastabilities in reversible Markov chains based on incomplete sampling},
url = {http://eudml.org/doc/288148},
volume = {5},
year = {2017},
}

TY - JOUR
AU - Konstantin Fackeldey
AU - Amir Niknejad
AU - Marcus Weber
TI - Finding metastabilities in reversible Markov chains based on incomplete sampling
JO - Special Matrices
PY - 2017
VL - 5
IS - 1
SP - 73
EP - 81
AB - In order to fully characterize the state-transition behaviour of finite Markov chains one needs to provide the corresponding transition matrix P. In many applications such as molecular simulation and drug design, the entries of the transition matrix P are estimated by generating realizations of the Markov chain and determining the one-step conditional probability Pij for a transition from one state i to state j. This sampling can be computational very demanding. Therefore, it is a good idea to reduce the sampling effort. The main purpose of this paper is to design a sampling strategy, which provides a partial sampling of only a subset of the rows of such a matrix P. Our proposed approach fits very well to stochastic processes stemming from simulation of molecular systems or random walks on graphs and it is different from the matrix completion approaches which try to approximate the transition matrix by using a low-rank-assumption. It will be shown how Markov chains can be analyzed on the basis of a partial sampling. More precisely. First, we will estimate the stationary distribution from a partially given matrix P. Second, we will estimate the infinitesimal generator Q of P on the basis of this stationary distribution. Third, from the generator we will compute the leading invariant subspace, which should be identical to the leading invariant subspace of P. Forth, we will apply Robust Perron Cluster Analysis (PCCA+) in order to identify metastabilities using this subspace.
LA - eng
KW - Markov State Models; sampling strategy; transition matrix; molecular simulation
UR - http://eudml.org/doc/288148
ER -