Volume 37, pp. 296-306, 2010.

A robust spectral method for finding lumpings and meta stable states of non-reversible Markov chains

Martin Nilsson Jacobi

Abstract

A spectral method for identifying lumping in large Markov chains is presented. The identification of meta stable states is treated as a special case. The method is based on the spectral analysis of a self-adjoint matrix that is a function of the original transition matrix. It is demonstrated that the technique is more robust than existing methods when applied to noisy non-reversible Markov chains.

Full Text (PDF) [542 KB]

Key words

Markov chain, stochastic matrix, metastable states, lumping, aggregation, modularity, block diagonal dominance, block stochastic

AMS subject classifications

15A18, 15A51, 60J10, 65F15

Links to the cited ETNA articles

[7]Vol. 29 (2007-2008), pp. 46-69 David Fritzsche, Volker Mehrmann, Daniel B. Szyld, and Elena Virnik: An SVD approach to identifying metastable states of Markov chains

< Back