# Existence of Markov chain on nonnegative integers with specified rates

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.

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.

• Why is the problem ill-posed if $\lambda_k$ is not summable? I don't see how. Jun 5, 2020 at 14:08
• And could you elaborate on why $\tilde Q$ corresponds to a unique conservative continuous-time Markov chain if $\lambda_k$ is summable? Jun 5, 2020 at 14:22
• @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. Jun 5, 2020 at 14:29
• Okay, thanks! And if in the future you could return to elaborate further (if you are compelled), I would greatly appreciate it. Jun 5, 2020 at 14:47