Markov-modulated infinite-server queues with general service times

Abstract

This paper analyzes several aspects of the Markov-modulated infinite-server queue. In the system considered (i) particles arrive according to a Poisson process with rate $\lambda _i$ when an external Markov process (“background process”) is in state $i$, (ii) service times are drawn from a distribution with distribution function $F_i(\cdot )$ when the state of the background process (as seen at arrival) is $i$, (iii) there are infinitely many servers. We start by setting up explicit formulas for the mean and variance of the number of particles in the system at time $t\ge 0$, given the system started empty. The special case of exponential service times is studied in detail, resulting in a recursive scheme to compute the moments of the number of particles at an exponentially distributed time, as well as their steady-state counterparts. Then we consider an asymptotic regime in which the arrival rates are sped up by a factor $N$, and the transition times by a factor $N^{1+\varepsilon }$ (for some $\varepsilon >0$). Under this scaling it turns out that the number of customers at time $t\ge 0$ obeys a central limit theorem; the convergence of the finite-dimensional distributions is proven.

1 Introduction

Owing to its wide applicability and its attractive mathematical features, the infinite-server queue has been intensively studied. Such a system describes units of work, e.g., particles or customers, arriving at a resource, that stay present for some random duration that is independent of other customers (in that there is no waiting). In the special case that these customers arrive according to a Poisson process with rate $\lambda$, and the sojourn times are i.i.d. random variables with finite mean $1/\mu$—a system commonly referred to as the M/G/$\infty$ queue—it is known that the stationary number of particles in the system has a Poisson distribution with mean $\lambda /\mu$. Also the transient behavior of such an M/G/$\infty$ queue is well understood; e.g. [24, p. 355].

When relaxing the model assumptions mentioned above, several interesting variants arise. In one branch of the literature, for instance, attention has been paid to the case of renewal (rather than Poisson) arrivals [10, 11]. In the present paper, however, we consider a variant in which we introduce some sort of “burstiness” in the arrivals and service times, using the concept of Markov modulation. This means that both the arrival process and the service-time distributions are driven by an external Markov process (“background process”), in the following manner. Let $X(t)$ denote an irreducible continuous-time Markov process defined on a finite state space $\{1,\ldots ,d\}$. When $X(t)=i$, then the (Poissonian) arrival rate at time $t$ equals $\lambda _i$, where ${\varvec{\lambda }}\equiv (\lambda _1,\ldots ,\lambda _d)$ is a vector with nonnegative entries. In addition, it is assumed that the time a particle remains in the system, the service time, has some general distribution with distribution function $F_i(\cdot )$ that depends on the state of the background process as seen upon arrival by the particle.

The resulting model could be called a Markov-modulated  M/G/$\infty$  queue, or an infinite-server queue in a Markov-modulated environment. This type of system is relevant in a broad variety of application domains, ranging from telecommunication networks to biology. The rationale behind using this model in a communication networks setting is that the arrival rate and service times of customers may vary during the day, or on shorter timescales. In the biological context, one could think of mRNA strings being transcribed and degraded in a cell, where these transcriptions typically tend to occur in a clustered fashion; the proposed model captures the key characteristics of this mechanism well, as argued in [23].

A variety of results exist on Markov-modulated single- and many-server queues, whereas the literature on their infinite-server counterpart is, surprisingly, considerably scarcer. In the case of a single server, the key result is that the stationary distribution of the number of customers is of matrix-geometric form [17], so this system can be viewed as a “matrix generalization” of the normal M/M/1 queue where the stationary distribution is scalar-geometric. In [20] the stationary distribution for the case of infinitely many servers is considered; the results are in terms of the factorial moments of the number of customers. More particularly, it is shown that the corresponding distribution is not of matrix-Poisson type; in other words: this system is not the “matrix generalization” of the M/M/$\infty$, which has a scalar-Poisson distribution. A somewhat more general model that includes retrials has been studied in [13].

The case of Markov-modulated renewal (rather than Poisson) arrivals, but exponential service times, is covered in [18]. Related results can be found in [16] as well, where special attention is paid to the autocorrelations in infinite-server systems of various types. Steady-state results for the infinite-server queue with modulated service rates have been derived in [2]. Falin [8] furthermore considers the simultaneous modulation of arrival and service rates and finds the mean number of customers in steady-state.

It should also be noted that introducing burstiness using a Markovian background process is by no means the only way to incorporate a nonhomogeneous arrival rate. Willmot and Drekic [25] apply bulk arrivals with a random bulk size, whereas Economou and Fakinos [7] study arrivals generated by a compound Poisson process, both to find the transient distribution of the number of customers in the system using a generating functions based approach.

D’Auria [5] studies the same model as we do in the present paper. Among several other results, he finds a recursion for the factorial moments of the stationary number of particles in the system. A key observation in his analysis is that the number of particles present has, in stationarity, a Poisson distribution with random parameter. Fralix and Adan [9] focus on the situation that the service times have specific phase-type distributions. In Hellings et al. [12] it was shown that if the transition times of the background process are sped up by a factor $N$, then the arrival process tends (as $N\rightarrow \infty$) to a Poisson process; the queue under consideration then essentially behaves as an M/G/$\infty$ system.

While the above results focus on Markov-modulated infinite-server queues in stationarity, there are considerably fewer results on the associated transient behavior. In [3], we studied both the transient and stationary behavior of a model similar to the one studied in the present paper, viz. the one with exponential service times and a Markovian background process with deterministic transition times. The main focus of [3] lies on specific time scalings. In the first scaling, just the background process’ transition times are sped up by a factor $N$; then it turns out that the distribution of the resulting queueing system converges to that of an appropriate M/M/$\infty$ queue (which has, in steady-state, a Poisson distribution). In the second scaling, the background process jumps at a faster rate than the arrival process: the arrival rates are scaled by a factor $N$ and the transition times by a factor $N^{1+\varepsilon }$ for some $\varepsilon >0$. Under this scaling a central limit result was proven, for both the transient and stationary distribution.

The main contributions of our paper are the following. In the first place we develop in Sect. 2 expressions for the transient mean and variance for the number of particles in the system at time $t\ge 0$. For exponential service times the resulting expressions simplify considerably. In Sect. 3 we exclusively consider the special case of exponential service times: we develop a differential equation that describes the moment generating function of the number of particles in the system, and show how this differential equation facilitates the computation of moments (at an exponentially distributed time epoch, as well as in steady-state). This section also includes a recursive scheme to compute the higher moments. Section 4 considers one of the scalings studied in [3]: the arrival rates $\lambda _i$ are replaced by $N\lambda _i$, while the transition times of the background Markov process are sped up by a factor $N^{1+\varepsilon }$, for some $\varepsilon >0$, where $N$ grows large. The objective is to prove a central limit theorem for the number of particles in the system in a finite-dimensional setting, that is, at multiple points in time. The result is established by first setting up a system of differential equations for the number of particles in the system at multiple points in time in the non-scaled system, then applying the scaling, and then deriving (using Taylor approximations) a limiting differential equation (as $N\rightarrow \infty$) which eventually provides us with the claimed multivariate central limit theorem. Finally, Sect. 5 contains examples demonstrating analytically and numerically the results from Sects. 3 and 4.

2 General results

In full detail, the model can be described as follows. Consider an irreducible continuous-time Markov process $X(t)$ on a finite state space $\{1,\ldots ,d\}$, with $d\in \mathbb{N }$. $X(t)$, often referred to as the background process, has a transition rate matrix given by $Q=\left( q_{ij}\right) _{i,j=1}^d$. The steady-state distribution of $X(t)$ is given by ${\varvec{\pi }}$, being a $d$-dimensional vector with non-negative entries summing to 1, solving ${\varvec{\pi }}Q={\varvec{0}}$. Define $q_i:=-q_{ii}=\sum _{j\ne i}q_{ij}$.

Now consider the embedded discrete-time Markov chain that corresponds to the jump epochs of $X(t)$. It has a probability transition matrix $P=\left( p_{ij}\right) _{i,j=1}^d$, with diagonal elements equalling 0 and $p_{ij}:= q_{ij}/q_i.$ Let $\hat{\pi }_i$ be the stationary probability vector at the jump epochs of $X(t)$; it solves (after normalization to 1) the linear system $\hat{\varvec{\pi }}D_Q^{-1}Q=0$, with $D_Q := \mathrm{diag}\{{\varvec{q}}\}$. The time spent by $X(t)$ in state $i$, denoted $T_i$, is referred to as transition time. $T_i$ has an exponential distribution with mean $1/q_i$. There is the following obvious relation between ${\varvec{\pi }}$ and $\hat{\varvec{\pi }}$:

