2.1. Time and customer averages

Consider a real-valued stochastic process $\{X(t);\, t\in \mathbb{R}\}$ with left-continuous sample paths and a point process $\{T_n;\, n\in \mathbb{Z}\}$ . X(t) represents the state of a system just prior to time t (because of its left continuity) and $\{T_n\}$ represents arrivals of customers to the system. Customers are labeled following the standard convention such that $T_0\le 0< T_1$ . We assume no batch arrivals; that is, $T_n<T_{n+1}$ for all $n\in \mathbb{Z}$ . The ‘state’ of the system may represent the number of customers or the total workload for the queueing systems.

The time average of $\{X(t)\}$ from time 0 up to time t is defined by

\begin{equation*} T_t=\frac{1}{t}\int_0^t X(s)\,{\mathrm{d}} s,\end{equation*}

and the customer average of $\{X(t)\}$ from time 0 to time t is defined by

\begin{equation*} C_t=\frac{1}{N(t)}\sum_{n=1}^{N(t)} X(T_n),\qquad N(t)\stackrel{\rm def}{=} \sum_{n=1}^\infty \mathbf{1}_{T_n\le t},\end{equation*}

where $\mathbf{1}_{A}$ is an indicator function, which is equal to 1 (0) if A is true (false). The analysis in this paper is conducted in the stationary and ergodic framework like [Reference Peköz, Ross and Seshadri22, Reference Shanthikumar and Zazanis26]; that is, $\{X(t)\}$ and $\{T_n;\, n\in \mathbb{Z}\}$ are assumed to be jointly stationary and ergodic under probability measure $\mathbb{P}$ . Under this framework,

\begin{equation*} \lim_{t\to\infty} T_t = \lim_{t\to\infty}\frac{1}{t}\int_0^t X(s)\,{\mathrm{d}} s = \mathbb{E}[X(0)],\end{equation*}

where $\mathbb{E}$ denotes the expectation with respect to $\mathbb{P}$ , and

\begin{equation*} \lim_{t\to\infty} C_t = \lim_{t\to\infty} \frac{1}{N(t)}\sum_{n=1}^{N(t)} X(T_n) = \mathbb{E}^0[X(0)],\end{equation*}

where $\mathbb{E}^0$ denotes the expectation with respect to $\mathbb{P}^0$ , which is the Palm transformation [Reference Baccelli and Bremaud1] of $\mathbb{P}$ with respect to $\{T_n\}$ . Similarly, the time-averaged probability that $\{X(t)\}$ is in any measurable set A is equal to $\mathbb{P}(X(0)\in A)$ because

\begin{equation*} \mathbb{P}(X(0)\in A) = \lim_{t\to\infty}\frac{1}{t}\int_0^t \mathbf{1}_{X(s)\in A}\,{\mathrm{d}} s,\end{equation*}

and the customer-averaged probability that $\{X(t)\}$ is in A is equal to $\mathbb{P}^0(X(0)\in A)$ because

\begin{equation*} \mathbb{P}^0(X(0)\in A) = \lim_{t\to\infty} \frac{1}{N(t)}\sum_{n=1}^{N(t)} \mathbf{1}_{X(T_n)\in A}.\end{equation*}

Thus, the issue of the inequalities between time and customer averages becomes one on the inequalities between the expectations by $\mathbb{P}$ and $\mathbb{P}^0$ .

2.2. Lack of anticipation assumption

We define a process $X_0(t)$ ( $t\in (0,\infty)$ ) to be the state of the above system at time t given that it is initiated at time 0 by a customer arrival and according to the Palm measure, so that $\mathbb{P}(X_0(0)\in A) = \mathbb{P}^0(X(0)\in A)$ , but it continues without allowing any further arrivals to enter the system after time 0 [Reference Peköz, Ross and Seshadri22].

The distribution function for the inter-arrival times for customers is denoted by $F_\tau(t)\stackrel{\rm def}{=}\mathbb{P}^0(T_1\le t)$ , and $\tau$ denotes a random variable with distribution function $F_\tau$ . The inter-arrival time for customers is assumed to have a finite mean; that is, $\mathbb{E}^0[T_1]=\mathbb{E}[\tau]=1/\lambda <\infty$ . Throughout this paper, the following lack of anticipation assumption is made.

Definition 2.1. The state of the system X(t) is said to satisfy the lack of anticipation assumption if, for any positive bounded real function h, X(t) satisfies

(2.1) \begin{equation} \mathbb{E}^0[h(X(t))\mid T_1> t]=\mathbb{E}^0[h(X(t))\mid T_1=t]=\mathbb{E}[h(X_0(t))]\quad \text{for $t>0$}. \end{equation}

According to [Reference Shanthikumar and Zazanis26], (2.1) is equivalent to the following condition:

(2.2) \begin{equation} \mathbb{E}^0[h(X(t))\mid T_1\ge t]=\mathbb{E}^0[h(X(t))\mid T_1=t]=\mathbb{E}[h(X_0(t))]\quad \text{for $t>0$}.\end{equation}

The lack of anticipation assumption was introduced in [Reference Shanthikumar and Zazanis26] and used in [Reference Peköz, Ross and Seshadri22]. This assumption intuitively states that, when customer 0 arrives at time 0 $(=T_0)$ , the state of the system at time $t>0$ is conditionally independent of $T_1$ , which is the arrival time for the next customer (customer 1), given that $T_1>t$ . The lack of anticipation assumption holds for a queue driven by a renewal arrival process [Reference Peköz, Ross and Seshadri22].

2.3. Stochastic order

Since the main results of this paper are stated using the notions of usual stochastic order, (increasing) convex order, NB(W)UE, and HNB(W)UE, their definitions and related results used here are summarized below. Concerning the details of these definitions and related results, please see a textbook on stochastic orders, such as [Reference Müller and Stoyan19, Reference Rolski24, Reference Shaked and Shanthikumar25].

Proposition 2.1. Let $Z_1$ and $Z_2$ be random variables. The following statements are equivalent:

1. (i) $Z_1\le_{\rm icx} Z_2$ ;

2. (ii) $\mathbb{E}[(Z_1-x)_+]\le \mathbb{E}[(Z_2-x)_+]$ for all $x\in\mathbb{R}$ ,

where

\begin{equation*} (x)_+ = \begin{cases} x & if\ x\ge 0,\\ 0 & otherwise. \end{cases} \end{equation*}

In the following two definitions, $Z_t$ denotes a random variable with distribution function $F_{Z_t}(x)\stackrel{\rm def}{=} \mathbb{P}(Z\le x+t\mid Z>t)$ , which is the distribution of the residual lifetime of Z after time t.

Definition 2.4. If

\begin{equation*} \frac{1}{t}\int_0^t\frac{{\mathrm{d}} s}{\mathbb{E}[Z_s]}\ge ({\le})\ \frac{1}{\mathbb{E}[Z]} \end{equation*}

for all $t>0$ , then we say that Z is HNBUE (HNWUE).

The notion of HNBUE (HNWUE) was introduced in [Reference Rolski23] and studied in [Reference Klefsjö10]. Although HNBUE (HNWUE) seems to be less familiar than NBUE (NWUE), it will take a main role in this paper. Note that the expression in Definition 2.4 can be written as

\begin{equation*} \bigg\{\frac{1}{t}\int_0^t\frac{{\mathrm{d}} s}{\mathbb{E}[Z_s]}\bigg\}^{-1} \le ({\ge})\ \mathbb{E}[Z],\end{equation*}

which means that the integral harmonic mean of $\mathbb{E}[Z_t]$ is less than (greater than) or equal to $\mathbb{E}[Z]$ for all t if Z is HNBUE (HNWUE). It follows from Definitions 2.3 and 2.4 that if Z is NBUE (NWUE), then Z is HNBUE (HNWUE). That is, the HNBUE (HNWUE) class is larger than the NBUE (NWUE) class. The following result will be used in the next section.

Proposition 2.2. Let Z be a random variable with mean a. The following statements are equivalent:

1. (i) Z is HNBUE (HNWUE);

2. (ii) $Z^{(\mathrm{e})} \le_{\rm st} ({\ge_{\rm st}})\ {\rm Exp}(a)$ ;

3. (iii) $Z \le_{\rm cv} ({\ge_{\rm cv}})\ {\rm Exp}(a)$ ,

where $Z^{(\mathrm{e})}$ is a random variable with the equilibrium distribution of Z defined by

\begin{equation*} F_Z^{(\mathrm{e})}(x)\stackrel{\rm def}{=}\frac{1}{\mathbb{E}[Z]} \int_0^x (1-F_Z(t))\,{\mathrm{d}} t, \end{equation*}

and ${\rm Exp}(a)$ denotes an exponential random variable with mean a.

In what follows, we say $\{T_n\}$ is HNBUE (HNWUE) if its inter-arrival time $\tau$ is HNBUE (HNWUE). According to Proposition 2.2, $\{T_n\}$ is HNBUE (HNWUE) if and only if

\begin{equation*} \frac{1}{\mathbb{E}^0[T_1]}\int_0^t \mathbb{P}^0(T_1> s)\,{\mathrm{d}} s \le ({\ge})\ \exp\bigg\{{-}\frac{t}{\mathbb{E}^0[T_1]}\bigg\}.\end{equation*}

2.4. Total time on test transform

For its use in Section 5, we describe the scaled total time on test (TTT) transform of a life distribution (that is, a distribution function with $F(0{-})=0$ ) [Reference Barlow, Doksum, Le Carn, Neyman and Scott2, Reference Klefsjö10, Reference Klefsjö11].

Definition 2.5. Let F(t) be a life distribution with mean $\lambda^{-1}$ . The scaled TTT-transform, $\varphi_F$ , of F is then defined by

\begin{equation*} \varphi_F(x)=\lambda\int_0^{F^{-1}(x)}(1-F(t))\,{\mathrm{d}} t\quad \text{for $0\le x\le 1$}, \end{equation*}

where $F^{-1}(x)=\inf\{x\colon F(t)\ge x\}$ .

The scaled TTT-transform is defined for values of $x\in[0,1]$ , and the transformed values are also in [0,1]. This means that the scaled TTT-transform can be illustrated by a curve within the unit square. It is easy to see that $\varphi_F(x)=x$ if $F(t)=1-\mathrm{e}^{-\mu t}$ . That is, the diagonal of the unit square corresponds to an exponential distribution.

The shape of the scaled TTT-transform of a life distribution shows the aging properties of the distribution [Reference Klefsjö10, Reference Klefsjö11]. For example, whether a random variable is NBUE or NWUE can be seen from the scaled TTT-transform of its distribution function, as shown in the next theorem.

Whether a random variable is HNBUE or HNWUE can also be seen from the scaled TTT-transform of its distribution function, as shown in the next theorem.

4.1. Workload of GI/G/c/K queue

