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?


My answer below shows that for any range $k\in[1,K]$, one gets both upper and lower bounds on $\tilde\gamma(P)$. However, the original question remains: If one wants to compute this quantity to within (say, additive) error $\epsilon$, how large must $K$ be behave as a function of $\epsilon$?

  • $\begingroup$ You could use Matlab function eigs mathworks.com/help/matlab/ref/… $\endgroup$ – Nawaf Bou-Rabee Jan 22 '18 at 21:30
  • $\begingroup$ Is there a function to compute the maximum over infinitely many k? $\endgroup$ – Aryeh Kontorovich Jan 22 '18 at 21:30
  • $\begingroup$ I was thinking you could recursively compute the leading two eigenvalues using eigs and hopefully the maximum converges quick enough. What do you think? $\endgroup$ – Nawaf Bou-Rabee Jan 22 '18 at 21:33
  • 2
    $\begingroup$ Oh it does :) -- but I was hoping for a formal result :) $\endgroup$ – Aryeh Kontorovich Jan 22 '18 at 21:34
  • $\begingroup$ For example, it seems that the sequence is unimodal in k. Even establishing that would be enormously useful. $\endgroup$ – Aryeh Kontorovich Jan 22 '18 at 21:35

Here's a crude approach. Since $\gamma(\cdot)$ is always in the range $[0,1]$ for a reversible Markov chain, it follows that $\gamma((P^*)^kP^k)/k\le1/k$. Thus, computing this value for $k\in[1,K]$ in fact gives both upper and lower bounds on $\tilde\gamma(P)$.

  • 1
    $\begingroup$ This remark solves the problem (with no time bound): let $\delta$ be the value for $k=1$. Then it's enough to compute for $k\leq 1/\delta$. $\endgroup$ – Lior Silberman Jan 23 '18 at 15:38
  • 1
    $\begingroup$ I meant that your remark was the solution,, not mine. $\endgroup$ – Lior Silberman Jan 23 '18 at 15:42
  • $\begingroup$ @LiorSilberman good point! Still, one might hope for a bound on $k$ that depends only on the desired precision $\epsilon$, and not on properties of $P$. After all, in "my solution", small $\delta$ requires large $k$... $\endgroup$ – Aryeh Kontorovich Jan 23 '18 at 17:50
  • $\begingroup$ Old question I know but I found it interesting now. Your solution works with only the precision as an input, since if you calculate for $k\leq 1/\epsilon$ you get something within the right precision $\endgroup$ – Kweku A Jan 24 '20 at 15:08
  • $\begingroup$ Also I don't think you can much improve that bound. Consider a `nearly periodic random walk': $j \to j+1 \mod n$ deterministically for $j\neq 0$, pausing at 0 with probability 1/2. The spectral gap is I think of order $1/n$ where $n$ is the number of elements in the state space (the characteristic polynomial is $(\lambda-1)(1+\lambda + ... + \lambda^{n-2} +2\lambda^{n-1})/2$; roots of the second factor are roughly 1/n perturbed from roots of unity) but $(P^*)^n P^n$ is roughly a matrix of 1s so has spectral gap $~1$. So you need to calculate up the $n$th term if you want precision $1/(2n)$. $\endgroup$ – Kweku A Jan 24 '20 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.