2
$\begingroup$

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?

EDIT

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$?

Improve this question
$\endgroup$
5
  • $\begingroup$ You could use Matlab function eigs mathworks.com/help/matlab/ref/… $\endgroup$
    – Nawaf Bou-Rabee
    Commented Jan 22, 2018 at 21:30
  • $\begingroup$ Is there a function to compute the maximum over infinitely many k? $\endgroup$
    – Aryeh Kontorovich
    Commented Jan 22, 2018 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
    Commented Jan 22, 2018 at 21:33
  • 2
    $\begingroup$ Oh it does :) -- but I was hoping for a formal result :) $\endgroup$
    – Aryeh Kontorovich
    Commented Jan 22, 2018 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
    Commented Jan 22, 2018 at 21:35

1 Answer 1

Reset to default
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$
5
  • 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
    Commented Jan 23, 2018 at 15:38
  • 1
    $\begingroup$ I meant that your remark was the solution,, not mine. $\endgroup$
    – Lior Silberman
    Commented Jan 23, 2018 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
    Commented Jan 23, 2018 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
    Commented Jan 24, 2020 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
    Commented Jan 24, 2020 at 15:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .