# Overlap Times in the Infinite Server Queue

Sergio Palomo
Systems Engineering
Cornell University
<EMAIL_ADDRESS>Jamol Pender 111Corresponding Author
School of Operations Research and Information Engineering
Cornell University
<EMAIL_ADDRESS>
###### Abstract

Imagine, you enter a grocery store to buy food. How many people do you overlap
with in this store? How much time do you overlap with each person in the
store? In this paper, we answer these questions by studying the overlap times
between customers in the infinite server queue. We compute in closed form the
steady state distribution of the overlap time between a pair of customers and
the distribution of the number of customers that an arriving customer will
overlap with. Finally, we define a residual process that counts the number of
overlapping customers that overlap in the queue for at least $\delta$ time
units and compute its mean, variance, and distribution in the exponential
service setting.

##  1 Introduction

Since the beginning of the COVID-19 pandemic, much work has focused on using
deterministic compartmentalized style models to estimate the infection rate
and dynamics of the spread, see for example Dandekar et al. [2], Nguemdjo et
al. [19], Kaplan [15]. However, we know that stochastic effects can play an
important role in determining the spread, see for example Drakopoulos et al.
[9], Palomo et al. [21], Pang and Pardoux [22], Forien et al. [12], Moein et
al. [18]. As shoppers crowd a store to stock up on water or large amounts of
non-perishable items it is inevitable that the virus would spread. To combat
the spread of the virus, many service facilities and systems have installed
new air filters, transparent barriers and have asked that patrons wear facial
masks. Moreover, these service systems also have implemented various forms of
social/physical distancing in order to minimize close proximity of one
customer to another Bove and Benoit [1].

However, there are some places where people work or shop that limiting
distance is not feasible. In this case, we really care about how much
customers overlap with one another. Recently there has been new work by Kang
et al. [14] and Palomo and Pender [20] that explores how one can calculate the
overlap times of customers in single server queues. More specifically, Kang et
al. [14] shows how to use the overlaps to compute a new $R_{0}$ value for
understanding infection rates in compartmentalized epidemic models and Palomo
and Pender [20] proves that the overlap distribution is exponential for the
M/M/1 and shows via simulation that a similar result holds for the non-
Markovian setting as well. Our analysis is important because it can
demonstrate, exactly, how much overlap occurs and can provide distributional
information or prediction intervals for possible overlap. Moreover, it can be
used as a tool to prevent large overlaps and our analysis can be used as a
design tool construct appropriate overlap by restricting the arrival rate or
service distributions.

In this paper, we extend the overlap time analysis to the setting of infinite
server queue. At first glance the infinite server queue analysis might not
seem relevant, however, for service entities such as grocery stores, outlets,
restaurants, and retail shops, an infinite server queue is quite relevant as
there is not much waiting or the waiting to check out may be insignificant
when compared to the shopping time. Moreover, the overlap times in the
infinite server queue serve as a lower bound for the overlap times that a
customer might experience in systems where there is significant waiting or in
a multi-server setting. What also makes the infinite server queue important is
that we are able to derive explicit formulas for the overlap distribution and
residual overlap distributions as well as the number of people that a customer
will overlap with during the duration of their service experience. In what
follows we describe the contributions of our work and how the rest of the
paper is organized.

###  1.1 Contributions of the Paper

  * •

We derive the steady state distribution for the overlap time for customers
that are exactly $k$ spaces apart.

  * •

We derive the distribution of the number of customers that any customer
overlaps with during their service.

  * •

We also construct a residual overlap process and compute its mean, variance
and distribution.

  * •

We use simulation to verify our results.

###  1.2 Organization of Paper

In Section 2, we describe the stochastic model that we will use in this work.
We derive an equation for describing the overlap times for customers in the
infinite server queue. We use this equation to compute the steady state
distribution of the overlap time of customers that are $k$ spaces apart. In
Section 3, we compute the mean and variance of the number of people a customer
will overlap with during their time in the queue. We also compute a residual
version where a customer must overlap at least $\delta$ units of time and
compute its mean and variance as well. Finally in Section 5, we provide a
conclusion and some future research directions.

##  2 Infinite Server Overlap Times

In this section, we study the infinite server queue with the intention of
understanding how much time do adjacent customers spend in the system
together. A similar type of analysis has been completed Kang et al. [14],
Palomo and Pender [20]. Before we get into studying the overlap times, we
review some concepts and results for the $M_{t}/G/\infty$ queueing model as
this will be very helpful in the analysis that follows.

###  2.1 Review of the $M_{t}/G/\infty$ Queue

In this section, we review the $M_{t}/G/\infty$ queueing model. The
$M_{t}/G/\infty$ queue $Q^{\infty}(t)$ has a Poisson distribution with time
varying mean $q^{\infty}(t)$. As observed in Eick et al. [10, 11],
$q^{\infty}(t)$ has the following integral representation

$\displaystyle q^{\infty}(t)$ $\displaystyle=$ $\displaystyle
E[Q^{\infty}(t)]$ (1) $\displaystyle=$
$\displaystyle\int^{t}_{-\infty}\overline{G}(t-u)\lambda(u)du$ (2)
$\displaystyle=$ $\displaystyle E\left[\int^{t}_{t-S}\lambda(u)du\right]$ (3)
$\displaystyle=$ $\displaystyle E[\lambda(t-S_{e})]\cdot E[S]$ (4)

where $\lambda(u)$ is the time varying arrival rate and $S$ represents a
service time with distribution G, $\overline{G}=1-G(t)=\mathbb{P}(S>t)$, and
$S_{e}$ is a random variable with distribution that follows the stationary
excess of residual-lifetime cdf $G_{e}$, defined by

$\displaystyle G_{e}(t)$ $\displaystyle\equiv$
$\displaystyle\mathbb{P}(S_{e}<t)=\frac{1}{E[S]}\int^{t}_{0}\overline{G}(u)du=\frac{1}{E[S]}\int^{t}_{0}\mathbb{P}(S>u)du,\
\ \ t\geq 0.$ (5)

We find it also useful to compute the mean of the $M/M/\infty$ queue using the
solution of a linear differential equation.

######  Lemma 2.1.

Let $q(t)$ be the solution to the following differential equation

$\raisebox{-0.4pt}{$\stackrel{{\scriptstyle\bullet}}{{q}}$}=\lambda-\mu q(t)$
(6)

where $q(0)=q_{0}$. Then the solution for any value of $t$ is given by

$q(t)=q_{0}e^{-\mu t}+\frac{\lambda}{\mu}\left(1-e^{-\mu t}\right).$ (7)

###### Proof.

This follows from standard results on ordinary differential equations. ∎

###  2.2 Review of the Incomplete Gamma Function

Before we begin, we would like to define a few functions that will be useful
in our future analysis. First we will recall the integral definition of the
gamma function i.e.

$\displaystyle\Gamma(a)$ $\displaystyle=$
$\displaystyle\int^{\infty}_{0}t^{a-1}e^{-t}dt\quad\mathrm{for}\ a>0.$

One can also partition the gamma function integral at a point $x\geq 0$ to
obtain the lower and upper incomplete gamma functions respectively as

$\displaystyle\gamma(a,x)$ $\displaystyle=$
$\displaystyle\int^{x}_{0}t^{a-1}e^{-t}dt,$ $\displaystyle\Gamma(a,x)$
$\displaystyle=$
$\displaystyle\int^{\infty}_{x}t^{a-1}e^{-t}dt=e^{-x}\int^{\infty}_{x}(t+x)^{a-1}e^{-t}dt.$

Moreover, we know that

$\displaystyle\frac{1}{c^{a}}\gamma(a,cx)$ $\displaystyle=$
$\displaystyle\int^{x}_{0}t^{a-1}e^{-ct}dt,$
$\displaystyle\frac{1}{c^{a}}\Gamma(a,cx)$ $\displaystyle=$
$\displaystyle\int^{\infty}_{x}t^{a-1}e^{-ct}dt.$

The lower and upper incomplete gamma functions will be used extensively in
what follows.

###  2.3 Overlap Time Distribution

