Externalities in Queues as Stochastic Processes: The Case of FCFS M/G/1

1. Introduction

Consider a conventional M/G/1 queueing system that is served according to the first-come, first-served (FCFS) discipline, with arrival rate $\lambda >0$ and with the service distribution given by $B(·)$. Assume that the queue is stable, and let the workload level at time t = 0 be $v\ge 0$ (say) minutes. Denote the workload at time $t\ge 0$ by $W_v(t)$, and let T_i be the arrival time of the ith customer. The main objective of this paper is to analyze the aggregate effect of an additional customer, who has arrived at time t = 0 with a service requirement of size $x\ge 0$, on the waiting times of all other customers. In other words, we are interested in the distribution of the externality:

Thus, the externality E(x, v) is to be interpreted as the total waiting time that could be saved if the additional customer reduced their service requirement from $x⩾0$ to zero. To the best of our knowledge, Haviv and Ritov (1998) is the only existing paper that analyzes E(x, v). In Haviv and Ritov (1998), it was shown that if (i) v is a random variable that is independent from the arrival process and the service requirements of the customers, and (ii) v is distributed according to the stationary distribution of the workload process, then the mean of E(x, v) is given by

where μ_i ($i=1,2,\dots$) is the ith moment pertaining to $B(·)$ and $\rho \equiv \lambda {\mu }_1$.

Whereas Haviv and Ritov (1998) focused on computing the mean externality (under the specific condition mentioned previously), we have managed to develop a full probabilistic analysis of E(x, v). In this context it is important to notice that

can be seen as a collection of random variables that are all defined on the same probability space. By considering v as a fixed parameter while x is given the role of a time index, we analyze the stochastic process $E_v(·)\equiv E(·,v)$. To underline the natural interpretation of this process, let the additional customer arrive to the queue when the existing workload is v and assume that this customer has two tasks that they want the server to do for them: a first one of size $x_1\ge 0$ and a second one of size $x_2\ge 0$. Then, $E_v(x_1+x_2)-E_v(x_1)$ is equal to the total waiting time that could be saved by the other customers if the customer gave up on their second task but insisted on completing the first one.

The main contribution of this work lies in an extensive analysis of $E_v(·)$ that, in the remainder of this paper, we refer to as the externalities process. Specific open questions that we have managed to solve in the current paper are as follows:

1. What can be said about the distribution of the externalities in a nonstationary FCFS M/G/1 queue? As it turns out, the externalities process $E_v(·)$ can be represented by an integral of a compound Poisson process that is shifted in time by an amount v. Importantly, this compound Poisson process is defined on the same probability space as the one on which our model is defined.

2. Observe that the expected value in (2) is convex in x, which indicates that the marginal effect of extra workload on the customer population is increasing. Is it possible to extend this result by showing convexity of the externalities process? The answer is affirmative, where we also provide an explicit representation of the corresponding right-derivative.

3. Is there a systematic way to evaluate the moments of the externality $E_v(x)$? To this end, we derive the Laplace-Stieltjes transform (LST) of the finite-dimensional distributions of the externalities process $E_v(·)$, from which the moments follow. In particular, we provide closed-form formulae for the auto-covariance and auto-correlation functions of $E_v(·)$. Remarkably, it is shown that when v is fixed, then the auto-correlation does not depend on the stochastic ingredients of the model, that is, the arrival rate and service distribution.

4. Is it possible to approximate the distribution of the externalities in some asymptotic regime? We show that, under an appropriate scaling, there is convergence of $E_v(·)$ to a specific Gaussian limiting process. The convergence takes place as the arrival rate tends to infinity and the service distribution is well behaved; for example, it tends to zero in an appropriate way.

1.1. Motivation

We proceed by discussing the relevance of our results and their applicability in an operational context. We do so by distinguishing three strands of application domains.

1.1.1. Choice of a Management Scheme.

In the introduction of their paper, Haviv and Ritov (1998, p. 580) discuss various applications of the externalities setup that they analyze: airplanes taking off from a runway, commuters crossing a bridge, jobs sharing a common CPU, and messages being routed through a common data network. Their motivation for studying the distribution of externalities is as follows. In the first place, they argue that “a zero profit operator who charges users for the use of a common facility usually likes to do so in accordance with the congestion costs that they impose on others.” This aligns with results in, for example, Ha (2001), Haviv (2014), Haviv and Oz (2018a, b), and Jacobovic (2022b), where various relations between optimal queue regulation schemes and externalities are revealed. Then, they point out that there are various policies of managing a queueing system (e.g., by implementing different service disciplines). Correspondingly, different management policies may result in different amounts of externalities imposed by the same user. This leads them to the conclusion that “the resulting pricing mechanism can serve as an additional criterion for deciding which management scheme to adopt.” A general account of externalities in a queueing context is given in Hassin and Haviv (2003), as well as various other connections between queueing and game theory.

1.1.2. Queues with Discretionary Services.

Recently, there has been a growing interest in queueing models with customers who themselves choose their service durations (see Feldman and Segev (2022a) and Jacobovic (2022b) and the references therein). When considering single-server queues with a nonpreemptive service discipline, the customer who gets service does not care about the increasing costs of the waiting customers behind them, thus yielding a resource allocation which is inefficient from a social point of view. To restore social efficiency, a social planner may want to impose some sort of regulation. For example, the planner may decide on a price function that tells every customer how much they are going to pay for every service duration to be purchased. A price function will be optimal if it makes the customers behave as they should according to the socially optimal resource allocation. A reasonable price mechanism amounts to requiring every customer to pay for the expected cost that is enforced on the others due to their service requirement.

Jacobovic (2022b) considered a model of a single-server queue with customers who arrive according to a Poisson process and dynamically choose their service durations, showing that when the social planner is restricted to choose a price function which is determined by the service requirement only, then the optimal price function internalizes the (expected) externalities. It is an open problem (Jacobovic 2022a) whether a similar phenomenon occurs when the social planner may choose a price function that depends on the state of the queue. If the answer to this question is affirmative and the social planner observes the workload level at the onset of every service duration, then the optimal price function is equal to $\mathbb{E}[E_v(x)]$, with v the initial workload at the start of the service and x the corresponding service requirement. As is shown in the present paper, this would reduce the search for the optimal price function to the parametric family of quadratic functions in x which are also linear in v.

Similarly, in another possible scenario a social planner observes the number of waiting customers at the start of every service, but they do not see the customers’ service requirements (Haviv 2014, section 3). In this case, the conjectured optimal price function is the conditional expectation of $E_v(x)$ given the available information at the start of the service. Once more, our results imply that this conditional expectation is quadratic in x and linear in the number of waiting customers at the time of the start of the service.

1.1.3. Queues with a Proactive Service Discipline.

Consider an emergency room with a single specific bed that is reserved for patients with special needs, for example, those who arrive because of strokes or heart attacks. We refer to these patients as urgent, whereas the patients who arrive due to other reasons are called regular. The special bed might be useful also for regular patients, whereas the urgent ones can be treated only in the special bed. Hence, a nontrivial question is as follows: If there are many regular patients and no urgent patients, should the regular patients be allowed to use the special bed? Doing so is evidently beneficial to the regular patients, but it is also possible that immediately after allocating a regular patient to the special bed, a batch of urgent patients arrives whose treatments will be delayed.

Now, assume that the urgent patients arrive according to a Poisson process with rate λ and their service requirements are independent and identically distributed (i.i.d.) random variables with a distribution function $B(·)$ that are independent from the arrival process. Then, observe that $E_0(x)$ is equal to the total damage that is caused to the urgent patients due to an allocation of a regular customer into the special bed for x minutes once it is empty. Clearly, the decision maker could benefit from the distributional properties of $E_0(x)$ that we establish in the present paper.

