Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $Q$ be the generator of a well-behaved (not necessarily reversible) Markov process $X$ on $[n] = \{1,\dots,n\}$ and let $Q^\otimes = \sum_{m=1}^N I^{\otimes(m-1)} \otimes Q \otimes I^{\otimes(N-m)}$ be the tensor sum generating $N$ instances of $X$ (see this MO answer). Let the spectrum of $Q$ be $\sigma(Q) = \{\lambda_j\}$. It can be shown that $\sigma(Q^\otimes) = \{\sum_{m=1}^N \lambda_{j_m}\}$.

In particular, the spectral gaps of $Q$ and $Q^\otimes$ coincide.

On the other hand, the exponential decay rate of the variance of $e^{tQ^\otimes}f^\otimes$ is $N$ times the decay rate for the variance of $e^{tQ}f$ (see, e.g. here).

As I understand it in the reversible case the spectral gap and (minimal) decay rate of the variance (given by the infimum of the quotient of the Dirichlet form and the variance itself) are supposed to be the same. But in tensor product land this weird factor of $N$ seems to keep popping up. I thought fleetingly that I understood this apparent contradiction, but now realize that I still don't.

So: if the spectral gap of $Q^\otimes$ equals that of $Q$ and the decay rate for the variance of $e^{tQ^\otimes}f^\otimes$ is $N$ times that for $e^{tQ}f$, how can these various facts(?) be reconciled?

I'm probably just being obtuse, but this issue is really annoying me, and so I'll retroactively award a bounty of 100 points for the best definitive answer that I can understand and that's provided within 24 hours of this question's posting time.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

Working with a single copy of the Markov chain for now, you can simplify the expression for the Dirichlet form as $\mathcal D_Q(f)=-\sum_{j,k}p_jQ_{jk}f_jf_k$ (you obtain this from the previous expression just by noting that the row sums of the $Q$ are 0).

Let $e^{(0)},\ldots,e^{(d-1)}$ be the eigenvectors of your $Q$. Assume reversibility of $Q$. Then $Q$ is self-adjoint with respect to the inner product $\langle f,g\rangle=\sum p_if_ig_i$. This guarantees that the eigenvectors are orthogonal with respect to this inner product. Let $e^{(0)}$ be the eigenvector of 1's (with eigenvalue 0). The other eigenvectors can be chosen to have length 1 with respect to the inner product. They have negative real eigenvalues $\lambda^{(1)}>\ldots>\lambda^{(d-1)}$.

Notice that the Dirichlet form is very simple for $f$'s that are expressed as a sum of eigenvectors: $D_Q(\sum a_i e^{(i)})=\sum a_i^2D_Q(e^{(i)})$ (using the orthogonality properties of $Q$). Further $D_Q(e^{(i)})=-\lambda^{(i)}$ so that $D_Q(\sum a_ie^{(i)})=\sum a_i^2|\lambda_i|$. Also Var($e^{(i)}$) is 1 for $i\ne 0$ and 0 for $i=0$. The minimum ratio of the Dirichlet form to the variance occurs at the non-trivial eigenvector with the smallest absolute eigenvalue.

Define $Q^\otimes=\sum_{i}c_i I^{\otimes(i-1)}\otimes Q\otimes I^{\otimes{n-i}}$ (this is the generalization of what's in your posting with multiple $c$'s). The eigenvectors of $Q^\otimes$ are simply the tensor products of the eigenvectors of $Q$ so that $e^{(i_1)}\otimes \cdots\otimes e^{(i_n)}$ has eigenvalue $c_1\lambda^{(i_1)}+\ldots+c_n\lambda^{(i_n)}$. The variance of each of these eigenvectors is 1 except for the eigenvector $e^{(0)}\otimes\cdots\otimes e^{(0)}$ which has variance 0. Once again the minimum ratio of the Dirichlet form to the variance occurs at the non-trivial eigenvector with the smallest absolute value. Assuming that $c_1\le c_2\le c_3\le\ldots$, this is the eigenvector $e^{(1)}\otimes e^{(0)}\otimes\cdots\otimes e^{(0)}$. In this case the ratio is given by $c_1|\lambda_1|$.

Hopefully this resolves the discrepancy?

share|improve this answer
    
OK, so this shows me that there is a mistake at the very end of my previous self-answer (the non-calculational part), where I wrongly concluded that the minimum ratio was at $e^{(1)\otimes N}$ instead of at $e^{(1)} \otimes e^{(0)\otimes(N-1)}$. I was (unsurprisingly) getting the same factor of $N$ when I computed the variance of $e^{(1)\otimes N}$ and didn't see that I was making the same silly mistake twice. –  Steve Huntsman Apr 22 '11 at 21:01
    
...Restricting to zero mean functions probably influenced this repeated error, because while the $e^{(i)}$ have mean zero for $i > 0$ and so do $e^{(1)\otimes N}$ and $e^{(1)} \otimes e^{(0)\otimes(N-1)}$, $e^{(0)}$ most emphatically does not. Anyway, many thanks for your patient help! I'll issue the bounty and select this answer when it becomes available. –  Steve Huntsman Apr 22 '11 at 21:02
add comment

Isn't it that the spectral gap arises from eigenvectors like $e_1\otimes e_0\otimes e_0\otimes\cdots \otimes e_0$ while the variance arises from $e_1\otimes e_1\otimes \cdots \otimes e_1$ (so in the first case you get just one factor of $e^{-\lambda t}$ whereas in the second case you get $n$ such factors)?

share|improve this answer
    
OK, but suppose $Q$ is reversible for convenience (so that $Q^\otimes$ is too). Isn't "spectral gap = decay rate of variance" supposed to hold not only for $Q$ but for $Q^\otimes$? –  Steve Huntsman Apr 22 '11 at 4:11
    
What happens if you compute the variance using $e_1\otimes e_0\otimes\cdots\otimes e_0$? Then you get 0 in all the terms except transitions in the first coordinate. I'm guessing what's wrong is the answer to your previous bounty Q, but I will try and think a bit more about this... –  Anthony Quas Apr 22 '11 at 6:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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