$$\begin{aligned} \pi _i:=\frac{\hat{\pi }_i\mathbb{E }T_i}{\sum _{j=1}^d\hat{\pi }_j\mathbb{E }T_j} =\frac{\hat{\pi }_i/q_i}{\sum _{j=1}^d\hat{\pi }_j/q_j}. \end{aligned}$$

While the process $X(t)$ is in state $i$, particles arrive according to a Poisson process with rate $\lambda _i\ge 0$, for $i=1,\ldots ,d$. The service times are assumed to be i.i.d. samples distributed as a random variable $B_i$ with mean $1/\mu _i$ if the client was generated when the background process was in state $i$; the corresponding distribution function is $F_i(x):=\mathbb{P }(B_i\le x)$, with $x\ge 0.$ The service times are independent of the background process $X(t)$ and the arrival process. The system we consider is an infinite-server queue, meaning that each particle stays in the system just for the duration of its service time (that is, there is no waiting). In the rest of this section we focus on analyzing the probabilistic properties of the number of particles in the system at given points in time, starting empty. It is assumed that the background process is in stationarity at time $0$.

We start by considering a somewhat different model than the one introduced above, where the relation with our model becomes clear soon. Consider an M/G/$\infty$ queue with (i) a nonhomogeneous arrival process with rate function $\lambda (\cdot )$ (such that the Poissonian arrival rate is $\lambda (s)$ at time $s$), and (ii) a time dependent distribution function $F(s,\cdot )$ (to be interpreted as the probability that a customer that arrives at time $s$ leaves before time $t+s$ is $F(s,t)$). Observe that, conditional on the event that there are $n$ arrivals by time $t$, the joint distribution of the arrival times is that of the order statistics taken from independent random variables with density

$$\begin{aligned} \frac{\lambda (s)}{\Lambda (t)}1_{[0,t]}(s), \end{aligned}$$

where $\Lambda (t)=\int _0^t\lambda (s)\mathrm{d}s$. It now follows that if $M(t)$ is the number of particles in the system at time $t$, starting with an empty system, then with $\bar{F}(\cdot ):=1-F(\cdot )$ we find that $M(t)$ has a Poisson distribution:

$$\begin{aligned} M(t)\stackrel{{\hbox {d}}}{=}{\mathbb{P }}\hbox {ois}\left( \int _0^t\bar{F}(s,t-s)\lambda (s)\mathrm{d}s\right) , \end{aligned}$$

and we note for later that 

$$\begin{aligned} \int _0^t\bar{F}(s,t-s)\lambda (s)\mathrm{d}s=\int _0^t\bar{F}(t-s,s)\lambda (t-s)\mathrm{d}s. \end{aligned}$$

After this general observation, we return to the initial context. Whereas we so far assumed that the input rate function and service-time distribution function were deterministic, we now assume that they are stochastic. More specifically, we use $\lambda _{i}$ for the arrival rate when the background process $X(\cdot )$ is in state $i$, and $F_{i}(\cdot )$ for the distribution function of particles arriving while the background process is in the state $i$.

By conditioning on the sample path of the background process, say $X(s)=f(s)$, we find that $M(t)$ is Poisson distributed with parameter $\int _0^t\bar{F}_{f(t-s)}(s)\lambda _{f(t-s)}\mathrm{d}s$. Then by unconditioning, i.e., averaging over all paths $f(\cdot )$ of the background process, its probability generating function (pgf) equals the moment generating function (mgf) of its random parameter, evaluated at $(z-1)$:

$$\begin{aligned} \mathbb{E }\,z^{M(t)}=\mathbb{E }\exp \left( -(1-z)\int _0^t\bar{F}_{X(t-s)}(s)\lambda _{X(t-s)}\mathrm{d}s\right) ; \end{aligned}$$

see for example [5, p. 226]. Recalling that $X(\cdot )$ is assumed to be stationary, we have the distributional equality $\{X(t+u)|\ u\in \mathbb{R }\}\stackrel{{\hbox {d}}}{=} \{X(u)|\ u\in \mathbb R \}$, so that

$$\begin{aligned} \mathbb{E }\,z^{M(t)}=\mathbb{E }\exp \left( -(1-z)\int _0^t\bar{F}_{X(-s)}(s)\lambda _{X(-s)}\mathrm{d}s\right) , \end{aligned}$$

or, denoting by $\hat{X}(\cdot )$ the time-reversed version of $X(\cdot )$, with $a_i(s):=\lambda _i\bar{F}_i(s)$,

$$\begin{aligned} \mathbb{E }\, z^{M(t)}&=\mathbb{E }\exp \left( -(1-z)\int _0^t\bar{F}_{\hat{X}(s)}(s)\lambda _{\hat{X}(s)}\mathrm{d}s\right) \\&=\mathbb{E }\exp \left( -(1-z)\int _0^ta_{\hat{X}(s)}(s)\mathrm{d}s\right) . \end{aligned}$$

This probability generating function allows us to analyze the mean and variance of $M(t).$ It is immediate that the mean of $M(t)$ equals, cf. [21, Thm. 2.1],

$$\begin{aligned} \mathbb{E }M(t)=\mathbb{E }\int _0^ta_{\hat{X}(s)}(s)\mathrm{d}s=\int _0^t \mathbb{E }a_{\hat{X}(s)}(s)\mathrm{d}s=\sum _{i=1}^d\pi _i\lambda _i\int _0^t\bar{F}_i(s)\mathrm{d}s. \end{aligned}$$

(1)

This evidently converges to $\sum _{i=1}^d \pi _i\varrho _i$ as $t\rightarrow \infty$, where $\varrho _i:=\lambda _i\int _0^\infty \bar{F}_i(s)\mathrm{d}s$ is the traffic intensity when in state $i$.

The variance can be computed as well, as follows. We start with the standard equality (commonly known as the “law of total variance”)

$$\begin{aligned} \mathbb{V }{\mathrm{ar}}(M(t))=\mathbb{E }\left[ \mathbb{V }{\mathrm{ar}}(M(t)|\hat{X})\right] +\mathbb{V }{\mathrm{ar}}\left[ \mathbb{E }(M(t)|\hat{X})\right] . \end{aligned}$$

First notice that $\mathbb{V }{\mathrm{ar}}(M(t)|\hat{X})=\mathbb{E }(M(t)|\hat{X})=\int _0^ta_{\hat{X}(s)}(s)\mathrm{d}s$ because $(M(t)\,|\,\hat{X})$ has a Poisson distribution (as was noted above). Hence,

$$\begin{aligned} \mathbb{E }\left[ \mathbb{V }{\mathrm{ar}}(M(t)|\hat{X})\right] = \mathbb{E }\left[ \mathbb{E }(M(t)\,|\,\hat{X})\right] =\mathbb{E }M(t) =\sum _{i=1}^d\pi _i\lambda _i\int _0^t\bar{F}_i(s)\mathrm{d}s. \end{aligned}$$

The only quantity that remains to be computed is now $\mathbb{V }{\mathrm{ar}}[\mathbb{E }(M(t)|\hat{X})]$. That is done as follows:

$$\begin{aligned} \mathbb{V }{\mathrm{ar}}\left( \int _0^t a_{\hat{X}(s)}(s)\mathrm{d}s\right)&=\int _0^t\int _0^t\mathbb{C }{\mathrm{ov}}\left( a_{\hat{X}(u)}(u),a_{\hat{X}(s)}(s)\right) \mathrm{d}u\,\mathrm{d}s\\&=\sum _{i,j=1}^d\int _0^t\int _0^ta_i(u)a_j(s)\,\mathbb{C }{\mathrm{ov}}\left( 1\{\hat{X}(u)=i\},1\{\hat{X}(s)=j\}\right) \mathrm{d}u\,\mathrm{d}s, \end{aligned}$$

where for $u<s$

$$\begin{aligned} \mathbb{C }{\mathrm{ov}}\left( 1\{\hat{X}(u)=i\},1\{\hat{X}(s)=j\}\right)&=\pi _i\left( e^{\hat{Q}(s-u)}\right) _{ij}-\pi _i\pi _j\nonumber \\&=\pi _j\left( e^{Q(s-u)}\right) _{ji}-\pi _i\pi _j. \end{aligned}$$

(2)

We now make the expressions more explicit for the case where $t$ tends to $\infty .$ With $D_\pi =\mathrm{diag}\{{\varvec{\pi }}\}, Q$ and $\hat{Q}=D_\pi ^{-1} Q^\mathrm{T}D_\pi ^{-1}$ are the transition rate matrices of $X$ and $\hat{X}$, respectively. Let us define the matrix $\Sigma (s)=(\sigma _{ij}(s))_{i,j=1}^d$ through