In this section, we consider the GI/GI/$\infty$ queue. In this queue we let
$A_{i}$ be the arrival time of the $i^{th}$ customer and we define the inter-
arrival time between the $i^{th}$ and $(i+1)^{th}$ customers to be
$A_{i+1}-A_{i}$, which are i.i.d random variables with cumulative distribution
function (cdf) $F(x)$. We also assume that $S_{i}$ is the service time of the
$i^{th}$ customer and the service times are i.i.d with cdf $G(x)$. In the
infinite server queue by definition, no customer will wait. Thus, the
departure time for the $n^{th}$ customer is given by the following equation

$\displaystyle D_{n}$ $\displaystyle=$ $\displaystyle S_{n}+A_{n}.$ (8)

Now that we understand the arrival and departure time for each customer, we
can now construct an equation for the overlap time between adjacent customers.
The overlap time between the $n^{th}$ and $(n+k)^{th}$ customers is given by

$\displaystyle O_{n,n+k}$ $\displaystyle=$
$\displaystyle\left(\min(D_{n},D_{n+k})-A_{n+k}\right)^{+}$ (9)
$\displaystyle=$
$\displaystyle\left(\min(A_{n}+S_{n},A_{n+k}+S_{n+k})-A_{n+k}\right)^{+}$ (10)
$\displaystyle=$ $\displaystyle\left((D_{n}-A_{n+k})^{+}\wedge S_{n+k}\right)$
(11) $\displaystyle=$ $\displaystyle\left((S_{n}+A_{n}-A_{n+k})^{+}\wedge
S_{n+k}\right)$ (12) $\displaystyle=$
$\displaystyle\left((S_{n}-\left(A_{n+k}-A_{n}\right))^{+}\wedge
S_{n+k}\right).$ (13)

It is important to observe that the overlap time between the $n^{th}$ and
$(n+k)^{th}$ customers can be decomposed into two parts. The first part (the
left term in the minimum) is the time that the $n^{th}$ customer overlaps with
the $(n+k)^{th}$ customer given that the $n^{th}$ customer stays longer. The
second part is the service time of the $(n+k)^{th}$ customer if the service
time of the $(n+k)^{th}$ stay is shorter than the $n^{th}$ customers service
time minus the inter-arrival time gap. We will leverage this representation
when considering the steady state overlap time and the fact that all of the
random variables are independent from one another. However, before we derive
the steady state distribution of the overlap time for the $M/M/\infty$ queue,
we find it useful to derive an important lemma about the distribution of an
exponential random variable minus an Erlang random variable. This lemma is
given below in Lemma 2.2.

######  Lemma 2.2.

Let $X$ be an Exp($\mu$) random variable and $Y$ be an Erlang$(k,\lambda)$
random variable. Then, the probability density function of $Z=X-Y$ is equal to

$f_{Z}(z)=\begin{cases}1-\frac{\mu\lambda^{k}}{(\lambda+\mu)^{k}}e^{-\lambda
z}\sum^{k-1}_{j=0}\frac{[(\lambda+\mu)z]^{j}}{j!},\quad\mathrm{for}\ z\leq
0\\\ \frac{\mu\lambda^{k}}{(\lambda+\mu)^{k}}e^{-\mu z}\quad\mathrm{for}\
z>0\end{cases}$ (14)

###### Proof.

See Palomo et al. [21]. ∎

######  Theorem 2.3.

Let $O_{k}$ be the steady state distribution of $O_{n,n+k}$ in the
$M/M/\infty$ queue, then the tail distribution of
$O_{k}=\lim_{n\to\infty}O_{n,n+k}$ is given by

$\displaystyle\mathbb{P}\left(O_{k}>t\right)$ $\displaystyle=$
$\displaystyle\left(\frac{\lambda}{\lambda+\mu}\right)^{k}e^{-2\mu t}$ (15)

and

$\displaystyle\mathbb{P}\left(O_{k}=0\right)$ $\displaystyle=$ $\displaystyle
1-\left(\frac{\lambda}{\lambda+\mu}\right)^{k}.$ (16)

###### Proof.

First, we need to decompose the overlap probability into two probabilities by
using a property of the minimum of two independent random variables i.e.

$\displaystyle\mathbb{P}\left(O_{k}>t\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\left((\mathcal{S}-\mathcal{A}_{k})^{+}\wedge\tilde{\mathcal{S}}\right)>t\right)$
(17) $\displaystyle=$
$\displaystyle\mathbb{P}\left(\left((\mathcal{S}-\mathcal{A}_{k})^{+}\right)>t\right)\cdot\mathbb{P}\left(\tilde{\mathcal{S}}>t\right)$
(18) $\displaystyle=$
$\displaystyle\mathbb{P}\left(\left((\mathcal{S}-\mathcal{A}_{k})^{+}\right)>t\right)\cdot
e^{-\mu t}.$ (19)

Now it suffices to compute the remaining probability expression. We can do
this by exploiting Proposition 2.2 as follows.

