Improved Estimation of Relaxation Time in Non-reversible Markov Chains

We show that the minimax sample complexity for estimating the pseudo-spectral gap of an ergodic Markov chain in constant relative error is of the order of $$\tilde{\Theta}\left( \frac{1}{\gamma_{\mathsf{ps}} \pi_\star} \right),$$ recovering the known bound in the reversible setting for estimating the absolute spectral gap [Hsu et al., 2019], and resolving an open problem of Wolfer and Kontorovich [2019]. Furthermore, we strengthen the known empirical procedure by making it fully-adaptive to the data, thinning the confidence intervals and reduce the computational complexity. Along the way, we derive new properties of the pseudo-spectral gap and introduce the notion of a reversible dilation of a stochastic matrix.