The previous example connects our work with server-allocation problems in multiclass queues. Recent progress in this direction can be found in Chan et al. (2021), Hu et al. (2022), Huang et al. (2015), and Liu et al. (2022).

1.2. Organization of the Paper

The organization of this work is as follows. Section 2 starts with a brief discussion of a known result, extensively used in the paper: a fixed-point relation that is satisfied by the LST of the distribution of the number of customers who arrive to a queue during a busy period. Besides this fixed-point relation, all results presented are novel contributions. Then, Section 3 includes a representation of the externalities process $E_v(·)$ in terms of a compound Poisson process, yielding two insightful decompositions.

1.2.1. Decomposition 1.

$E_v(·)$ is equal to an integral of a compound Poisson process which is shifted in time by v. The rate of this process is equal to λ and its jumps have the distribution identified in Section 2. Section 5 provides a compact analysis of the crossing times of the right-derivative of $E_v(·)$. An important application of this decomposition can be found in Section 6, where we derive of a functional central limit theorem for the externalities process.

1.2.2. Decomposition 2.

The distribution of $E_v(x_1+x_2)-E_v(x_1)$ is the same as the distribution of a sum of independent random variables. This helps in Section 4, where we derive the LST of the finite-dimensional distributions pertaining to the process $E_v(·)$. Moreover, this decomposition plays an important role in the derivations in Section 7 where we consider the more general framework when v is a nonnegative random variable, independent from the arrival process and the service requirements of the customers. In particular, the results of this part include a generalization of (2) to the case where v is not necessarily distributed according to the stationary distribution of the workload process.

Section 8 concludes by discussing some related open problems that lead to several directions of future research. To optimize the flow of the paper, all proofs are given in Section 9.

2. Number of Customers During a Busy Period

This section discusses a few results concerning the number of customers who arrive to a stable FCFS M/G/1 queue during a single busy period, needed in the upcoming sections. Proposition 1 is standard (Cohen 1969, chapter II.4.4), whereas all the other results in this section are essentially direct consequences. However, because we did not find a reference for Propositions 2 and 3, we decided to include their proofs. For additional work on the distribution of the number of customers who arrive during a busy period, see Novak et al. (2006) and the references therein.

As before, we consider the setting of an M/G/1 queue with arrival rate λ and a service distribution $B(·)$, but now the system starts empty at time t = 0. In addition, denote the LST of $B(·)$ by

For any $n\ge 1$, denote the nth moment of $B(·)$ by

Throughout this paper, we assume that $\rho \equiv \lambda {\mu }_1\in (0,1)$ to ensure stability.

Let N(s) be the probability that exactly s customers received service during the first busy period. The associated kth moment is denoted by

Proposition 1.

For every $z\in (0,1)$, the following fixed-point equation in y

$$y=z\hspace{0.17em}b(\lambda (1-y))$$(6)

has a unique solution y_z that belongs to (0, 1). Furthermore, y_z equals the generating function

$$\widehat{N}(z)\equiv {\displaystyle \sum _{s=1}^{\infty }{z}^s}N(s).$$(7)

Remark 1.

Notice that

$$0<zb\left(\lambda \right)<zb(0)<1.$$(8)

Thus, because both sides of (6) are continuous in y, for every $z\in (0,1)$, it is possible to find y_z efficiently by a standard line-search algorithm.

In particular, for every $\alpha >0$, we can insert $z=e^{-\alpha }$ into (6). This yields the following fixed-point relation for the LST:

$$\tilde{N}(\alpha )\equiv {\displaystyle \sum _{s=1}^{\infty }{e}^{-\alpha s}}N(s)=e^{-\alpha }b\{\lambda [1-\tilde{N}(\alpha )]\},\hspace{0.17em}\hspace{0.17em}\alpha >0.$$(9)

Therefore, we can differentiate both sides of (9) at zero to get a recursive formula for the moments η_n, $n\ge 1$. In the sequel, for any pair of integers m and k such that $1\le m\le k$, denote the corresponding incomplete Bell’s polynomial

$$\begin{array}{ll}{\mathcal{B}}_{k,m}\hfill & [x_1,x_2,\dots ,x_{k-m+1}]\hfill \\ \hfill & \equiv {\displaystyle \sum \frac{k!}{j_1!j_2!\dots j_{k-m+1}!}}{\left(\frac{x_1}{1!}\right)}^{j_1}{\left(\frac{x_2}{2!}\right)}^{j_2}\dots {\left(\frac{x_{k-m+1}}{(k-m+1)!}\right)}^{j_{k-m+1}},\hfill \end{array}$$(10)

where the summation is over all nonnegative integers $j_1,j_2,\dots ,j_{k-m+1}$ that satisfy the following two conditions:

$${\displaystyle \sum _{i=1}^{k-m+1}{j}_i}=m,\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum _{i=1}^{k-m+1}i}{j}_i=k.$$(11)

In addition, for any pair of integers m and k such that $1\le m\le k$, we introduce the following compact notation:

$${\check{\mathcal{B}}}_{k,m}\equiv {\mathcal{B}}_{k,m}\left[-{\eta }_1,{\eta }_2,\dots ,{(-1)}^{(k-m+1)}{\eta }_{k-m+1}\right].$$

Proposition 2.

For every positive integer n,

$${\eta }_n\hspace{0.17em}=\frac{{(-1)}^n}{1-\rho }\left\{{(-1)}^n+{\displaystyle \sum _{k=1}^{n-1}\left(\begin{array}{c}n\\ k\end{array}\right)}{(-1)}^{n-k}{\displaystyle \sum _{m=1}^k{\lambda }^m}{\mu }_m{\check{\mathcal{B}}}_{k,m}+{\displaystyle \sum _{m=2}^n{\lambda }^m}{\mu }_m{\check{\mathcal{B}}}_{n,m}\right\}.$$(12)

The following corollary, providing explicit expressions for the first three moments in terms of the moments of $B(·)$, is an immediate consequence of Proposition 2. The first moment η₁ also follows from the well-known result that the expected length of the busy period is ${\mu }_1/(1-\rho )$, in combination with Little’s law.

Corollary 1.

The first three moments are given by

$$\begin{array}{ll}\hfill & {\eta }_1=\frac{1}{1-\rho },\hfill \\ \hfill & {\eta }_2=\frac{1}{1-\rho }·\left[1+\frac{2\rho }{1-\rho }+\frac{{\lambda }^2{\mu }_2}{{(1-\rho )}^2}\right],\hfill \\ \hfill & {\eta }_3=\frac{1}{1-\rho }\left\{1+\frac{3\rho }{1-\rho }+3\left[\rho {\eta }_2+\frac{{\lambda }^2{\mu }_2}{{(1-\rho )}^2}\right]+\frac{3{\lambda }^2{\mu }_2{\eta }_2}{1-\rho }+\frac{{\lambda }^3{\mu }_3}{{(1-\rho )}^3}\right\}.\hfill \end{array}$$(13)

In a similar fashion, a combinatorial formula for the probability mass function N(s), $s=1,2,\dots$ may be derived by repeatedly differentiating

at zero. Using the compact notationwe arrive at the following recursion.

Proposition 3.

For any $s\ge 2$,

$$N(s)=\frac{1}{(s-1)!}{\displaystyle \sum _{m=1}^{s-1}{(-\lambda )}^m}\hspace{0.17em}{b}^{(m)}(\lambda )\hspace{0.17em}{\overline{\mathcal{B}}}_{s-1,m},$$(15)

