2
$\begingroup$

I would like to calculate the mixing time of a continuous time starting from the rate matrix and not necessarily assuming that the time in between jumps have rate 1 - all I have is the (finite dimensional) transition rate matrix $Q$ for this system. I am fine with other basic assumptions about the chain (e.g., irreducible). The only references I can find (e.g., here) do not seem to cover this case. Is there a theorem or transformation that covers this case?

UPDATE It seems that by uniformization, I can turn my continuous time Markov chain with different jump rates $\gamma_i$ for each element in my state space $\Omega$ (defined by the generator matrix $Q$) into a continuous time Markov chain with transition matrix $P$ (which is now not a generator matrix) and jump rate $\gamma \geq \sup_i | \gamma_i |$. So, my question above is really:

How can the methods for finding mixing times with transition times distributed as an exponential random variable of mean 1 be generalized to the case of where the transition time are distributed according to an exponential random variable with arbitrary (positive, real valued) mean $\gamma$?

Really, I think this just means transforming a CTMC with rate $\gamma$ into a CTMC with rate 1 that has the same dynamics, but I don't really know how to do this.

UPDATE I figured it out: uniformization let's you choose any value for the rate, larger than the slowest rate, which works out in my case, since my rates are all less than 1.

$\endgroup$

1 Answer 1

3
$\begingroup$

Given a (not necessarily reversible but well-behaved) Markov generator $Q$ with invariant distribution $p$, the corresponding Dirichlet form is

$\mathcal{E}(f) := \frac{1}{2} \sum_{j,k} p_j Q_{jk} (f_j-f_k)^2.$

Write

$\lambda_* := \inf_{f} 2\mathcal{E}(f)/\mbox{Var}_{p}(f),$

where the infimum is over $f$ s.t. $\text{Var}_{p}(f) \ne 0$. Now $\lambda_*^{-1}$ is the $L^2$ mixing time.

Another reference than the one you cite is Montenegro and Tetali, "Mathematical Aspects of Mixing Times in Markov Chains", available as of this writing here (PDF).

$\endgroup$
1
  • $\begingroup$ This looks great, but I'm not super up on some of the notation: what is $f$ here? Is it just an function on the state space? I'm also having a bit of a hard time finding where this theorem is in the attached document - is it in there? If not, where is it from? I really appreciate the advice on this. $\endgroup$
    – Danny W.
    Nov 3, 2014 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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