Functional central limit theorems for Markov-modulated infinite-server systems

Abstract

In this paper we study the Markov-modulated M/M/$\infty$ queue, with a focus on the correlation structure of the number of jobs in the system. The main results describe the system’s asymptotic behavior under a particular scaling of the model parameters in terms of a functional central limit theorem. More specifically, relying on the martingale central limit theorem, this result is established, covering the situation in which the arrival rates are sped up by a factor N and the transition rates of the background process by $N^\alpha$, for some $\alpha >0$. The results reveal an interesting dichotomy, with crucially different behavior for $\alpha >1$ and $\alpha <1$, respectively. The limiting Gaussian process, which is of the Ornstein–Uhlenbeck type, is explicitly identified, and it is shown to be in accordance with explicit results on the mean, variances and covariances of the number of jobs in the system.

Appendices

Appendix 1

In this appendix we characterize the probability generating functions $\Xi _{ij}(\cdot ,\cdot ,\cdot ,\cdot )$ by setting up a system of partial differential equations. The starting point for this is the system of Kolmogorov equations related to the transient probabilities of the number of jobs present (jointly with the background state) at two time epochs:

$$\begin{aligned} p_{ij}(m,n,t,u):={\mathbb {P}}(M(t) = m, M(t+u)= n, J(t)=i, J(t+u)=j); \end{aligned}$$

we suppress the u as this is held fixed for the moment. Standard arguments from Markov chain theory immediately yield the equations, for $i,j\in \{1,\ldots ,d\},\,m,n\in \{0,1,2\ldots \}$, and $q_i:=-q_{ii}$,

$$\begin{aligned} p_{ij}(m,n,t+\Delta t,u)= & {} p_{ij}(m,n,t,u)\left( 1- \left( \lambda _i+\lambda _j +m\,\mu _i+n\,\mu _j+q_i+q_j\right) \Delta t\right) \\&+\,p_{ij}(m-1,n,t,u)\lambda _i \Delta t\,+\, p_{ij}(m,n-1,t,u)\lambda _j \Delta t\\&+\,p_{ij}(m+1,n,t,u)\,(m+1)\mu _i \Delta t\\&+ p_{ij}(m,n+1,t,u)\,(n+1)\mu _j \Delta t\\&+\,\sum _{k\not =i}p_{kj}(m,n,t,u)q_{ki} \Delta t\,+\,\sum _{k\not =j} p_{ik}(m,n,t,u)q_{kj} \Delta t\\&+\,o(\Delta t); \end{aligned}$$

here $p_{ij}(-1,n,t,u)$ and $p_{ij}(m,-1,t,u)$ are to be understood as 0. As a consequence, with $p_{ij}'(m,n,t,u)$ denoting the derivative of $p_{ij}(m,n,t,u)$ with respect to t, it is readily obtained that the transient probabilities satisfy the following system of (ordinary) differential equations:

$$\begin{aligned} p_{ij}'(m,n,t,u)= & {} \lambda _i \left( p_{ij}(m-1,n,t,u)-p_{ij}(m,n,t,u)\right) \\&+\,\lambda _j\left( p_{ij}(m,n-1,t,u)-p_{ij}(m,n,t,u)\right) \\&+\,\mu _i\left( (m+1)p_{ij}(m+1,n,t,u)-mp_{ij}(m,n,t,u)\right) \\&+\,\mu _j\left( (n+1)p_{ij}(m,n+1,t,u)-np_{ij}(m,n,t,u)\right) \\&+\,\sum _{k=1}^dp_{kj}(m,n,t,u)q_{ki} \,+\,\sum _{k=1}^d p_{ik}(m,n,t,u)q_{kj}. \end{aligned}$$

Our goal is to transform these differential equations into a system of partial differential equations for the corresponding probability generating functions. To this end, multiply both sides of the equation by $z^mw^n$, and sum over $m,n=0,1,2,\ldots$. This results in the following equation:

$$\begin{aligned} \frac{\partial }{\partial t} \Xi _{ij}(z,w,t,u)= & {} \left( \lambda _i(z-1)+\lambda _j(w-1) \right) \cdot \Xi _{ij}(z,w,t,u)\\&-\, \mu _i (z-1) \frac{\partial }{\partial z} \Xi _{ij}(z,w,t,u)- \mu _j(w-1) \frac{\partial }{\partial w} \Xi _{ij}(z,w,t,u)\\&+\,\sum _{k=1}^d\Xi _{kj}(z,w,t,u)q_{ki} \,+\,\sum _{k=1}^d \Xi _{ik}(z,w,t,u)q_{kj}, \end{aligned}$$

which in matrix notation coincides with Eq. (1).

Appendix 2

As will be proven in “Appendix 3” below, the statement (5) can be refined to, for some constant $\kappa$ (whose precise form is irrelevant here),

$$\begin{aligned} {\mathbb {E}} M^{(N)}(t) =\left( N\,\varrho ^{({{{i}}})}+ N^{1-\alpha }\kappa \right) \left( 1-e^{-\mu _\infty t}\right) +o(1). \end{aligned}$$

(13)

Likewise, for any $x\ge 0$,

$$\begin{aligned} {\mathbb {E}} \left( M^{(N)}(t)\,|\,M^{(N)}(0)=x\right) =\left( N\varrho ^{({{{i}}})}+N^{1-\alpha }\kappa \right) \left( 1-e^{-\mu _\infty t}\right) + x e^{-\mu _\infty t}+o(1).\nonumber \\ \end{aligned}$$

(14)

In the sequel we write $a(N):=N\varrho ^{({{{i}}})}+N^{1-\alpha }\kappa$. Applying an elementary time shift, we obtain that

$$\begin{aligned}&{\mathbb {E}}\left( M^{(N)}(t)M^{(N)}(t+u)\right) \\&\quad = \int _0^\infty {\mathbb {E}} \left( M^{(N)}(t)M^{(N)}(t+u)\,|\,M^{(N)}(t)=x\right) {\mathbb {P}}\left( M^{(N)}(t)\in \mathrm{d} x\right) \\&\quad =\int _0^\infty x{\mathbb {E}} \left( M^{(N)}(u)\,|\,M^{(N)}(0)=x\right) {\mathbb {P}}\left( M^{(N)}(t)\in \mathrm{d} x\right) . \end{aligned}$$

By plugging in (14), the expression in the last display equals

$$\begin{aligned}&\int _0^\infty x\left( a(N)(1-e^{-\mu _\infty u})+ x e^{-\mu _\infty u}+o(N^{1-\alpha })\right) {\mathbb {P}}\left( M^{(N)}(t)\in \mathrm{d} x\right) \\&\quad =\left( a(N)(1-e^{-\mu _\infty u})+o(N^{1-\alpha })\right) {\mathbb {E}}M^{(N)}(t) +e^{-\mu _\infty u}\,{\mathbb {E}} \left( \left( M^{(N)}(t)\right) ^2\right) \\&\quad =(\xi _N(u)+o(N^{1-\alpha }))(\xi _N(t)+o(N^{1-\alpha })) +e^{-\mu _\infty u}\,{\mathbb {E}} \left( \left( M^{(N)}(t)\right) ^2\right) , \end{aligned}$$

where $\xi _N(u):=a(N)(1-e^{-\mu _\infty u}).$ Now note that, due to the computations underlying (Blom et al. 2015, Thm. 2), with $\varrho ^{({{{i}}})}(t)$ and $\varsigma ^{({{{i}}})}(t)$ as defined in Section 3.2, and with $\psi (N)=o(N^{\max \{1,2-\alpha \}}),$ that

$$\begin{aligned} {\mathbb {E}} \left( (M^{(N)}(t))^2\right) -\left( {\mathbb {E}} M^{(N)}(t) \right) ^2= N^{2-\alpha }\varsigma ^{({{{i}}})}(t)1_{\{\alpha \le 1\}}+N\varrho ^{({{{i}}})}(t)1_{\{\alpha \ge 1\}}+\psi (N). \end{aligned}$$