and $N(1)=b(\lambda )$.

3. Decompositions of Externalities

This section first introduces the notation that will be used throughout the paper and provides a detailed model description. Then we state our decomposition results.

3.1. Model Description

With λ and $B(·)$ as defined earlier, let $\{J(t):t\ge 0\}$ be a compound Poisson process with rate $\lambda \in (0,\infty )$ and a nonnegative jump distribution $B(·)$. In addition, for each $i\ge 1$, we let T_i be the time of the ith jump of the process $J(·)$. In addition, consider two processes $X_1(·)$ and $X_2(·)$ that are given by

for some two parameters $x,v\ge 0$. Then, for each i = 1, 2, let $Y_i(·)$ be the reflection of $X_i(·)$ at the origin; this reflection, formally defined in Dȩbicki and Mandjes (2015, section 2.4), can be thought of as a mechanism preventing the “free processes” $X_i(·)$ from becoming negative. Then, define, for a given initial workload v and service requirement x, the externality via

Notice that $Y_2(t)\ge Y_1(t)$, but the stability condition $\rho <1$ implies that the hitting time of $Y_2(·)$ in the origin is an almost surely finite random variable. Denote this random variable by ζ, and this makes E(x, v) an almost surely finite random variable. Observe that from time ζ on, the processes $Y_1(t)$ and $Y_2(t)$ are coupled (in that they coincide).

Importantly, $Y_1(·)$ (respectively, $Y_2(·)$) coincides with $W_v(·)$ (respectively, $W_{v+x}(·)$), which was defined in the beginning of Section 1. Therefore, the quantity E(x, v) represents the externality that is due to an arrival of a customer with a service demand of x when the processing time of the existing workload is v. More generally, fixing the initial workload $v\ge 0$, we can consider a stochastic process $E_v(x)\equiv E(x,v)$ indexed by $x\in [0,\infty )$, which in the sequel we refer to as the externalities process.

3.2. Decomposition 1

For the analysis of the externalities process, the following notation and definitions are needed. Throughout, the initial workload v pertaining to $Y_1(t)$ is held fixed. In the first place, let τ₀ be the end of the first busy period of $Y_1(t)$. Also, let σ₁ be the time of the first jump of $J(·)$ that occurs after τ₀. In addition, denote the first time after σ₁ in which $Y_1(·)$ hits the origin by τ₁ (i.e., the end of the second busy period of $Y_1(t)$). Similarly, we can define σ₂ to be the time of the first jump of $J(·)$ which occurs after τ₁. Moreover, let τ₂ be the first time after σ₂ in which $Y_1(·)$ hits the origin. We may continue recursively with this construction in the evident manner, thus yielding the two sequences ${({\tau }_k)}_{k\ge 1}$ and ${({\sigma }_k)}_{k\ge 1}$.

Also, for each $k\ge 1$ denote $I_k\equiv {\sigma }_k-{\tau }_{k-1}$ and notice that $I_1,I_2,\dots$ is a sequence of i.i.d. random variables that have an exponential distribution with rate λ. Furthermore, for each $k\ge 1$, let N_k be the number of jumps of $J(·)$ on $[{\sigma }_k,{\tau }_k]$. Note that $N_1,N_2,\dots$ is a sequence of i.i.d. random variables that are distributed according to $N(·)$ (explicitly given in Proposition 3). In a similar fashion, denote the number of jumps of $J(·)$ on $(0,{\tau }_0]$ by M and notice that M depends on v. Furthermore, it is important to notice that the random objects M, ${(I_k)}_{k\ge 1}$ and ${(N_k)}_{k\ge 1}$ are all independent.

The following identity, which directly follows from the pictorial illustration in Figure 1, is a key ingredient for the rest of our analysis:

Theorem 1.

For every $x\ge 0$ denote

$$\xi (x)\equiv \min \left\{k\ge 1:\hspace{0.17em}{\displaystyle \sum _{j=1}^k{I}_j}>x\right\}-1.$$(19)

In addition, define a right-continuous nondecreasing stochastic process (in x) as follows:

$${\dot{E}}_v(x)\equiv M+{\displaystyle \sum _{k=1}^{\xi (x)}{N}_k},\hspace{0.17em}\hspace{0.17em}x\ge 0.$$(20)

Then, for each $x\ge 0$,

$$E_v(x)={\displaystyle {\int }_0^x{\dot{E}}_v}(y)\hspace{0.17em}\text{d}y,$$(21)

and hence $E_v(·)$ is convex with a right-derivative that equals ${\dot{E}}_v(·)$.

Remark 2.

Theorem 1 implies that $E_v(·)$ is a convex stochastic process. For more examples of convex stochastic processes that arise in different applications, see Jacobovic and Kella (2020).

For each $y\ge 0$, let S(y) be the number of jumps that $J(·)$ has until

$$\inf \left\{t\ge 0:J(t)-t\le -y\right\}.$$(22)

Notice that $S(v+y)={\dot{E}}_v(y)$ for every $y\ge 0$. Therefore, when replacing ${\dot{E}}_v(·)$ by $S(v+·)$ in (21), this equation remains valid. Furthermore, the same technique that was applied in the proof of Proposition 1 can be used to show that $S(·)$ is a compound Poisson process with rate λ and jump distribution $N(·)$. As a result, we obtain the following compact representation of the externalities process.

Corollary 2.

In the same probability space in which the model is defined, there is a compound Poisson process $S(·)$ with rate λ and jump distribution $N(·)$ such that

$$E_v(x)={\displaystyle {\int }_0^{x}S}(v+y)\hspace{0.17em}\text{d}y,\hspace{0.17em}\hspace{0.17em}\forall x\ge 0.$$(23)

3.3. Decomposition 2

It is interesting to notice that ${\dot{E}}_v(·)$ equals the number of jumps of $J(·)$ that cause an increase in the value of $E_v(x)$. Consider some arbitrary $x_1,x_2\ge 0$ and denote

It is illustrated in Figure 2 that every jump of $J(·)$ that causes an increase in the value of $E_v(x_1)$ contributes x₂ to the value of $\mathrm{\Delta }(x_1+x_2,x_1)$. This means that we can write

Especially, because the workload process is strong Markov, the sum in the right-hand side is distributed as $E_0(x_2)$ and is independent of ${\dot{E}}_v(x_1)$ (Figure 2).

Furthermore, assume that $\xi \sim \text{Poi}(\lambda x_2)$ and $U_1,U_2,\dots$ is an i.i.d. sequence of random variables that are distributed uniformly on $[0,1]$. In particular, assume that ξ, ${(U_k)}_{k\ge 1}$ and ${(N_k)}_{k\ge 1}$ are independent. In addition, for each $j\ge 1$ we use the notation

to denote the order statistics of $U_1,U_2,\dots ,U_j$. Then an application of known “symmetry properties” yields the following distributional equality:

This argument can be applied recursively to derive the following theorem. As illustrated in Section 4, it provides us with a systematic approach to compute the moments of the finite-dimensional distributions of $E_v(·)$.

Theorem 2.

Let $x_1,x_2,\dots ,x_k\ge 0$ and assume that $\mathcal{N}\equiv \{N_{m,i}:i,m\ge 1\},\hspace{0.17em}\mathcal{U}\equiv \{U_{m,i}:i,m\ge 1\}$ and ${({\xi }_j)}_{j\ge 1}$ are such that:

1. $\mathcal{N}$ is an infinite array of i.i.d. random variables such that $N_{1,1}$ is distributed according to $N(·)$.