$\displaystyle\mathbb{P}\left(O_{k}>t\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left((\mathcal{S}-\mathcal{A}_{k})^{+}>t\right)\cdot
e^{-\mu t}$ (20) $\displaystyle=$
$\displaystyle\mathbb{P}\left(\mathcal{S}-\mathcal{A}_{k}>t\right)\cdot
e^{-\mu t}$ (21) $\displaystyle=$
$\displaystyle\mathbb{P}\left(\mathcal{S}>t+\mathcal{A}_{k}\right)\cdot
e^{-\mu t}$ (22) $\displaystyle=$
$\displaystyle\left(\int^{\infty}_{t}\frac{\mu\lambda^{k}}{(\lambda+\mu)^{k}}e^{-\mu
z}dz\right)\cdot e^{-\mu t}$ (23) $\displaystyle=$
$\displaystyle\left(\frac{\mu\lambda^{k}}{(\lambda+\mu)^{k}}\int^{\infty}_{t}e^{-\mu
z}dz\right)\cdot e^{-\mu t}$ (24) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{(\lambda+\mu)^{k}}e^{-\mu t}\cdot e^{-\mu t}$
(25) $\displaystyle=$
$\displaystyle\left(\frac{\lambda}{\lambda+\mu}\right)^{k}e^{-2\mu t}.$ (26)

This completes the proof. ∎

Figure 1: Histograms for the Overlap Times Exponential Distributions
$(\lambda=.5,\mu=1)$. Upper Left (k=1), Upper Right (k=2), Lower Left (k=3),
Lower Right (k=4).

Figure 2: Histograms for the Overlap Times Exponential Distributions
$(\lambda=.5,\mu=1)$. Upper Left (k=1), Upper Right (k=2), Lower Left (k=3),
Lower Right (k=4).

In Figure 1, we plot the histograms of the overlap times of customers that
have distance $k=\\{1,2,3,4\\}$ in the $M/M/\infty$ queue. We find that the
conditional distribution that the overlap time is greater than zero is an
exponential distribution with rate $2\mu$. However, why does the tail decay
with rate $2\mu$? One observation is that in order for the overlap time to be
large, it must be that both service times are also large. Since they each
decay at rate $\mu$, then both being large is given by $2\mu$. Note that this
is different from the single server setting in Palomo and Pender [20] where
the decay of overlap times is equal to $\mu$. This is because the $(n+k)^{th}$
customer cannot leave until the $n^{th}$ customer has departed. Thus, the
decay only depends on the service time of the $n^{th}$ customer being large.

To see how well our theoretical analysis matches with our simulation
experiments, using maximum likelihood estimation, we fit an exponential
distribution to the overlap times in Figure 2 showing that the exponential
distribution is accurate as predicted by our theoretical analysis. What is
also apparent from Figure 2 is that the number of overlap times decreases as
we increase the distance $k$. This is consistent with the geometric-like decay
of the coefficient in front of the exponential distribution given in Equation
15. Although we mostly have analyzed the $GI/GI/\infty$ queue in the context
of Poisson arrivals, we can also find the steady state overlap time
distribution for renewal arrivals when the service distribution is
deterministic. Theorem 2.4 below provides a proof of this result.

######  Theorem 2.4.

The steady state distribution of $O_{k}$ in the $GI/D/\infty$ queue is given
by

$\displaystyle\mathbb{P}\left(O_{k}>t\right)$ $\displaystyle=$ $\displaystyle
F^{(k)}\left((\Delta-t)^{+}\right).$ (27)

###### Proof.

$\displaystyle\mathbb{P}\left(O_{k}>t\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left((\Delta-\mathcal{A}_{k})^{+}>t\right)$ (28)
$\displaystyle=$
$\displaystyle\mathbb{P}\left(\Delta-\mathcal{A}_{k}>t\right)$ (29)
$\displaystyle=$
$\displaystyle\mathbb{P}\left(\mathcal{A}_{k}<\Delta-t\right)$ (30)
$\displaystyle=$ $\displaystyle F^{(k)}\left((\Delta-t)^{+}\right)$ (31)

where $F^{(k)}(x)$ is the $k$-fold convolution of distribution function
$F(x)$. ∎

Figure 3: CDF for the Overlap Times Deterministic Service
$(\lambda=.5,\mu=1)$. Upper Left (k=1), Upper Right (k=2), Lower Left (k=3),
Lower Right (k=4).

######  Corollary 2.5.

In the $Gamma(\alpha,\lambda)/D/\infty$ queue, the steady state overlap
distribution is given by

$\displaystyle\mathbb{P}\left(O_{k}>t\right)$ $\displaystyle=$
$\displaystyle\frac{\gamma(k\alpha,\lambda(\Delta-t)^{+})}{\Gamma(k\alpha)}.$
(32)

In Figure 3, we plot the cumulative distribution function (cdf) of the overlap
times of the $M/D/\infty$ queue. We observe that unlike the exponential
service setting, the distribution changes significantly as we change the
adjacency $k$. We find in all of the plots that the empirical distribution
matches almost perfectly to the theoretical analysis given in Equation 27. It
would be interesting to explore more distributions for the arrival and service
random variables and see if we can compute them in closed form. Suppose that
we let the arrival and service distribution be Gamma distributed, then the
resulting distribution can be described as a gamma difference distribution,
see for example Klar [16]. However, beyond this, it seems quite difficult to
get results for other distributions in closed form.

##  3 Computing the Number of Overlaps

In addition to knowing how much time adjacent customers will spend together in
a service system, it is important to also know how many customers one expects
to overlap with. In the context of epidemics, the more customers that one
actually overlaps with increases the chances that one might contract the
disease. In this section, we restrict our analysis to that of the
$M_{t}/G/\infty$ queue and leverage results from the $M_{t}/G/\infty$ queue in
Eick et al. [11] to compute the exact distribution of overlapping customers.
In what follows, we assume without loss of generality that all queues start
with zero customers. Under this assumption, we know that the queue
$M_{t}/G/\infty$ queue at time $t$ is given by the following expression

$\displaystyle Q^{\infty}(t)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{N^{(b)}(t)}\\{A_{j}<t<A_{j}+S_{j}\\}.$ (33)

Thus, the number of people in the system at the time of arrival of the
$k^{th}$ person is given by

$\displaystyle Q^{\infty}(A_{k}-)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{N^{(b)}(A_{k}-)}\\{A_{j}<A_{k}<A_{j}+S_{j}\\}.$ (34)

In order to compute the total number of overlapping customers, we also need to
calculate the number of people that arrive during the service time of the
$k^{th}$ customer as well. The number of customers that arrive during the
$k^{th}$ customer’s service time is equal to

$\displaystyle N^{(b)}(A_{k}+S_{k})-N^{(b)}(A_{k}).$ (35)

Adding the number of people upon arrival and the number that arrive during
service, we arrive at an expression for $T_{k}$, the total number of people
that the $k^{th}$ person will overlap with. Thus, $T_{k}$ is equal to

$\displaystyle T_{k}$ $\displaystyle=$ $\displaystyle
N^{(b)}(A_{k}+S_{k})-N^{(b)}(A_{k})+\sum_{j=1}^{N^{(b)}(A_{k})}\\{A_{j}<A_{k}<A_{j}+s_{j}\\}.$
(36)

It is important to note that the total number of overlapping customers for the
$k^{th}$ arrival can be only computed when the $k^{th}$ arrival departs the
queue and it is not known at the time of arrival. Thus, this representation
for the number of overlaps provides a methodology for computing the number of
overlaps for each customer via simulation. However, this representation is
customer centered and not time centered. In what follows, we provide a time
centered perspective of the number of overlaps.

If a person arrives at time $t$, then we define $O(t)$ as the number of people
that the arriving customer will overlap with. $O(t)$ has the following
expression

$\displaystyle O(t)$ $\displaystyle=$
$\displaystyle\underbrace{N^{(b)}(t+\mathcal{S})-N^{(b)}(t)}_{\text{\\# of
customer arrivals during
service}}+\underbrace{\sum_{j=1}^{N^{(b)}(t)}\\{A_{j}<t<A_{j}+S_{j}\\}}_{\text{\\#
of customers upon arrival}}$ (37) $\displaystyle=$
$\displaystyle\underbrace{N^{(b)}(t+\mathcal{S})-N^{(b)}(t)}_{\text{\\# of
customer arrivals during service}}+\underbrace{Q^{\infty}(t)}_{\text{queue
length at time t}}.$ (38)

It is important to note here that the number of overlapping customers $O(t)$
is not completely known at time $t$. It is only fully known after the service
of the customer that arrives at time $t$. However, we can use the expression
of $O(t)$ to compute the distribution of the number of customers that an
arrival will overlap with at time $t$. In this way, it is time centered as the
expression depends on time and not the specific number of the customer
arriving. In addition to knowing the exact number of customers an arrival at
time $t$ would overlap with or an exact sample path, we can also describe the
exact distribution of the number of customers that an arrival at time $t$
would overlap. One important ingredient to describing the exact distribution
is knowing that the number of customers upon arrival is independent from the
number of arrivals that arrive during service. We provide the exact
distribution in the following theorem.

######  Theorem 3.1.

The distribution of the number of overlapping customers in the
$M_{t}/G/\infty$ queue at time $t$ is equal to

$\displaystyle O(t)$ $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\mathcal{S}}_{t}\lambda(s)ds+\int^{t}_{0}\lambda(u)\overline{G}(t-u)du\right).$
(39)

Moreover, the transient state probabilities are given by the following
integral expression

$\displaystyle\mathbb{P}\left(O(t)=k\right)$ $\displaystyle=$
$\displaystyle\int^{\infty}_{0}e^{-(\Lambda(t,s)+q^{\infty}(t))}\frac{(\Lambda(t,s)+q^{\infty}(t))^{k}}{k!}dG(s)$
(40)

where $\Lambda(t,s)$ is defined as $\Lambda(t,s)=\int^{t+s}_{t}\lambda(u)du$.

###### Proof.

$\displaystyle O(t)$ $\displaystyle=$ $\displaystyle
N^{(b)}(t+\mathcal{S})-N^{(b)}(t)+Q^{\infty}(t)$ (41)
$\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\mathcal{S}}_{t}\lambda(u)du\right)+\text{Poisson}\left(q^{\infty}(t)\right)$
(42) $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\mathcal{S}}_{t}\lambda(u)du\right)+\text{Poisson}\left(\int^{t}_{0}\lambda(u)\overline{G}(t-u)du\right)$
(43) $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\mathcal{S}}_{t}\lambda(u)du+\int^{t}_{0}\lambda(u)\overline{G}(t-u)du\right).$
(44)

This completes the proof. ∎

###  3.1 Number of Arrivals During Service

It is important to remark that the distribution of the number of overlapping
customers is not necessarily Poisson unless the service distribution is given
by a discrete random variable. To see this, note that even in the constant
arrival rate case, an exponential service time yields a geometric random
variable. Moreover, a gamma distributed service time yields a negative
binomial random variable. In what follows, we calculate the number of arrivals
during service for several service time distributions that are common in
applied probability. We also find an expression in terms of an expectation for
any non-negative continuous random variable as well.

######  Proposition 3.2.

Let $\mathcal{S}$ be a Erlang$(\alpha,\mu)$ random variable, then the number
of customers that arrive during service has a negative binomial distribution
i.e.

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)={{k+\alpha-1}\choose{k}}(1-\rho)^{\alpha}\rho^{k}$
(45)