$$\begin{aligned} \sigma _{ij}(s):=\pi _j\left( e^{Qs}\right) _{ji}-\pi _i\pi _j. \end{aligned}$$

Letting $t\rightarrow \infty$, we obtain

$$\begin{aligned} \mathbb{V }{\mathrm{ar}}\left( \int _0^\infty a_{\hat{X}(s)}(s)\mathrm{d}s\right)&= \sum _{i,j=1}^d\int _0^\infty \int _0^\infty a_i(u)a_j(s)\left( \sigma _{ij}(s-u)1\{s>u\}\right. \\&\left. +\,\sigma _{ji}(u-s)1\{s<u\}\right) \mathrm{d}u\,\mathrm{d}s\\&= \sum _{i,j=1}^d\int _0^\infty \int _0^\infty \left( a_i(u)a_j(u+s)\sigma _{ij}(s)\right. \\&\left. +\,a_i(u+s)a_j(u)\sigma _{ji}(s)\right) \mathrm{d}u\,\mathrm{d}s\\&= 2\sum _{i,j=1}^d\int _0^\infty \int _0^\infty a_i(u)a_j(u+s)\sigma _{ij}(s)\mathrm{d}u\,\mathrm{d}s . \end{aligned}$$

When the service-time distributions are exponential, that is, $\bar{F}_i(t)=e^{-\mu _i t}$, so that $a_i(t)=\lambda _ie^{-\mu _i t}$, we have

$$\begin{aligned} \mathbb{V }{\mathrm{ar}}\left( \int _0^\infty a_{\hat{X}(s)}(s)\mathrm{d}s\right) ={2}\sum _{i,j}\frac{\lambda _i\lambda _j}{\mu _i+\mu _j}\int _0^\infty e^{-\mu _js}\sigma _{ij}(s)\mathrm{d}s. \end{aligned}$$

(3)

We summarize (some of) our findings.

Proposition 1

The transient mean of the number of particles is

$$\begin{aligned} \mathbb{E }M(t)=\mathbb{E }\int _0^ta_{\hat{X}(s)}(s)\mathrm{d}s=\int _0^t \mathbb{E }a_{\hat{X}(s)}(s)\mathrm{d}s =\sum _{i=1}^d\pi _i\lambda _i\int _0^t\bar{F}_i(s)\mathrm{d}s, \end{aligned}$$

whereas the stationary variance is

$$\begin{aligned} \mathbb{V }{\mathrm{ar}}M(\infty )=\sum _{i=1}^d\pi _i \frac{\lambda _i}{\mu _i} + 2\sum _{i,j=1}^d\int _0^\infty \int _0^\infty a_i(u)a_j(u+s)\sigma _{ij}(s)\mathrm{d}u\,\mathrm{d}s, \end{aligned}$$

provided that the system started empty.

We finish this section by performing some explicit calculations for the case that $X$ is reversible and exponential service times; later on we further focus on the situation of $d=2.$ Due to the reversibility, $\pi _iq_{ij}=\pi _j q_{ji}$ for all $i,j\in \{1,\ldots ,d\}$. As a consequence $D_\pi Q = Q^\mathrm{T}D_\pi$, so that the matrix

$$\begin{aligned} D_\pi ^{{1}/{2}} Q D_\pi ^{-{1}/{2}} \end{aligned}$$

is symmetric, and can be written as $G(-\Delta )G^\mathrm{T}$, where $G$ is a (real-valued) orthogonal matrix, and $\Delta =\mathrm{diag}\{{\varvec{\delta }}\}$ is a (real-valued) diagonal matrix (where it is noted that, owing to the background process’ irreducibility all but one entries of ${\varvec{\delta }}$ are strictly positive). It follows that

$$\begin{aligned} Q = (D_\pi ^{-{1}/{2}}G)(-\Delta ) (D_\pi ^{-{1}/{2}}G)^{-1}, \end{aligned}$$

and therefore

$$\begin{aligned} e^{Qs}&= (D_\pi ^{-{1}/{2}}G)(e^{-\Delta s}) (D_\pi ^{-{1}/{2}}G)^{-1}= D_\pi ^{-{1}/{2}}G\,e^{-\Delta s}\, G^\mathrm{T} D_\pi ^{{1}/{2}};\\ (e^{Qs})^\mathrm{T}&= D_\pi ^{{1}/{2}}G\,e^{-\Delta s}\, G^\mathrm{T} D_\pi ^{-{1}/{2}}. \end{aligned}$$

It now follows that

$$\begin{aligned} \Sigma (s) = (e^{Qs})^\mathrm{T}D_\pi -{\varvec{\pi }}{\varvec{\pi }}^\mathrm{T} = D_\pi ^{{1}/{2}}G\,e^{-\Delta s}\, G^\mathrm{T} D_\pi ^{{1}/{2}} -{\varvec{\pi }}{\varvec{\pi }}^\mathrm{T} \end{aligned}$$

is symmetric, and hence for each $i,j\in \{1,\ldots ,d\}$ we can write $\sigma _{ij}(s) = \sum _{k=1}^d c_{ijk} e^{-\delta _k s}-\pi _i\pi _j.$ As a consequence,

$$\begin{aligned} \mathbb{V }{\mathrm{ar}}\left( \int _0^\infty a_{\hat{X}(s)}(s)\mathrm{d}s\right)&={2}\sum _{i,j}\frac{\lambda _i\lambda _j}{\mu _i+\mu _j}\int _0^\infty e^{-\mu _js}\sigma _{ij}(s)\mathrm{d}s\\&= {2}\sum _{i,j,k}\frac{\lambda _i\lambda _j}{\mu _i+\mu _j} \left( \frac{c_{ijk}}{\mu _j+\delta _k}-\frac{\pi _i\pi _j}{\mu _j}\right) . \end{aligned}$$

In the case of $d=2$, we have $\pi _1= q_2/\bar{q}=1-\pi _2$, with $\bar{q} :=q_1+q_2.$ It is readily verified that $\delta _1=0$ and $\delta _2=\bar{q}.$ It requires a standard computation to verify that

$$\begin{aligned} e^{Qs} = \left( \begin{array}{cc}\pi _1+\pi _2e^{-\bar{q}s}&{}\pi _2-\pi _2e^{-\bar{q}s}\\ \pi _1-\pi _1e^{-\bar{q}s}&{}\pi _2+\pi _1e^{-\bar{q}s}\end{array}\right) , \end{aligned}$$

and also

$$\begin{aligned} \int _0^\infty \Sigma (s) \left( \begin{array}{cc}e^{-\mu _1 s}&{}0\\ 0&{}e^{-\mu _2 s}\end{array}\right) \mathrm{d}s = \pi _1\pi _2\left( \begin{array}{rr}(\bar{q}+\mu _1)^{-1}&{}-(\bar{q}+\mu _2)^{-1}\\ -(\bar{q}+\mu _1)^{-1}&{}(\bar{q}+\mu _2)^{-1}\end{array}\right) . \end{aligned}$$

Elementary calculus now yields that (3) equals

$$\begin{aligned} \frac{q_1q_2}{\bar{q}^2}\left( \frac{\lambda _1^2}{\mu _1}\cdot \frac{1}{\bar{q}+\mu _1}+ \frac{\lambda _2^2}{\mu _2}\cdot \frac{1}{\bar{q}+\mu _2}-2\frac{\lambda _1\lambda _2}{\mu _1+\mu _2}\left( \frac{1}{\bar{q}+\mu _1}+\frac{1}{\bar{q}+\mu _2}\right) \right) . \end{aligned}$$

3 Exponential service times

In this section we analyze the special case of exponential service times in greater detail. We set up a system of differential equations for the moment generating function of the transient number of particles in the system. Then this is used to determine the mean and higher moments after an exponential amount of time.

We start this section with some preliminaries and additional notation. Here and in the remaining sections we denote by $M_i(t)$ the number of particles in the system at time $t$, conditional on the background process being in state $i$ at time 0. It is evident that $M_i(t)$ can be written as the sum of two independent components: the number of particles still present at time $t$ out of the original population of size $x_0$ (in the sequel denoted by $\check{M}(t)$), increased by the number of particles that arrived in $(0,t]$ that is still present at time $t$ (in the sequel denoted by $\bar{M}_i(t)$ in case the background process is in state $i$ at time $0$).

Due to the assumption that the service times are exponentially distributed, there are positive numbers $\mu _i$ (for $i=1,\ldots ,d$) such that $\bar{F}_i(t) = e^{-\mu _i t}.$ In the case that the $\mu _i$ are identical (say equal to $\mu >0$), $\check{M}(t)$ follows a binomial distribution with parameters $x_0$ and $e^{-\mu t}$. In the case the $\mu _i$ are not identical, we need to know the number $x_{0,i}$ particles present at time 0 that were generated while the background process was in state $i$. The resulting (independent) random variables $\check{M}_i(t)$ follow binomial distributions with parameters $x_{0,i}$ and $e^{-\mu _i t}$; indeed, $\check{M}(t)=\sum _{i}\check{M}_i(t).$

