7
$\begingroup$

Context

Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by

$$\xi = 1 - \lambda_\max$$

where $\lambda_\max = \max\{\lambda_2, -\lambda_n\}$, i.e. the second largest eigenvalue of the transition matrix $P$.

This is related to the mixing time of the Markov chain; the bigger the spectral gap, the faster the convergence to the stationary distribution.

Problem

Now suppose I have two such chains on the same state space, with transition matrices $P_1$ and $P_2$, and spectral gaps $\xi_1$ and $\xi_2$.

Furthermore, let me define a new Markov chain with transition matrix:

$$ P' = \alpha P_1 + (1-\alpha) P_2 $$

in other words, each transition is done according to $P_1$ with probability $\alpha$, and according to $P_2$ with probability $1 - \alpha$.

Now the question is, what can I say about the spectral gap of $P'$? Intuitively, I would guess that the spectral gap is concave, i.e.

$$\xi' \ge \alpha \xi_1 + (1-\alpha) \xi_2$$

But I have no idea how to show this... Any help is appreciated!

$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

This is not an easy thing to prove and in general the spectral gap of a matrix does not exceed the convex combination of its component gaps. It's a hard problem and an active area of research. However, if one of your Markov chains happens to be rank 1, you can apply Corollary 1 of http://arxiv.org/pdf/math/0307056v1.pdf. The earlier results in this paper can help you prove additional useful results, too.

One can prove your conjecture in the case that both chains share the same limiting distribution. (Sort of trivial and left as exercise.)

$\endgroup$
3
  • $\begingroup$ Many thanks. You say it's an active area of research; would you happent to have some additional references? $\endgroup$
    – lum
    Sep 4, 2014 at 13:29
  • $\begingroup$ Sure, but there's no one resource. You'll likely be able to come up with some examples by playing with numerics. Although I'd like to avoid citing myself, the following contains an example where you can have an exponentially small gap arising from the convex combination of two matrices that individually have finite sized gaps, you can see section 3 of my recent paper: arxiv.org/abs/1405.7552. In this example, one of the matrices is a graph laplacian (which could have been written as a markov chain) and the other is not. Nonetheless, it might be instructive. $\endgroup$
    – Michael Jarret
    Sep 4, 2014 at 13:51
  • $\begingroup$ I should have added that if you want additional resources you can feel free to contact me at the email address listed in that paper. $\endgroup$
    – Michael Jarret
    Sep 4, 2014 at 14:00

You must log in to answer this question.

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