where $\rho=\frac{\lambda}{\mu+\lambda}$.

###### Proof.

Since $\mathcal{S}$ is Erlang$(\alpha,\mu)$ distributed, we can decompose it
into $\alpha$ i.i.d exponential random variables. Thus, it suffices to prove
the result and show the distribution is Geometric$\left(\rho\right)$. Thus, we
need to show that if $\mathcal{S}$ is Exp($\mu$), then

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)=(1-\rho)\rho^{k}.$
(46)

Thus, we have

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)$ $\displaystyle=$
$\displaystyle\int^{\infty}_{0}e^{-\lambda x}\frac{(\lambda x)^{k}}{k!}\mu
e^{-\mu x}dx$ (47) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}\mu}{k!}\int^{\infty}_{0}x^{k}e^{-(\lambda+\mu)x}dx$
(48) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}\mu}{(\lambda+\mu)k!}\int^{\infty}_{0}x^{k}\cdot(\lambda+\mu)e^{-(\lambda+\mu)x}dx$
(49) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}\mu}{(\lambda+\mu)k!}\frac{k!}{(\lambda+\mu)^{k}}$
(50) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}\mu}{(\lambda+\mu)^{k+1}}$ (51)
$\displaystyle=$
$\displaystyle\left(\frac{\lambda}{\lambda+\mu}\right)^{k}\cdot\left(\frac{\mu}{\lambda+\mu}\right)$
(52) $\displaystyle=$
$\displaystyle\left(\frac{\lambda}{\lambda+\mu}\right)^{k}\cdot\left(1-\frac{\lambda}{\lambda+\mu}\right)$
(53) $\displaystyle=$ $\displaystyle(1-\rho)\rho^{k}.$ (54)

This completes the proof. ∎

Figure 4: Total Overlap (Exponential), $(\lambda=10,\mu=1)$ (Top Left).
Overlap After Arrival (Exponential), $(\lambda=10,\mu=1)$ (Top Right).
Overlap Upon Arrival (Exponential), $(\lambda=10,\mu=1)$ (Bottom).

In Figure 4, we plot the distribution for the total number of overlaps, the
number of overlaps upon arrival and the number overlaps during service. We see
that the distribution of the overlaps upon arrival is still Poisson and the
number of overlaps during service is geometric as predicted by our theoretical
results. The total number is a the convolution of the two as well. Thus, we
have a good sense of how many customers might overlap with during their
service experience.

######  Proposition 3.3.

Let $\mathcal{S}$ be a Uniform$(a,b)$ random variable, then the number of
customers that arrive during service has the following distribution

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)$ $\displaystyle=$
$\displaystyle\frac{\gamma(k+1,\lambda b)-\gamma(k+1,\lambda
a)}{\lambda(b-a)k!}.$ (55)

###### Proof.

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)$ $\displaystyle=$
$\displaystyle\int^{b}_{a}e^{-\lambda x}\frac{(\lambda
x)^{k}}{k!}\cdot\frac{1}{b-a}dx$ (56) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{(b-a)k!}\int^{b}_{a}x^{k}e^{-\lambda x}dx$
(57) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{(b-a)k!}\left(\int^{b}_{0}x^{k}e^{-\lambda
x}dx-\int^{a}_{0}x^{k}e^{-\lambda x}dx\right)$ (58) $\displaystyle=$
$\displaystyle\frac{\gamma(k+1,\lambda b)-\gamma(k+1,\lambda
a)}{\lambda(b-a)k!}.$ (59)

This completes the proof. ∎

######  Proposition 3.4.

Let $\mathcal{S}$ be a Truncated Normal$(a,b,\mu,\sigma^{2})$ random variable,
then the number of customers that arrive during service has the following
distribution

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)$ $\displaystyle=$
$\displaystyle\frac{\gamma(k+1,\lambda b)-\gamma(k+1,\lambda
a)}{\lambda(b-a)k!}.$ (60)

###### Proof.

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)$ $\displaystyle=$
$\displaystyle\int^{b}_{a}e^{-\lambda x}\frac{(\lambda
x)^{k}}{k!}\cdot\frac{e^{-(x-\mu)^{2}/(2\sigma^{2})}}{\sqrt{2\pi}\sigma\left(\Phi(b)-\Phi(a)\right)}dx$
(61) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{\sqrt{2\pi}\sigma(\Phi(b)-\Phi(a))k!}\int^{b}_{a}x^{k}e^{-\lambda
x}e^{-(x-\mu)^{2}/(2\sigma^{2})}dx$ (62) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}e^{\lambda\sigma^{2}/2-\mu}}{\sqrt{2\pi}\sigma(\Phi(b)-\Phi(a))k!}\int^{b}_{a}x^{k}e^{-(x-\left(\mu-\lambda\sigma^{2}\right))^{2}/(2\sigma^{2})}dx$
(63) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}e^{\lambda\sigma^{2}/2-\mu}}{k!}\int^{b}_{a}x^{k}\frac{e^{-(x-\left(\mu-\lambda\sigma^{2}\right))^{2}/(2\sigma^{2})}}{\sqrt{2\pi}\sigma(\Phi(b)-\Phi(a))}dx$
(64) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}e^{\lambda\sigma^{2}/2-\mu}}{k!}M(k,a,b,\mu-\lambda\sigma^{2}/2,\sigma^{2})$
(65)

where $M(k,a,b,\mu-\lambda\sigma^{2}/2,\sigma^{2})$ is the $k^{th}$ moment of
the truncated normal distribution and its expression is given in Theorem 2.3
of Pender [25]. Note that this can also be viewed as a change of measure of a
Gaussian distribution and taking the truncated moment. ∎

######  Proposition 3.5.

Let $\mathcal{S}$ be a Hyper-exponential$(\vec{p},\vec{\mu},\ell)$ random
variable, then the number of customers that arrive during service has the
following distribution

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)=\sum^{\ell}_{j=1}p_{j}(1-\rho_{j})\rho_{j}^{k}$
(66)

where $\rho_{j}=\frac{\lambda}{\mu_{j}+\lambda}$.

###### Proof.

Thus, we have

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)$ $\displaystyle=$
$\displaystyle\sum^{\ell}_{j=1}\int^{\infty}_{0}e^{-\lambda x}\frac{(\lambda
x)^{k}}{k!}p_{j}\mu_{j}e^{-\mu_{j}x}dx$ (67) $\displaystyle=$
$\displaystyle\sum^{\ell}_{j=1}p_{j}(1-\rho_{j})\rho_{j}^{k}.$ (68)

∎

From Proposition 3.5, we observe that a hyper-exponential service time turns
the number of arrival after service into a convex combination of geometric
probabilities. This is nice from an analytical point of view since the
distribution is a weighted sum of geometric distributions and the associated
random variable is a Mixed-Geometric random variable, which is the discrete
analogue of the hyper-exponential distribution. Note that the Mixed-Geometric
is not called hyper-geometric as hyper-geometric refers to another
distribution already.

In addition to computing the distribution of arrivals during service for
different service distribution, we can also compute the distribution in terms
of a Laplace transform times a moment of the service distribution. This is
given in Theorem 2.4 below.

######  Proposition 3.6.

Let $\mathcal{S}$ be a continuous non-negative random variable, then the
number of customers that arrive during service has the following distribution

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)=\frac{\lambda^{k}}{k!}\mathbb{E}\left[\mathcal{S}^{k}e^{-\lambda\mathcal{S}}\right]=\frac{\lambda^{k}}{k!}\mathbb{E}\left[e^{-\lambda\mathcal{S}+k\log(\mathcal{S})}\right].$
(69)

###### Proof.

We have the following expression

$\displaystyle\mathbb{P}\left(N(t+\mathcal{S})-N(t)=k\right)$ $\displaystyle=$
$\displaystyle\int^{\infty}_{0}e^{-\lambda x}\frac{(\lambda x)^{k}}{k!}g(x)dx$
(70) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{k!}\int^{\infty}_{0}e^{-\lambda
x}x^{k}g(x)dx$ (71) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{k!}\mathbb{E}\left[\mathcal{S}^{k}e^{-\lambda\mathcal{S}}\right]$
(72) $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{k!}\mathbb{E}\left[e^{-\lambda\mathcal{S}+k\log(\mathcal{S})}\right]$
(73) $\displaystyle=$
$\displaystyle\frac{(-\lambda)^{k}}{k!}\frac{\partial^{k}}{\partial\lambda^{k}}\mathbb{E}\left[e^{-\lambda\mathcal{S}}\right].$
(74)