Given these observations we concentrate in the remainder of this section on the more complicated component of $M(t)$, that is $\bar{M}_i(t)$.

3.1 Differential equation

Recall that we write, for ease of notation, $q_i:=1/\mathbb{E }T_i$, and $q_{ij}:= p_{ij}q_i$ (where $i\not = j$), with $q_{ii}=-q_i$. The main quantity in this subsection is the moment generating function of $\bar{M}_i(t)$:

$$\begin{aligned} \Lambda _i(\vartheta ,t):= \mathbb{E }e^{\vartheta \bar{M}_i(t)}. \end{aligned}$$

Consider a small time period $\Delta t$, and focus on all terms of magnitude $O(\Delta t)$ or larger. In our continuous-time Markov setting, the background process has either zero jumps (with probability $1-q_i\Delta t+o(\Delta t)$), or a jump to state $j\ne i$ (with probability $q_{ij}\Delta t + o(\Delta t)$); the probability of more than one transition is $o(\Delta t)$ (see for instance [19, Thm. 2.8.2]).

Note that

$$\begin{aligned} \Lambda _i(\vartheta ,t)&= \sum _{k=0}^{\infty } e^{-\lambda _i \Delta t} \frac{(\lambda _i \Delta t)^k}{k!} \left( p_i(\vartheta ,t)\right) ^k \nonumber \\&\quad \times \left( \sum _{j \ne i} q_{ij}\Delta t \,\Lambda _j(\vartheta ,t-\Delta t) + \left( 1 - \sum _{j \ne i} q_{ij}\Delta t \right) \Lambda _i(\vartheta ,t-\Delta t) \right) \nonumber \\&\quad + O\left( (\Delta t)^2\right) ; \end{aligned}$$

(4)

here $p_i(\vartheta ,t)$ is the mgf of a random variable distributed on $\{0,1\}$, indicating whether a particle arriving in the time period $(0, \Delta t)$ is still present at $t$. It is seen that the value 1 occurs with probability

$$\begin{aligned}&\int _0^{\Delta t} \frac{1}{\Delta t} \left( \int _{t-u} ^{\infty } \mu _i e^{-\mu _i v} \mathrm{d}v \right) \mathrm{d}u= \frac{e^{-\mu _i t}}{\Delta t} \int _0^{\Delta t} e^{\mu _i u} \mathrm{d}u = \frac{e^{-\mu _i t}}{\mu _i \Delta t} (e^{\mu _i \Delta t} - 1)\nonumber \\&\quad = e^{-\mu _i t} + O\left( \Delta t\right) . \end{aligned}$$

Hence, $p_i(\vartheta ,t) = 1 + e^{-\mu _i t} \left( e^{\vartheta } - 1\right) + O\left( \Delta t\right)$, and thus

$$\begin{aligned} \sum _{k=0}^{\infty } e^{-\lambda _i \Delta t} \frac{(\lambda _i \,\Delta t)^k}{k!} \left( p_i(\vartheta ,t)\right) ^k&= e^{-\lambda _i \Delta t} \exp \left[ \lambda _i \,\Delta t \,p_i(\vartheta ,t)\right] \\&= 1 + \lambda _i \Delta t \left( e^{\vartheta } - 1\right) e^{-\mu _i t} + O\left( (\Delta t)^2\right) . \end{aligned}$$

Now $q_i = \sum _{j\ne i} q_{ij}$ yields

$$\begin{aligned} \Lambda _i(\vartheta ,t)&= \left( 1+\lambda _i \,\Delta t\,(e^\vartheta -1)e^{-\mu _i t}\right) \,\\&\times \left( \sum _{j\not =i}q_{ij}\Delta t\,\Lambda _j(\vartheta ,t-\Delta t)+\left( 1-q_i\Delta t\right) \Lambda _i(\vartheta ,t-\Delta t)\right) +O\left( (\Delta t)^2\right) \\&= \left( 1+\lambda _i \,\Delta t\,(e^\vartheta -1)e^{-\mu _i t}\right) \,\\&\times \left( \sum _{j\not =i}q_{ij}\Delta t\,\Lambda _j(\vartheta ,t)+ \Lambda _i(\vartheta ,t)-\Delta t\,\Lambda _i^{\prime }(\vartheta ,t)- q_i\Delta t\,\Lambda _i(\vartheta ,t)\right) +O\left( (\Delta t)^2\right) \\&= \left( 1+\lambda _i \,\Delta t\,(e^\vartheta -1)e^{-\mu _i t}\right) \,\\&\times \left( \sum _{j=1}^dq_{ij}\Delta t\,\Lambda _j(\vartheta ,t)+ \Lambda _i(\vartheta ,t)-\Delta t\,\Lambda _i^{\prime }(\vartheta ,t)\right) +O\left( (\Delta t)^2\right) , \end{aligned}$$

where the derivative is with respect to $t$. We have found the following system of differential equations.

Proposition 2

The mgf s $\Lambda _i(\vartheta ,t)$ satisfy

$$\begin{aligned} \lambda _i \,(e^\vartheta -1)e^{-\mu _i t} \Lambda _i(\vartheta ,t) = \Lambda _i^{\prime }(\vartheta ,t) -\sum _{j=1}^dq_{ij} \Lambda _j(\vartheta ,t). \end{aligned}$$

(5)

Now define $\psi _i(\alpha ,\vartheta ) :=\int _0^\infty \alpha e^{-\alpha t} \Lambda _i(\vartheta ,t) \mathrm{d}t$. Then, by integrating,

$$\begin{aligned} \int _0^\infty \alpha e^{-\alpha t} \Lambda _i^{\prime }(\vartheta ,t) \mathrm{d}t=\alpha (\psi _i(\alpha ,\vartheta )-1). \end{aligned}$$

We thus obtain

$$\begin{aligned} \lambda _i(e^\vartheta -1)\frac{\alpha }{\alpha +\mu _i}\psi _i(\alpha +\mu _i,\vartheta )= \alpha (\psi _i(\alpha ,\vartheta )-1)-\sum _{j=1}^dq_{ij} \psi _j(\alpha ,\vartheta ); \end{aligned}$$

(6)

cf. [1, Eq. (4.6), Cor. 1] in the one-dimensional case and [15, Thm. 3] in the network case for equations that resemble (5) for Markov-modulated shot-noise models. These may be viewed as continuous state-space analogs or weak limits of the infinite-server queue (see [14] regarding a general framework that includes both for the network version in the non-modulated case).

3.2 Mean

To compute $\mathbb{E }\bar{M}_i(\tau _\alpha )$, with $\tau _\alpha \sim \exp (\alpha )$, we differentiate Eq. (6) with respect to $\vartheta$ and let $\vartheta \downarrow 0$, thus obtaining

$$\begin{aligned} \lambda _i\frac{\alpha }{\alpha +\mu _i}\psi _i(\alpha +\mu _i,0)=\alpha \cdot \lim _{\vartheta \downarrow 0}\frac{\mathrm{d}}{{\mathrm{d}}\vartheta }\psi _i(\alpha ,\vartheta )-\sum _{j=1}^dq_{ij}\cdot \lim _{\vartheta \downarrow 0}\frac{\mathrm{d}}{{\mathrm{d}}\vartheta }\psi _j(\alpha ,\vartheta ), \end{aligned}$$

or

$$\begin{aligned} \lambda _i\frac{\alpha }{\alpha +\mu _i}&= \alpha \int _0^\infty \alpha e^{-\alpha t} \mathbb{E }\bar{M}_i(t)\mathrm{d}t -\sum _{j=1}^dq_{ij}\int _0^\infty \alpha e^{-\alpha t} \mathbb{E }\bar{M}_j(t)\mathrm{d}t\nonumber \\&= \alpha \mathbb{E }\bar{M}_i(\tau _\alpha ) -\sum _{j=1}^dq_{ij} \mathbb{E }\bar{M}_j(\tau _\alpha ). \end{aligned}$$

(7)

Now consider the special case that the background process is in equilibrium at time $0$. It turns out that the expressions simplify significantly. We have, due to (7), using the fact that $\sum _i\pi _iq_{ij}=0$,

$$\begin{aligned} \sum _{i=1}^d\pi _i \mathbb{E }\bar{M}_i(\tau _\alpha )=\sum _{i=1}^d\pi _i\lambda _i\frac{1}{\alpha +\mu _i}. \end{aligned}$$

Laplace inversion yields

$$\begin{aligned} \sum _{i=1}^d\pi _i\mathbb{E }\bar{M}_i(t)=\sum _{i=1}^d \frac{\pi _i\lambda _i}{\mu _i}(1-e^{-\mu _i t}), \end{aligned}$$

in line with (1). Now consider steady-state behavior, that is, we let $\alpha \downarrow 0.$ From the above, we obtain an expression that could as well have been found by applying Little’s law:

$$\begin{aligned} \sum _{i=1}^d\pi _i\mathbb{E }\bar{M}_i(\infty )=\sum _{i=1}^d\pi _i \frac{\lambda _i}{\mu _i}. \end{aligned}$$

3.3 Higher moments

A second differentiation of (6) yields

$$\begin{aligned} 2\lambda _i \frac{\alpha }{\alpha +\mu _i} \mathbb{E }\bar{M}_i(\tau _{\alpha +\mu _i}) + \lambda _i \frac{\alpha }{\alpha +\mu _i} = \alpha \mathbb{E }\bar{M}_i^2(\tau _\alpha )-\sum _{j=1}^d q_{ij} \mathbb{E }\bar{M}_j^2(\tau _\alpha ). \end{aligned}$$

In other words, once we know the $\mathbb{E }\bar{M}_i(\tau _{\alpha })$ for all $\alpha >0$, we can compute the associated second moment as well.

Along the same lines,

$$\begin{aligned} \lambda _i\frac{\alpha }{\alpha +\mu _i}\sum _{k=0}^{n-1}{n\atopwithdelims ()k}\cdot \lim _{\vartheta \downarrow 0} \frac{\mathrm{d}^k}{{\mathrm{d}}\vartheta ^k}\psi _i(\alpha +\mu _i,\vartheta )&= \lambda _i\frac{\alpha }{\alpha +\mu _i}\sum _{k=0}^{n-1}{n\atopwithdelims ()k} \mathbb{E }\bar{M}_i^k(\tau _{\alpha +\mu _i})\\&= \alpha \mathbb{E }\bar{M}_i^n(\tau _\alpha )-\sum _{j=1}^d q_{ij} \mathbb{E }\bar{M}_j^n(\tau _\alpha ). \end{aligned}$$

As a consequence, these higher moments (at exponentially distributed epochs) can be recursively determined. Again there is a simplification if the background process is in equilibrium at time $0$. Then we have the equation

$$\begin{aligned} \sum _{i=1}^d\pi _i \mathbb{E }\bar{M}_i^n(\tau _\alpha )= \sum _{i=1}^d\pi _i \lambda _i\frac{1}{\alpha +\mu _i}\sum _{k=0}^{n-1}{n\atopwithdelims ()k} \mathbb{E }\bar{M}_i^k(\tau _{\alpha +\mu _i}). \end{aligned}$$

For the steady-state we obtain, cf. [1],

$$\begin{aligned} \sum _{i=1}^d\pi _i \mathbb{E }\bar{M}_i^n(\infty )=\sum _{i=1}^d\pi _i \frac{\lambda _i}{\mu _i}\sum _{k=0}^{n-1}{n\atopwithdelims ()k} \mathbb{E }\bar{M}_i^k(\tau _{\mu _i}). \end{aligned}$$

4 Asymptotic normality for general service times

In this section we consider our Markov-modulated infinite-server system, but, as opposed to the setting discussed in the previous section, now with generally distributed service times. The main result is a central limit theorem (for $N\rightarrow \infty$) under the scaling $q_{ij}\mapsto N^{1+\varepsilon }q_{ij}$ and $\lambda _i\mapsto N\lambda _i$; here $\varepsilon >0$. The intuitive idea behind this scaling is that the state of the background process moves at a faster time scale than the arrival processes (so that the arrival process is effectively a single Poisson process as $N\rightarrow \infty$), while this arrival process is sped up by a factor $N$ (so that a central limit regime kicks in).

Remark 1

We already observed that the number $\check{M}_i^{(N)}(t)$ of particles still present at time $t$, out of the initial population of size $Nx_0$ and that arrived while the background process was in state $i$, is not affected by the evolution of the background process, as the departure rate has been determined upon arrival. Specializing to the case of exponential service times (with mean $\mu _i^{-1}$ if the particle under consideration had entered while the background process was in state $i$), the corresponding random variables have independent binomial distributions with parameters $Nx_{0,i}$ and $e^{-\mu _i t}$. $Nx_{0,i}$ denotes the number of particles present at time $0$ that arrived while the background was in state $i$. Therefore, as $N \rightarrow \infty$

$$\begin{aligned} \frac{\check{M}_i^{(N)}(t) - Nx_{0,i} e^{-\mu _i t}}{\sqrt{N}}\stackrel{\hbox {d}}{\rightarrow } {\mathbb{N }}{\mathrm{orm}}\left( 0, x_{0,i}e^{-\mu _i t}(1-e^{-\mu _i t})\right) . \end{aligned}$$

For other service-time distributions the quantities $e^{-\mu _i t}$ have to be replaced by the appropriate survival probability associated with the residual lifetime of a particle that is present at time 0 and that had arrived while the background process was in $i$.

In light of the above, it suffices to focus on establishing a central limit theorem for the number of particles that arrived in $(0,t]$ that are still present at time $t$. Let, in line with earlier definitions, this number be denoted by $\bar{M}_i^{(N)}(t)$ in case the modulating process is in state $i$ at time 0.$\Diamond$

One of the leading intuitions of this section is that, due to the fact that the timescale of the background process is faster than that of the arrival process, we can essentially replace our Markov-modulated infinite-server system, as $N\rightarrow \infty$, by an M/G/$\infty$ queue. This effectively means that, irrespective of the initial state $i, \bar{M}^{(N)}_i(t)$ can be approximated by a Poisson distribution with parameter $N\varrho _t$. The candidate for $\varrho _t$ can be easily identified using the theory of Sect. 2:

$$\begin{aligned} \varrho _t:=\sum _{i=1}^d \pi _i{\lambda _i}\int _0^t\bar{F}_i(s)\,\mathrm{d}s. \end{aligned}$$

(8)

Let us now focus on identifying a candidate for the limiting covariance between $\bar{M}^{(N)}_i(t)$ and $\bar{M}^{(N)}_i(t+u)$; this is a rather elementary computation that we include for the sake of completeness. Let $N(t)$ be the number present in an M/G/$\infty$ queue that started off empty at time $0$; the arrival rate is $\lambda$ and the distribution function of the service times is denoted by $F(\cdot )$. In this system it is possible to compute the covariance between $N(t)$ and $N(t+u)$ explicitly in terms of the arrival rate and the distribution function $F(\cdot )$ of the service times. Realize that $N(t+u)$ can be written as the sum of the particles that were already present at time $t$ and that are still present at time $t+u$ (which we denote by $N_t(t+u)$), and the ones that have arrived in $(t,t+u]$ and that are still present at time $t+u$. The latter quantity being independent of $N(t)$, we have

$$\begin{aligned} \mathbb{C }{\mathrm{ov}}(N(t),N(t+u))=\mathbb{C }{\mathrm{ov}}(N(t),N_t(t+u)). \end{aligned}$$

It thus suffices to compute the quantity $\mathbb{C }{\mathrm{ov}}(N(t),N_t(t+u))$. To this end, define

$$\begin{aligned} q^\mathrm{A}\equiv q^\mathrm{A}_{u,t}&:= \int _0^t \frac{1}{t} F(t-v)\mathrm{d}v = \int _0^t \frac{1}{t} F(v)\mathrm{d}v,\\ q^\mathrm{B}\equiv q^\mathrm{B}_{u,t}&:= \int _0^t \frac{1}{t} (F(t+u-v)- F(t-v))\mathrm{d}v = \int _0^t \frac{1}{t} (F(v+u)- F(v))\mathrm{d}v,\\ q^\mathrm{C}\equiv q^\mathrm{C}_{u,t}&:= \int _0^t \frac{1}{t} (1-F(t+u-v))\mathrm{d}v = \int _0^t \frac{1}{t} (1-F(v+u))\mathrm{d}v;\end{aligned}$$

the first of these quantities can be interpreted as the probability that an arbitrary particle that has arrived in $[0,t)$ has already left the system at time $t$, the second as the probability that it is still present at time $t$ but not at $t+u$ anymore, and the third as the probability that it is still present at time $t+u$. It now follows that

