Tail asymptotics of a Markov-modulated infinite-server queue

Abstract

This paper analyzes large deviation probabilities related to the number of customers in a Markov-modulated infinite-server queue, with state-dependent arrival and service rates. Two specific scalings are studied: in the first, just the arrival rates are linearly scaled by $N$ (for large $N$), whereas in the second in addition the Markovian background process is sped up by a factor $N^{1+\varepsilon }$, for some $\varepsilon >0$. In both regimes (transient and stationary) tail probabilities decay essentially exponentially, where the associated decay rate corresponds to that of the probability that the sample mean of i.i.d. Poisson random variables attains an atypical value.

Appendix

Represent the elements of the set of combinations of arrival rates and service rates, i.e., $\{({\mu _i,\lambda _i})\,|\,i\in \{1,\ldots ,d\}\}$, as points in the $({\mu ,\lambda })$-plane. Also, we define, for any $i,j$ such that $\mu _i\not =\mu _j$,

$$\begin{aligned} \gamma (i,j):=\frac{\lambda _i-\lambda _j}{\mu _i-\mu _j}, \end{aligned}$$

denoting the slope between the points $({\mu _i,\lambda _i})$ and $({\mu _j,\lambda _j})$ in the $({\mu ,\lambda })$-plane. Now consider the following algorithm in pseudocode to find ${\varrho }^+$, i.e., the maximum slope between the origin and any $(\mu _i,\lambda _i)$.

Algorithm 1

Input: $\lambda _i, \mu _i, i\in \{1,\ldots ,d\}$ – Output: k, $I_0,\ldots , I_k$ and $i_1,\ldots , i_k$.

• 0. Set $\ell :=1, I_0:=0, {\fancyscript{A}}_0:=\{1,\ldots ,d\}$, and

  $$\begin{aligned} i_1:=\arg \min \left\{ \mu _i: \lambda _i=\max _{j\in {\fancyscript{A}}_0}\lambda _j\right\} . \end{aligned}$$

• 1. Let

  $$\begin{aligned} {\fancyscript{A}}_\ell :=\left\{ i: I_{\ell -1}<\gamma (i,i_\ell )<\varrho _{i_\ell }\,\mathtt{and}\, \mu _i<\mu _{i_\ell }\right\} . \end{aligned}$$

  If ${\fancyscript{A}}_\ell$ is empty go to step (3), otherwise, go to step (2).

• 2. Let

  $$\begin{aligned} I_\ell :=\min _{j\in A_\ell }\gamma (j,i_{\ell }),\,\,\,i_{\ell +1}:=\arg \min _{i\in {\fancyscript{A}}_\ell }\left\{ \mu _i:\gamma (i,i_\ell ) =I_\ell \right\} . \end{aligned}$$

  Set $\ell :=\ell +1$ and return to step (1).

• 3. Set $I_\ell :=\varrho _{i_\ell }$ and STOP.

To aid in understanding, see Fig. 1 for an example with ${d}=7$ and $k=2$. Note that $i_1$ is the index of the node with the largest $\lambda _i$ and $i_2$ is that of the node with the largest $\varrho _i$ ($=\varrho ^+$). $I_0$ is the slope zero, $I_1$ is the slope of the segment connecting $(\mu _{i_1},\lambda _{i_1})$ and $(\mu _{i_2},\lambda _{i_2})$, and $I_2=\varrho ^+$. Note that in this case there are two indices $j$ for which $I{_1}=\gamma (i_1,j)$, and that $i_2$ is the one having the smaller value of $\mu _j$. Also note that there is a point (close to (0,0)) that if we connect a segment between it and $i_2$ the slope is greater than $I_1$. However, since this slope is also greater than $\varrho _{i_2}=\varrho ^+$, the algorithm stops at $\ell =2$. The bold segments describe a concave function, which is the reason why $\varrho _\ell$, the slopes of the segment connecting $(0,0)$ and $({\mu _{i_\ell },\lambda _{i_\ell }})$, increases in $\ell$ and in particular when the algorithm stops then $\varrho _{i_\ell }=\varrho ^+$. Figure 2 demonstrates that the maximal value of $\lambda _i-c\mu _i$ is given by $i_1$ for $I_0<c<I_1$ and $(\mu _i,\lambda _i) \in [\mu _{i_2},\mu _{i_1}]\times [\lambda _{i_2},\lambda _{i_1}]$ and by $i_2$ for $I_1<c<I_2$ and $(\mu _i,\lambda _i) \in [0,\mu _{i_2}]\times [0,\lambda _{i_2}]$.

Fig. 1

Example with $d=7$ and $k=2$

Fig. 2

Maximal value of $\lambda _i-c\mu _i$

Algorithm 2

Input: $\lambda _i, \mu _i, i\in \{1,\ldots ,d\}$ – Output: k, $I_0,\ldots , I_k$ and $i_1,\ldots , i_k$.

• 0. Set $\ell :=1, I_0:=0, {\fancyscript{A}}_0:=\{1,\ldots ,d\}$, and

  $$\begin{aligned} i_1:=\arg \max \left\{ \mu _i:\lambda _i=\min _{j\in {\fancyscript{A}}_0}\lambda _j\right\} . \end{aligned}$$

• 1. Let

  $$\begin{aligned} {\fancyscript{A}}_\ell :=\left\{ i: I_{\ell -1}<\gamma (i,{i_\ell })<\varrho _{i_\ell }\,\mathtt{and}\,\mu _i>\mu _{i_\ell }\right\} . \end{aligned}$$

  If ${\fancyscript{A}}_\ell$ is empty go to step (3), otherwise, go to step (2).

• 2. Let

  $$\begin{aligned} I_\ell :=\min _{j\in {\fancyscript{A}}_\ell }\gamma (j,i_{\ell })\!,\,\,\, i_{\ell +1}:=\arg \max _{i\in {\fancyscript{A}}_\ell }\left\{ \mu _i:\gamma (i,i_\ell ) =I_\ell \right\} \!. \end{aligned}$$

  Set $\ell :=\ell +1$ and return to step (1).

• 3. Set $I_\ell :=\varrho _{i_\ell }$ and STOP.

Fig. 3

Example with $d=7$ and $k=2$

Fig. 4

Minimal value of $\lambda _i-c\mu _i$

The corresponding figures are Figs. 3 and 4.