Let $\lambda_k,\mu_k\in\mathbb R_{\ge0}$ $(k\ge1)$ be nonnegative real numbers, 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 Math.StackExchange post.)

For example, 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, for which parameters $\lambda_k,\mu_k$ does such a Markov chain exist? I have heard that the Hille-Yoshida theorem may be helpful and we need a ``dissipative" condition on the growth rate of the terms $Q(n,m).$ However, I don't know how to apply such a theorem here.

In addition, for which parameters $\lambda_k,\mu_k$ does there exist such a Markov chain with all the regularity properties that are important for applications? (E.g., conservative, standard (maybe?), maybe more....)

I have leafed through parts of Anderson's Continuous-Time Markov Chains, Karlin & Taylor's Second Course and Ethier & Kurtz's Markov Processes, but none of these books contains anything directly helpful.

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.


1 Answer 1


Define first the modified rates $$ \tilde Q(n,m) = \frac{Q(n,m)}{n + 1} \, . $$ Clearly, $\tilde Q(n, n+k) = \lambda_k$, and $\tilde Q(n, n-k) \leqslant \mu_k$. Assuming that $\lambda_k$ is summable (otherwise the problem is clearly ill-posed), $\tilde Q$ corresponds to a unique conservative continuous-time Markov chain $\tilde X_t$.

Now $Q$ corresponds to a time-change of $\tilde X_t$: the corresponding Markov chain $X_t$ follows the same path as $\tilde X_t$, but the holding times at $n$ are $(n+1)$ times shorter.

The only thing that can go wrong with $X_t$ is a finite-time explosion: if $\tilde X_t$ goes to infinity too fast, then $X_t$ may diverge to infinity in finite time. More precisely, the life-time of $X_t$ is $$ \tau = \int_0^\infty \frac{1}{\tilde X_t + 1} \, dt . $$ Thus, your question can be phrased equivalently: when is $\tau$ infinite almost surely?

  • If $k \lambda_k$ is a summable sequence, then it is not very difficult to show that $\limsup (\tilde X_t / t) < \infty$, and consequently $\tau = \infty$. This requires a pointwise comparison of $\tilde X_t$ with a continuous-time random walk that only has positive jumps with rates $\lambda_k$, plus the strong law of large numbers.

  • If, on the other hand, $\mu_k = 0$ for $k$ large enough (or at least $\mu_k$ decays sufficiently fast) and $\lambda_k \asymp k^{-1-\alpha}$ for some $\alpha \in (0, 1)$, then it can be proved that $\tilde X_t$ is of the order $t^{1/\alpha}$, and consequently $\tau$ is infinite.

  • However, if $\mu_k$ decays sufficiently slowly (or perhaps grows sufficiently fast), it can well compensate the slow decay of $\lambda_k$. Here, I suppose, things get complicated (and interesting!).

Edited: a note on the construction of $\tilde X_t$.

Suppose that $\lambda_k$ is a summable sequence. Then the overall transition rates from state $n$: $$Q(n) = \sum_{m \ne n} \tilde Q(n, m) = \sum_{k = 1}^\infty \lambda_k + \sum_{k = 1}^n \frac{n + 1 - k}{n + 1} \mu_k$$ are finite.

Consider the usual construction of a Markov chain: let $E_n$ be a sequence of standard exponentially distributed random variables, let $Z_n$ be a discrete-time Markov chain with transition probabilities $(Q(n))^{-1} \tilde Q(n, m)$ (or zero if $n = m$), define $$ T_n = \sum_{j = 0}^{n - 1} \frac{E_j}{Q(Z_j)} \, , $$ and $$ \tilde X_t = Z_n \qquad \text{for $t \in [T_n, T_{n+1})$.}$$ In other words, $\tilde X_t$ follows the path of $Z_n$, with state-dependent holding times given by $E_n / Q(Z_n)$.

If $T_n$ go to infinity as $n \to \infty$, then it is a standard exercise to verify that $\tilde X_t$ is a continuous-time Markov chain (and this is exactly how these are introduced in some textbooks; I do not have a reference off the top of my head, though). Thus, we need to verify that indeed $T_n \to \infty$ as $n \to \infty$.

This is true in greater generality: if the overall transition rate of positive jumps, $$\sum_{m > n} \tilde Q(n, m),$$ is bounded as $n \to \infty$. Perhaps there is a neat, single-line argument for that. A somewhat involved proof goes roughly as follows.

Let $n_1 < n_2 < \ldots$ be the enumeration of all positive jumps of $Z_n$, that is, all $n$ such that $Z_n > Z_{n-1}$. Then it is a nice (but rather technical) exercise to see that $T_{n_{j+1}} - T_{n_j}$ (the waiting time for a positive jump of $\tilde X_t$) is exponentially distributed, with mean $(\sum_{k = 1}^\infty \lambda_k)^{-1}$. (Note that in the more general situation described above, $T_{n_{j+1}} - T_{n_j}$ is no longer exponentially distributed, but it is bounded from below by some exponentially distributed random variable with a fixed mean). Therefore, $$ \lim_{n \to \infty} T_n = \sum_{j = 0}^\infty (T_{n_{j+1}} - T_{n_j}) = \infty $$ almost surely, as desired.

  • $\begingroup$ Why is the problem ill-posed if $\lambda_k$ is not summable? I don't see how. $\endgroup$ Commented Jun 5, 2020 at 14:08
  • $\begingroup$ And could you elaborate on why $\tilde Q$ corresponds to a unique conservative continuous-time Markov chain if $\lambda_k$ is summable? $\endgroup$ Commented Jun 5, 2020 at 14:22
  • $\begingroup$ @xFioraMstr18: The holding time at $n$ is exponential with mean $(\sum_{m\ne n} Q(n,m))^{-1}$. Regarding the other question: if $\lambda_k$ and $\mu_k$ are summable, then the holding time of $\tilde{X}_t$ at any state $n$ has mean greater than a constant, and so the usual construction of a continuous-time Markov chain can be applied. If $\mu_k$ are not summable, the construction is more involved: essentially one shows that the exit times from $\{1, 2, \ldots, N\}$ diverge to infinity as $N \to \infty$. Unfortunately I do not have enough time now to elaborate. $\endgroup$ Commented Jun 5, 2020 at 14:29
  • $\begingroup$ Okay, thanks! And if in the future you could return to elaborate further (if you are compelled), I would greatly appreciate it. $\endgroup$ Commented Jun 5, 2020 at 14:47

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.