Consider a GI/G/c/K queue, where an arriving customer is assigned to an empty server or waits in a queue if all servers are busy. Once assigned to a server, a customer is served at the unit rate until completion. Let W(t) and L(t) respectively denote the workload and the number of customers in the queue at time t. The time- and customer-stationary distribution functions of the workload are respectively denoted by $F_W(x)\stackrel{\rm def}{=}\mathbb{P}(W(0)\le x)$ and $F_W^0(x)\stackrel{\rm def}{=}\mathbb{P}^0(W(0{-})\le x)$ , where $W(0{-})\stackrel{\rm def}{=}\lim_{t\downarrow 0}W({-}t)$ is the left-hand limit of W(0). Let $\{W_0(t);\, t\in [0,\infty)\}$ denote a process which represents the workload of a virtual queue without allowing any further arrivals to enter the system after time 0 and satisfies $\mathbb{P}(W_0(0)\le x) = \mathbb{P}^0(W(0)\le x)$ for all $x\ge 0$ . Likewise, let $\{L_0(t);\, t\in [0,\infty)\}$ denote a process which represents the number of customers in the virtual queue and satisfies $\mathbb{P}(L_0(0)=x) = \mathbb{P}^0(L(0)=x)$ for all $x\ge 0$ .

Let $L_s(t)\stackrel{\rm def}{=} \min\{s,L_0(t)\}$ . Since $L_s(t)$ is the number of busy servers for the virtual queue, $W_0(t)$ can be expressed as (Figure 2)

(4.1) \begin{equation} W_0(t) = W_0(0) - \int_0^t L_s(t)\,{\mathrm{d}} t.\end{equation}

Using this fact, we first show the following result.

Figure 2.

Change of workload over time ( $c\ge 4$ ).

Proof. We define $g(t) \stackrel{\rm def}{=} \mathbb{E}[(W_0(t{-})-x)_+]$ . Note that $\mathbb{E}[(W_0(t{-})-x)_+]$ is equal to $\mathbb{E}[(W_0(t)-x)_+]$ because there are no arrivals after time 0 in the virtual queue, and thus $W_0(t)$ is continuous for $t>0$ . It follows from (4.1) that, for $t>0$ ,

\begin{equation*} \frac{{\mathrm{d}}}{{\mathrm{d}} t}(W_0(t)-x)_+ = -L_s(t)\mathbf{1}_{W_0(t)\ge x}\le 0. \end{equation*}

In addition to this, $\frac{{\mathrm{d}}}{{\mathrm{d}} t}(W_0(t)-x)_+$ is increasing because $L_s(t)$ is decreasing. In summary, $W_0(t)$ is decreasing and convex with respect to sample path, and thus g(t) is also decreasing and convex. Hence, it follows from Theorem 3.1 that if $\tau$ is HNBUE (HNWUE), then

\begin{equation*} \mathbb{E}^0[(W(0{-})-x)_+] \le ({\ge})\ \mathbb{E}[(W(0)-x)_+]. \end{equation*}

The above equality holds for all x, and thus the stated result follows from Proposition 2.1.

We could have a stronger result for GI/G/1/K queues than for GI/G/c/K queues. To show this, let $F_\textrm{S}^0(x)\stackrel{\rm def}{=}\mathbb{P}^0(W(0)\le x)$ . Note that $F_\textrm{S}^0(x)$ is the distribution function of the sojourn time for a customer when the service discipline is first in, first out (FIFO).

Proof. First, assume that $\{T_n\}$ is HNBUE. We define, for $t>0$ ,

\begin{equation*} g(t;\,x) \stackrel{\rm def}{=} \mathbb{E}[\mathbf{1}_{W_0(t{-})\le x}] = \mathbb{E}[\mathbf{1}_{W_0(t)\le x}]. \end{equation*}

We can see that

(4.2) \begin{equation} g(t;\,x) = \mathbb{P}(W_0(t)\le x) = \mathbb{P}(W_0(0)\le x+t) = \mathbb{P}^0(W(0)\le x+t) = F_\mathrm{S}^0(x+t), \end{equation}

where the second equality follows from $W_0(t)$ being continuous for $t> 0$ because there are no arrivals after time 0 in the virtual queue. The fact that $F_\mathrm{S}^0(x)$ is increasing and concave, together with (4.2), proves that $g(t;\,x)$ is increasing and concave in t. Hence, it follows from Corollary 3.1 that $\mathbb{E}^0[\mathbf{1}_{W(0{-})\le x}] \ge \mathbb{E}[\mathbf{1}_{W(0)\le x}]$ , which means that $F_W^0\le_{\rm st} F_W$ . Reversing the inequalities in the above arguments proves that $F_W^0\ge_{\rm st} F_W$ when $\{T_n\}$ is HNWUE.

Proof. It is known [Reference Shortle, Thompson, Gross and Harris27] that

(4.3) \begin{equation} F_\mathrm{S}^0(x) = 1-\mathrm{e}^{-\mu(1-\eta)x}, \end{equation}

where $\mu$ is the inverse of the mean service time for a customer, and $\eta$ is the unique solution to the following equation for $z\in (0,1)$ :

(4.4) \begin{equation} z = \mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]. \end{equation}

Since the $F_\mathrm{S}^0(x)$ in (4.3) is increasing and concave, applying Lemma 4.2 completes the proof.

Remark 4.1. Corollary 4.1 can be shown by the following elementary consideration. For GI/M/1 queues,

(4.5) \begin{equation} F_W^0(x) = 1-\eta\mathrm{e}^{-\mu(1-\eta)x}, \qquad F_W(x) = 1-\rho\mathrm{e}^{-\mu(1-\eta)x}, \end{equation}

where $\rho\stackrel{\rm def}{=} \lambda/\mu$ and $\eta$ is the solution to (4.4) in (0,1). Note that $F_W^0(x)$ is the distribution of the actual waiting time for a GI/M/1 queue for FIFO discipline and its expression was given in [Reference Shortle, Thompson, Gross and Harris27]; $F_W(x)$ is the distribution of virtual waiting time. Now, suppose that $\{T_n\}$ is HNBUE. It follows from Proposition 2.2 that $\tau\le_{\rm cx} {\rm Exp} (1/\lambda )$ , and thus