$$\begin{aligned} \mathbb{E }N(t)\,N_t(t+u)&= \sum _{k=0}^\infty \sum _{\ell =0}^k k\ell \,\mathbb{P }(N(t)=k,N_t(t+u)=\ell )\\&= \sum _{m=0}^\infty e^{-\lambda t}{\frac{(\lambda t)^m}{m!}}\sum _{k=0}^m\sum _{\ell = 0}^k k\ell {m\atopwithdelims ()k,\ell } (q^\mathrm{A})^{m-k} (q^\mathrm{B})^{k-\ell }(q^\mathrm{C})^\ell , \end{aligned}$$

which turns out to equal (after some elementary computations) $q^\mathrm{C}\,\lambda t+ q^\mathrm{C}(1-q^\mathrm{A})\lambda ^2 t^2.$ As $\mathbb{E }N(t) = (1-q^\mathrm{A})\lambda t$ and $\mathbb{E }N_t(t+u)=q^\mathrm{C}\,\lambda t$, it follows that

$$\begin{aligned} \mathbb{C }{\mathrm{ov}}(N(t),N(t+u)) = q^\mathrm{C}\,\lambda t=\lambda \int _0^t (1-F(v+u))\mathrm{d}v. \end{aligned}$$

This computation provides us with the candidate for the central limit result in the case of general service times. Define in this context, for $t_1\le t_2$,

$$\begin{aligned} c_{t_1,t_2}:=\sum _{i=1}^d\pi _i\lambda _i\int _0^{t_1}\bar{F}_i(v+t_2-t_1)\mathrm{d}v \end{aligned}$$

(while if $t_2<t_1$ we put $c_{t_1,t_2}=c_{t_2,t_1}$).

The following result covers the asymptotic multivariate normality. In the proof we consider the bivariate case (time epochs $t$ and $t+u$), but the extension to a general dimension (time epochs $t_1$ up to $t_K$ with, without loss of generality, $t_1\le \ldots \le t_K$) is straightforward and essentially a matter of careful bookkeeping.

Theorem 1

For any ${\varvec{\alpha }}\in {\mathbb{R }}^K$ and ${\varvec{t}}\in {\mathbb{R }}^K$ (with $t_1\le \ldots \le t_K$), and general service times, as $N\rightarrow \infty$,

$$\begin{aligned} \frac{\sum _{k=1}^K \alpha _k\bar{M}^{(N)}_i(t_k) - N \sum _{k=1}^K\alpha _k \varrho _{t_k}}{\sqrt{N}}\stackrel{\hbox {d}}{{\rightarrow }} N(0,\sigma ^2), \end{aligned}$$

with

$$\begin{aligned} \sigma ^2:=\sum _{k=1}^K\alpha _k^2 \varrho _{t_k}+2\sum _{k=1}^{K-1}\sum _{\ell =1}^{k-1} \alpha _k\alpha _\ell c_{t_k,t_\ell }. \end{aligned}$$

This theorem shows convergence of the finite-dimensional distributions to a multivariate Normal distribution. A next step would be to prove convergence at the process level, viz. convergence of

$$\begin{aligned} \left( \frac{\bar{M}^{(N)}_i(t) - N \varrho _{t}}{\sqrt{N}}\right) _{t\ge 0} \end{aligned}$$

to a Gaussian process with a specific correlation structure. Such a result has been proven for the regular (that is, non-modulated) M/M/$\infty$ queue in which the Poisson arrival rate is scaled by $N$; the limiting process is then an Ornstein-Uhlenbeck process—see, for example [22]. The proofs of such weak convergence results typically consist of three steps: single-dimensional convergence, finite-dimensional convergence, and a tightness argument, where the tightness step tends to be relatively complicated. In our setup (that is, the Markov-modulated M/G/$\infty$ queue) we have proven the first two steps; the third step (tightness) is beyond the scope of this paper.

We prove Thm. 1 for the case of $K=2$, with $t_1=t$ and $t_2=t+u$ (for $t,u\ge 0$); higher dimensions can be dealt with fully analogously but these require substantially more administration. Our starting point is to set up a system of differential equations for the non-scaled process. This system is derived in the very same way as the differential equations for the univariate exponential case (see Prop. 2). Define, for fixed scalars $\alpha _1,\alpha _2$, and for $u\ge 0$ given,

$$\begin{aligned} \Lambda _i(\vartheta ,t):=\mathbb{E } \exp ({\vartheta \alpha _1 \bar{M}_i(t)+\vartheta \alpha _2 \bar{M}_i(t+u)}). \end{aligned}$$

In addition, let

$$\begin{aligned} p_i(\vartheta ,t)&:= F_i(t)\,+ e^{\vartheta \alpha _1} (F_i(t+u)-F_i(t))\,+ e^{\vartheta (\alpha _1+\alpha _2)}(1-F_i(t+u) )\\&= e^{\vartheta (\alpha _1+\alpha _2)} -(e^{\vartheta \alpha _1} -1)F_i(t) - e^{\vartheta \alpha _1}(e^{\vartheta \alpha _2} -1)F_i(t+u). \end{aligned}$$

Proposition 3

The mgf s $\Lambda _i(\vartheta ,t)$ satisfy

$$\begin{aligned} \bar{p}_i(\vartheta ,t)\Lambda _i(\vartheta ,t)=\Lambda ^{\prime }_i(\vartheta ,t)- \sum _{j=1}^dq_{ij}\Lambda _j(\vartheta ,t), \end{aligned}$$

where $\bar{p}_i(\vartheta ,t):=\lambda _i (p_i(\vartheta ,t)-1).$

Proof

Let $I_i(t)$ be the indicator function of the event that a particle arriving in $(0,\Delta t]$ (while the background process was in state $i$) is still in the system at time $t$, and consider the random variable $\alpha _1 I_i(t)+\alpha _2 I_i(t+u)$. Similarly to what we did earlier in this section, $\alpha _1 I_i(t)+\alpha _2 I_i(t+u)$ can be split into three contributions; one corresponding to the event that a particle that arrived in $(0,{\Delta }t]$ has already left the system at time $t$, one corresponding to the event that it is still present at time $t$ but not anymore at time $t+u$, and finally one corresponding to the event that it is still present at time $t+u$. With some standard calculus it is readily obtained that

$$\begin{aligned} \mathbb{E }\, \exp \left( \vartheta \alpha _1 I_i(t)+\vartheta \alpha _2 I_i(t+u)\right) =p_i(\vartheta ,t)+O(\Delta t). \end{aligned}$$

This means that we obtain

$$\begin{aligned} \Lambda _i(\vartheta ,t)&= \lambda _i\Delta t \cdot p_i(\vartheta ,t)\Lambda _i(\vartheta ,t-\Delta t)\\&\!+\!\,\sum _{j\not =i}q_{ij}\Delta t\cdot \Lambda _j(\vartheta ,t\!-\!\Delta t) \!+\!\left( 1-\lambda _i\Delta t\!-\!q_i\Delta t\right) \Lambda _i(\vartheta ,t-\Delta t)+o(\Delta t). \end{aligned}$$

Now subtracting $\Lambda _i(\vartheta ,t-\Delta t)$ from both sides, dividing by $\Delta t$, and letting $\Delta t\downarrow 0$ leads to the desired system of differential equations.$\square$

Proof of Thm. 1. Now we are ready to prove the bivariate asymptotic normality for the case of general service times. The idea behind the proof is to (i) start off with the differential equations for the non-scaled system as derived in Prop. 3; (ii) incorporate the scaling in the differential equations, and apply the centering and normalization corresponding to the central limit regime; (iii) use Taylor expansions (for large $N$); (iv) obtain a limiting differential equation (as $N\rightarrow \infty$). This limiting differential equation finally yields the claimed central limit theorem.

We first “center” the random variable $\alpha _1 \bar{M}_i^{(N)}(t)+\alpha _2 \bar{M}_i^{(N)}(t+u)$; to this end we subtract $N\varrho (t,u)$ from this random variable, with

$$\begin{aligned} \varrho (t,u):= \alpha _1 \varrho _t+\alpha _2\varrho _{t+u}, \end{aligned}$$

and $\varrho _t$ defined as in Eq. (8). At this point we impose the scaling, that is, we replace $q_{ij}$ by $N^{1+\varepsilon } q_{ij}$, and $\lambda _i$ by $N\lambda _i$. With these parameters, we now study the appropriately centered and scaled random variable

$$\begin{aligned} \frac{\vartheta \alpha _1 \bar{M}_i^{(N)}(t)+\vartheta \alpha _2 \bar{M}_i^{(N)}(t+u) - N\vartheta \varrho (t)}{\sqrt{N}}, \end{aligned}$$

where we suppress the argument $u$ in $\varrho (t,u)$ (as $u$ is held fixed throughout the proof). It means that we study the “centered and scaled mgf”

