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.


1 Answer 1


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.$


$\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).

  • $\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .