## Spectral gap of a product of Markov processes

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2011 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 2011 at 20:47

## 2 Answers

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 2011 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 2011 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 2011 at 22:35

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 2011 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 2011 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 2011 at 3:21
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9427358508110046, "perplexity_flag": "head"}