1
$\begingroup$

Let $\lambda_k,\mu_k\in\mathbb R_{\ge0}$ $(k\ge1)$ be nonnegative real numbers such that $\sum_{k=1}^\infty k\lambda_k<\infty,$ let $S=\mathbb Z_{\ge0}$ be the nonnegative integers, let $T=\mathbb R_{\ge0}$ be the nonnegative real numbers and consider the continuous-time Markov chain $X=(X_t)_{t\in T}$ on $S$ with rates $$Q(n,n+k)=(n+1)\lambda_k\quad(k\ge1),\qquad Q(n,n-k)=(n+1-k)\mu_k\quad(1\le k\le n).$$ (This Markov chain appears in biology as a model of the length of an evolving DNA sequence (Miklós et. al. 2004). I have also examined some properties of this process in a previous Math.StackExchange post.)

In addition, assume $X$ is irreducible and reversible. Next, let $A=\{k\in\mathbb Z_{\ge1}:\mu_k\ne0\}.$ Then it can be shown that the following conditions hold: (1) $\forall k\in\mathbb Z_{\ge1}\quad\lambda_k=0\leftrightarrow\mu_k=0;$ (2) $\gcd A=1;$ and (3) $\forall j,k\in A\quad r_j^{1/j}=r_k^{1/k}<1.$ The converse can also be shown; if (1), (2) and (3) are true, then $X$ must be irreducible and reversible. (The proof of this if-and-only-if condition involves a lot of manipulating detailed-balance equations and a little bit of number theory, in the form of Bezout's lemma and Schur's lemma.)

For example, if $0<\lambda_1=\mu_1$ and if $0=\lambda_k=u_k$ for all integers $k\ge2,$ then we recover the linear birth-death process with immigration with birth rate $\lambda_1,$ death rate $\mu_1$ and immigration rate $\lambda_1,$ whose nonzero rates are $$Q(n,n+1)=(n+1)\lambda_1\quad(n\ge0,k\ge1),\qquad Q(n,n-1)=n\mu_1\quad(n\ge1).$$ Or, for example, given parameters $\mu\in\mathbb R_{>0},\gamma,r\in(0,1),$ we can let $\mu_k=\mu(1-r)^2r^{k-1}$ and $\lambda_k=\mu(1-r)^2\gamma^kr^{k-1}$ for all $k\ge1.$ Both these examples have been used in, and are of interest in, computational biology.

Now, my question is, what is the spectral gap, $\text{gap}(X),$ of $X$?

For the linear birth-death process with immigration mentioned in the above paragraph, we can show the spectral gap is $\mu_1-\lambda_1$ via the "dual variational formula" for reversible irreducible birth-death processes, which reads: Let $X$ with birth rates $b_i$ ($i\in S$) and death rates $d_i$ ($i\in\mathbb Z_{\ge1}$); then $$\text{gap}(X)=\sup_{v\in{\cal V}}\inf_{i\in S}R_i(v),$$ where ${\cal V}=(\mathbb R_{>0})^S$ is the set of strictly-positive-real-valued nonnegative-integer-indexed sequences and where $$R_i(v)=d_{i+1}+b_i-d_i/v_{i-1}-b_{i+1}v_i=\Delta d(i)-\Delta b(i)+d_i(1-v_{i-1}^{-1})+b_{i+1}(1-v_i),$$ where $\Delta d(i)=d_{i+1}-d_i,\Delta b(i)=b_{i+1}-b_i,a_0=0,v_{-1}=1,$ for all $i\in S.$ (This result is Theorem 1.1 in Chen (1996).) Coming back to the linear birth-death process with immigration, note that taking $v=1=(1,1,1,\dots)$ to be the constant sequence with all 1's yields $R_i(v)=\mu_1-\lambda_1$ for all $i\in S,$ and thus $\text{gap}(X)\ge\mu_1-\lambda_1.$ In addition, it turns out that $\mu_1-\lambda_1$ is an eigenvalue, so the bound is sharp, i.e., $\text{gap}(X)=\mu_1-\lambda_1.$

I conjecture that "in general", if $\sum_{k=1}^\infty k\mu_k<\infty$ (a reasonable assumption), then $\text{gap}(X)=\mu-\lambda,$ where $\mu=\sum_{k=1}^\infty k\mu_k$ is "the total deletion rate per site" and $\lambda=\sum_{k=1}^\infty k\lambda_k$ is "the total insertion rate per site". I have no idea how to prove it, though; the coupling is no longer monotone in general, since $X$ can make jumps of size $>\!\!1.$ In addition, I don't know of any generalizations of the Chen's theorem above, so I don't know how to get a lower bound.


Chen, Mufa, Estimation of spectral gap for Markov chains, Acta Math. Sin., New Ser. 12, No. 4, 337-360 (1996). ZBL0867.60038.

Miklós, I., Lunter, G. A., & Holmes, I. (2004). A “long indel” model for evolutionary sequence alignment. Molecular Biology and Evolution, 21(3), 529-540.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.