\begin{equation*} \mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}] \le \mathbb{E}[\mathrm{e}^{\mu(z-1){\rm Exp} (1/\lambda )}]. \end{equation*}

Since $\eta$ is the intersection of $f(z)=\mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]$ and $f(z)=z$ , we see that $\eta\le \rho$ when $\mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]\le \mathbb{E}[\mathrm{e}^{\mu(z-1){\rm Exp} (1/\lambda )}]$ . As an example, we compare $\mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]$ when $\tau=1/\lambda$ (D/M/1 queue: solid curve) and $\mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]$ when $\tau={\rm Exp} (1/\lambda)$ (M/M/1 queue: dashed curve) in Figure 3. It follows from (4.5) that, if $\eta\le\rho$ , then $F_W^0(x)\ge F_W(x)$ for all $x\ge 0$ . Thus, if $\{T_n\}$ is HNBUE, then $F_W^0\le_{\rm st} F_W$ . We can also obtain the desired result when $\{T_n\}$ is HNWUE in a similar way.

Figure 3.

Comparison of $\mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]$ for D/M/1 and M/M/1 queues.

4.2. Number of customers of GI/M/c/K queue

Consider a GI/M/c/K queue where the mean service time for a customer is $1/\mu$ . The time- and customer-stationary distribution functions of the number of the customers in the queues are respectively denoted by

\begin{align*} F_L(x)\stackrel{\rm def}{=}\mathbb{P}(L(0)\le x),\qquad F_L^0(x)\stackrel{\rm def}{=}\mathbb{P}^0(L(0{-})\le x),\end{align*}

where $L(0{-})\stackrel{\rm def}{=}\lim_{t\downarrow 0}L({-}t)$ is the left-hand limit of L(0). Let $D_0(t)$ denote the number of customers departed from the virtual queue (see Section 4.1) during (0, t]. $L_0(t)$ can be expressed as $L_0(t)=L_0(0) - D_0(t)$ . Note that $D_0(t)$ admits the $\mathscr {F}_t$ -predictable stochastic intensity $\mu L_s(t{-})$ , where $\mathscr {F}_t$ is the history [Reference Baccelli and Bremaud1] of the virtual queue up to time t and the arrival process up to time 0. It follows from a property of stochastic intensity [Reference Baccelli and Bremaud1] that

(4.6) \begin{equation} \mathbb{E}[D_0(t)\mid\mathscr {F}_0] = \mathbb{E}\bigg[\int_{0}^t \mu L_s(u{-})\,{\mathrm{d}} u\bigg].\end{equation}

Proof. We define $g(t) \stackrel{\rm def}{=} \mathbb{E}[(L_0(t{-})-x)_+]$ and $g_A(t)\stackrel{\rm def}{=} \mathbb{E}[(L_0(t{-})-x)_+\mid\mathscr {F}_0]$ . It follows from (4.6) that

\begin{equation*} \frac{{\mathrm{d}}}{{\mathrm{d}} t}g_A(t) = -E\big[\mu L_s(t{-})\mathbf{1}_{L_0(t)\ge x}\mid\mathscr {F}_0\big] \le 0. \end{equation*}

Thus, $g_A(t)$ is decreasing. Since $g(t)=\mathbb{E}[g_A(t)]$ , g(t) is also decreasing. In addition to this, $\frac{{\mathrm{d}}}{{\mathrm{d}} t}g_A(t)$ is increasing because $L_s(t)$ is decreasing. Thus, $g_A(t)$ and therefore also g(t) are convex for $t>0$ . Hence, if $\{T_n\}$ is HNBUE (HNWUE), then

\begin{equation*} \mathbb{E}^0[(L(0{-})-x)_+] \le ({\ge})\ \mathbb{E}[(L(0)-x)_+]. \end{equation*}

This inequality holds for all x, and thus the stated result follows from Proposition 2.1.

Next, consider GI/M/1 queues.

Proof. Letting

\begin{align*} \mathbb{P}(k,t) & \stackrel{\rm def}{=} \mathbb{E}[\mathbf{1}_{L_0(t{-})\le k}] = \mathbb{P}(L_0(t{-})\le k), \\ \mathbb{P}(k,t) & \stackrel{\rm def}{=} \mathbb{E}[\mathbf{1}_{L_0(t{-})= k}] = \mathbb{P}(L_0(t{-})= k), \end{align*}

it follows that $\frac{{\mathrm{d}}}{{\mathrm{d}} t}p(k,t) = \mu(p(k+1,t)-p(k,t))$ and $\frac{{\mathrm{d}}}{{\mathrm{d}} t}p(0,t) = \mu p(1,t)$ . Hence,

(4.7) \begin{align} \frac{{\mathrm{d}}}{{\mathrm{d}} t}\mathbb{P}(k,t) & = \sum_{l=0}^k\frac{{\mathrm{d}}}{{\mathrm{d}} t}p(l,t) = \mu p(1,t) + \sum_{l=1}^k \mu(p(k+1,t)-p(k,t)) = \mu p(k+1,t)\ge 0, \end{align}

(4.8) \begin{align} \frac{{\mathrm{d}}^2}{{\mathrm{d}} t^2}\mathbb{P}(k,t) & = \mu\frac{{\mathrm{d}}}{{\mathrm{d}} t}p(k+1,t) = \mu^2(p(k+2,t)-p(k+1,t)). \end{align}

It can be seen that

where we use $p(k,0)=\mathbb{P}(L_0(0{-}) = k)=(1-\eta)\eta^k$ [Reference Shortle, Thompson, Gross and Harris27]. Substituting the above equality into (4.8) yields

(4.9) \begin{equation} \frac{{\mathrm{d}}^2}{{\mathrm{d}} t^2}\mathbb{P}(k,t) = -\mu^2 (1-\eta)^2 \eta^{k}\mathrm{e}^{-\mu t (1-\eta)}\le 0. \end{equation}

