# Spectral gap of a product of Markov processes

For $m \in [N] \equiv \{1,\dots, N\}$, let $Q^{(m)}$ be the generator of a (well-behaved) continuous-time Markov process on a finite state space $[n_m]$. Write $J \equiv (j_1,\dots,j_N) \in \prod_m [n_m]$ with $j_m \in [n_m]$.

The composite Markov generator corresponding to running each of the $N$ processes independently has off-diagonal entries given by $Q^\otimes_{JJ'}=\lim_{\Delta \downarrow 0} \mathbb{P}(J \overset{\Delta}{\rightarrow} J')/\Delta$ for $J \ne J'$, where the probability of a transition from $J$ to $J'$ in a time interval of duration $\Delta$ is indicated. In this limit a.s. at most one of the component processes can execute a transition, so that the only nonzero off-diagonal terms are of the form $Q^\otimes_{JJ'} = Q^{(M)}_{j_M j'_M}$ with $j'_m = j_m$ for $m \ne M$.

What can be said about the spectral gap of $Q^\otimes$ or the mixing time of the underlying process?

Of particular interest is the case $Q^{(m)} \equiv Q$.

I've looked in the most obvious place (Levin, Peres, and Wilmer) and in some less obvious places, and I haven't seen this anywhere (perhaps I'm making a silly oversight). In the literature "product chains" usually mean something rather different than the discrete-time analogue of the above, and in general I expect that any terminology is overloaded. With that in mind, specific references would be most helpful.

• hmm, could you maybe translate it to a purely linear-algebraic question on eigenvalues of Q-matrices? I think you would find more people able to help you then. – Federico Poloni Mar 15 '11 at 22:10
• I have also found recent papers by Ycart and coworkers that touch on this sort of thing. Diaconis and Saloff-Coste have also written a relevant paper. – Steve Huntsman Mar 31 '11 at 20:47

The spectral gap is just the smallest of the spectral gaps of the component chains. The matrix $Q$ can be simply written as the sum of $Q^{(1)}\otimes I\otimes\ldots\otimes I$, $I\otimes Q^{(2)}\otimes I\otimes\cdots\otimes I$ etc.

If the matrix $Q^{(i)}$ has eigenvalues $(\lambda^{(i)}_j)_{j=1}^{n_i}$, then the matrix $Q$ has eigenvalues $\lambda^{(1)}_{i_1}+\lambda^{(2)}_{i_2}+\ldots+\lambda^{(N)}_{i_N}$ (with eigenvectors $e^{(1)}_{i_1}\otimes \cdots \otimes e^{(N)}_{i_N}$).

• I checked the sum formula for $Q$ and the eigenvalues on a small random case and they appear to be correct. I still need to understand how to prove it but it will be instructive to do that myself. Thanks! – Steve Huntsman Mar 16 '11 at 21:27
• I think the only thing to check is that $Q$ is what I said it was. Once you've got that you can just plug in the eigenvectors and see that they have the claimed eigenvalues. Since the number of eigenvectors matches the dimension, this must give the complete spectral decomposition of $Q$. <p> For checking that $Q$ is as claimed, of course it's sufficient just to pick one component. – Anthony Quas Mar 16 '11 at 21:41
• I gather from the literature that this is well known. The key phrase is either "tensor sum" or "Kronecker sum" in conjunction with "Markov". – Steve Huntsman Mar 29 '11 at 22:35

Hi Steve, Does section 12.4 of Levin, Peres, and Wilmer address your question? My first impression is that your problem corresponds to taking the weight $w_i$ in (12.19) of their book as $1/N$. Then the gap according to corollary 12.12 should be $\min_i w_i \gamma_i$ where $\gamma_i$ is the spectral gap of $Q^{(i)}$. Continuous time or discrete time shouldn't make a big difference to the spectral gap, as the former is just the exponentiation of the latter.

• A closer analogue would be the exercise 12.7 they mention. The spectral gap of this discrete-time case is very easily dealt with. But I don't see how it adapts to the continuous-time case. – Steve Huntsman Mar 15 '11 at 22:03
• Actually since you suggested that the off-diagonal block entries of the generator are all zero, due to the fact jumps cannot happen simulatneously in different components, I think your product chain is closer to the independent jump version as in corollary 12.12. Exercise 12.7 describes a chain which when translated into the continuous setting would have simultaneous action in each component. Thus the generator would have nonzero entries everywhere. Is that right? – John Jiang Mar 16 '11 at 1:02
• I guess it depends on what the key property being related is. In my case the archetypal situation is independent copies of the same process, hence my remark about 12.7. But I see your point. – Steve Huntsman Mar 16 '11 at 3:21