Arrival processes to service systems often display fluctuations that are larger than anticipated under the Poisson assumption, a phenomenon that is referred to as overdispersion. Motivated by this, we analyze a class of discrete-time stochastic models for which we derive heavy-traffic approximations that are scalable in the system size. Subsequently, we show how this leads to novel capacity sizing rules that acknowledge the presence of overdispersion. This, in turn, leads to robust approximations for performance characteristics of systems that are of moderate size and/or may not operate in heavy traffic.
1 Introduction
One of the most prevalent assumptions in queueing theory is the assumption that the number of arrivals over any given period is a Poisson random variable with deterministic rate, whose variance equals its expectation. Although natural and convenient from a mathematical viewpoint, the Poisson assumption often fails to be confirmed in practice. Namely, a growing number of empirical studies show that the variance of demand typically deviates from the mean significantly. Recent work [24, 26] reports variance being strictly less than the mean in health care settings employing appointment booking systems. This reduction of variability can be accredited to the goal of the booking system to create a more predictable arrival pattern. On the other hand, in other scenarios with no control over the arrivals, the variance can dominate the mean; see [4‐6, 11, 12, 17, 19, 23, 25, 30, 31, 34, 38, 41]. The feature that variability is higher than one expects from the Poisson assumption is referred to as overdispersion and serves as the primary motivation for this work.
Stochastic models with the Poisson assumption have been widely applied to optimize capacity levels in service systems. When stochastic models, however, do not take into account overdispersion, resulting performance estimates are likely to be overoptimistic. The system then ends up being underprovisioned, which possibly causes severe performance problems, particularly in critical loading.
Anzeige
A significant part of the queueing literature has focused on extending Poisson arrival processes to more bursty arrival processes, and analyzing these models using, for example, matrix-analytic models [29, 33]. In this paper, we focus on a different cause of overdispersion in arrival processes, which is arrival rate uncertainty. Since model primitives, in particular the arrival rate, are typically estimated through historical data, these are prone to be subject to forecasting errors. In the realm of Poisson processes, this inherent uncertainty can be acknowledged by viewing the arrival rate \(\Lambda _n\) itself as being stochastic. The resulting doubly stochastic Poisson process, also known as a Cox process (first presented in [14]), implies that demand in a given interval \(A_{k,n}\) follows a mixed Poisson distribution. In this case, the expected demand per period equals \(\mu _n = {\mathbb {E}}[\Lambda _n]\), while the variance is \(\sigma _n^2 = {\mathbb {E}}[\Lambda _n]+\mathrm{Var}\,\Lambda _n\). By selecting the distribution of the mixing factor \(\Lambda _n\), the magnitude of overdispersion can be made arbitrarily large, and only a deterministic \(\Lambda _n\) leads to a true Poisson process.
The mixed Poisson model presents a useful way to fit both the mean and variance to real data, particularly in case of overdispersion. The mixing distribution can be estimated parametrically or nonparametrically; see [23, 30]. A popular parametric family is the Gamma distribution, which gives rise to an effective data fitting procedure that uses the fact that a Gamma mixed Poisson random variable follows a negative binomial distribution. We will in this paper adopt the assumption of a Gamma–Poisson mixture as the demand process.
We investigate the impact of this modeling assumption within the context of a classical model in queueing theory, which is the reflected random walk. In particular, we consider a sequence of such random walks, indexed by n, with increments \(A_{k,n}-s_n\), where \(A_{k,n}\sim \,\mathrm{Pois}(\Lambda _n)\) and \(s_n\) denotes the system capacity, and we consider a regime in which the system approaches heavy traffic. We are especially interested in the impact of overdispersion on the way performance measures scale, and how they impact capacity allocation rules.
A sensible candidate capacity allocation rule is \(s_n = \mu _n + \beta \sigma _n + o(\sigma _n)\) for some \(\beta >0\), which is asymptotically equivalent to the scaling
where \(\rho _n := \mu _n/s_n\) denotes the utilization. We will verify mathematically that this is asymptotically the appropriate choice and our methods allow us to quantify the accuracy of the resulting performance formulae for finite systems. Studies that have addressed similar capacity allocation problems with stochastic arrival rates include [28, 30, 39, 40]. Of the aforementioned papers, our work best relates to [30], in the sense that we also assess the asymptotic performance of a queueing system having a stochastic arrival rate in heavy traffic. We therefore expand the paradigm of the quality-and-efficiency-driven (QED) regime, which relies on the popular square-root staffing rule \(s_n = \mu _n + \beta \sqrt{\mu _n}\), in order to have it accommodated for overdispersed demand that follows from a doubly stochastic Poisson process.
Anzeige
The first part of our analysis relates to [37], in which a sequence of cyclically thinned queues, denoted by \(G_n/G_n/1\) queues, is considered. Here, \(G_n\) indicates that only every \(n\mathrm{th}\) point of the original point process is considered. In this framework, it is shown that the stationary waiting time can be characterized as the maximum of a random walk, in which the increments grow indefinitely. Under appropriate heavy-traffic scaling, the authors prove convergence to a Gaussian random walk and moreover characterize the limits of the stationary waiting time moments. Our work differs with respect to [37] in the sense that we study a discrete-time model, rather than the continuous-time \(G_n/G_n/1\) queue. Also, the presence of the overdispersion requires us to employ an alternative scaling.
Furthermore, our approach through Pollaczek’s formula allows us to derive estimates for performance measures in pre-limit, i.e., large but finite-size, systems. Mathematically, this second part of our analysis is related to previous work [22]. In particular, we use a refinement of the saddle point technique to establish our asymptotic estimates. The associated analysis is substantially more involved in the present situation, as we will explain in Sect. 4.
Structure of the paper The remainder of this paper is structured as follows. Our model is introduced in Sect. 2 together with some preliminary results. In Sect. 3, we derive the classical heavy-traffic scaling limits for the queue length process in the presence of overdispersed arrivals both for the moments and the distribution itself. Section 4 presents our main theoretical result, which provides a robust refinement to the heavy-traffic characterization of the queue length measures in pre-limit systems. In Sect. 5, we describe the numerical results and demonstrate the heavy-traffic approximation.
2 Model description and preliminaries
We consider a sequence of discrete stochastic models, indexed by n, in which time is divided into periods of equal length. At the beginning of each period \(k=1,2,3,\ldots \), new demand \(A_{k,n}\) arrives to the system. The demands per period \(A_{1,n},A_{2,n},\ldots \) are assumed independent and equal in distribution to some nonnegative integer-valued random variable \(A_n\). For brevity, we define \(\mu _n:= {\mathbb {E}}A_{n}\) and \(\sigma _n^2 = \mathrm {Var}\,A_n\). The system has a service capacity \(s_n\in {\mathbb {N}}\) per period, so we have the recursion
i.e., the maximum of the first k steps of a random walk with steps distributed as \(A_n-s_n\). Even more, we can characterize \(Q_{n}\), the stationary queue length, as
The behavior of \(Q_{k,n}\) greatly depends on the characteristics of \(A_n\) and \(s_n\). First, note that \(\mu _n<s_n\) is a necessary condition for the maximum to be finite and therefore for the queue to be stable. This random variable is finite a.s. if \({\mathbb {E}}[A_{i,n}]< s_n\), which is guaranteed by our Assumption 1 (in particular \(\beta >0\)) below. Before continuing the analysis of \(Q_{n}\), we impose a set of conditions on the asymptotic properties of \(s_n,\mu _n\) and \(\sigma _n\), which are assumed to hold throughout the remainder of this paper.
By Assumption 1(a), we insist that the expected demand per period grows infinitely large, which allows us to develop approximations for systems with large yet finite arrival volumes. Moreover, it is assumed that the order of stochastic variability of the arrival process relative to the mean arrival volume does not vanish in the limit. In fact, the assumption on the persistence of overdispersion says that the variance of the demand per period is of higher order than its mean as n grows large. We note that the scenario with \(\sigma _n^2/\mu _n\rightarrow \gamma \) for some \(\gamma > 0\) is asymptotically equivalent to the process studied in [22], in which case overdispersion of the arrival process does not play a role in the limit as \(n\rightarrow \infty \). In order to establish heavy-traffic approximations for large systems that do face overdispersion we need to construct an asymptotic regime in which overdispersion continues to play a dominant role as \(n\rightarrow \infty \), which is secured by Assumption 1(b). The subsequent analysis will clarify why the heavy-traffic condition in Assumption 1(c) is the correct one for our purposes. Note that Assumption 1(c) is satisfied for the capacity allocation rule
Since we are mainly interested in the system behavior in heavy traffic, it is appropriate to study the queue length process in a scaled form. Substituting \(s_n\) as in Assumption 1(c), and dividing both sides of (3) by \(\sigma _n\), gives
we see that the scaled queue length process is in distribution equal to the maximum of a random walk with i.i.d. increments distributed as \({\hat{A}}_n-\beta \). Besides \({\mathbb {E}}{\hat{A}}_n = 0\) and \(\mathrm{Var}\,{\hat{A}}_n=1\), the scaled and centered arrival counts \({\hat{A}}_n\) have a few other nice properties which we turn to later in this section.
The model in (1) is valid for any distribution of \(A_n\), also for the original case where the number of arrivals follows a Poisson distribution with fixed parameter \(\lambda _n\), but Assumption 1(b) does not hold then. Instead, we assume \(A_n\) to be Poisson distributed with uncertain arrival rate rendered by the nonnegative random variable \(\Lambda _n\). This \(\Lambda _n\) is commonly referred to as the prior distribution, while \(A_n\) is given the name of a Poisson mixture; see [18]. Given that the moment generation function of \(\Lambda _n\), denoted by \(M^\Lambda _n(\cdot )\), exists, we are able to express the probability generating function (pgf) of \(A_n\) through the former. Namely,
The prevalent choice for \(\Lambda _n\) is the Gamma distribution. The Gamma–Poisson mixture turns out to provide a good fit to arrival counts observed in service systems, as was observed by [23, 30]. Assuming \(\Lambda _n\) to be of Gamma type with scale and rate parameters \(a_n\) and \(1/b_n\), respectively, we get
Note that in the context of a Gamma prior, the restrictions in Assumption 1 reduce to only two rules. For completeness, we include the revised list below.
Assumption 2
(a)
(Asymptotic regime and persistence of overdispersion)
The next result follows from the fact that \(\Lambda _n\) is a Gamma random variable:
Corollary 1
Let \(\Lambda _n\sim \text { Gamma}(a_n,1/b_n)\), \(A_n\sim \mathrm{Poisson }(\Lambda _n)\) and \(a_n,b_n\rightarrow \infty \). Then, \({\hat{A}}_n\) converges weakly to a standard normal random variable as \(n\rightarrow \infty \).
Proof
With Lemma 1 in mind, it is sufficient to prove that \({\hat{\Lambda }}_n\Rightarrow N(0,1)\) for this particular choice of \(\Lambda _n\). We do this by proving the pointwise convergence of the characteristic function (cf) of \({\hat{\Lambda }}_n\) to \(\exp ({-} t^2/2)\), the cf of the standard normal distribution. Let \(\varphi _{G}(\cdot )\) denote the characteristic function of a random variable G. By basic properties of the cf,
for \(n\rightarrow \infty \). Since \(b_n/\sigma _n = a_n^{-1/2}(1+1/b_n)^{-1/2}\rightarrow 0\) as \(n\rightarrow \infty \), we can take the principal value in (13) for the logarithm when t is in any compact set and n is large enough. By Lévy’s continuity theorem, see, for example, [16, Thm. 18.21], this implies \({\hat{\Lambda }}_n\) is indeed asymptotically standard normal. \(\square \)
The characterization of the arrival process as a Gamma–Poisson mixture is of vital importance in later sections.
2.1 Expressions for the stationary distribution
Our main focus is on the stationary queue length distribution, denoted by
To continue our analysis of \(Q_{n}\), we need one more condition on \(A_n\).
Assumption 3
The pgf of \(A_n\), denoted by \({\tilde{A}}_n(w)\), exists within \(|w|<r_0\), for some \(r_0>1\), so that all moments of \(A_n\) are finite.
We next recall two characterizations of \({\tilde{Q}}_n(w)\) that play prominent roles in the remainder of our analysis. The first characterization of \({\tilde{Q}}_n(w)\) originates from a random walk perspective. As we see from (3), the (scaled) stationary queue length is equal in distribution to the all-time maximum of a random walk with i.i.d. increments distributed as \(A_n-s_n\) (or \({\hat{A}}_n-\beta \) in the scaled setting). Spitzer’s identity, see, for example, [3, Theorem VIII4.2], then gives
Pollaczek-type integrals like (19)–(22) first occurred in the work of Pollaczek on the classical single-server queue (see [1, 13, 21] for historical accounts). These integrals are fairly straightforward to evaluate numerically and hence give rise to efficient algorithms for performance evaluation [1, 9]. The integrals also proved useful in establishing heavy-traffic results by asymptotic evaluation of the integrals in various heavy-traffic regimes [8, 13, 22, 27], and in this paper we follow that approach for a heavy-traffic regime that is suitable for overdispersion.
3 Heavy-traffic limits
In this section, we present the result on the convergence of the discrete process \({\hat{Q}}_{n}\) to a non-degenerate limiting process and of the associated stationary moments. The latter requires an interchange of limits. Using this asymptotic result, we derive two sets of approximations for \({\mathbb {E}}Q_n\), \(\mathrm{Var}\,Q_n\) and \({\mathbb {P}}(Q_{n}=0)\) that capture the limiting behavior of \(Q_{n}\). The first set provides a rather crude estimation for the first cumulants of the queue length process for any arrival process \(A_{n}\) satisfying Assumption 1. The second set, which is the subject of the next section, is derived for the specific case of a Gamma prior and is therefore expected to provide more accurate, robust approximations for the performance metrics.
We start by indicating how the asymptotic properties of the scaled arrival process give rise to a proper limiting random variable describing the stationary queue length. The asymptotic normality of \({\hat{A}}_{n}\) provides a link with the Gaussian random walk and nearly deterministic queues [36, 37]. The main results in [36, 37] were obtained under the assumption that \(\rho _n\sim 1-\beta /\sqrt{n}\), in which case it follows from [37, Thm. 3] that the rescaled stationary waiting time process converges to a reflected Gaussian random walk.
We shall also identify the Gaussian random walk as the appropriate scaling limit for our stationary system. However, since the normalized natural fluctuations of our system are given by \(\mu _n/\sigma _n\) instead of \(\sqrt{n}\), we assume that the load grows like \(\rho _n \sim 1 - \frac{\beta }{\mu _n/\sigma _n}\). Hence, in contrast to [36, 37], our systems’ characteristics display larger natural fluctuations, due to the mixing factor that drives the arrival process. Yet, by matching this overdispersed demand with the appropriate hedge against variability, we again obtain Gaussian limiting behavior. This is not surprising, since we saw in Lemma 1 that the increments start resembling Gaussian behavior for \(n\rightarrow \infty \). The following result summarizes this.
Theorem 1
Let \(A_n\) be a nonnegative random variable such that \({\hat{A}}_n = (A_n-\mu _n)/\sigma _n\) is asymptotically standard normal, with \(\mu _n\) and \(\sigma _n\) as defined in (9), and \({\mathbb {E}}[(\max \{{\hat{A}}_n,0\})^4]\) is bounded in n. Then, under Assumption 1, for \(n\rightarrow \infty \),
where \(M_\beta \) is the all-time maximum of a random walk with i.i.d. normal increments with mean \(-\beta \) and unit variance.
The proof of Theorem 1 is given in Appendix A. We remark that for convergence of the mean scaled queue length, only \({\mathbb {E}}[(\max \{{\hat{A}}_n,0\})^3]<\infty \) is needed. The following result shows that Theorem 1 also applies to Gamma mixtures, which is a direct consequence of Corollary 1.
Corollary 2
Let \(\Lambda _n\sim \) Gamma\((a_n,b_n)\). Then, under Assumption 2 the four convergence results of Theorem 1 hold true.
It follows from Theorem 1 that the scaled stationary queueing process converges under (4) to a reflected Gaussian random walk. Hence, the performance measures of the original system should be well approximated by the performance measures of the reflected Gaussian random walk, yielding heavy-traffic approximations.
Like our original system, the Gaussian random walk falls in the classical setting of the reflected one-dimensional random walk, whose behavior is characterized by both Spitzer’s identity and Pollaczek’s formula. In particular, Pollaczek’s formula gives rise to contour integral expressions for performance measures that are easy to evaluate numerically, also in heavy-traffic conditions. The numerical evaluation of such integrals is considered in [1]. For \({\mathbb {E}}M_\beta \), such an integral is as follows:
with \(\phi (z) = \exp (-\beta \,z+\tfrac{1}{2}\,z^2)\), the Laplace transform of a normal random variable with mean \(-\beta \) and unit variance, and \(z=x+iy\) with an appropriately chosen real part x. Note that this integral involves complex-valued functions with complex arguments. Similar Pollaczek-type integrals exist for \({\mathbb {P}}(M_\beta =0)\) and \(\mathrm{Var}\,M_\beta \); see [1]. The following result simply rewrites these integrals in terms of real integrals and uses the fact that the scaled queue length process mimics the maximum of the Gaussian random walk for large n.
Corollary 3
Under Assumption 1, the leading order behavior of \({\mathbb {P}}(Q_{n}=0)\), \({\mathbb {E}}Q_n\) and \(\mathrm{Var}\,Q_n\) as \(n\rightarrow \infty \) is given by, respectively,
The proof of Theorem 2 requires asymptotic evaluation of the Pollaczek-type integrals (20)–(22), for which we shall use a nonstandard saddle point method. The saddle point method in its standard form is typically suitable for large deviation regimes, for instance excess probabilities, and it cannot be applied to asymptotically characterize other stationary measures such as the mean or mass at zero. Indeed, in the presence of overdispersion, the saddle point converges to one (as \(n\rightarrow \infty \)), which is a singular point of the integrand, and renders the standard saddle point method useless. Our nonstandard saddle point method, originally proposed by [15] and also applied in [22], aims specifically to overcome this challenge. Subsequently, we apply the nonstandard saddle point method to turn these contour integrals into practical approximations. In contrast to the setting of [22], the analyticity radius tends to one in the setting with overdispersion, which is a singular point of the integrand. For the proof of Theorem 2, we therefore modify the special saddle point method developed in [22] to account for this circumstance.
Proof
Our starting point is the probability generating function of the number of arrivals per time slot, given in (11), which is analytic for \(|z|<1+1/b_n=:r_0\). Under Assumption 2, we consider \({\mathbb {E}}{Q}_n\) as given in (20). We set
to be considered in the entire complex plane with branch cuts \((-\infty ,0]\) and \([r,\infty )\). The relevant saddle point \(z_\mathrm{sp}\) is the unique zero z of \(g'(z)\) with \(z\in (1,r_0)\). Since
in the range \({-}\tfrac{1}{2}\delta _n \le v\le \tfrac{1}{2} \delta _n\) with \(\delta _n \rightarrow 0\) as \(n\rightarrow \infty \). Note that this range depends on n, whereas these bounds \(\pm \tfrac{1}{2} \delta _n\) remained bounded away from zero in [22]. This severely complicates the present analysis. We consider the approximate representation
of \({\mathbb {E}}{Q}_n\). We have to operate here with additional care, since both the analyticity radius \(r_0=1+1/b_n\) and the saddle point \(z_\mathrm{sp}\) outside the unit circle tend to 1 as \(n\rightarrow \infty \). Specifically, proceeding under the assumptions that \((1-\rho _n)^2a_n\) is bounded while \(a_n\rightarrow \infty \) and \(b_n\ge 1\), see Assumption 2, we have from (32) that
where the O-term is small compared to \((1-\rho _n)/b_n\) when \(b_n\rightarrow \infty \). Next, we approximate \(r_0\), using that \(r_0>1\) satisfies
In (34) we choose \(\delta _n\) so large that the integral has converged within exponentially small error using \(\pm \,\delta _n\) as integration limits and, at the same time, so small that there is a convergent power series
Therefore, (34) approximates \({\mathbb {E}}{Q}_n\) with exponentially small error when we take \(\tfrac{1}{2} \delta _n\) of the order \(1/b_n\).
We next aim at showing that we have a power series for z(v) as in (36) that converges for \(|v|\le \tfrac{1}{2}\delta _n\), with \(\tfrac{1}{2}\delta _n\) of the order \(1/b_n\).
Then \(G(z_{\mathrm{sp}})=1\) and so we can write (4) as
$$\begin{aligned} F(z):=(z-z_{\mathrm{sp}})\sqrt{G(z)} = i v \end{aligned}$$
(40)
when \(|z-z_{\mathrm{sp}}|\) is sufficiently small. Since \(F(z_\mathrm{sp})=0\), \(F'(z_{\mathrm{sp}})=1\), the Bürmann–Lagrange inversion theorem implies validity of a power series as in (36), with real \(c_k\) since G(z) is positive and real for real z close to \(z_{\mathrm{sp}}\). We therefore just need to estimate the convergence radius of this series from below.
where we take \(\zeta \) such that \(|\zeta -1|\le 1/2b_n\). It is easy to see from \(1<z_{\mathrm{sp}}<1+1/2b_n\) that \(|\zeta -1|\le 1/2b_n\) holds when \(|z-z_{\mathrm{sp}}|\le r_n=1/2b_n-(z_{\mathrm{sp}}-1)\). We have, furthermore, from (32) that \(0<g''(z_{\mathrm{sp}})\le 1+b_n/\rho _n\). Using this, together with (43) where \(\zeta \) is as in (45), yields
Hence, for any v with \(|v|\le m_n\), there is exactly one solution \(z=z(v)\) of the equation \(F(z)-iv=0\) in \(|z-z_{\mathrm{sp}}|\le r_n\) by Rouché’s theorem [2]. This z(v) is given by
and depends analytically on v, \(|v|\le m_n\). From \(|z(v)-z_\mathrm{sp}|\le r_n\), we can finally bound the power series coefficients \(c_k\) according to
where we have used that all \(c_k\) are real, so that \(z(-v)=z(v)^*\), where \( ^*\) denotes the complex conjugate. Now, from (38) and realness of the \(c_k\), we have
when \(0\le v\le \tfrac{1}{2}\delta _n\). The order terms in (46), (47) are negligible in leading order, and so we get for \(\mu _{Q_{n}}\) via (34) the leading order expression
We finally approximate \(q(v) = g(z_{\mathrm{sp}})-\tfrac{1}{2} g''(z_\mathrm{sp})v^2\). There is a \(z_1\), \(1\le z_1\le z_{\mathrm{sp}}\), such that
where (35) has been used, and \(a_nb_n = s_n(1+o(1))\). Therefore, the O-term in (48) tends to 0 by our assumption that \((1-\rho _n)^2a_n\) is bounded. Thus, we get for \(\mu _{Q_{n}}\) in leading order
When we substitute \(t=v\sqrt{s_n\,g''(z_{\mathrm{sp}})/2}\) and extend the integration in (49) to all \(t\ge 0\) (at the expense of an exponentially small error), we get for \(\mu _{Q_{n}}\) in leading order
This robust approximation for \({\mathbb {E}}{Q}_n\) is suggestive of the following two properties that extend beyond the mean system behavior, and hold at the level of approximating the queue by \(\sigma _n\) times the Gaussian random walk:
(i)
At the process level, the space should be normalized with \(\sigma _n\), as in (8). The approximation (27) suggests that it is better to normalize with \(\tilde{\sigma }_n\). Although \(\tilde{\sigma }_n / \sigma _n \rightarrow 1\) for \(n\rightarrow \infty \), the \({\tilde{\sigma }}_n\) is expected to lead to sharper approximations for finite n.
(ii)
Again at the process level, it seems better to replace the original hedge \(\beta \) by the robust hedge \(\beta _n\). This thus means that the original system for finite n is approximated by a Gaussian random walk with drift \(-\beta _n\). Apart from this approximation being asymptotically correct for \(n\rightarrow \infty \), it is also expected to approximate the behavior better for finite n.
5.1 Convergence of the robust hedge
We next examine the accuracy of the heavy-traffic approximations for \({\mathbb {E}}{Q}_n\) and \(\sigma ^2_Q\), following Corollary 3 and Theorem 2. We expect the robust approximation to be considerably better than the classical approximation when \(\beta _n\) and \(\tilde{\sigma }_n\) differ substantially from their limiting counterparts. Before substantiating this claim numerically, we present a result on the convergence rates of \(\beta _n\) to \(\beta \) and \(\tilde{\sigma }_n\) to \(\sigma _n\).
Proposition 1
Let \(a_n,b_n\) and \(s_n\) be as in Assumption 2. Then
which, together with \(\sigma _n^2=a_nb_n(b_n+1)\), proves the proposition. \(\square \)
Note that \(\beta _n\) always approaches \(\beta \) from below. Also, (51) shows that \(b_n\) is the dominant factor in determining the rate of convergence of \(\beta _n\).
In Fig. 1, we visualize the convergence speed of both parameters in the case \(\mu _n=n\), \(\sigma _n = n^\delta \) with \(\delta =0.7\) and \(\beta =1\). This implies \(a_n = n/(n^{2\delta }-1)\) and \(b_n = n^{2\delta }-1\).
Fig. 1
Convergence of the robust hedge. a Convergence of \(\beta _n\), b convergence of \(\tilde{\sigma }_n\)
×
We observe that \(\beta _n\) starts resembling \(\beta \) fairly quickly, as predicted by Proposition 1; \(\tilde{\sigma }_n\), on the other hand, converges extremely slowly to its limiting counterpart. Since \({\mathbb {E}}{Q}_n\) and \(\mathrm{Var}\,Q_n\) are approximated by \(\tilde{\beta }_n\) and \(\tilde{\sigma }_n\), multiplied by a term that remains almost constant as n grows, the substitution of \(\sigma _n\) by \(\tilde{\sigma }_n\) is essential for obtaining accurate approximations, as we illustrate further in the next subsection.
Table 1
Numerical results for the Gamma–Poisson case with \(\beta =1\) and \(\delta =0.6\)
5.2 Comparison between heavy-traffic approximations
We set \(\mu _n=n\) and \(\sigma ^2_n=n^{2\delta }\) with \(\delta >\tfrac{1}{2}\), so that \(s_n = n+\beta n^{\delta }\), and \(a_n =n/(n^{2\delta -1}-1)\) and \(b_n = n^{2\delta -1}-1\). Tables 1, 2, 3 and 4 present numerical results for various parameter values. The exact values are calculated using the method in Appendix B. Several conclusions are drawn from these tables. Observe that the heavy-traffic approximations based on the Gaussian random walk, (25) and (26), capture the right order of magnitude for both \({\mathbb {E}}Q_n\) and \(\mathrm{Var}\,Q_n\). However, the values are off, in particular for small \(s_n\) and relatively low \(\rho _n := {\mathbb {E}}[A_{n}] / s_n\). The inaccuracy also increases with the level of overdispersion. In contrast, the approximations that follow from Theorem 2, (27) and (29), are remarkably accurate. Even for small systems with \(s_n = 5\) or 10, the approximations for \({\mathbb {E}}Q_n\) are within 6\(\%\) of the exact value for small \(\rho _n\) and within \(2\%\) for \(\rho _n\) close to 1. For \(\sigma _Q^2\), these percentages even reduce to \(3\%\) and \(1\%\), respectively. For larger values of \(s_n\) these relative errors naturally reduce further. Overall, we observe that the approximations improve for heavily loaded systems, and the corrected approximations are particularly useful for systems with increased overdispersion.
Table 2
Numerical results for the Gamma–Poisson case with \(\beta =1\) and \(\delta =0.8\)
The authors are grateful to Avi Mandelbaum for many inspiring discussions and comments. The research of BM was supported by NWO Free Competition Grant No. 613.001.213. The research of JvL is supported by an ERC Starting Grant and by NWO Gravitation Networks Grant No. 024.002.003. The research of BZ is supported by NWO VICI Grant No. 639.033.413.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
This section presents the details of the proofs of Lemma 1 and Theorem 1, using the random walk perspective of the process \(\{Q_{k,n}\}_{k=0}^\infty \). This section is structured as follows. The next two lemmata are necessary for proving the first assertion of Theorem 1, concerning the weak convergence of the scaled process to the maximum of the Gaussian random walk, which is summarized in Proposition 4. The two remaining propositions of this section show convergence of \({\hat{Q}}_{n}\) at the process level as well as in terms of the three characteristics.
We show weak convergence of the random variable \({\hat{A}}_{n}\), as defined as the common distribution of (7), to a standard normal random variable. Since \({\hat{\Lambda }}_n\) is asymptotically standard normal, its characteristic function converges pointwise to the corresponding limiting characteristic function, i.e.,
in which the order term tends to zero as \(n\rightarrow \infty \) by our assumption that \(\mu _n/\sigma _n^2\rightarrow 0\). Combining this with (54), we find that \(\phi _{{\hat{A}}_{n}}(t)\) converges to \(\mathrm{e}^{{-}t^2/2}\) for all \(t\in {\mathbb {R}}\), so that we can conclude by Lévy’s continuity theorem that \({\hat{A}}_{k,n} {\;\buildrel {d}\over \Rightarrow \;}N(0,1)\). \(\square \)
To secure convergence in distribution of \({\hat{Q}}_{n}\) to \(M_\beta \), i.e., the maximum of a Gaussian random walk with negative drift, the following property of the sequence \(\{Y_{k,n}\}_{n\in {\mathbb {N}}}\) needs to hold. Because the sequence \(\{Y_{k,n}\}_{k\in {\mathbb {N}}}\) is i.i.d. for all n, we omit the index k in this result and its proof.
Lemma 3
Let \(Y_{n}\) be defined as in (52) with \(\mu _n,\sigma _n^2 < \infty \) for all \(n\in {\mathbb {N}}\). Then, the sequence \(\{(Y_{n})^+\}_{n\in {\mathbb {N}}}\) is uniformly integrable.
Proof
Note that the sequence \(\{Y_n\}_{n\in {\mathbb {N}}}\) has constant finite mean and variance equal to 0 and 1, respectively, which implies it is bounded in \(L^2\). Since \((Y^+_n)^2 \le Y_n^2\), the sequence \(\{Y_n^+\}_{n\in {\mathbb {N}}}\) is bounded in \(L^2\) as well. It readily follows from elementary probability theory that any sequence bounded in \(L^2\) is uniformly integrable; see, for example, [7]. \(\square \)
By combining the properties proved in Lemmas 1 and 3 with Assumption 1, the next result follows directly by [3, Thm. X6.1].
Although Proposition 3 tells us that the properly scaled \(Q_{n}\) converges to a non-degenerate limiting random variable, it does not cover the convergence of its mean, variance and the empty-queue probability. In order to secure convergence of these performance measures as well, we follow an approach similar [37], using Assumptions 1 and 3.
Proposition 4
Let \({\hat{Q}}_{n}\) be as in (53), \(\mu _n,\sigma _n^2 \rightarrow \infty \) such that both \(\sigma _n^2/\mu _n\rightarrow \infty \) and \({\mathbb {E}}[(\max \{{\hat{A}}_n,0\})^m]\) is bounded in n for \(m=3,4\). Then
First, we recall that \({\hat{Q}}_{n}{\;\buildrel {d}\over = \;}M_{\beta ,n}\) for all \(n\in {\mathbb {N}}\), so that \({\mathbb {P}}({\hat{Q}}_{n} = 0) = {\mathbb {P}}(M_{\beta ,n}=0)\), \({\mathbb {E}}[{\hat{Q}}_{n}]={\mathbb {E}}[M_{\beta ,n}]\) and \(\mathrm{Var}\,\,{\hat{Q}}_{n}=\mathrm{Var}\,\,M_{\beta ,n}\) as defined in (52). Our starting point is Spitzer’s identity, see [3, p. 230],
for \(n\rightarrow \infty \), where the \(Z_i\) are independent and identically normally distributed with mean \(-\beta \) and variance 1. Because equivalent expressions to (58)–(60) apply to the limiting Gaussian random walk, it is sufficient to show that the sums converge uniformly in n, so that we can apply dominated convergence to prove the result.
We start with the empty-queue probability. To justify interchangeability of the infinite sum and limit, note
where we used that \({\mathbb {E}}[ S_{k,n}] = k{\mathbb {E}}[Y_{1,n}] = -k\beta \) and \(\mathrm{Var}\,S_{k,n} = k\), and apply Chebyshev’s inequality, so that
Finding a suitable upper bound on \(\frac{1}{k}\int _0^\infty {\mathbb {P}}({\hat{Q}}_{n}>x) \mathrm{d}x\) and \(\frac{1}{k}\int _0^\infty {\mathbb {P}}({\hat{Q}}_{n}>\sqrt{x}) \mathrm{d}x\) requires a bit more work. We initially focus on the former, and the latter follows easily. The following inequality from [32] proves to be very useful:
where \({\bar{S}}_k\) is the sum of k i.i.d. random variables distributed as X, with \({\mathbb {E}}[X] = 0\) and \(\mathrm{Var}\,\, X=\sigma ^2\), \(y > 0\), \(r>0\) and \(C_r\) a constant only depending on r. We take \(r=3\) for brevity in the remainder of the proof, although any \(r>2\) will suffice. We have, from (61) with \(X={\hat{A}}_n\), so that \({\mathbb {E}}[X]=0,\ \mathrm{Var}\,\, X = 1\), and \(r=3\), \(y=x+k\beta \),
Hence, we conclude, as in (69), that \(\lim _{n\rightarrow \infty } \mathrm{Var}\,{\hat{Q}}_n = \mathrm{Var}\,M_\beta \). This completes the proof. \(\square \)
We shall now indicate that the condition in Proposition 4 on boundedness of \({\mathbb {E}}[(\max \{{\hat{A}}_n,0\})^m]\) in n for \(m=3,4\) is not overly restrictive by showing that it is satisfied by the Poisson mixture \(A_n\) considered in Sect. 2. With \(p_{n,k} = {\mathbb {P}}(A_n = k)\), we have that the pgf \({\tilde{A}}_n\) of A is given by
with integration along a circle with center 0 and radius less than \((1+b)/b\). For convenience, we have temporarily omitted the index n in \(p_{n,k-1}\), \(a_n\), \(b_n\) and \(\mu _n\). The saddle point \(z_{\mathrm{sp}}\) lies on the positive real axis between 0 and \((1+b)/b\) and is obtained by setting \(f'(z)=0\), where
with k restricted to the range \(0\le k-ab = O(ab)\). This range of k is sufficiently large for the series and the integral in (86) below to have converged. We now use this approximation in (79). Thus we have, using \(\sigma _n^2 = a_nb_n(b_n+1) \approx a_nb_n^2\) and \(\mu _n = a_nb_n\),
The final member of (86) is independent of n, and this provides evidence that \({\mathbb {E}}[(\max \{{\hat{A}}_n,0\})^m]\) is bounded.
B Numerical procedures
An alternative characterization of the stationary distribution is based on the analysis in [10] and considers a factorization in terms of (complex) roots:
where \(z_1,\ldots ,z_{s_n-1}\) denote the zeros of \(z^{s_n} - {\tilde{A}}_{n}(z)\) in \(|z|<1\). These zeros exist under the assumption \(s_n > a_nb_n\); see [2]. A robust numerical procedure to obtain these zeros is essential for a base of comparison. We discuss two methods that fit these requirements. The first follows directly from [20].
with \(w^n_k = \mathrm{e}^{2\pi ik/s_n}\) and \(z_k^{n,0}=0\) for \(k=0,1,\ldots ,s_{n-1}\). Then \(z_k^{n,l} \rightarrow z_k^n\) for all \(k=0,1,\ldots ,s_n-1\) for \(l\rightarrow \infty \).
Proof
The successive substitution scheme given in (87) is the fixed point iteration scheme described in [20], applied to the pgf of our arrival process. The authors show that, under the assumption of \({\tilde{A}}_{n}(z)\) being zero-free within \(|z|\le 1\), the zeros can be approximated arbitrarily closely, given that the function \([{\tilde{A}}_{n}(z)]^{1/s_n}\) is a contraction for \(|z|\le 1\), i.e.,
when \(|z|\le 1\). Hence, the expression in (88) is less than 1 for all \(|z|\le 1\). Evidently, \({\tilde{A}}_{n}(z)\) is also zero-free in \(|z|\le 1\). Thus, [20, Lemma 3.8] shows that \(z_k^{n,l}\) as in (87) converges to the desired roots \(z^n_k\) for all k as l tends to infinity. \(\square \)
Remark 2
The asymptotic convergence rate of the iteration in (87) equals \(\frac{\mathrm{d}}{\mathrm{d}z}[{\tilde{A}}_{n}(z)]^{1/s_n}\) evaluated at \(z=z_k^n\). Hence, convergence is slow for zeros near 1 and fast for zeros away from 1.
A different approach is based on the Bürmann–Lagrange inversion formula.
Lemma 5
Let \(w^n_k = \hbox {e}^{2\pi ik/s_n}\) and \(\alpha _n = a_n/s_n\). Then, the zeros of \(z^{s_n}-{\tilde{A}}_{n}(z)\) are given by
where \(w = w_k = \mathrm{e}^{2\pi i k/s_n}\). The Bürmann–Lagrange formula for \(z=z(w)\), as can be found in [15, Sec. 2.2] for \(z=z(w)\), is given by
for \(0<\rho _n<1\) and \(b_n>0\). Furthermore, the quantity in (90) vanishes at \(\rho _n=1\) and is therefore negative for \(0<\rho _n<1\) and \(b_n>0\). \(\square \)
Remark 3
The formula for the radius of convergence in (89) clearly shows the decremental effect of both having a large \(b_n\) and/or having \(\rho _n\) close to 1. The quantities \(\beta (l\alpha +l-1)/(\beta (l+1)\beta (l\alpha ))\) in the power series for z(w) are not very convenient for recursive computation, although normally \(\alpha = a_n/s_n\) is a rational number.