∎

######  Proposition 3.7.

For the $M_{t}/D/\infty$ queue the overlap distribution at time $t$ is equal
to

$\displaystyle O(t)$ $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\Delta}_{(t-\Delta)^{+}}\lambda(u)du\right).$
(75)

###### Proof.

$\displaystyle O(t)$ $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\mathcal{S}}_{t}\lambda(u)du+\lambda\int^{t}_{0}\overline{G}(t-u)du\right)$
(76) $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\Delta}_{t}\lambda(u)du+\int^{t}_{(t-\Delta)^{+}}\lambda(u)du\right)$
(77) $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\int^{t+\Delta}_{(t-\Delta)^{+}}\lambda(u)du\right).$
(78)

This completes the proof. ∎

Figure 5: Total Overlap Deterministic Service $(\lambda=10,\Delta=1)$ (Left).
Total Overlap Exponential Service $(\lambda=10,\mu=1)$ (Right).

In Figure 5, we plot the total overlap distribution for deterministic service
and exponential service. We see that while both overlap distributions have a
mean of about 20, we see very different shapes in their distributions. For the
deterministic case, we know the overlap is Poisson, however, for the
exponential setting it is the sum of a Poisson and geometric random variables.
The deterministic service setting results in a more symmetric distribution
while the exponential setting is positively skewed.

######  Corollary 3.8.

For the $M_{t}/D(\ell)/\infty$ queue the overlap distribution at time $t$ is
equal to

$\displaystyle O(t)$ $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\text{Poisson}\left(\sum^{\ell}_{j=1}\int^{t+\Delta_{j}}_{(t-\Delta_{j})^{+}}p_{j}\lambda(u)du\right).$
(79)

###### Proof.

The proof follows immediately from Poisson thinning and Proposition 3.7 ∎

######  Theorem 3.9.

For the $M/M/\infty$ queue the overlap distribution at time $t$ is equal to

$\displaystyle\mathbb{P}\left(O(t)=k\right)$ $\displaystyle=$
$\displaystyle\rho^{k}(1-\rho)e^{\frac{\mu}{\lambda}q^{\infty}(t)}\frac{\Gamma\left(k+1,\frac{\lambda+\mu}{\lambda}q^{\infty}(t)\right)}{\Gamma(k+1)}$
(80)

and the mean and variance are given by

$\displaystyle E[O(t)]$ $\displaystyle=$
$\displaystyle\frac{\lambda}{\mu}(2-e^{-\mu t}),$ (81)
$\displaystyle\mathrm{Var}[O(t)]$ $\displaystyle=$
$\displaystyle\frac{\lambda^{2}}{\mu^{2}}+\frac{\lambda}{\mu}(1-e^{-\mu t}).$
(82)

Moreover, we have that $O(t)$ can be decomposed into a sum of geometric and
Poisson random variables i.e.

$\displaystyle O(t)$ $\displaystyle\stackrel{{\scriptstyle D}}{{=}}$
$\displaystyle\mathrm{Geometric}\left(\frac{\lambda}{\lambda+\mu}\right)+\mathrm{Poisson}(q^{\infty}(t)).$
(83)

###### Proof.

$\displaystyle\mathbb{P}\left(O(t)=k\right)$ $\displaystyle=$
$\displaystyle\int^{\infty}_{0}e^{-(\lambda s+q^{\infty}(t))}\frac{(\lambda
s+q^{\infty}(t))^{k}}{k!}\mu e^{-\mu s}ds$ (84) $\displaystyle=$
$\displaystyle\frac{\mu}{\lambda}e^{\frac{\mu}{\lambda}q^{\infty}(t)}\int^{\infty}_{q^{\infty}(t)}e^{-u}\frac{u^{k}}{k!}e^{-\frac{\mu}{\lambda}u}du,\quad\quad
u=\lambda s+q^{\infty}(t)$ (85) $\displaystyle=$
$\displaystyle\frac{\mu}{\lambda}e^{\frac{\mu}{\lambda}q^{\infty}(t)}\int^{\infty}_{q^{\infty}(t)}\frac{u^{k}}{k!}e^{-\frac{\lambda+\mu}{\lambda}u}du$
(86) $\displaystyle=$
$\displaystyle\frac{\mu}{\lambda}e^{\frac{\mu}{\lambda}q^{\infty}(t)}\frac{\Gamma\left(k+1,\frac{\lambda+\mu}{\lambda}q^{\infty}(t)\right)}{\Gamma(k+1)\cdot\left(\frac{\lambda+\mu}{\lambda}\right)^{k+1}}.$
(87)

Finally for the mean, we have that

$\displaystyle E[O(t)]$ $\displaystyle=$ $\displaystyle
E\left[N^{(b)}(t+\mathcal{S})-N^{(b)}(t)\right]+E[Q^{\infty}(t)]$ (88)
$\displaystyle=$ $\displaystyle\lambda
E[\mathcal{S}]+\lambda\int^{t}_{0}\overline{G}(t-u)du$ (89) $\displaystyle=$
$\displaystyle\frac{\lambda}{\mu}+\frac{\lambda}{\mu}(1-e^{-\mu t})$ (90)
$\displaystyle=$ $\displaystyle\frac{\lambda}{\mu}(2-e^{-\mu t})$ (91)

Moreover, the variance can be calculated as follows

$\displaystyle\mathrm{Var}[O(t)]$ $\displaystyle=$
$\displaystyle\mathrm{Var}\left[N^{(b)}(t+\mathcal{S})-N^{(b)}(t)\right]+\mathrm{Var}[Q^{\infty}(t)]$
(92) $\displaystyle=$ $\displaystyle\lambda
E[\mathcal{S}]+\lambda^{2}\mathrm{Var}[\mathcal{S}]+\lambda\int^{t}_{0}\overline{G}(t-u)du$
(93) $\displaystyle=$
$\displaystyle\frac{\lambda^{2}}{\mu^{2}}+\frac{\lambda}{\mu}(2-e^{-\mu t}).$
(94)

This completes the proof. ∎

######  Proposition 3.10.

For the $M/H_{\ell}/\infty$ queue the overlap distribution at time $t$ is
equal to

$\displaystyle\mathbb{P}\left(O(t)=k\right)$ $\displaystyle=$
$\displaystyle\sum^{\ell}_{j=0}\rho^{k}_{j}(1-\rho_{j})e^{\frac{\mu_{j}}{\lambda}q^{\infty}_{j}(t)}\frac{\Gamma\left(k+1,\frac{\lambda+\mu_{j}}{\lambda}q^{\infty}_{j}(t)\right)}{\Gamma(k+1)}$
(95)

and the mean is given by

$\displaystyle E[O(t)]$ $\displaystyle=$
$\displaystyle\sum^{\ell}_{j=0}p_{j}\frac{\lambda}{\mu_{j}}(2-e^{-\mu_{j}t}).$
(96)

###### Proof.

The proof follows easily from conditioning on the hyper-exponential state. ∎

Figure 6: Total Overlap Lognormal Service $(\lambda=10,\mu=1,\sigma=1)$
(Left).
Overlap During Service Lognormal Service $(\lambda=10,\mu=1,\sigma=1)$
(Right).

In Figure 6, we plot the overlap distribution and the number of overlaps after
arrival for lognormal service times where the mean and variance of the service
times are equal to 1. We see that the total overlap distribution is centered
around 20 while the mean of the arrival during service is roughly 10. One
important thing to note is that the number of arrivals during service
distribution appears to be similar to an exponential with rate $\mu=1$,
however, we observe that the tail of the lognormal is larger. In fact, we
notice that there are a few times where the number overlaps is near 200, while
this does not get larger than 50 for the exponential case. This is clearly
connected to the fact that the lognormal distribution does not have a moment
generating function all positive values.