2. $\mathcal{U}$ is an infinite array of i.i.d. random variables that are distributed uniformly on $[0,1]$.

3. ${\xi }_1,{\xi }_2,\dots$ are independent random variables such that ${\xi }_1\sim \text{Poi}(\lambda v)$ and ${\xi }_j\sim \text{Poi}(\lambda x_{j-1}),\hspace{0.17em}j\ge 2$.

4. $\mathcal{N},\mathcal{U}$ and ${({\xi }_j)}_{j\ge 1}$ are independent.

Then,

$$E_v\left({\displaystyle \sum _{i=1}^k{x}_i}\right)\stackrel{d}{=}{\displaystyle \sum _{j=1}^k{x}_j}\left({\displaystyle \sum _{l=1}^j{\displaystyle \sum _{m=1}^{{\xi }_l}{N}_{m,l}}}+{\displaystyle \sum _{m=1}^{{\xi }_{j+1}}{N}_{m,j+1}}{U}_{m,j+1}\right)$$(28)

and

$${\mathrm{\Delta }}_v(x_1+x_2,x_1)\stackrel{d}{=}{x}_2\left({\displaystyle \sum _{m=1}^{{\xi }_1}{N}_{m,1}}+{\displaystyle \sum _{m=1}^{{\xi }_2}{N}_{m,2}}+{\displaystyle \sum _{m=1}^{{\xi }_3}{N}_{m,3}}{U}_{m,3}\right).$$(29)

4. Moments of the Finite-Dimensional Distributions

This section concentrates on the evaluation of moments corresponding to the finite dimensional distributions of the externalities process $E_v(·)$. We first present the mean and variance and then the auto-covariance and auto-correlation, after which we proceed with higher moments.

4.1. Mean and Variance

Fix x > 0 and notice that an insertion of k = 1 into (28) yields

Thus, by an application of the formula of an expectation of a compound Poisson random variable, we directly obtain that

and, as expected, $\mathbb{E}[E_v(x)]$ is convex in x. Similarly, the formula of the variance of a compound Poisson random variable may be used to derive

4.2. Auto-Covariance and Auto-Correlation

Fix some $x_1,x_2>0$. Because the sums in the right-hand side of (29) are independent, we find

In addition,

and hence, an insertion of (32) implies that the auto-covariance function of $E_v(·)$ equals

As argued in the Introduction, in the situation of a customer arriving at time 0 with two tasks (of size x₁ and x₂, respectively), $E_v(x_1+x_2)-E_v(x_1)$ represents the total waiting time that could be saved by the other customers if the customer gave up on their second task but insisted on completing the first one. The auto-covariance (35) provides insight into the effect of the additional x₂.

As a result, the auto-correlation function is given by

Surprisingly, the expression in (36) is invariant with respect to the service distribution and the arrival rate. At the same time, observe that $R_v(x_1,x_1+x_2)$ is positive. In addition, the expression of $R_v(x_1,x_1+x_2)$ actually shows that the externalities process is not wide sense stationary (see the definition in Yaglom (2004), p. 15).

Remark 3.

In Section 7, we consider a setup in which v is a general nonnegative random variable, independent from the arrival process and service requirements. There, it is shown that in the more complex setup, the auto-correlation function depends on the arrival rate and service distribution unless v is a degenerate random variable.

4.3. Higher Moments

Higher moments (including joint moments) of $E_v(·)$ may be derived via differentiation of the LST formula that is given in the next theorem. This is a tedious derivation that we decided to leave out. The result is particularly useful when analyzing a situation in which the customer arriving at time 0 has k tasks, having sizes $x_1,\dots ,x_k$.

Theorem 3.

Let $k\ge 1$ and $\alpha \equiv ({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k),x\equiv (x_1,x_2,\dots ,x_k)\in {(0,\infty )}^k$. In addition, define

$$w(x,\alpha )\equiv {\alpha }_1{x}_1+{\alpha }_2(x_1+x_2)+\cdots +{\alpha }_k{\displaystyle \sum _{i=1}^k{x}_i},$$(37)

and for every $u\in (0,1)$ denote

$$s_1(x,\alpha ,u)\equiv {\alpha }_1{x}_{1}u+{\alpha }_2(x_{1}u+x_2)+\cdots +{\alpha }_k\left(x_{1}u+{\displaystyle \sum _{i=2}^k{x}_i}\right),$$(38)

$$\begin{array}{l}{s}_2(x,\alpha ,u)\equiv {\alpha }_2{x}_{2}u+{\alpha }_3(x_{2}u+x_3)+\cdots +{\alpha }_k\left(x_{2}u+{\displaystyle \sum _{i=3}^k{x}_i}\right),\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}⋮\hfill \\ s_k(x,\alpha ,u)\equiv {\alpha }_k{x}_{k}u.\hfill \end{array}$$(39)

Then, for any v > 0,

$$\begin{array}{ll}\mathbb{E}\exp \left\{-{\displaystyle \sum _{l=1}^k{\alpha }_l}{E}_v\left({\displaystyle \sum _{i=1}^l{x}_i}\right)\right\}\hfill & =\exp \left\{\lambda v\left[\tilde{N}\left(w(x,\alpha )\right)-1\right]\right\}\hfill \\ \hfill & ·{\displaystyle \prod _{l=1}^k{\displaystyle {\int }_0^1\exp }}\left\{\lambda x_l\left[\tilde{N}(s_l(x,\alpha ,u))-1\right]\right\}\text{d}u.\hfill \end{array}$$(40)

5. Crossing Times of ${\dot{E}}_0(·)$

The process ${\dot{E}}_v(·)$ is nondecreasing such that ${\dot{E}}_v(0)=M$, and $E_v(x)\uparrow \infty$ as $x\to \infty$. Therefore, it is natural to study the crossing times of the process ${\dot{E}}_v(·)$. Namely, fix some y > 0, and the corresponding crossing time is

In the remainder of this paper, we consider the special case v = 0 for which M = 0, and hence $x(y)\equiv x_0(y)$ has a relatively tractable representation (but see Remark 5 for some reflections on the case v > 0). In fact, Theorem 2 yields that

where $\upsilon (y)\equiv \min \{t\ge 1:{\sum }_{m=1}^t{N}_k\ge \lceil y\rceil \}$. In particular, $\upsilon (y)$ and $I_1,I_2,\dots$ are independent. Furthermore, $\upsilon (y)$ can be described as the time until absorption in a Markov chain with a unique absorbing state. Specifically, this chain has a state-space $\{0,1,2,\dots ,\lceil y\rceil \}$ with an absorbing state $\lceil y\rceil$ and an initial state 0. In addition, the transition matrix is equal to $P\equiv {[p_{ij}]}_{1\le i,j\le \lceil y\rceil }$, given by

It is well known that the mean of $\upsilon (y)$ can be characterized via

where ${\psi }_{\lceil y\rceil -1}=1$ and ${\psi }_1,{\psi }_2,\dots ,{\psi }_{\lceil y\rceil -2}$ are given recursively by the equations

Therefore, Wald’s identity may be applied to (42) to deduce that

Remark 4.

The second moment of $\upsilon (y)$ can be computed using a similar technique, thus also yielding $\text{Var}[\upsilon (y)]$. Hence, it is possible to compute the variance of x(y) via the formula

$$\text{Var}\left[x(y)\right]=\frac{{\psi }_0(y)+\text{Var}\left[\upsilon (y)\right]}{{\lambda }^2}.$$(47)

Remark 5.

When v > 0, it makes sense to rely on a similar computation in which we condition and de-condition on M. In practice, we do not see how this computation leads to a tractable expression for the general case.