As (4.7) and (4.9) mean that p(k, t) is increasing and concave with respect to t, it follows from Corollary 3.1 that $\mathbb{E}^0[\mathbf{1}_{L(0{-})\le k}]\ge ({\le})\ \mathbb{E}[\mathbf{1}_{L(0)\le k}]$ , or $\mathbb{P}^0(L(0{-})> k)\le ({\ge})\ \mathbb{P}(L(0)> k)$ , which completes the proof.

Remark 4.2. Consider a GI/GI/1/K queue and let $\{T^\mathrm{D}_n \colon n \in \mathbb{Z}\}$ denote the departure times for the customers from the queue. The departure times are assumed to be labeled such that $T^\mathrm{D}_0\le 0 < T^\mathrm{D}_1$ . Let $F_\sigma^{(\mathrm{e})}$ denote the equilibrium distribution of the service time for the customers. If the remaining service time for a customer in service at customer arrival instants follows the equilibrium distribution $F_\sigma^{(\mathrm{e})}$ , that is,

(4.10) \begin{equation} \mathbb{P}^0(T^\mathrm{D}_1 \le x\mid L_s(0+) > 0) = F^{(\mathrm{e})}_\sigma (x), \end{equation}

then (4.6) holds because $D_1,D_2,\dots$ becomes a stationary renewal process and thus $D_0(t)=\mu t$ [Reference Durrett5]. This argument suggests that Lemma 4.3 holds for GI/GI/1/K queues if (4.10) holds, and the same argument can also be applied to GI/GI/c/K queues. However, note that (4.10) does not hold in general, and thus this argument does not prove that Lemma 4.3 holds for all GI/GI/1/K queues. Nevertheless, as shown in Section 5, we have numerically found that $\mathbb{E}^0[L]\le ({\ge})\ \mathbb{E}[L]$ seems to hold for GI/GI/1 queues if the arrival process is HNBUE (HNWUE) even for non-exponential service time distributions. This result implies that (4.10) approximately holds for most of the conditions of these queues.

Remark 4.3. For GI/M/1 queues,

\begin{alignat*}{2} \mathbb{P}^0(L(0{-})> k) & = \eta^{k+1}, \qquad & k & = 0,1,\dots,\\ \mathbb{P}(L(0)> k) & = \rho\eta^{k}, & k & = 0,1,\dots, \end{alignat*}

where $\eta$ is the solution of (4.4) in (0,1). If $\tau$ is HNBUE (HNWUE), then $\eta\le ({\ge})\ \rho$ , as shown in Remark 4.1. From this fact, Corollary 4.2 also follows.

4.3. Workload of GI+G/GI/1 queue

Next, we consider an example given in [Reference Shanthikumar and Zazanis26] where the superposition of two stationary and ergodic arrival processes, $\{T_n^i;\, n\in \mathbb{Z}\}$ , $i=0,1$ , is fed into a single-server queue. The two arrival processes are independent. We assume that $\{T_n^0\}$ is a renewal arrival process; that is, its inter-arrival times are independent and identically distributed.

Lemma 4.4. If $\{T_n^0\}$ is HNBUE (HNWUE) then, for GI+G/GI/1 queues,

\begin{equation*} \mathbb{E}^0[W(0{-})]\le ({\ge})\ \mathbb{E}[W(0)]. \end{equation*}

Proof. In the proof, we call customers arriving at $\{T_n^i\}$ , $i=0,1$ , type-i customers, and assume that type-1 customers have preemptive priority over type-0 customers. Note that this assumption is not at all essential, because the concern of this lemma is the total workload. We let $W(t)=W^0(t)+W^1(t)$ , where $W^0(t)$ ( $W^1(t)$ ) is the workload due to type-0 (type-1) customers. Note that $W^1(t)$ is independent of the arrival process $\{T_n^0\}$ . Because of this, the statistics of $W^1(t)$ under $P^0$ , which is the Palm probability measure with respect to $\{T_n^0\}$ , and P are the same, as mentioned in [Reference Shanthikumar and Zazanis26]. For $t>0$ , we let $g(t) \stackrel{\rm def}{=} \mathbb{E}[W_0(t{-})]$ . Note that $W_0(t{-})$ is expressed as the sum of $W_0^0(t{-})$ and $W_0^1(t{-})$ , where $W_0^0(t)$ ( $W_0^1(t)$ ) is the workload in the virtual queue due to type-0 (type-1) customers. Since $\mathbb{E}[W_0^1(t{-})]= \mathbb{E}^0[W^1(t{-})]$ (from the definition of $W_0$ ) and $\mathbb{E}^0[W^1(t{-})]=\mathbb{E}[W^1(t{-})]$ ( $W^1(t)$ under $P^0$ is statistically the same as under P), it follows that

\begin{equation*} g(t) = \mathbb{E}[W_0^0(t{-})] + \mathbb{E}[W^1(t{-})] = \mathbb{E}[W_0^0(t)] + \mathbb{E}[W^1(0)], \end{equation*}

where the second equality follows from the stationarity of $W^1(t)$ and the continuity of $W_0^0(t)$ for $t>0$ . Since $\frac{{\mathrm{d}}}{{\mathrm{d}} t}W_0^0(t) = -1$ if $W_0^1(t)=0$ with respect to sample path, it follows that

