In the paper “Concentration inequalities for Markov chains by Marton couplings and spectral methods”, https://projecteuclid.org/euclid.ejp/1465067185, D. Paulin defines the pseudo-spectral gap for any finite Markov chain as follows. Let $ P$ be an ergodic finite Markov chain represented by a row-stochastic matrix, and let $ P^*$ denote its time reversal: $ $ P^*(x,y) = \frac{ P(y,x) \pi(y)}{\pi(x)},$ $ where $ \pi$ is the (unique) stationary distribution of $ P$ . Then the pseudo-spectral gap of $ P$ is defined as $ $ \tilde\gamma(P):= \max_{k\ge1} \gamma( (P^*)^kP^k) / k $ $ where $ \gamma(\cdot)$ denotes the ordinary spectral gap of the reversible Markov chain supplied in the argument.

Now it is straightforward to efficiently compute lower bounds on $ \tilde\gamma(P)$ , and for many purposes this suffices. Suppose, however, one actually wanted to compute this quantity to some fixed precision. How would one effectively do that?