6. Gaussian Approximation of $E_v(·)$

The main result of this section concerns a Gaussian approximation for the externalities process. To provide an accurate statement of this result, the model that was described in Section 3 is characterized by the triplet $(\lambda ,B(·),v)$. Fix $v\ge 0$ and consider a sequence of models

such that the nth model is associated with an arrival rate ${\lambda }_n>0$ and a service distribution $B_n(·)$. Respectively, for each $n\ge 1$, we introduce the notation

In addition, for each $n\ge 1$, denote the externalities process that is associated with the nth model by $E_v^{(n)}(·)$. Also, let $N_n(·)$ be the probability mass function of the number of customers who got service during a single busy period of a FCFS M/G/1 queue with an arrival rate λ_n and a service distribution $B_n(·)$. Correspondingly, for each $n,k\ge 1$, denote

and observe that ${\eta }_{k,n}$ is the analogue of η_k in the nth model.

6.1. Functional Central Limit Theorem

The main result of this section is stated in the next functional central limit theorem.

Theorem 4.

Define, for a fixed $v\ge 0$,

1. A stochastic process

   $$H_v(x)\equiv {\displaystyle {\int }_0^{x}W}(v+y)\hspace{0.17em}\text{d}y,\hspace{0.17em}\hspace{0.17em}x\ge 0$$(51)
   such that $W(·)$ is a standard Wiener process.

2. A sequence (in $n=1,2,\dots$) of stochastic processes

   $${\widehat{E}}_v^{(n)}(x)\equiv \frac{E_v^{(n)}(x)-\mathbb{E}[E_v^{(n)}(x)]}{\sqrt{{\lambda }_n{\eta }_{2,n}}},\hspace{0.17em}\hspace{0.17em}x\ge 0.$$(52)

In addition, assume that the next conditions hold:

• (i) ${\lambda }_n\to \infty$ as $n\to \infty$.

• (ii) There is $n^{\prime }\ge 1$ such that ${\rho }_n<1$ for every $n\ge n^{\prime }$.

• (iii) $\frac{{\eta }_{3,n}}{\sqrt{{\lambda }_n{\eta }_{2,n}^3}}\to 0$ as $n\to \infty$.

Then,

$${\widehat{E}}_v^{(n)}(·)\Rightarrow H_v(·)\hspace{0.17em}\hspace{0.17em}as\hspace{0.17em}\hspace{0.17em}n\to \infty ,$$(53)

where $\Rightarrow$ denotes weak convergence on $\mathcal{D}[0,\infty )$ equipped with the uniform metric (on compacta).

Observe that checking condition (iii) is not straightforward because it is phrased in terms of the moments of $N_n(·)$. The following proposition presents two sets of sufficient conditions that are considerably easier to verify. Broadly speaking, the proof of these sets of conditions being sufficient relies on the expressions appearing in the statement of Corollary 1.

Proposition 4.

The following two claims hold

1. Assume that condition (i) and in addition the two conditions

   $$\underset{n\to \infty }{\text{lim sup}}\hspace{0.17em}{\rho }_n<1,\hspace{0.17em}\underset{n\to \infty }{\text{lim sup}}\hspace{0.17em}{\lambda }_n^3{\mu }_{3,n}<\infty ,$$(54)
   are all satisfied. Then, (53) is valid.

2. Assume that condition (i), condition (ii), and in addition, the three conditions

   $$\underset{n\to \infty }{\text{lim inf}}\hspace{0.17em}{\lambda }_n^2{\mu }_{2,n}>0,\hspace{0.17em}\underset{n\to \infty }{\text{lim sup}}\hspace{0.17em}{\lambda }_n^3{\mu }_{3,n}<\infty ,\hspace{0.17em}\underset{n\to \infty }{\lim }{\lambda }_n(1-{\rho }_n)=\infty ,$$(55)
   are all satisfied. Then, (53) is valid.

Remark 6.

The condition

$$\underset{n\to \infty }{\text{lim sup}\hspace{0.17em}}{\rho }_n<1$$

implies condition (ii). In addition, it does not go together with a heavy-traffic regime (i.e., ${\rho }_n\uparrow 1$ as $n\to \infty$) under the first set of conditions in Proposition 4. Thus, the added value of the second set of conditions in Proposition 4 is that it could cover a heavy-traffic regime, that is, ${\rho }_n\uparrow 1$ as $n\to \infty$.

Remark 7.

Assume that condition (i) is satisfied. Thus, if

$$\underset{n\to \infty }{\lim }\sqrt{{\lambda }_n}(1-{\rho }_n)=c$$(56)

for some $c\in (0,\infty )$, then

$$\underset{n\to \infty }{\lim }{\lambda }_n(1-{\rho }_n)=\infty .$$(57)

At the same time, observe that (56) is not necessary for (57) even under the assumption that condition (i) is satisfied.

The general idea of the proof of Theorem 4 is as follows. Condition (ii) allows us to apply Corollary 2, and hence, for each $n\ge n^{\prime }$, there is a compensated compound Poisson process $S_n(·)$ with rate $({\lambda }_n)$ and jump distribution $(N_n(·))$ such that

$${\widehat{E}}_n^{(n)}(x)={\displaystyle {\int }_0^x\frac{S_n(v+y)}{\sqrt{{\lambda }_n{\eta }_{2,n}}}}\text{d}y,\hspace{0.17em}\hspace{0.17em}\forall x\ge 0.$$(58)

Then, the crucial part of the proof is to show that

$$\frac{S_n(·)}{\sqrt{{\lambda }_n{\eta }_{2,n}}}\Rightarrow W(·)\hspace{0.17em}\hspace{0.17em}\text{as}\hspace{0.17em}\hspace{0.17em}n\to \infty \hspace{0.17em};$$(59)

the rest will follow from this benchmark via standard arguments. In Section 6.2, we address a general result about a Gaussian approximation of compound Poisson processes. This will help in proving (59).

Remark 8.

An extensive account of heavy-traffic approximations of queueing systems can be found in Whitt (2002). Notably, heavy-traffic approximations have been developed for various functionals of the queueing process (such as the number of customers and the waiting time), but to the best of our knowledge, we are the first to do so for the externalities process. This means that, in the strict sense, we cannot compare our Theorem 4 with existing results. This being said, there is a vast literature on Gaussian approximations for sequences of compound Poisson processes, related to Theorem 5 (that is heavily relied on in our derivation of Theorem 4); we therefore include in Section 6.2 a comparison between Theorem 5 and related results.

We proceed by discussing an immediate implication of Theorem 4. To this end, fixing $x\ge 0$, recall that it is well-known result that

$${\displaystyle {\int }_0^{x}W}(v+y)\hspace{0.17em}\text{d}y\sim \mathcal{N}\left(0,x^{2}v+\frac{x^3}{3}\right).$$(60)

Hence, under the conditions of Theorem 4, we conclude the following convergence:

$${\widehat{E}}_v^{(n)}(x)\stackrel{d}{\to }\mathcal{N}\left(0,x^{2}v+\frac{x^3}{3}\right)\hspace{0.17em}\hspace{0.17em}\text{as}\hspace{0.17em}\hspace{0.17em}n\to \infty .$$(61)

Remark 9.

In fact, taking into account (32), the current analysis gives a new proof for (60) that is not based on stochastic calculus at all but only on approximation of a standard Wiener process by normalized compensated compound Poisson processes. Because (60) is known and the current proof is not simpler than the existing one, we mention this result in passing.

6.2. Gaussian Approximation to Compound Poisson Process

In this section, we discuss a general Gaussian approximation result for compound Poisson processes and relate it to existing results. As mentioned, it is used in the proof of Theorem 4, but may have broader applications.

