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

If $Q$ is the generator of a well-behaved continuous-time Markov process on a finite state space and $p$ is the invariant distribution, the corresponding Dirichlet form is $\mathcal{D}_Q(f) := \frac{1}{2} \sum_{j,k} p_j Q_{jk} (f_j - f_k)^2$. Write $Var_p(f)$ for the variance of $f$. In studies of convergence it is of great interest to find the infimum of $\mathcal{D}_Q/Var_p$ (where the denominator is restricted to be nonzero). W/l/o/g it suffices to consider $f$ for which $\sum_j p_j f_j = 0$, so that $Var_p(f) = \sum_j p_j f_j^2$.

If $Q^{(m)} = c_m Q$ for $c_m > 0$ and $Q^\otimes = \sum_m I^{\otimes(m-1)} \otimes Q^{(m)} \otimes I^{\otimes(N-m)}$, it can be shown that $\mathcal{D}_{Q^\otimes}(f^{\otimes N})/Var_{p^{\otimes N}}(f^{\otimes N}) = N \langle c \rangle \mathcal{D}_Q(f)/Var_{p}(f)$, where the arithmetic mean is indicated. Which is great and all, but:

Is the infimum of $\mathcal{D}_{Q^\otimes}/Var_{p^{\otimes > N}}$ actually attained for an argument of the form $f^{\otimes N}$?

I feel like the answer should be trivial but for some reason I'm not seeing it.

UPDATE: Given my answer below, I will award the bounty to the best answer that deals with some combination of finding/addressing any errors in this answer and reconciling the implied result for mixing times of tuples of Markov processes with this paper (PDF) of Ycart and coworkers

viz., if the cutoff and mixing times are equivalent as claimed, why do they appear to grow differently with $N$?

For an $N$-tuple of identical processes, the result (Lemma 2 and Theorem 3) of Ycart et al. seems to indicate that the ($L^2$) mixing time should go as $\frac{1}{2} \log N$ times the mixing time of a single process. The calculations here seem to indicate that the mixing time goes as $1/N$ times the mixing time of a single process. Clearly I am mistaken somewhere.

share|improve this question
    
PS. Numerical experiments on a simple 2-dimensional $Q$ and $N=2$ suggest that (at least in one case) the answer is yes. But I still don't see how to prove it. –  Steve Huntsman Apr 5 '11 at 23:16
1  
This is put to bed at mathoverflow.net/questions/62577 –  Steve Huntsman Apr 22 '11 at 21:07
add comment

1 Answer

UPDATE: There is an error at the end of this answer, addressed here and in comments. I am leaving the original answer here because it is discussed elsewhere.


Ugh, this turned out to be a nasty bit of brute forcing and I found myself grappling with notation before I got it (I think) right.

Write $J := (j_1,\dots,j_N)$ and $p^\otimes := p^{(1)} \otimes \dots \otimes p^{(N)}$ for the tensor product measure. Besides the obvious variations of the above notation, write $f^\otimes_{J^\land_m} := \prod_{\ell \ne m} f^{(\ell)}_{j_\ell}$. Finally, write $\partial_\ell \equiv \partial_{f_\ell}$.

Now for $\mbox{Var}_p \ne 0$ we have

$\partial_\ell \left( \mathcal{D}/\mbox{Var}_p \right) = 0 \iff -\partial_\ell \mathcal{D} \cdot \mbox{Var}_p + \mathcal{D} \cdot \partial_\ell \mbox{Var}_p = 0$

and

$\partial_\ell \mathcal{D} = -\sum_j \left( p_j Q_{j\ell} + p_\ell Q_{\ell j} \right) f_j,$

while if we assume w/l/o/g that $\sum_j p_j f_j = 0$ throughout then $\partial_\ell \mbox{Var}_p = 2p_\ell f_\ell$.

It follows that the equalities in the first equation above are equivalent to

$\sum_j (p_j Q_{j\ell} + p_\ell Q_{\ell j})f_j \cdot \mbox{Var}_p(f) + 2\mathcal{D}(f) \cdot p_\ell f_\ell = 0$.

For $F: [\dim Q^\otimes] \rightarrow \mathbb{R}$ (not necessarily of the form $f^\otimes \equiv f^{\otimes N}$), set $(F^\land_{L^\land_m})_j := F_{\ell_1,\dots,\ell_{m-1},j,\ell_{m+1},\dots,\ell_N}$. Now if $Q^{(m)} = c_m Q$ then

$\mathcal{D}^\otimes(F) = \frac{1}{2} \sum_{JK} p^\otimes_J Q^\otimes_{JK} (F_J - F_K)^2 = \frac{1}{2} \sum_{m,J^\land_m,j_m,k} p^\otimes_{J^\land_m} p_{j_m} c_m Q_{j_m k} \left ( (F^\land_{J^\land_m})_{j_m} - (F^\land_{J^\land_m})_{k} \right )^2$

$= \sum_m c_m \sum_{J^\land_m} p^\otimes_{J^\land_m} \mathcal{D}(F^\land_{J^\land_m})$

and

$\partial_L \mathcal{D}^\otimes(F) = -\sum_J (p^\otimes_J Q^\otimes_{JL} + p^\otimes_L Q^\otimes_{LJ}) F_J = -\sum_m c_m p^\otimes_{L^\land_m} \sum_j (p_j Q_{j \ell_m} + p_{\ell_m} Q_{\ell_m j})(F^\land_{L^\land_m})_j$.

Since $([f^\otimes]^\land_{L^\land_m})_j = f_j \cdot f^\otimes_{L^\land_m}$ and $\mathcal{D}([f^\otimes]^\land_{J^\land_m}) = (f^\otimes_{J^\land_m})^2 \cdot \mathcal{D}(f)$ it follows from the above that

$\left ( -\partial_L \mathcal{D}^\otimes \cdot \mbox{Var}_{p^\otimes} + \mathcal{D}^\otimes \cdot \partial_L \mbox{Var}_{p^\otimes} \right ) |_{f^\otimes}$

$= \sum_m c_m p^\otimes_{L^\land_m} \sum_j (p_j Q_{j \ell_m} + p_{\ell_m} Q_{\ell_m j})f_j \cdot f^\otimes_{L^\land_m} \cdot \mbox{Var}_p^N(f) + \sum_m c_m \sum_{J^\land_m} p^\otimes_{J^\land_m} (f^\otimes_{J^\land_m})^2 \cdot \mathcal{D}(f) \cdot 2 p^\otimes_L f^\otimes_L$

$= \mbox{Var}_{p}^{N-1}(f) \cdot \sum_m c_m p^\otimes_{L^\land_m} f^\otimes_{L^\land_m} \cdot \left [ \sum_j (p_j Q_{j \ell_m} + p_{\ell_m} Q_{\ell_m j})f_j \cdot \mbox{Var}_{p}(f) + 2\mathcal{D}(f) \cdot p_{\ell_m} f_{\ell_m} \right ]$.

Comparison with above shows that the term in brackets is zero iff $\partial_{\ell_m} \left( \mathcal{D}/\mbox{Var}_{p} \right) = 0$. Inspection of the above equations also shows that $\mathcal{D}^\otimes/\mbox{Var}_{p^\otimes}$ has a local minimum (resp. maximum) at $f^\otimes$ iff $\mathcal{D}/\mbox{Var}_p$ has a local minimum (resp. maximum) at $f$. Finally, the uniqueness of extrema follows from viewing $\mathcal{D}/\mbox{Var}_p$ as the (well-behaved) quotient of two homogeneous quadratic polynomials in the entries of $f$.

share|improve this answer
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.