Computationally Efficient Estimation of the Spectral Gap of a Markov Chain

• Published in: Performance evaluation review 2019-12, Vol.47 (1), p.98-100
• Main Authors: Combes, Richard, Touati, Mikael
• Format: Article
• Language: English
• Subjects: Mathematics of computing; Mathematics of computing / Probability and statistics; Mathematics of computing / Probability and statistics / Probabilistic representations; Mathematics of computing / Probability and statistics / Probabilistic representations / Markov networks; Mathematics of computing / Probability and statistics / Stochastic processes; Mathematics of computing / Probability and statistics / Stochastic processes / Markov processes; Theory of computation; Theory of computation / Design and analysis of algorithms; Theory of computation / Models of computation; Theory of computation / Theory and algorithms for application domains; Theory of computation / Theory and algorithms for application domains / Machine learning theory; Theory of computation / Theory and algorithms for application domains / Machine learning theory / Markov decision processes
• ISSN: 0163-5999
• DOI: 10.1145/3376930.3376993

We consider the problem of estimating from sample paths the absolute spectral gap 1 - λ of a reversible, irreducible and aperiodic Markov chain (Xt )t€N over a finite state space Ω. We propose the UCPI (Upper Confidence Power Iteration) algorithm for this problem, a low-complexity algorithm which estimates the spectral gap in time O(n) and memory space O((lnn)2) given n samples. This is in stark contrast with most known methods which require at least memory space O((ln n)2), so that they cannot be applied to large state spaces. Furthermore, UCPI is amenable to parallel implementation.