6.2.1. Gaussian Approximation Result.

The following theorem, proven in Section 9.4, includes a statement about a Gaussian approximation of a general compound Poisson process. Possibly, this theorem may have other applications besides those that appear in the current work.

Theorem 5.

For each $n\ge 1$, let $\{J_n(t):t\ge 0\}$ be a compensated compound Poisson process with rate ${\lambda }_n>0$ and jump distribution $F_n(·)$ such that

$${\sigma }_n\equiv {\displaystyle {\int }_{-\infty }^{\infty }{t}^2}\text{d}{F}_n(t)\in (0,\infty ).$$(62)

In addition, denote

$$\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\nu }_n\equiv {\displaystyle {\int }_{-\infty }^{\infty }|}t{|}^3\text{d}{F}_n(t),$$(63)

and assume that both of the following conditions hold:

• (I) ${\lambda }_n\to \infty$ as $n\to \infty$.

• (II) $\frac{{\nu }_n}{\sqrt{{\lambda }_n{\sigma }_n^3}}\to 0$ as $n\to \infty$.

Then,

$$\frac{J_n(·)}{\sqrt{{\lambda }_n{\sigma }_n}}\Rightarrow W(·)\hspace{0.17em}\hspace{0.17em}as\hspace{0.17em}\hspace{0.17em}n\to \infty ,$$(64)

where $W(·)$ is a standard Wiener process and $\Rightarrow$ denotes weak convergence on $\mathcal{D}[0,\infty )$ equipped with the uniform metric (on compacta).

Remark 10.

Intuitively speaking, condition (I) implies that the jumps become more frequent as $n\to \infty$, whereas condition (II) makes sure that the jump distribution should not become too “wild” as $n\to \infty$.

6.2.2. Comparison with the Existing Literature.

Let $J(·)$ be a compensated-compound Poisson process with rate λ and a jump distribution with finite fourth moment. Denote the standard deviation of the jump distribution by γ. Then, Khoshnevisan (1993, corollary 3.7) states conditions under which the sequence (in n) of processes

weakly converges to a standard Wiener process in $\mathcal{D}[0,1]$ equipped with the Skorohod topology. Thus, some differences between Theorem 5 and Khoshnevisan (1993, corollary 3.7) are as follows:

1. Consider the setup of Theorem 5 with (i.e., ${\lambda }_n=n\lambda$) and ${\sigma }_n\equiv \frac{{\gamma }^2}{\lambda }$. Then, we get that $J_n\equiv {\tilde{J}}_n$, and hence in that sense, the setup of Theorem 5 is more general.

2. Theorem 5 guarantees weak convergence in a different topological space.

3. Khoshnevisan (1993, corollary 3.7) requires that the fourth moment of the jump distribution is finite, whereas Theorem 5 imposes no conditions on the fourth moment of F_n (for any $n\ge 1$).

4. In Khoshnevisan (1993, corollary 3.7), we get that λ_n grows linearly in n that implies condition (I), but obviously condition (I) might be satisfied in other asymptotic regimes.

5. In Khoshnevisan (1993 corollary 3.7), we get that ν_n and σ_n remain fixed (in n), and hence, due to the linear growth of λ_n, condition (II) is satisfied. Once again, obviously it could be satisfied in other asymptotic regimes as well.

Another result (Pang and Zheng 2017, theorem 1.1) is about a weak convergence in $\mathcal{D}[0,\infty )$ equipped with the Skorohod topology of a sequence of modulated compound Poisson processes. When all the processes in this sequence are compound Poisson processes (i.e., when the modulating Markov chains in the background are all degenerate ones), then Pang and Zheng (2017, assumption 1) is reduced to

1. Linear growth of the sequence λ_n as $n\to \infty$

2. The sequences (in n) of the means and standard deviations of F_n should both converge to constants

We conclude that there is a strong resemblance between the comparison of Theorem 5 with Pang and Zheng (2017, theorem 1.1) and the comparison of Theorem 5 with Khoshnevisan (1993, corollary 3.7).

Another strand of literature regards the properties of a sequence of compound Poisson processes that weakly converges to a limiting process (Sarkar and Sen 2005, Lambert et al. 2013, Lambert and Simatos 2015). This literature predominantly focuses on necessary conditions for weak convergence of such sequences, whereas Theorem 5 presents sufficient conditions.

7. When v Is a Random Variable

In this part, we revisit some results of the previous sections in the situation that v is a nonnegative random variable that is independent from the arrival process and the service requirements of the customers. The motivation for this extension of the existing framework lies in the fact that if v has the stationary distribution of an M/G/1 queue with an arrival rate λ and a service distribution $B(·)$, then we recover the setup of Haviv and Ritov (1998). For simplicity of notation, denote the conditional expectation (respectively, covariance) given v by ${\mathbb{E}}_v$ (respectively, ${\text{Cov}}_v$).

7.1. Expressions for Moments

To begin with, it is immediate that the decompositions of Section 3 remain true when the initial workload v is a general random variable. Similarly, Theorem 4 may be phrased in the extended setup. This is because for every bounded uniformly continuous functional f, we may apply the law of total expectation and then apply the dominated convergence theorem with Theorem 4 to deduce the needed result (Pollard 2012, corollary IV.9).

A similar approach may be applied to derive the moments of the externalities process. For example, for every $x\ge 0$,

Furthermore, for every $x_1,x_2\ge 0$ deduce that

and once $\mathbb{E}{v}^2<\infty$, we also get

Thus, the law of total covariance yields that

In particular, when $x_1=x$ and $x_2=0$, the following variance is obtained:

Remark 11.

Equations (69) and (70) imply that the correlation is invariant to the arrival rate and the service distribution if and only if $\text{Var}(v)=0$ (or equivalently, when v equals a constant with a probability of one).

For higher moments, it is possible to differentiate the LST formula, as given in the next corollary. Just like in Section 4, we do not include these computations here. The proof follows from conditioning and de-conditioning on v with the result of Theorem 3.

Corollary 3.