$$\begin{aligned} \tilde{\Lambda }_i^{(N)}(\vartheta ,t):= \Lambda _i\left( \frac{\vartheta }{\sqrt{N}},t\right) \exp \left( -\sqrt{N}\vartheta \varrho (t)\right) , \end{aligned}$$

(9)

where, due to Prop. 3, $\Lambda _i(\vartheta /\sqrt{N},t)$ satisfies

$$\begin{aligned} N \bar{p}_i\left( \frac{\vartheta }{\sqrt{N}},t\right) \Lambda _i \left( \frac{\vartheta }{\sqrt{N}},t\right) =\Lambda ^{\prime }_i\left( \frac{\vartheta }{\sqrt{N}},t\right) -N^{1+\varepsilon }\sum _{j=1}^dq_{ij}\Lambda _j \left( \frac{\vartheta }{\sqrt{N}},t\right) . \end{aligned}$$

Realize that, as a straightforward application of the chain rule,

$$\begin{aligned} \left( \tilde{\Lambda }_i^{(N)}\right) ^{\prime }(\vartheta ,t)=\Lambda _i^{\prime } \left( \frac{\vartheta }{\sqrt{N}},t\right) \exp \left( -\sqrt{N}\vartheta \varrho (t) \right) -\sqrt{N}\vartheta \varrho ^{\prime }(t) \tilde{\Lambda }_i^{(N)}\left( {\vartheta },t\right) . \end{aligned}$$

Upon combining the above, we find a relation which is completely in terms of the centered/scaled mgf $\tilde{\Lambda }_i^{(N)}(\vartheta ,t)$:

$$\begin{aligned} N\bar{p}_i\left( \frac{\vartheta }{\sqrt{N}},t\right) \tilde{\Lambda }_i^{(N)} \left( {\vartheta },t\right)&= \left( \tilde{\Lambda }_i^{(N)}\right) ^{\prime }\left( {\vartheta },t\right) \nonumber \\&\quad + \sqrt{N}\vartheta \varrho ^{\prime }(t)\tilde{\Lambda }_i^{(N)}\left( {\vartheta },t\right) -N^{1+\varepsilon }\sum _{j=1}^d q_{ij} \tilde{\Lambda }_j^{(N)}\left( {\vartheta },t\right) .\nonumber \\ \end{aligned}$$

(10)

We now study the solution of this system of differential equations for ${N}$ large by “Tayloring” the function $\bar{p}_i(\vartheta /\sqrt{N},t)$ with respect to ${N}$. It is an elementary exercise to check that

$$\begin{aligned} \bar{p}_i\left( \frac{\vartheta }{\sqrt{N}},t\right) =\frac{h_{1,i}(\vartheta ,t)}{\sqrt{N}}+\frac{h_{2,i}(\vartheta ,t)}{N}+O(N^{-\frac{3}{2}}), \end{aligned}$$

with

$$\begin{aligned} h_{1,i}(\vartheta ,t)&:= \lambda _i\left( \vartheta \alpha _1\bar{F}_i(t)+ \vartheta \alpha _2\bar{F}_i(t+u)\right) ,\,\,\,\\ h_{2,i}(\vartheta ,t)&:= \frac{\lambda _i}{2}\left( \vartheta ^2\alpha _1^2\bar{F}_i(t)+\vartheta ^2(\alpha _2(2\alpha _1+\alpha _2))\bar{F}_i(t+u)\right) . \end{aligned}$$

We thus obtain the differential equation

$$\begin{aligned}&\left( \sqrt{N}\left( h_{1,i}(\vartheta ,t)- \vartheta \varrho ^{\prime }(t)\right) +{h_{2,i}(\vartheta ,t)}+O(N^{-\frac{1}{2}})\right) \tilde{\Lambda }^{(N)}_i(\vartheta ,t)\\&= \left( \tilde{\Lambda }_i^{(N)}\right) ^{\prime }(\vartheta ,t)-N^{1+\varepsilon } \sum _{j=1}^d q_{ij} \tilde{\Lambda }_j^{(N)}(\vartheta ,t), \end{aligned}$$

or in self-evident matrix/vector notation,

$$\begin{aligned} N^{1+\varepsilon }Q\tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)&= \left( \tilde{\varvec{\Lambda }}^{(N)}\right) ^{\prime }(\vartheta ,t)-\sqrt{N} \left( H_1(\vartheta ,t)-\vartheta \varrho ^{\prime }(t)\right) \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)\\&-\, H_2(\vartheta ,t) \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)+O(N^{-\frac{1}{2}}). \end{aligned}$$

Now premultiply this equation by the so-called fundamental matrix $\mathcal F :=(\Pi -Q)^{-1}$, where $\Pi :={\varvec{1}}{\varvec{\pi }}^\mathrm{T}$. It holds that $\Pi ^2=\Pi , \mathcal F \Pi =\Pi \mathcal F =\Pi$, and $Q\mathcal F =\mathcal F Q=\Pi -I$; see for these properties and more background on fundamental matrices and deviations matrices e.g. [4]. We then obtain

$$\begin{aligned} N^{1+\varepsilon }\tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)&= N^{1+\varepsilon }\Pi \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)-\mathcal F \left( \tilde{\varvec{\Lambda }}^{(N)}\right) ^{\prime }(\vartheta ,t) +\sqrt{N}\mathcal F \left( H_1(\vartheta ,t)\right. \\&\left. -\vartheta \varrho ^{\prime }(t)\right) \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)\\&+\, \mathcal F H_2(\vartheta ,t) \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)+O(N^{-\frac{1}{2}}). \end{aligned}$$

Iterating this identity once, we obtain

$$\begin{aligned} N^{1+\varepsilon }\tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)&= N^{1+\varepsilon }\Pi \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t) -\Pi \mathcal F \left( \tilde{\varvec{\Lambda }}^{(N)}\right) ^{\prime }(\vartheta ,t) +\sqrt{N}\mathcal F \left( H_1(\vartheta ,t)\right. \\&\left. -\vartheta \varrho ^{\prime }(t)\right) \Pi \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)\\&+\, \mathcal F H_2(\vartheta ,t)\Pi \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)+O(N^{-\frac{1}{2}})+O(N^{-\varepsilon }). \end{aligned}$$

Now premultiply the equation by $d\,{{\varvec{\pi }}^\mathrm{T} = }{\varvec{1}}^\mathrm{T}\Pi$. Recalling the identity $\Pi \mathcal F =\Pi$ and noting that it follows from the definition of $\varrho (t)$ that

$$\begin{aligned} {\varvec{1}}^\mathrm{T}\Pi \left( H_1(\vartheta ,t)-\vartheta \varrho ^{\prime }(t)\right) {\varvec{1}}=0, \end{aligned}$$

all terms of $O(N^\alpha )$ with $\alpha > 0$ cancel. For $\lim _{N\rightarrow \infty }{\varvec{\pi }}^\mathrm{T} \tilde{\varvec{\Lambda }}^{(N)}(\vartheta ,t)=:\tilde{\Lambda }(\vartheta ,t)$ we thus obtain the following differential equation:

$$\begin{aligned} \tilde{\Lambda }^{\prime }(\vartheta ,t) = \left( \sum _{i=1}^d\pi _i h_{2,i}(\vartheta ,t)\right) \tilde{\Lambda }(\vartheta ,t). \end{aligned}$$

Using the technique of separation of variables, it follows that

$$\begin{aligned} \tilde{\Lambda }(\vartheta ,t)=\exp \left( \int _0^t \sum _{i=1}^d \pi _i h_{2,i}(\vartheta ,s)\mathrm{d}s\right) {\kappa }(\vartheta ,u), \end{aligned}$$

or

$$\begin{aligned} \tilde{\Lambda }(\vartheta ,t)\!=\!\exp \left( \frac{\vartheta ^2}{2}\sum _{i=1}^d \pi _i\int _0^t\left( {\lambda _i} \left( {\alpha _1^2}\bar{F}_i(s)+{(2\alpha _1\!+\!\alpha _2)\alpha _2}\bar{F}_i(s+u)\right) \right) \mathrm{d}s\right) {\kappa }(\vartheta ,u), \end{aligned}$$

for some function ${\kappa }(\vartheta ,u)$ that is independent of $t$. Now note that this expression should not depend on $\alpha _1$ if $t=0$. In addition, if we insert $u=0$, then $\alpha _1$ and $\alpha _2$ should appear in the expression as $\alpha _1+\alpha _2$. This enables us to identify ${\kappa }(\vartheta ,u)$. We eventually obtain

$$\begin{aligned} \tilde{\Lambda }(\vartheta ,t)&= \exp \left( \frac{\vartheta ^2}{2}\left( \alpha _1^2\varrho _t+2\alpha _1\alpha _2 c_{t,t+u}+\alpha _2^2\varrho _{t+u}\right) \right) , \end{aligned}$$

