Skip to main content
Log in

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

  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  • Anderson D, Blom J, Mandjes M, Thorsdottir H, de Turck K (2015) A functional central limit theorem for a Markov-modulated infinite-server queue. Methodol Comput Appl Probab. doi:10.1007/s11009-014-9405-8

    MATH  Google Scholar 

  • Blom J, Mandjes M (2013) A large-deviations analysis of Markov-modulated inifinite-server queues. Oper Res Lett 41:220–225

    Article  MathSciNet  MATH  Google Scholar 

  • Blom J, de Turck K, Mandjes M (2013a) A central limit theorem for Markov-modulated infinite-server queues. In: Dudin A, de Turck K (eds) Proceedings ASMTA 2013. Lecture Notes in Computer Science (LNCS) series, vol 7984, Ghent, Belgium, pp 81–95

  • Blom J, de Turck K, Mandjes M (2013b) Rare event analysis of Markov-modulated infinite-server queues: a Poisson limit. Stoch Models 29:463–474

    Article  MathSciNet  MATH  Google Scholar 

  • Blom J, Kella O, Mandjes M, de Turck K (2014a) Tail asymptotics of a Markov-modulated infinite-server queue. Queueing Syst 78:337–357

    Article  MathSciNet  MATH  Google Scholar 

  • Blom J, Kella O, Mandjes M, Thorsdottir H (2014b) Markov-modulated infinite server queues with general service times. Queueing Syst 76:403–424

    Article  MathSciNet  MATH  Google Scholar 

  • Blom J, de Turck K, Mandjes M (2015) Analysis of Markov-modulated infinite-server queues in the central-limit regime. Probab Eng Inf Sci, FirstView, http://journals.cambridge.org/article_S026996481500008X

  • D’Auria B (2008) M/M/\(\infty \) queues in semi-Markovian random environment. Queueing Syst 58:221–237

    Article  MathSciNet  MATH  Google Scholar 

  • Huang G, Jansen HM, Mandjes M, Spreij P, de Turck K (2014) Markov-modulated Ornstein–Uhlenbeck processes. Adv Appl Probab 48(1):235–254

    Article  MathSciNet  MATH  Google Scholar 

  • Jacod J, Shiryayev A (1987) Limit theorems for stochastic processes. Springer, Berlin

    Book  Google Scholar 

  • Keilson J, Servi L (1993) The matrix M/M/\(\infty \) system: retrial models and Markov modulated sources. Adv Appl Probab 25:453–471

    Article  MathSciNet  MATH  Google Scholar 

  • O’Cinneide C, Purdue P (1986) The M/M/\(\infty \) queue in a random environment. J Appl Probab 23:175–184

    Article  MathSciNet  MATH  Google Scholar 

  • Whitt W (2007) Proofs of the martingale FCLT. Probab Surv 4:268–302

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors thank Peter Spreij (Korteweg-de Vries Institute for Mathematics, University of Amsterdam) for useful suggestions.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to K. De Turck.

Additional information

M. Mandjes’ research is partly funded by the NWO Gravitation project NETWORKS, Grant No. 024.002.003.

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.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Blom, J., De Turck, K. & Mandjes, M. Functional central limit theorems for Markov-modulated infinite-server systems. Math Meth Oper Res 83, 351–372 (2016). https://doi.org/10.1007/s00186-016-0531-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00186-016-0531-7

Keywords

Navigation