# Spectral gap of a Markov chain on the nonnegative integers

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.

• This paper seems not directly relevant. It doesn't give any equalities, only inequalities that may not be sharp. And my model doesn't seem to fit exactly their class of models. For instance, the process I'm describing is "often" not a birth-death process (if $\exists k\in\mathbb Z_{\ge2}\enspace\mu_k\ne0$ then what I'm describing is not a birth-death process). And I don't see how to generalize their results to this case. – xFioraMstr18 Jun 23 '20 at 23:44