We now turn our attention to characterizing the covariance between $M^{(N)}(t)$ and $M^{(N)}(t+u)$. Based on the above we have

$$\begin{aligned}&{\mathbb {C}}\mathrm{ov}(M^{(N)}(t),M^{(N)}(t+u)) = {\mathbb {E}}\left( M^{(N)}(t)M^{(N)}(t+u)\right) \\&\qquad - {\mathbb {E}}\left( M^{(N)}(t)\right) {\mathbb {E}}\left( M^{(N)}(t+u)\right) \\&\quad =(\xi _N(u)+o(N^{1-\alpha }))(\xi _N(t)+o(N^{1-\alpha }))+e^{-\mu _\infty u}\left( \xi _N(t)+o(N^{1-\alpha })\right) ^2\\&\qquad +\,e^{-\mu _\infty u}\left( N^{2-\alpha }\varsigma ^{({{{i}}})}(t)1_{\{\alpha \le 1\}} + N\varrho ^{({{{i}}})}(t)1_{\{\alpha \ge 1\}}+\psi (N)\right) \\&\qquad -\,\left( \xi _N(t)+o(N^{1-\alpha })\right) \left( \xi _N (t+u))+o(N^{1-\alpha })\right) . \end{aligned}$$

A direct computation now yields that the zero-order terms cancel, and that we end up with (7).

Appendix 3

In this appendix, we establish (13). The idea is to manipulate differential equation (4), so as to characterize the behavior of ${\pmb m}(t)$ for N large. The first step is to postmultiply the equation by the fundamental matrix $F:=D+\Pi$. We obtain, multiplying the equation by $N^{-\alpha }$ as well,

$$\begin{aligned} {\pmb m}(t) = {\pmb m}(t) \Pi -N^{-\alpha }\,{\pmb m}(t) {{\mathcal {M}}}F + N^{1-\alpha }\,{\pmb \pi }^\mathrm{T}\Lambda F-N^{-\alpha }{\pmb m}'(t)F. \end{aligned}$$

Iterate this equation once, we obtain

$$\begin{aligned}&{\pmb m}(t)={\pmb m}(t)\Pi -N^{-\alpha }{\pmb m}(t){{\mathcal {M}}}\Pi + N^{1-\alpha }{\pmb \pi }^\mathrm{T}\Lambda \Pi -N^{-\alpha }{\pmb m}'(t)\Pi \\&\quad -\,N^{-\alpha }{\pmb m}(t)\Pi {{\mathcal {M}}}F - N^{1-2\alpha }{\pmb \pi }^\mathrm{T}\Lambda F{{\mathcal {M}}}F + N^{1-\alpha }{\pmb \pi }^\mathrm{T}\Lambda F- N^{-\alpha }{\pmb m}'(t)\Pi +o(N^{-\alpha }). \end{aligned}$$

Iterating once again to replace all occurrences of ${\pmb m}(t)$ by ${\pmb m}(t) \Pi$, we obtain, with ${\pmb n}(t):={\pmb m}(t)\Pi$,

$$\begin{aligned}&{\pmb m}(t)= {\pmb n}(t)-N^{-\alpha }{\pmb n}(t)\Pi {{\mathcal {M}}}\Pi \ -N^{1-2\alpha }{\pmb \pi }^\mathrm{T}\Lambda F {{\mathcal {M}}}\Pi +N^{1-\alpha }{\pmb \pi }^\mathrm{T}\Lambda \Pi -N^{-\alpha }{\pmb n}'(t)\\&\quad -\,N^{-\alpha }{\pmb n}(t) \Pi {{\mathcal {M}}}F- N^{1-2\alpha }{\pmb \pi }^\mathrm{T}\Lambda F{{\mathcal {M}}}F + N^{1-\alpha }{\pmb \pi }^\mathrm{T} \Lambda F-N^{-\alpha }{\pmb n}'(t)+ o(N^{-\alpha }). \end{aligned}$$