(4.11) \begin{align} \frac{{\mathrm{d}}}{{\mathrm{d}} t}g(t) & = -\mathbb{E}[\mathbf{1}_{W_0^0(t)=0}\mathbf{1}_{W_0^1(t)>0}] \nonumber \\ & = -\mathbb{E}[\mathbb{E}[\mathbf{1}_{W_0^1(t)=0}\mathbf{1}_{W_0^0(t)>0}\mid\mathbf{1}_{W_0^1(t)>0}]]\nonumber\\ & = -\mathbb{E}[\mathbf{1}_{W_0^1(t)=0}\mathbf{1}_{W_0^0(t)>0}\mid W_0^1(t)>0] \mathbb{P}(W_0^1(t)>0) \nonumber\\ & \quad - \mathbb{E}[\mathbf{1}_{W_0^1(t)=0}\mathbf{1}_{W_0^0(t)>0}\mid W_0^1(t)=0]\mathbb{P}(W_0^1(t)=0)\nonumber\\ & = -\mathbb{E}[\mathbf{1}_{W_0^1(t)=0}\mathbf{1}_{W_0^0(t)>0}\mid W_0^1(t)=0]\mathbb{P}(W_0^1(t)=0)\nonumber\\ & = -\mathbb{E}[\mathbf{1}_{W_0^0(t)>0}\mid W^1(t)=0]\mathbb{P}(W^1(0)=0)\le 0, \end{align}

where the last equality follows from the fact that $\mathbb{P}(W_0^1(t)=0)=\mathbb{P}^0(W^1(t)=0)=$ $\mathbb{P}(W^1(t)=0)$ and the stationarity of $W^1(t)$ under P. From (4.11), we see that g(t) is decreasing. In addition to this, $\frac{{\mathrm{d}}}{{\mathrm{d}} t}g(t)$ is increasing because $W_0^0(t)$ is decreasing. These arguments give us the conclusion that g(t) is decreasing and convex. Hence, it follows from Theorem 3.1 that if $\{T_n^0\}$ is HNBUE (HNWUE), then $\mathbb{E}^0[W(0{-})] \le ({\ge})\ \mathbb{E}[W(0)]$ .

4.4. Age process for superposition of two independent point processes

Finally, we consider another example given in [Reference Shanthikumar and Zazanis26]. Let $\{T_n^i;\, n\in \mathbb{Z}\}$ , $i=0,1$ , be two point processes that are assumed to be jointly stationary and ergodic under the probability measure $\mathbb{P}$ . These two point processes are independent. Let $\mathbb{P}^i$ denote the Palm probability measure with respect to the point process $\{T_n^i\}$ and $\mathbb{E}^i$ be the corresponding expectation. Let $\{R_n;\, n\in \mathbb{Z}\}$ denote the superposition of the two point processes, and define the following ‘age’ process:

\begin{equation*} A(t)\stackrel{\rm def}{=} \sum_{n=-\infty}^\infty \mathbf{1}_{R_n<t\le R_{n+1}}(t-R_n).\end{equation*}

Note that A(t) is left-continuous. The inter-arrival times for point processes $\{T_n^i;\, n\in \mathbb{Z}\}$ ( $i=0,1$ ) are not necessarily independent of each other.

Lemma 4.5. If $\{T_n^0\}$ is HNBUE (HNWUE) then, for all x,

\begin{equation*} \mathbb{E}[(A(0)-x)_+]\le ({\ge})\ \mathbb{E}^0[(A(0)-x)_+]. \end{equation*}

That is, the age at the arrival instants of the 0th point process is greater than the age at an arbitrary instant with respect to the increasing convex order.

Proof. Define $g(t) \stackrel{\rm def}{=} \mathbb{E}^0[(A(t)-x)_+\mid T_1^0=t]$ . Let $F_{\tau_1}(t) \stackrel{\rm def}{=} P^1 (T_1^1\le x)$ and $F_{\tau_1}^{(\mathrm{e})}(t)$ denote its equilibrium distribution, that is,

\begin{equation*} F_{\tau_1}^{(\mathrm{e})}(t) = \frac{1}{\mathbb{E}^1[T_1^1]}\int_0^t (1-F_{\tau_1}(s))\,{\mathrm{d}} s. \end{equation*}

It can be seen [Reference Shanthikumar and Zazanis26] that

(4.12) \begin{align} g(t) & = \int_0^t (s-x)_+\,{\mathrm{d}} F_{\tau_1}^{(\mathrm{e})}(s) + (t-x)_+\big(1-F_{\tau_1}^{(\mathrm{e})}(t)\big) \nonumber \\ & = -\big[(s-x)_+ \big(1-F_{\tau_1}^{(\mathrm{e})}(s)\big)\big]_0^t + \int_x^t \big(1-F_{\tau_1}^{(\mathrm{e})}(s)\big)\,{\mathrm{d}} s + (t-x)_+\big(1-F_{\tau_1}^{(\mathrm{e})}(t)\big)\nonumber\\ & = \int_x^t \big(1-F_{\tau_1}^{(\mathrm{e})}(s)\big)\,{\mathrm{d}} s. \end{align}

Note that the first term on the right-hand side of the first line is the expectation of age conditioned on the first arrival of the first point process after time 0 occurring before time t, and the second term is the expectation of age conditioned on the first arrival of the first point process after time 0 being after time t. It follows from (4.12) that

\begin{equation*} \frac{{\mathrm{d}}}{{\mathrm{d}} t}g(t) = 1-F_{\tau_1}^{(\mathrm{e})}(t)\ge 0, \qquad \frac{{\mathrm{d}}^2}{{\mathrm{d}} t^2}g(t) = -\frac{{\mathrm{d}}}{{\mathrm{d}} t}F_{\tau_1}^{(\mathrm{e})}(t) = -\frac{1-F_{\tau_1}(t)}{\mathbb{E}^1[T_1^1]}\le 0. \end{equation*}

This means that g(t) is increasing and concave, and thus the stated result follows from Proposition 2.1.

5.1. Utilization of a GI/M/1 queue