(11)

as desired. We have proven the claimed convergence.

Remark 2

It is remarked that the central limit theorem does not carry over to the case $\varepsilon \in (-1,0]$, as then the term of order $N^{1-2\varepsilon }$ cannot be neglected relative to the term of order $N^{1-\varepsilon }$. As a result, in that situation the variance featuring in the central limit theorem will contain the fundamental matrix $\mathcal F$ for these values of $\varepsilon$.$\Diamond$

5 Examples

5.1 Two-state model

In this example we consider the case $d=2$, and exponential sojourn times of the background process, that is, the time spent in state $i$ is exponential with mean $1/q_i\in (0,\infty )$. From $\mathbb{E }\bar{\varvec{M}}(\tau _\alpha ) = (A(\alpha ))^{-1} {\varvec{\varphi }}(\alpha )$ we obtain for the mean number in the system after an exponential time with mean $1/\alpha$ (ignoring the effect of an initial population)

$$\begin{aligned} \left( \begin{array}{c} \mathbb{E }\bar{M}_1(\tau _\alpha )\\ \mathbb{E }\bar{M}_2(\tau _\alpha )\end{array}\right)&= \frac{1}{q_1+q_2+\alpha } \left( \begin{array}{cc} q_2+\alpha &{}\quad q_1\\ q_2&{}\quad q_1+\alpha \end{array}\right) \left( \begin{array}{c} {\displaystyle \frac{\lambda _1}{\alpha +\mu _1}}\\ {\displaystyle \frac{\lambda _2}{\alpha +\mu _2}}\end{array}\right) \\&= \left( \begin{array}{c} {\displaystyle \frac{\alpha +q_2}{\alpha +q_1+q_2}}{\displaystyle \frac{\lambda _1}{\alpha +\mu _1}}+ {\displaystyle \frac{q_1}{\alpha +q_1+q_2}}{\displaystyle \frac{\lambda _2}{\alpha +\mu _2}}\\ {\displaystyle \frac{\alpha +q_1}{\alpha +q_1+q_2}}{\displaystyle \frac{\lambda _2}{\alpha +\mu _2}}+ {\displaystyle \frac{q_2}{\alpha +q_1+q_2}}{\displaystyle \frac{\lambda _1}{\alpha +\mu _1}}\end{array}\right) \end{aligned}$$

When sending $\alpha$ to $\infty$, we indeed obtain that $\mathbb{E }\bar{M}_i(\tau _\infty )=0$; when sending $\alpha$ to $0$, the resulting formula is consistent with the long-term mean number in the system, as found earlier. Replacing $q_i$ by $Nq_i$ (for $i=1,2$), we obtain that both components of $\mathbb{E }\bar{\varvec{M}}(\tau _\alpha )$ converge (as $N\rightarrow \infty$) to

$$\begin{aligned} \pi _1 \frac{\lambda _1}{\alpha +\mu _1}+\pi _2 \frac{\lambda _2}{\alpha +\mu _2}, \end{aligned}$$

which is for $\mu _1=\mu _2$ in line with the findings in [12].

We now focus on computing the second moment; for ease we consider the stationary case. From Sect. 3.3, we have

$$\begin{aligned} \sum _{i=1}^d \frac{2\pi _i\lambda _i}{\alpha +\mu _i} \mathbb{E }\bar{M}_i(\tau _{\alpha +\mu _i}) + \sum _{i=1}^d \frac{\pi _i\lambda _i}{\alpha +\mu _i} = \sum _{i=1}^d \pi _i \mathbb{E }\bar{M}_i^2(\tau _\alpha ), \end{aligned}$$

which becomes after sending $\alpha$ to $0$,

$$\begin{aligned} \mathbb{E }\bar{M}^2(\infty ):=\sum _{i=1}^d \pi _i \mathbb{E }\bar{M}_i^2(\infty )= \sum _{i=1}^d 2\pi _i\frac{\lambda _i}{\mu _i} \mathbb{E }\bar{M}_i(\tau _{\mu _i})+ \sum _{i=1}^d \pi _i\frac{\lambda _i}{\mu _i} ; \end{aligned}$$

obviously, $\pi _1=1-\pi _2=q_2/(q_1+q_2)$.

We now find a lower bound on the variance of the stationary number of particles in the system. Restricting ourselves to the case $\mu _i\equiv \mu$ for all $i=1,\ldots ,d$, elementary computations yield, with $r_i:=\lambda _i/\mu$ and $q:=q_1+q_2$,

$$\begin{aligned} \mathbb{E }\bar{M}^2(\infty )= \frac{\pi _1r_1}{\mu -q}\left( (\mu -q_2)r_1\! -\!q_1 r_2\right) +\pi _1r_1\!+\! \frac{\pi _2r_2}{\mu -q}\left( (\mu -q_1)r_2 \!-\!q_2 r_1\right) +\pi _2r_2. \end{aligned}$$

We now claim that, with $R$ denoting the stationary mean $\pi _1r_1+\pi _2r_2$, the stationary variance is larger than this $R$, or equivalently

$$\begin{aligned} \mathbb{E }\bar{M}^2(\infty ) \ge R^2+R, \end{aligned}$$

(12)

with equality only if $\lambda _1=\lambda _2$. This can be shown as follows. Writing $r_1 = a r_2$, the above claim reduces to verifying that, for all $a\in (0,\infty )$,

$$\begin{aligned} a^2(f_1-\pi _1)\pi _1 +a (f_2-\pi _2)\pi _1 +a (g_1-\pi _1)\pi _2 +(g_2-\pi _2)\pi _2\ge 0, \end{aligned}$$

(13)

with equality only if $a=1$; here

$$\begin{aligned} f_1=1-f_2:= \frac{\mu -q_2}{\mu -q},\,\,\,\, g_2:=1-g_1:=\frac{\mu -q_1}{\mu -q}. \end{aligned}$$

Observe that $f_1>\pi _1$, so that the left-hand side of (13) has a minimum. Now realize that $f_1-\pi _1 = -(f_2-\pi _2)$ and $g_2-\pi _2=-(g_1-\pi _1)$. As a result, (13) reduces to

$$\begin{aligned} (a-1)(a(f_1-\pi _1)\pi _1 -(g_2-\pi _2)\pi _2)\ge 0, \end{aligned}$$

which, due to $(f_1-\pi _1)\pi _1=(g_2-\pi _2)\pi _2$ can be rewritten as $(f_1-\pi _1)\pi _1(a-1)^2\ge 0.$ Claim (12) thus follows. We conclude that $\mathbb{V }{\mathrm{ar}}\bar{M}(\infty ) \ge \mathbb{E }\bar{M}(\infty ),$ with equality if and only if $\lambda _1=\lambda _2$.

This result can be intuitively understood. As argued before, $\bar{M}(\infty )$ is distributed as a Poisson random variable with a random parameter. We showed with an elementary argument in the introduction of [12] that this entails that $\mathbb{V }\mathrm{ar}\bar{M}(\infty ) \ge \mathbb{E }\bar{M}(\infty );$ informally, this says that Markov modulation increases the variability of the stationary distribution. We have now shown that for $d=2$ this inequality is in fact strict, unless the $\lambda _i$ match (and equal, say $\lambda$). In fact, then the queue is just an M/M/$\infty$ system which has the Poisson($\lambda /\mu$) distribution as the equilibrium distribution, for which mean and variance coincide (and have the value $\lambda /\mu$). In other words, for $d=2$ there are no other ways to obtain a Poisson stationary distribution than letting all $\lambda _i$ be equal.

5.2 Computational results

We include computational results demonstrating the converging behavior of the two-state scaled process in one dimension (i.e., $K=1$ in Thm. 1). Unscaled, the parameters are ${\varvec{\lambda }} = (1,2), {\varvec{\mu }} = (1,1)$, and ${\varvec{q}}=( 1, 3)$. Depicted in Fig. 1 is the limiting behavior of Eq. (9) assuming exponential service times, obtained by solving the scaled version of the differential equation (5) with the mgf parameter $\vartheta =0.5$ and $\varepsilon = 0.5$. The corresponding limiting curve from Eq. (11) is plotted as well. As in the case with deterministic transition times [3], we observe loglinear convergence, with the solution curve closely following the limiting curve for $N=1000$. Tweaking the parameters results in the same convergence behavior.

Fig. 1

(left) The scaled process, $\tilde{\Lambda }^{(N)}(0.5,t)$, approaches the limiting curve as $N$ grows larger. (right) Maximum error as a function of $N$ shows loglinear convergence.