Now postmultiply this equation by $N^\alpha \Pi {{\pmb 1}}$. Recalling that $F{\pmb 1}={\pmb 1}$ and $\Pi {\pmb 1}={\pmb 1}$, we obtain

$$\begin{aligned} {\pmb n}'(t){\pmb 1}=-{\pmb n}(t)\Pi {{\mathcal {M}}}{\pmb 1}+N{\pmb \pi }^\mathrm{T}\Lambda {\pmb 1} - N^{1-\alpha }{\pmb \pi }^\mathrm{T} \Lambda F{{\mathcal {M}}}{\pmb 1}+o(1). \end{aligned}$$

which leads to, using ${\pmb n}(t){\pmb 1}:=\phi (t)$ and $\Pi ={\pmb 1}{\pmb \pi }^\mathrm{T}$,

$$\begin{aligned} \phi '(t)=-\mu _\infty \phi (t)+N\lambda _\infty - N^{1-\alpha }{\pmb \pi }^\mathrm{T} \Lambda F{{\mathcal {M}}}{\pmb 1}+o(1). \end{aligned}$$

We find that, with $\phi (0)=0$,

$$\begin{aligned} {\mathbb {E}}M^{(N)}(t) = \left( N\frac{\lambda _\infty }{\mu _\infty } -\frac{1}{\mu _\infty } N^{1-\alpha }{\pmb \pi }^\mathrm{T} \Lambda F{{\mathcal {M}}}{\pmb 1}\right) (1-e^{-\mu _\infty t})+o(1). \end{aligned}$$

Appendix 4

We first focus on the first term in the right hand side of (8). To this end, consider the following decomposition:

$$\begin{aligned}&M(t):= M^{(1)}(t,t+u)+ M^{(2)}(t,t+u),\\&M(t+u):= M^{(2)}(t,t+u)+ M^{(3)}(t,t+u), \end{aligned}$$

where $M^{(1)}(t,t+u)$ are the jobs that arrived in [0, t) that are still present at time t but have left at time $t+u,\,M^{(2)}(t,t+u)$ the jobs that have arrived in [0, t) that are still present at time $t+u$, and $M^{(3)}(t,t+u)$ the jobs that have arrived in $[t,t+u)$ that are still present at time $t+u$. Observe that, conditional on J, these three random quantities are independent. As a result,

$$\begin{aligned} {\mathbb {E}}({\mathbb {C}}\mathrm{ov}(M(t),M(t+u))\,|\,J)) = {\mathbb {E}}({\mathbb {V}}\mathrm{ar}\,M^{(2)}(t,t+u)\,|\,J). \end{aligned}$$

Mimicking the arguments used in D’Auria (2008), it is immediate that $M^{(2)}(t,t+u)$, conditional on J, has a Poisson distribution with parameter

$$\begin{aligned} \int _0^t \lambda _{J(s)} e^{-\mu _{J(s)}(t+u-s)}\mathrm{d}s. \end{aligned}$$

We conclude that

$$\begin{aligned} {\mathbb {E}}({\mathbb {C}}\mathrm{ov}(M(t),M(t+u))\,|\,J))= & {} {\mathbb {E}}\left( \int _0^t \lambda _{J(s)} e^{-\mu _{J(s)}(t+u-s)}\mathrm{d}s \right) \\= & {} \sum _{i=1}^d \pi _i \lambda _i\int _0^t e^{-\mu _i(t+u-s)} \mathrm{d}s \\= & {} \sum _{i=1}^d \pi _i \frac{\lambda _i}{\mu _i}\left( 1-e^{-\mu _i t}\right) e^{-\mu _iu}. \end{aligned}$$

Now analyze the second term in the right hand side of (8). First observe that it can be written as

$$\begin{aligned} {\mathbb {C}}\mathrm{ov}\left( \int _0^t \lambda _{J( r)} e^{-\mu _{J( r)}(t-r)}\mathrm{d}r, \int _0^{t+u}\lambda _{J(s)} e^{-\mu _{J(s)}(t+u-s)}\mathrm{d}s \right) . \end{aligned}$$