In this subsection, we numerically investigate the relationship between customer-averaged and time-averaged utilization of a GI/M/1 queue. We also show how this relationship is related to the coefficient of variation of inter-arrival times for customers. The utilization is the probability that a non-zero workload remains in the queue. The time-averaged utilization is thus equal to $\mathbb{P}(W(0)> 0)$ and the customer-averaged utilization (utilization at a customer arrival instant) is equal to $\mathbb{P}^0(W(0{-})> 0)$ . As shown in Remark 4.1, for a GI/M/1 queue, $\mathbb{P}(W(0)>0)$ and $\mathbb{P}^0(W(0{-})> 0)$ are respectively given as $\mathbb{P}(W(0)> 0)=\rho=\lambda/\mu$ and $\mathbb{P}^0(W(0{-})> 0)=\eta$ , where $\mu$ is the inverse of the mean service time, $\lambda$ is the inverse of the mean inter-arrival time for customers, and $\eta$ is the solution of $z = \mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]$ in (0,1). Now assume that the inter-arrival time for customers is distributed according to the nth Erlang distribution, where $\mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]$ is given as

\begin{equation*} \mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}] = \bigg(\frac{n\rho}{n\rho + 1-z}\bigg)^n.\end{equation*}

In Figure 4(a), we show the customer-averaged utilization of the GI/M/1 queue, in which the inter-arrival time for customers is distributed according to the nth Erlang distribution, by changing n from 1 to 25. The time-averaged utilization is set to 0.5, 0.7, or 0.9. The horizontal axis of the figure shows the coefficient of variation of inter-arrival times for customers, instead of showing the values of n. Note that the coefficient of variation of the nth Erlang distribution is equal to $n^{-1/2}$ . Because the Erlang distribution is HNBUE, it follows from Corollary 4.1 that

\begin{equation*} \mathbb{P}^0(W(0{-})> 0)\ \big[=1-F_W^0(0)\big] \le \mathbb{P}(W(0)> 0)\ \big[=1-F_W(0)\big].\end{equation*}

Thus, the customer-averaged utilization is smaller than (or equal to) the time-averaged utilization, which is consistent with the results in Figure 4(a). Figure 4(a) also shows that the customer-averaged utilization becomes smaller as the coefficient of variation of inter-arrival times for customers becomes smaller. This result can be explained using theory as follows. The proof of Corollary 4.1 (and the proof of Lemma 4.2) shows that, for a GI/M/1 queue, $g(t;x) \stackrel{\rm def}{=} \mathbb{E}^0[\mathbf{1}_{W_0(t)\le x}]$ is a concave function of t. Thus, $\mathbb{E}^0[\mathbf{1}_{W_0(t)> 0}] = 1- g(t,0)$ is a convex function of t. Now, let $\tau^{\mathrm{Er}(n)}$ denote a random variable following the nth Erlang distribution. If $\tau^{\mathrm{Er}(n_1)}$ and $\tau^{\mathrm{Er}(n_2)}$ have the same mean and $n_2\le n_1$ , $\tau^{\mathrm{Er}(n_1)}\le_{\rm cv} \tau^{\mathrm{Er}(n_2)}$ . Thus,

\begin{equation*} \mathbb{E}^0\big[\mathbf{1}_{W_0(\tau^{\mathrm{Er}(n_1)})>0}\big] \le \mathbb{E}^0\big[\mathbf{1}_{W_0(\tau^{\mathrm{Er}(n_2)})>0}\big],\end{equation*}

showing that when the inter-arrival time for customers follows the nth Erlang distribution, the customer-averaged utilization decreases as n increases. Since the coefficient of variation of the nth Erlang distribution becomes smaller as n increases, the customer-averaged utilization decreases as the coefficient of variation of inter-arrival times decreases.

Figure 4.

Utilization of a GI/M/1 at queue the instant of packet arrival.

Next, assume that the inter-arrival time for customers is distributed according to a second-order hyperexponential distribution with mean $1/\lambda$ , whose distribution function is given as

(5.1) \begin{equation} P(\tau\le t) = \begin{cases} \dfrac{1}{n+1}(1-\mathrm{e}^{-\lambda t/n}) + \dfrac{n}{n+1}(1-\mathrm{e}^{-n\lambda t}), & t \ge 0,\\[4pt] 0, & t<0. \end{cases}\end{equation}

Note that the distribution in (5.1) is parametrized with n, where n is not necessarily an integer, and its coefficient of variation is equal to $\sqrt{(2n^2-3n+2)/n}$ . Under the distribution in (5.1), $\mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}]$ is given as

\begin{equation*} \mathbb{E}[\mathrm{e}^{\mu(z-1)\tau}] = \frac{\rho}{n+1}\bigg(\frac{1}{\rho + n(1-z)}+\frac{n^2}{n\rho+1-z}\bigg).\end{equation*}

In Figure 4(b), we show the customer-averaged utilization of the GI/M/1 queue, in which the distribution of the inter-arrival time for packets is given by (5.1), by increasing n from 1. The time-averaged utilization is set to 0.5, 0.7, or 0.9. As in Figure 4(a), the horizontal axis of the figure shows the coefficient of variation of inter-arrival times for customers. Because the hyperexponential distribution is HNWUE, it follows from Corollary 4.1 that $\mathbb{P}^0(W(0{-})> 0) \ge \mathbb{P}(W(0)> 0)$ . Thus, the customer-averaged utilization is larger than the time-averaged utilization, which is consistent with the results in Figure 4(b). Figure 4(b) also shows that the customer-averaged utilization becomes larger as the coefficient of variation of inter-arrival times for customers becomes larger, which can also be confirmed via theory by an argument similar to that for the Erlang distribution.

5.2. Piecewise exponential distributions

If a random variable Z has a piecewise-constant hazard function, then Z is called a piecewise exponential random variable [Reference Friedman7]. The distribution function of an n-piece exponential random variable Z with cut points $t_0=0<t_1<\dots<t_n=\infty$ is