Figure 7: Total Overlap Uniform $(\lambda=10,a=0,b=10)$ (Top Left).
Overlap During Service Uniform $(\lambda=10,a=1,b=10)$ (Top Right).
Overlap Upon Service Uniform $(\lambda=10,a=1,b=10)$ (Bottom).

In Figure 7, we plot the overlap distribution and the number of overlaps after
arrival for uniform service times in the interval [0,10]. We see that the
total overlap distribution is centered around 100 while the mean of the
arrival during service is roughly 50. What is fascinating is that the
distribution of overlap is clustered around the mean in a pretty uniform
manner. Moreover, for the overlaps during service, the distribution is quite
uniform until it hits 100, which is the boundary of the uniform times the
arrival rate, then the distribution begins to decay exponentially, which is
similar to the decay obtained by the probability of a Poisson random variable
exceeding its mean. Finally, on the bottom of Figure 7 we plot the overlap
upon arrival, which is Poisson with mean roughly equal to 50.

##  4 Residual Overlap Time

In addition to understanding the distribution of the number of overlapping
customers at any point in time, it is also important to understand how long
you spend overlapping with those customers as well. In what follows, we
introduce a residual overlap process. This residual overlap process
$O(t,\delta)$ counts the number of customers that you overlap with at least
for $\delta$ units of time. Thus, the process $O(t,\delta)$ has the following
representation

$\displaystyle O(t,\delta)$ $\displaystyle=$
$\displaystyle\sum^{N^{(b)}(t+(\mathcal{S}-\delta)^{+})}_{j=N^{(b)}(t)+1}\\{S_{j}\geq\delta\\}+\sum_{j=1}^{N^{(b)}(t)}\\{(A_{j}+S_{j}-t)^{+}\geq\delta\\}\cdot\\{\mathcal{S}\geq\delta\\}$
(97)

######  Theorem 4.1.

The mean and variance of the residual overlap time is given by the following
expressions

$\displaystyle E[O(t,\delta)]$ $\displaystyle=$ $\displaystyle\lambda
E[(\mathcal{S}-\delta)^{+}]\cdot\overline{G}(\delta)+\lambda\overline{G}(\delta)\int^{t}_{0}\overline{G}(t+\delta-u)du$
(98) $\displaystyle\mathrm{Var}[O(t,\delta)]$ $\displaystyle=$
$\displaystyle\left(\lambda^{2}\mathrm{Var}\left[(\mathcal{S}-\delta)^{+}\right]+\lambda
E[(\mathcal{S}-\delta)^{+}]\right)\cdot\overline{G}(\delta)^{2}+\overline{G}(\delta)\cdot
G(\delta)\cdot\lambda E[(\mathcal{S}-\delta)^{+}]$ (99) $\displaystyle+$
$\displaystyle\left(\lambda\int^{t}_{0}\overline{G}(t+\delta-u)du\right)\cdot\left(\overline{G}(\delta)\cdot
G(\delta)+\overline{G}(\delta)^{2}\right)$ $\displaystyle+$
$\displaystyle\overline{G}(\delta)\cdot
G(\delta)\cdot\left(\lambda\int^{t}_{0}\overline{G}(t+\delta-u)du\right)^{2}.$

###### Proof.

For the mean we have the following derivation