This decomposes into $I_1+I_2$, where

$$\begin{aligned} I_1:= & {} \sum _{i=1}^d\sum _{j=1}^d\lambda _i\lambda _j\mathscr {K}_{ij},\,\,\text{ where }\,\,\mathscr {K}_{ij}\\:= & {} \int _0^t\int _0^s e^{-\mu _i(t-r)} e^{-\mu _j(t+u-s) }\pi _i\left( p_{ij}(s-r)-\pi _j\right) \mathrm{d}r\mathrm{d}s,\\ I_2:= & {} \sum _{i=1}^d\sum _{j=1}^d\lambda _i\lambda _j\mathscr {L}_{ij},\,\,\text{ where }\,\,\mathscr {L}_{ij}\\:= & {} \int _0^t\int _s^{t+u} e^{-\mu _i(t-r)} e^{-\mu _j(t+u-s) }\pi _j\left( p_{ji}(r-s)-\pi _i\right) \mathrm{d}r\mathrm{d}s. \end{aligned}$$

Let us first evaluate $\mathscr {K}_{ij}\equiv \mathscr {K}_{ij}(t,u).$ To this end, substitute $w:=s-r$ (i.e., replace r by $s-w$), and then interchange the order of integration, so as to obtain

$$\begin{aligned} \mathscr {K}_{ij}= e^{-\mu _j(t+u) }\pi _i \int _0^t\left( \int _w^t e^{(\mu _i+\mu _j)s}\mathrm{d}s\right) e^{-\mu _i(t+w)} \left( p_{ij}(w)-\pi _j\right) \mathrm{d}w. \end{aligned}$$

Performing the inner integral (i.e., the one over s) leads to

$$\begin{aligned} \mathscr {K}_{ij} =\frac{1}{\mu _i+\mu _j} e^{-\mu _j(t+u)} \pi _i \int _0^t \left( e^{-\mu _iw+\mu _jt}-e^{-\mu _it+\mu _jw}\right) \left( p_{ij}(w)-\pi _j\right) \mathrm{d}w. \end{aligned}$$

For $\mathscr {L}_{ij}\equiv \mathscr {L}_{ij}(t,u)$, again by a substitution and by interchanging the order of integration, we obtain $\mathscr {L}_{ij}^{(1)}+\mathscr {L}_{ij}^{(2)}$, where

$$\begin{aligned} \mathscr {L}_{ij}^{(1)}:= & {} e^{-\mu _j(t+u)}\pi _j \int _0^{u}\left( \int _0^t e^{(\mu _i+\mu _j)s}\mathrm{d}s\right) e^{-\mu _i(t-w)} \left( p_{ji}(w)-\pi _i\right) \mathrm{d}w,\\ \mathscr {L}_{ij}^{(2)}:= & {} e^{-\mu _j(t+u)}\pi _j \int _{u}^{t+u}\left( \int _0^{t+u-w}e^{(\mu _i+\mu _j)s}\mathrm{d}s\right) e^{-\mu _i(t-w)} \left( p_{ji}(w)-\pi _i\right) \mathrm{d}w, \end{aligned}$$

which reduce to

$$\begin{aligned} \mathscr {L}_{ij}^{(1)}:= & {} \frac{1}{\mu _i+\mu _j}e^{-\mu _j(t+u)}\pi _j \left( e^{\mu _j t}-e^{-\mu _i t}\right) \int _0^{u} e^{\mu _i w} \left( p_{ji}(w)-\pi _i\right) \mathrm{d}w,\\ \mathscr {L}_{ij}^{(2)}:= & {} \frac{1}{\mu _i+\mu _j}e^{-\mu _i t}\pi _j \int _{u}^{t+u} \left( e^{\mu _i (t+u) -\mu _jw}- e^{\mu _i w-\mu _j(t+u)}\right) \left( p_{ji}(w)-\pi _i\right) \mathrm{d}w. \end{aligned}$$

Now Eq. (9) follows.