(5.2) \begin{equation} F_Z(t) = 1 - \sum_{k=1}^n c_k \mathrm{e}^{-\lambda_k t} \mathbf{1}_{t_{k-1}< t\le t_k},\end{equation}

where $c_k = \prod_{l=1}^k \mathrm{e}^{(\lambda_l-\lambda_{l-1}) t_{l-1}}$ . Note that its hazard function $h_Z(t)$ and its expectation $\mathbb{E}[Z]$ are given by

\begin{equation*} h_Z(t) = \sum_{k=1}^n \lambda_i \mathbf{1}_{t_{k-1}<t\le t_k}, \qquad \mathbb{E}[Z] = \sum_{k=1}^n \frac{c_k}{\lambda_k} \big(\mathrm{e}^{-\lambda_k t_{k-1}}-\mathrm{e}^{-\lambda_k t_k}\big).\end{equation*}

The scaled TTT-transform of a piecewise exponential distribution is a piecewise linear function. In fact, the scaled TTT-transform of the n-piece exponential distribution (5.2) is given as

\begin{equation*} \varphi_{F_Z}(x) = \sum_{i=1}^n\bigg(\varphi_Z(x_{i-1}) + \frac{\lambda}{\lambda_i}(x-x_{i-1})\bigg) \mathbf{1}_{x_{i-1}<x\le x_i}, \qquad \lambda \stackrel{\rm def}{=} \frac{1}{\mathbb{E}[Z]},\end{equation*}

where $x_i\stackrel{\rm def}{=} F_Z(t_i)$ . Figure 5(a) shows the distribution function of the four-piece exponential random variable with parameters (5.3), and Figure 5(b) shows its scaled TTT-transform. According to Theorems 2.1 and 2.2, Figure 5(b) proves that this four-piece exponential random variable is not NBUE but HNBUE.

Figure 5.

Piecewise exponential distribution that is not NBUE but HNBUE.

The set of piecewise exponential random variables includes those that are not NBUE (NWUE) but HNBUE (HNWUE). Klefsjö showed that a four-piece exponential random variable with the following parameters is not NBUE but HNBUE [Reference Klefsjö9, Reference Klefsjö10]:

(5.3) \begin{equation} \begin{alignedat}{4} t_1 & = 0.359, & t_2 & = 0.592, & t_3 & = 1.662, & & \\ \lambda_1 & = 0.143, \qquad & \lambda_2 & = 3.600, \qquad & \lambda_3 & = 0.175, \qquad & \lambda_4 & = 3.400. \end{alignedat}\end{equation}

We found that a four-piece exponential random variable with the following parameters is not NWUE but HNWUE:

(5.4) \begin{equation} \begin{alignedat}{4} t_1 & = 0.2, & t_2 & = 1.0, & t_3 & = 2.0, & & \\ \lambda_1 & = 2.0, \qquad & \lambda_2 & = 0.1, \qquad & \lambda_3 & = 2.0, \qquad & \lambda_4 & = 0.2. \end{alignedat}\end{equation}

Figure 6(a) shows the distribution function of the four-piece exponential random variable with parameters (5.4), and Figure 6(b) shows its scaled TTT-transform, which proves that the four-piece exponential random variable with parameters (5, 4) is not NWUE but HNWUE.

Figure 6.

Piecewise exponential distribution that is not NWUE but HNWUE.

Figure 7 shows the customer and time averages of the workload of a GI/GI/1 queue under the condition that the inter-arrival time for customers follows the four-piece exponential distribution with parameters (5.3). We considered three different service-time distributions: constant (GI/D/1), exponential distribution (GI/M/1), and the second-order hyperexponential distribution (GI/H $_2$ /1) whose distribution function is

\begin{equation*} F(t) = \begin{cases} \frac{1}{4}(1-\mathrm{e}^{-\mu t/3})+\frac{3}{4}(1-\mathrm{e}^{-3\mu t}),&t \ge 0,\\ 0,& t<0. \end{cases}\end{equation*}

The results in Figure 7(a) (GI/D/1) and Figure 7(c) (GI/H $_2$ /1) were obtained from simulation, and the results in Figure 7(b) were obtained by theory (for the GI/M/1 queue). Figure 7 confirms the conclusion of Lemma 4.1 that the customer average of the workload is smaller than the time average when the arrival process is HNBUE. (The customer and time averages are very close when $\rho\ge 0.8$ , and we tabulate these customer and time averages in tables in the Appendix.) Figure 8 compares the customer and time averages of the number of customers of a GI/GI/1 queue under the same conditions with the workload. Figure 8 shows that the customer average of the number of customers in the queue is smaller than the time average when the arrival process is HNBUE. Note that the inequalities between the customer and time averages of the number of customers are proved only for GI/M/1 queues (Lemma 4.3). Thus, these numerical examples imply that inequalities between the customer and time averages of the number of customers may hold for GI/GI/1 queues.

Figure 7.

Average workload (arrival process is not NBUE but HNBUE).

Figure 8.

Average number of customers (arrival process is not NBUE but HNBUE).

Figure 9.

Average workload (arrival process is not NWUE but HNWUE).

Figure 9. (workload) and Figure 10 (number of customers) show the customer and time averages of the GI/GI/1 queue under the condition that the inter-arrival time for customers follows a four-piece exponential distribution with parameters (5.4), which is not NWUE, but HNWUE. These figures numerically confirm that the customer average is larger than the time average when the arrival process is HNWUE.

Figure 10.

Average number of customers (arrival process is not NWUE but HNWUE).

Table 1.

Workload when arrival process is not NBUE but HNBUE.

Table 2.

Number of customers in system when arrival process is not NBUE but HNBUE.