$\displaystyle E[O(t,\delta)]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum^{N^{(b)}(t+(\mathcal{S}-\delta)^{+})}_{j=N^{(b)}(t)+1}\\{S_{j}\geq\delta\\}\right]+\mathbb{E}\left[\sum_{j=1}^{N^{(b)}(t)}\\{(A_{j}+S_{j}-t)^{+}\geq\delta\\}\cdot\\{\mathcal{S}\geq\delta\\}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[N^{(b)}(t+(\mathcal{S}-\delta)^{+})-N^{(b)}(t)\right]\cdot\mathbb{E}\left[\\{S_{j}\geq\delta\\}\right]$
$\displaystyle+$
$\displaystyle\mathbb{E}\left[\sum_{j=1}^{N^{(b)}(t)}\\{(A_{j}+S_{j}-t)^{+}\geq\delta\\}\right]\cdot\mathbb{E}\left[\\{\mathcal{S}\geq\delta\\}\right]$
$\displaystyle=$ $\displaystyle\lambda
E[(\mathcal{S}-\delta)^{+}]\cdot\overline{G}(\delta)+\lambda\overline{G}(\delta)\int^{t}_{0}\overline{G}(t+\delta-u)du.$

Finally, for the variance we have

$\displaystyle\mathrm{Var}[O(t,\delta)]$ $\displaystyle=$
$\displaystyle\mathrm{Var}\left[\sum^{N^{(b)}(t+(\mathcal{S}-\delta)^{+})}_{j=N^{(b)}(t)+1}\\{S_{j}\geq\delta\\}\right]+\mathrm{Var}\left[\sum_{j=1}^{N^{(b)}(t)}\\{(A_{j}+S_{j}-t)^{+}\geq\delta\\}\cdot\\{\mathcal{S}\geq\delta\\}\right]$
$\displaystyle=$
$\displaystyle\mathrm{Var}\left[\sum^{N^{(b)}((\mathcal{S}-\delta)^{+})}_{j=1}\\{S_{j}\geq\delta\\}\right]+\mathrm{Var}\left[Q^{\infty}(t,\delta)\cdot\\{\mathcal{S}\geq\delta\\}\right]$
$\displaystyle=$
$\displaystyle\mathrm{Var}\left[\sum^{N^{(b)}((\mathcal{S}-\delta)^{+})}_{j=1}\\{S_{j}\geq\delta\\}\right]+\mathrm{Var}\left[Q^{\infty}(t,\delta)\right]\cdot\mathrm{Var}\left[\\{\mathcal{S}\geq\delta\\}\right]$
$\displaystyle+$
$\displaystyle\mathrm{Var}\left[Q^{\infty}(t,\delta)\right]\cdot
E\left[\\{\mathcal{S}\geq\delta\\}\right]^{2}+\mathrm{Var}\left[\\{\mathcal{S}\geq\delta\\}\right]\cdot
E\left[Q^{\infty}(t,\delta)\right]^{2}$ $\displaystyle=$
$\displaystyle\left(\lambda^{2}\mathrm{Var}\left[(\mathcal{S}-\delta)^{+}\right]+\lambda
E[(\mathcal{S}-\delta)^{+}]\right)\cdot\overline{G}(\delta)^{2}+\overline{G}(\delta)\cdot
G(\delta)\cdot\lambda E[(\mathcal{S}-\delta)^{+}]$ $\displaystyle+$
$\displaystyle\mathrm{Var}\left[Q^{\infty}(t,\delta)\right]\cdot\overline{G}(\delta)\cdot
G(\delta)$ $\displaystyle+$
$\displaystyle\mathrm{Var}\left[Q^{\infty}(t,\delta)\right]\cdot\overline{G}(\delta)^{2}+\overline{G}(\delta)\cdot
G(\delta)\cdot E\left[Q^{\infty}(t,\delta)\right]^{2}$ $\displaystyle=$
$\displaystyle\left(\lambda^{2}\mathrm{Var}\left[(\mathcal{S}-\delta)^{+}\right]+\lambda
E[(\mathcal{S}-\delta)^{+}]\right)\cdot\overline{G}(\delta)^{2}+\overline{G}(\delta)\cdot
G(\delta)\cdot\lambda E[(\mathcal{S}-\delta)^{+}]$ $\displaystyle+$
$\displaystyle\mathrm{Var}\left[Q^{\infty}(t,\delta)\right]\cdot\left(\overline{G}(\delta)\cdot
G(\delta)+\overline{G}(\delta)^{2}\right)+\overline{G}(\delta)\cdot
G(\delta)\cdot E\left[Q^{\infty}(t,\delta)\right]^{2}.$

This completes the proof. ∎

Using the mean and variance of the residual overlap process, one can construct
an approximate prediction interval for how many people are expected to overlap
with a customer that arrives at time $t$. This analysis is useful since it can
inform managers of how to ”restrict” the arrival rate to achieve a particular
mean overlap or type of distribution of overlap that is sufficient for risk
tolerance for employees and patrons.

######  Proposition 4.2.

Let $\mathcal{S}$ be a continuous and non-negative random variable with cdf
given by $G(x)$ and define $N((\mathcal{S}-\delta)^{+})$ to be the the number
of arrivals during service given that service, then its distribution is given
by the following expression

$\displaystyle\mathbb{P}\left(N((\mathcal{S}-\delta)^{+})=k\right)$
$\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{k!}e^{\lambda\delta}\mathbb{E}\left[(\mathcal{S}-\delta)^{k}e^{-\lambda\mathcal{S}}\bigg{|}\mathcal{S}>\delta\right]\overline{G}(\delta)$
$\displaystyle\mathbb{P}\left(N((\mathcal{S}-\delta)^{+})=0\right)$
$\displaystyle=$ $\displaystyle
G(\delta)+e^{\lambda\delta}\mathbb{E}\left[e^{-\lambda\mathcal{S}}\bigg{|}\mathcal{S}>\delta\right]\overline{G}(\delta).$

###### Proof.

$\displaystyle\mathbb{P}\left(N((\mathcal{S}-\delta)^{+})=k\right)$
$\displaystyle=$
$\displaystyle\int^{\infty}_{\delta}e^{-\lambda(x-\delta)}\frac{(\lambda(x-\delta))^{k}}{k!}dG(x)$
$\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{k!}e^{\lambda\delta}\int^{\infty}_{\delta}(x-\delta)^{k}e^{-\lambda
x}dG(x)$ $\displaystyle=$
$\displaystyle\frac{\lambda^{k}}{k!}e^{\lambda\delta}\mathbb{E}\left[(\mathcal{S}-\delta)^{k}e^{-\lambda\mathcal{S}}\bigg{|}\mathcal{S}>\delta\right]\overline{G}(\delta).$

The term for zero follows easily by computing what is left over so the sum
totals one. ∎

######  Corollary 4.3.

Let $\mathcal{S}$ be a Exp$(\mu)$ random variable, then

$\displaystyle\mathbb{P}\left(N((\mathcal{S}-\delta)^{+})=k\right)=\left(\frac{\mu}{\lambda+\mu}\right)\left(\frac{\lambda}{\lambda+\mu}\right)^{k}e^{-\mu\delta},\quad
k\geq 1$ (100)
$\displaystyle\mathbb{P}\left(N((\mathcal{S}-\delta)^{+})=0\right)=1-\left(\frac{\lambda}{\lambda+\mu}\right)e^{-\mu\delta}.$
(101)

###### Proof.

This follows by directly computing the necessary conditional expectation.

$\displaystyle\mathbb{P}\left(N((\mathcal{S}-\delta)^{+})=k\right)$
$\displaystyle=$
$\displaystyle\int^{\infty}_{\delta}e^{-\lambda(x-\delta)}\frac{(\lambda(x-\delta))^{k}}{k!}\mu
e^{-\mu x}dx$ $\displaystyle=$
$\displaystyle\frac{\mu\lambda^{k}}{k!}e^{\lambda\delta}\int^{\infty}_{\delta}(x-\delta)^{k}e^{-(\lambda+\mu)x}dx$
$\displaystyle=$
$\displaystyle\frac{\mu\lambda^{k}}{k!}e^{-\mu\delta}\int^{\infty}_{0}y^{k}e^{-(\lambda+\mu)y}dx$
$\displaystyle=$
$\displaystyle\frac{\mu\lambda^{k}}{k!}e^{-\mu\delta}\frac{k!}{(\lambda+\mu)^{k+1}}$
$\displaystyle=$
$\displaystyle\left(\frac{\mu}{\lambda+\mu}\right)\left(\frac{\lambda}{\lambda+\mu}\right)^{k}e^{-\mu\delta}.$

The remaining term when $k=0$ follows from summing all of the other terms and
subtracting it from 1. This completes the proof. ∎

######  Proposition 4.4.

Let $\mathcal{S}$, be a Exp$(\mu)$ random variable, $S_{j}$ i.i.d random
variables with cdf $G(x)$ and define $Z(t,\delta)$ to be the the number of
arrivals during service that overlap at least $\delta$ units of time i.e.

$\displaystyle
Z(t,\delta)=\sum^{N^{(b)}(t+(\mathcal{S}-\delta)^{+})}_{j=N^{(b)}(t)+1}\\{S_{j}\geq\delta\\}.$
(102)

Then, we have the following expression for the distribution of $Z(t,\delta)$

$\displaystyle\mathbb{P}\left(Z(t,\delta)=k\right)$ $\displaystyle=$
$\displaystyle(1-\rho)\rho^{k}e^{-\mu\delta}\overline{G}(\delta)^{k}\frac{1}{(1-\rho
G(\delta))^{k+1}}.$

###### Proof.

$\displaystyle\mathbb{P}\left(Z(t,\delta)=k\right)$ $\displaystyle=$
$\displaystyle\sum^{\infty}_{\ell=0}\mathbb{P}\left(Z(t,\delta)=k\bigg{|}N^{(b)}((\mathcal{S}-\delta)^{+})=\ell\right)\cdot\mathbb{P}\left(N^{(b)}((\mathcal{S}-\delta)^{+})=\ell\right)$
$\displaystyle=$ $\displaystyle\sum^{\infty}_{\ell=k}{\ell\choose
k}\overline{G}(\delta)^{k}G(\delta)^{\ell-k}\cdot(1-\rho)\rho^{\ell}e^{-\mu\delta}$
$\displaystyle=$
$\displaystyle\left(\frac{\overline{G}(\delta)}{G(\delta)}\right)^{k}(1-\rho)e^{-\mu\delta}\sum^{\infty}_{\ell=k}{\ell\choose
k}G(\delta)^{\ell}\cdot\rho^{\ell}$ $\displaystyle=$
$\displaystyle\left(\frac{\overline{G}(\delta)}{G(\delta)}\right)^{k}(1-\rho)e^{-\mu\delta}\sum^{\infty}_{\ell=k}{\ell\choose
k}(\rho G(\delta))^{\ell}$ $\displaystyle=$
$\displaystyle\left(\frac{\overline{G}(\delta)}{G(\delta)}\right)^{k}(1-\rho)e^{-\mu\delta}\sum^{\infty}_{j=0}{j+k\choose
k}(\rho G(\delta))^{j+k}$ $\displaystyle=$
$\displaystyle\left(\overline{G}(\delta)\rho\right)^{k}(1-\rho)e^{-\mu\delta}\sum^{\infty}_{j=0}{j+k\choose
k}(\rho G(\delta))^{j}$ $\displaystyle=$
$\displaystyle\left(\overline{G}(\delta)\rho\right)^{k}(1-\rho)e^{-\mu\delta}\frac{1}{(1-\rho
G(\delta))^{k+1}}.$

∎

Figure 8: Total Residual Overlap (Exponential), $(\lambda=10,\mu=1,\delta=.5)$
(Top Left).
Residual Overlap After Arrival (Exponential), $(\lambda=10,\mu=1,\delta=.5)$
(Top Right).
Residual Upon Arrival (Exponential), $(\lambda=10,\mu=1,\delta=.5)$ (Bottom).

In Figure 8, we plot the residual distribution for the total number of
overlaps, the number of overlaps upon arrival and the number overlaps during
service. We see that the distribution is much different than that of Figure 4.
We see much fewer overlaps since we are requiring at least an overlap of .5
time units, which is decently large given the service time has a mean equal to
one.

##  5 Conclusion and Future Work

In this paper, we consider the overlap times for customers in an infinite
server queue. The infinite server model is appropriate in retail settings
where the time a customer waits is small relative to their shopping
experience. We derive the steady state distribution for the overlap time of
customers that are $k$ arrivals apart. We also compute explicitly the
distribution of the number of customers that a randomly arriving customer will
overlap with as the sum of a Poisson random variable and Poisson with a random
arrival rate. Finally, we compute an expression for the number of customers
that a random arrival will overlap at least $\delta$ time units. We compute
the mean and variance for this quantity and are able to provide a prediction
interval for a randomly arriving customer at any time. Our analysis has
implications for understanding the interaction time between customers in a
pandemic setting and sheds light on the interactions of customers.

Despite our analysis, there are many avenues for additional research. First,
we would like to complete our analysis by analyzing the $G/G/\infty$ queue in
explicit detail. Issues like dependent arrivals or service times like in Pang
and Whitt [23, 24], Daw and Pender [3, 4], Daw et al. [7] would be interesting
to explore as well. Second, we would like to extend our analysis to more
complicated queueing systems like the Erlang-A, see for example Daw and Pender
[6], Massey and Pender [17], Hampshire et al. [13] where customers can abandon
the system. Abandoning customers clearly reduces the number of overlapping
customers, but by how much? It would also be great to extend our analysis to
queueing systems with batch arrivals. In this case, the scaled Poisson
decomposition of Daw and Pender [5], Daw et al. [8] might be helpful in
replicating our analysis in the batch setting. Finally, we would like to
extend our analysis to spatial point processes and think about the overlap in
terms of not only time, number, but spatial distance as well.

We are also interested in knowing the overlap distribution for more than two
customers. For example, if one considers the overlap time of three customers
$(n,n+j,n+k)$ where $1\leq j<k$, then one obtains the following overlap time
for the $n^{th}$, $(n+j)^{th}$, and the $(n+k)^{th}$ customers as

$\displaystyle O_{n,n+j,n+k}$ $\displaystyle=$
$\displaystyle\left(\min(D_{n},D_{n+j},D_{n+k})-A_{n+k}\right)^{+}$
$\displaystyle=$
$\displaystyle\left(\min(A_{n}+S_{n},A_{n+j}+S_{n+j},A_{n+k}+S_{n+k})-A_{n+k}\right)^{+}$
$\displaystyle=$
$\displaystyle(S_{n}+A_{n}-A_{n+k})^{+}\bm{\wedge}(S_{n+j}+A_{n+j}-A_{n+k})^{+}\bm{\wedge}S_{n+k}$
$\displaystyle=$
$\displaystyle(S_{n}+A_{n}-A_{n+k})^{+}\bm{\wedge}(S_{n+j}+A_{n}+(A_{n+j}-A_{n})-A_{n+k})^{+}\bm{\wedge}S_{n+k}.$

Unlike the two customer situation, it is clear here that the random variables
are not independent anymore. This presents a new issue that must be resolved
in future work.

## References

  * Bove and Benoit [2020] Liliana L Bove and Sabine Benoit.  Restrict, clean and protect: signaling consumer safety during the pandemic and beyond.  _Journal of Service Management_ , 2020.
  * Dandekar et al. [2021] Raj Dandekar, Shane G Henderson, Hermanus M Jansen, Joshua McDonald, Sarat Moka, Yoni Nazarathy, Christopher Rackauckas, Peter G Taylor, and Aapeli Vuorinen.  Safe blues: The case for virtual safe virus spread in the long-term fight against epidemics.  _Patterns_ , 2(3):100220, 2021.
  * Daw and Pender [2018a] Andrew Daw and Jamol Pender.  Exact simulation of the queue-hawkes process.  In _Proceedings of the 2018 Winter Simulation Conference_ , pages 4234–4235, 2018a.
  * Daw and Pender [2018b] Andrew Daw and Jamol Pender.  Queues driven by hawkes processes.  _Stochastic Systems_ , 8(3):192–229, 2018b.
  * Daw and Pender [2019a] Andrew Daw and Jamol Pender.  On the distributions of infinite server queues with batch arrivals.  _Queueing Systems_ , 91(3):367–401, 2019a.
  * Daw and Pender [2019b] Andrew Daw and Jamol Pender.  New perspectives on the Erlang-A queue.  _Advances in Applied Probability_ , 51(1):268–299, 2019b.
  * Daw et al. [2020a] Andrew Daw, Antonio Castellanos, Galit B Yom-Tov, Jamol Pender, and Leor Gruendlinger.  The co-production of service: Modeling service times in contact centers using hawkes processes.  _arXiv preprint arXiv:2004.07861_ , 2020a.
  * Daw et al. [2020b] Andrew Daw, Brian Fralix, and Jamol Pender.  Non-stationary queues with batch arrivals.  _arXiv preprint arXiv:2008.00625_ , 2020b.
  * Drakopoulos et al. [2017] Kimon Drakopoulos, Asuman Ozdaglar, and John N Tsitsiklis.  When is a network epidemic hard to eliminate?  _Mathematics of Operations Research_ , 42(1):1–14, 2017.
  * Eick et al. [1993a] Stephen G Eick, William A Massey, and Ward Whitt.  ${M}_{t}/{G}/\infty$ queues with sinusoidal arrival rates.  _Management Science_ , 39(2):241–252, 1993a.
  * Eick et al. [1993b] Stephen G Eick, William A Massey, and Ward Whitt.  The physics of the ${M}_{t}/{G}/\infty$ queue.  _Operations Research_ , 41(4):731–742, 1993b.
  * Forien et al. [2020] Raphaël Forien, Guodong Pang, and Étienne Pardoux.  Epidemic models with varying infectiosity.  _arXiv preprint arXiv:2006.15377_ , 2020.
  * Hampshire et al. [2020] Robert C Hampshire, Shan Bao, Walter S Lasecki, Andrew Daw, and Jamol Pender.  Beyond safety drivers: Applying air traffic control principles to support the deployment of driverless vehicles.  _PLoS one_ , 15(5):e0232837, 2020.
  * Kang et al. [2021] Kang Kang, Sherwin Doroudi, Mohammad Delasay, and Alexander Wickeham.  A queueing-theoretic framework for evaluating transmission risks in service facilities during a pandemic.  _arXiv preprint arXiv:2103.13441_ , 2021.
  * Kaplan [2020] Edward H Kaplan.  OM forum—COVID-19 scratch models to support local decisions.  _Manufacturing & Service Operations Management_, 22(4):645–655, 2020.
  * Klar [2015] Bernhard Klar.  A note on gamma difference distributions.  _Journal of Statistical Computation and Simulation_ , 85(18):3708–3715, 2015.
  * Massey and Pender [2018] William A Massey and Jamol Pender.  Dynamic rate Erlang-A queues.  _Queueing Systems_ , 89(1):127–164, 2018.
  * Moein et al. [2021] Shiva Moein, Niloofar Nickaeen, Amir Roointan, Niloofar Borhani, Zarifeh Heidary, Shaghayegh Haghjooy Javanmard, Jafar Ghaisari, and Yousof Gheisari.  Inefficiency of sir models in forecasting covid-19 epidemic: a case study of isfahan.  _Scientific Reports_ , 11(1):1–9, 2021.
  * Nguemdjo et al. [2020] Ulrich Nguemdjo, Freeman Meno, Audric Dongfack, and Bruno Ventelou.  Simulating the progression of the covid-19 disease in cameroon using sir models.  _PloS one_ , 15(8):e0237832, 2020.
  * [20] Sergio Palomo and Jamol Pender.  Measuring the overlap with other customers in the G/G/1 queue.  In KH Bae, B Feng, S Kim, S Lazarova-Molnar, Z Zheng, T Roeder, and R Thiesing, editors, _Submitted to the Proceedings of the 2021 Winter Simulation Conference_.
  * Palomo et al. [2020] Sergio Palomo, Jamol Pender, William Massey, and Robert C Hampshire.  Flattening the curve: Insights from queueing theory.  _arXiv preprint arXiv:2004.09645_ , 2020.
  * Pang and Pardoux [2020] Guodong Pang and Étienne Pardoux.  Functional limit theorems for non-markovian epidemic models.  _arXiv preprint arXiv:2003.03249_ , 2020.
  * Pang and Whitt [2012] Guodong Pang and Ward Whitt.  The impact of dependent service times on large-scale service systems.  _Manufacturing & Service Operations Management_, 14(2):262–278, 2012.
  * Pang and Whitt [2013] Guodong Pang and Ward Whitt.  Two-parameter heavy-traffic limits for infinite-server queues with dependent service times.  _Queueing Systems_ , 73(2):119–146, 2013.
  * Pender [2015] Jamol Pender.  The truncated normal distribution: Applications to queues with impatient customers.  _Operations Research Letters_ , 43(1):40–45, 2015\.