Let $k\ge 1$ and $\alpha \equiv ({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k),x\equiv (x_1,x_2,\dots ,x_k)\in {(0,\infty )}^k$. In addition, denote the LST of v by

$$\tilde{v}(t)\equiv \mathbb{E}\hspace{0.17em}{e}^{-tv},\hspace{0.17em}\hspace{0.17em}t>0,$$(71)

and consider the notation of Theorem 3. Then,

$$\begin{array}{ll}\mathbb{E}\exp \left\{-{\displaystyle \sum _{l=1}^k{\alpha }_l}{E}_v\left({\displaystyle \sum _{i=1}^l{x}_i}\right)\right\}\hfill & =\tilde{v}\left\{\lambda \left[1-\tilde{N}(w(x,\alpha ))\right]\right\}\hfill \\ \hfill & ·{\displaystyle \prod _{l=1}^k{\displaystyle {\int }_0^1\exp }}\left\{\lambda x_l\left[\tilde{N}(s_l(x,\alpha ,u))-1\right]\right\}\text{d}u.\hfill \end{array}$$(72)

7.2. Comparison with Existing Literature

Haviv and Ritov (1998) considered the special case when v is distributed according to the stationary distribution of the corresponding M/G/1 queue with an arrival rate λ and a service distribution $B(·)$. In this case, the expected value of v is given by

Observe that an insertion of these formulae into (66) provides exactly the same expression as in Haviv and Ritov (1998, equation (7)). Thus, in that sense, the formulae in this section may be considered as a natural generalization of this theorem, as in our framework v can have any distribution. Importantly, the proof in the current work stems from other considerations than those that appeared in the original proof of Haviv and Ritov (1998). Moreover, Corollary 3 might be applied for the special case of v that is distributed according to the stationary distribution of the corresponding M/G/1 system. This is a systematic approach to compute all externality moments in the model of Haviv and Ritov (1998).

8. Discussion and Open Problems

The main contributions of this work lie in the introduction of the notion of the externalities process and in the derivation of various of its properties in the case of an FCFS M/G/1 queue. The rest of this section includes a set of open problems, related to the research presented in this paper.

1. The current analysis is sensitive to the service discipline in that it is FCFS specific. Thus, it might be interesting to analyze the externalities process that corresponds to other service disciplines (e.g., preemptive ones) and examine the differences with respect to the results of the present paper. A particularly intriguing question concerns the characterization of the set of service disciplines for which the externalities process is convex.

2. One could think about the externalities processes of more complex queues, for example, G/G/1 and M_t/G/1. It is anticipated that in such cases the analysis is considerably more involved.

3. Consider the following natural multiserver version of the externalities process. Assume that there are k servers and a Poisson arrival process of customers, where the service demands of the customers constitute a sequence of i.i.d. k-dimensional nonnegative random vectors that are independent from the arrival process. This defines k coupled FCFS M/G/1 queues. Then, define a k-dimensional process such that its ith ($1\le i\le k$) coordinate is the externalities process that is associated with the ith queue. Also, in this setup, one would like to describe the externalities process. A specific natural question is: Are there nontrivial assumptions on the k-dimensional service distributions under which we get an asymptotic independence of the externalities processes?

4. The Lévy-driven queue, as analyzed in Dȩbicki and Mandjes (2015), forms a class of storage models that can be seen as a natural generalization of the classic FCFS M/G/1 queue. A first question is as follows: How should the externalities process be defined for such Lévy queues? In particular, it is interesting to analyze whether there is a definition for which the results of the current work may be generalized relying on the machinery developed for Lévy processes.

9. Proofs

9.1. Proofs for Section 2

9.1.1. Proof of Proposition 2.

Define a function

and observe that for each $l\ge 1$, the chain rule implies that

In particular, when x = 1, we get that $f^{(l)}(1)={\lambda }^l{\mu }_l$. As a result, according to the Faá di Bruno’s formula, for each $k\ge 1$,

Thus, observe that differentiating n times (at zero) for both sides of (9) with the general Leibniz rule yields

Notice that η_n appears in the right-hand side only in the term

This immediately yields the required recursive formula. □

9.1.2. Proof of Corollary 1.

Inserting n = 1 into (12) immediately yields that ${\eta }_1=1/(1-\rho )$. In addition,

Thus, according to (12),

In a similar fashion, we get that

9.1.3. Proof of Proposition 3.

$N(1)=b(\lambda )$ follows by differentiating both sides of (14) at zero. Now, consider some $s\ge 2$, then the general Leibniz rule and the Faá di Bruno’s formula (recall $f(·)$, defined in (74)) yield

9.2. Proofs for Section 3

The proofs of Corollary 2 and Theorem 2 follow directly from the material presented in Section 3. Thus, we are now providing only the proof of Theorem 1.

9.2.1. Proof of Theorem 1.

Observe that by definition of $\xi (x)$, for each $m\ge 1$ and y > 0,

As a result, for every x > 0 we have that

With this identity at our disposal, the required result is a consequence of (18). □

9.3. Proofs of Section 4

9.3.1. Proof of Corollary 3.

With the notations that have been used in Theorem 2, observe that (28) can be rephrased as follows:

Thus, we obtain that

Given $\mathcal{U}$, the sequences $\{N_{m,l}:m\ge 1\},\hspace{0.17em}1\le l\le k+1$ are independent. As a consequence, the result follows by conditioning and de-conditioning on $\mathcal{U}$ with an application of the LST formula of a compound Poisson distribution. □

9.4. Proofs of Section 6

Because the proof of Theorem 4 includes an application of Theorem 5, we start by providing the proof of Theorem 5.

9.4.1. Proof of Theorem 5.

The following well-known bound is useful in the proof of Theorem 5:

With this bound in hands, we prove convergence of the finite-dimensional distributions as stated in the next lemma. For the proof, it is convenient to denote

Lemma 1.

The conditions of Theorem 5 imply that for every $1\le d<\infty$ and $0\le x_1<x_2<\cdots <x_d<\infty$,

$$\frac{1}{\sqrt{{\lambda }_n{\mu }_{2,n}}}\left[J_n(x_1),J_n(x_2),\dots ,J_n(x_d)\right]\stackrel{d}{\to }\mathcal{N}(0,{\mathrm{\Sigma }}_x)\hspace{0.17em}\hspace{0.17em}as\hspace{0.17em}\hspace{0.17em}n\to \infty ,$$(89)

where Σ is a covariance matrix such that ${\mathrm{\Sigma }}_{ij}\equiv x_i\wedge x_j$ for every $1\le i,j\le d$.

Proof.

To begin with, consider the special case d = 1 and assume that for each $n\ge 1$, W_n is a random variable which is distributed according to $F_n(·)$. Fix some $x\ge 0$ and for each $n\ge 1$ denote

$${\varphi }_{F_n}(y)\equiv \mathbb{E}{e}^{{\mathit{\text{iyW}}}_n}={\displaystyle {\int }_{-\infty }^{\infty }{e}^{\mathit{\text{iyt}}}}\text{d}{F}_n(t),\hspace{0.17em}\hspace{0.17em}y\in \mathbb{R}.$$(90)

In particular, (87) implies that for every $y\in \mathbb{R}$,

$$\begin{array}{ll}\left|{\varphi }_{F_n}(y)-1-iy{\theta }_n+\frac{y^2{\sigma }_n}{2}\right|\hfill & =\left|\mathbb{E}\left(e^{{\mathit{\text{iyW}}}_n}-1-{\mathit{\text{iyW}}}_n+\frac{y^2{W}_n^2}{2}\right)\right|\hfill \\ \hfill & \le \mathbb{E}\left|e^{{\mathit{\text{iyW}}}_n}-1-{\mathit{\text{iyW}}}_n+\frac{y^2{W}_n^2}{2}\right|\hfill \\ \hfill & \le \frac{|y{|}^3{\nu }_n}{6}.\hfill \end{array}$$(91)

Thus, for a fixed $y\in \mathbb{R}$ and every $n\ge 1$, we have

$$\begin{array}{ll}\hfill & \left|{\lambda }_n{x}_1\left[{\varphi }_{F_n}\left(\frac{y}{\sqrt{{\lambda }_n{\sigma }_n}}\right)-1\right]-i\frac{y{\varrho }_n{x}_1}{\sqrt{{\lambda }_n{\sigma }_n}}-\left(-\frac{y^2{x}_1}{2}\right)\right|\hfill \\ \hfill & ={\lambda }_n{x}_1\left|{\varphi }_{F_n}\left(\frac{y}{\sqrt{{\lambda }_n{\sigma }_n}}\right)-1-\left(i\frac{y{\theta }_n}{\sqrt{{\lambda }_n{\sigma }_n}}-\frac{y^2}{2{\lambda }_n}\right)\right|\le \frac{|y{|}^3{x}_1{\nu }_n}{6\sqrt{{\lambda }_n{\sigma }_n^3}},\hfill \end{array}$$(92)

and condition (II) implies that the upper bound in (92) converges to zero as $n\to \infty$. As a result, deduce that for every $y\in \mathbb{R}$,

$$\begin{array}{ll}\underset{n\to \infty }{\lim }\mathbb{E}{e}^{iy\frac{J_n(x)}{\sqrt{{\lambda }_n{\sigma }_n}}}\hfill & =\underset{n\to \infty }{\lim }\exp \left\{{\lambda }_n{x}_1\left[{\varphi }_{F_n}\left(\frac{y}{\sqrt{{\lambda }_n{\sigma }_n}}\right)-1\right]-i\frac{y{\varrho }_n{x}_1}{\sqrt{{\lambda }_n{\sigma }_n}}\right\}\hfill \\ \hfill & =\exp \left\{-\frac{y^2{x}_1}{2}\right\},\hfill \end{array}$$(93)

and hence the result follows (for d = 1) by Levy’s continuity theorem.

The next stage is to extend this result for d > 1. To this end, for each $n\ge 1$, define d i.i.d. stochastic processes

$$J_n^{(1)}(·),J_n^{(2)}(·),\dots ,J_n^{(d)}(·),$$

which have the same distribution as $J_n(·)$. Because $J_n(·)$ has stationary independent increments, then for each $n\ge 1$, we get

$$\frac{1}{\sqrt{{\lambda }_n{\sigma }_n}}\left[J_n(x_1),J_n(x_2),\dots ,J_n(x_d)\right]$$(94)

is distributed like

$$\left[\frac{J_n^{(1)}(x_1)}{\sqrt{{\lambda }_n{\sigma }_n}},\frac{J_n^{(2)}(x_2-x_1)}{\sqrt{{\lambda }_n{\sigma }_n}},\dots ,\frac{J_n^{(d)}(x_d-x_{d-1})}{\sqrt{{\lambda }_n{\sigma }_n}}\right]\mathrm{\Gamma },$$(95)

where $\mathrm{\Gamma }=[{\gamma }_{ij}]$ such that ${\gamma }_{ij}={\mathbf{1}}_{\{i\le j\}}$ for every $1\le i,j\le d$. The vector in (95) consists of d independent coordinates. Thus, according to the special case d = 1, we deduce that

$$\left[\frac{J_n^{(1)}(x_1)}{\sqrt{{\lambda }_n{\sigma }_n}},\frac{J_n^{(2)}(x_2-x_1)}{\sqrt{{\lambda }_n{\sigma }_n}},\dots ,\frac{J_n^{(d)}(x_d-x_{d-1})}{\sqrt{{\lambda }_n{\sigma }_n}}\right]$$(96)

converges in distribution to

$${\mathcal{N}}_d\left[\mathbf{0},\hspace{0.17em}\text{diag}\left(x_1,x_2-x_1,\dots ,x_d-x_{d-1}\right)\right]$$(97)

as $n\to \infty$. Finally, it is readily verified that

$${\mathrm{\Gamma }}^{\prime }\text{diag}\left(x_1,x_2-x_1,\dots ,x_d-x_{d-1}\right)\mathrm{\Gamma }=\mathrm{\Sigma },$$(98)

from which the result follows. □

Now, we are ready to prove the next lemma that is about validity of a tightness condition.

Lemma 2.

For every $\delta >0$, there exist $n_0\ge 1$ and $\alpha ,\beta >0$ such that

$$\mathbb{P}\left\{\left|\frac{J_n(t)-J_n(s)}{\sqrt{{\lambda }_n{\sigma }_n}}\right|\le \delta \right\}\ge \beta ,\hspace{0.17em}\hspace{0.17em}\forall n\ge n_0\hspace{0.17em} \mathit{\text{and}} \hspace{0.17em}t,s\ge 0\hspace{0.17em}s.t.\hspace{0.17em}\hspace{0.17em}|t-s|<\alpha .$$(99)

Proof.

Fix some $\delta >0$ and take some $0\le s<t$. Notice that $J_n(·)$ is a process with stationary increments, and $J_n(t-s)$ has a continuous distribution function. Therefore, Lemma 1 yields that

$$\begin{array}{ll}\mathbb{P}\left\{\left|\frac{J_n(t)-J_n(s)}{\sqrt{{\lambda }_n{\sigma }_n}}\right|\le \delta \right\}\hfill & =\mathbb{P}\left\{\left|\frac{J_n(t-s)}{\sqrt{{\lambda }_n{\sigma }_n}}\right|\le \delta \right\}\hfill \\ \hfill & =\mathbb{P}\left\{\frac{J_n(t-s)}{\sqrt{{\lambda }_n{\sigma }_n}}\le \delta \right\}-\mathbb{P}\left\{\frac{J_n(t-s)}{\sqrt{{\lambda }_n{\sigma }_n}}\le -\delta \right\}\hfill \\ \hfill & \stackrel{n\to \infty }{\to }\mathbb{P}\left\{\mathcal{N}(0,t-s)\le \delta \right\}-\mathbb{P}\left\{\mathcal{N}(0,t-s)\le -\delta \right\}\hfill \\ \hfill & =\mathbb{P}\left\{|\mathcal{N}(0,t-s)|<\delta \right\}.\hfill \end{array}$$(100)

Clearly, the probability in the right-hand side of (100) can be made sufficiently close to one by taking s and t, which are close enough to each other, and hence the result follows. □

Finally, for each $n\ge 1,\hspace{0.17em}{J}_n(·)$ has independent increments. Thus, using Lemmas 1 and 2, for each $k=1,2,\dots$, Pollard (2012, theorem V.19) gives the required convergence on $\mathcal{D}[0,k]$ equipped with the uniform metric. Finally, to complete the proof of Theorem 5, it now suffices to apply Pollard (2012, theorem V.23). □

9.4.2. Proof of Theorem 4.

Let k > 0 and observe that condition (i), condition (ii), and condition (iii) allow us to apply Theorem 5 with the sequence $\{S_n(·):n\ge 1\}$ to deduce that

when the convergence is in $\mathcal{D}[0,k+v]$ equipped with the uniform metric. Because the limit process is concentrated on $C[0,k+v]$, according to the representation theorem (Pollard 2012, theorem VI.13), there is a probability space with a random processessuch thatwith a probability of one. In particular,

Because the right-hand side converges to zero with a probability of one, deduce that the process

admits weak convergence in $\mathcal{D}[0,k]$ equipped with the uniform metric to the process $x\mapsto {\int }_0^x\tilde{W}(v+y)\text{d}y$. Especially, because k is an arbitrary positive number and the limiting process is concentrated in $C[0,\infty )$, then this convergence can be extended to $\mathcal{D}[0,\infty )$ via Pollard (2012, theorem V.23). Thus, the claim of Theorem 4 follows. □

9.4.3. Proof of Proposition 4.

Inserting the expressions that appear in the statement of Corollary 1 yields that, for each $n\ge 1$,

with

In addition, Jensen’s inequality yields that

implies that

Therefore, the assumption

implies that the nominator of (104) is $\mathcal{O}(1)$ as $n\to \infty$. In addition, under the assumption (108), the denominator of (104) is bounded from below by $(1-{\rho }_n)\sqrt{{\lambda }_n}$, which tends to $\infty$ as $n\to \infty$. The proof of the first statement follows immediately from these results.

Because of the first statement, to prove the second statement, it is enough to consider the case when ${\rho }_n\uparrow 1$ as $n\to \infty$. Under the assumption

the denominator of (104) isas $n\to \infty$. In addition, because of (106) and (107), the nominator of (104) is $\mathcal{O}({(1-{\rho }_n)}^{-4})$ as $n\to \infty$. Combining these results with the assumption that ${\lambda }_n(1-{\rho }_n)\to \infty$ as $n\to \infty$ completes the proof. □