Source-linked AI summary
Infinite-server queues with Hawkes input
David Koops, Mayank Saxena, Onno Boxma, Michel Mandjes
TL;DR
The paper asks how to analyze customer counts in infinite-server queues when arrivals are self-exciting rather than governed by a deterministic-rate Poisson process. It combines Markovian transform and moment equations with a branching-process fixed-point approach for more general settings, deriving heavy-tail and heavy-traffic asymptotics. The results include computational approximations and simulation verification.
Problem
The paper studies customer counts in infinite-server queues with Hawkes arrivals, motivated by overdispersion that violates the standard Poisson-arrival assumption.
Source: §1 · pp. 1–2Method
For Markovian Hawkes input and exponential service, the paper derives joint-distribution and moment equations; for general excitation and service, it uses a branching representation and a fixed-point equation.
Source: §1 · p. 3, §3 · p. 5, §4 · p. 12Results
The paper derives customer-count tail asymptotics for heavy-tailed intensity jumps and heavy-traffic asymptotics, and reports computational procedures with simulation verification.
Source: §1 · p. 3, §6 · p. 16Takeaways & Limitations
The analysis gives explicit moment results under Markovian assumptions and a fixed-point description for less explicit general cases, which the paper uses to derive asymptotics.
Source: §7 · p. 22The analysis relies on independent customer service in the infinite-server setting, a property absent in single-server queues, where exact analysis may be prohibitively difficult.
Source: §7 · p. 22
Abstract
from arXiv · showhide
In this paper we study the number of customers in infinite-server queues with a self-exciting (Hawkes) arrival process. Initially we assume that service requirements are exponentially distributed and that the Hawkes arrival process is of a Markovian nature. We obtain a system of differential equations that characterizes the joint distribution of the arrival intensity and the number of customers. Moreover, we provide a recursive procedure that explicitly identifies (transient and stationary) moments. Subsequently, we allow for non-Markovian Hawkes arrival processes and non-exponential service times. By viewing the Hawkes process as a branching process, we find that the probability generating function of the number of customers in the system can be expressed in terms of the solution of a fixed-point equation. We also include various asymptotic results: we derive the tail of the distribution of the number of customers for the case that the intensity jumps of the Hawkes process are heavy-tailed, and we consider a heavy-traffic regime. We conclude the paper by discussing how our results can be used computationally and by verifying the numerical results via simulations.
1 Introduction
The paper studies infinite-server queues with Hawkes arrivals, motivated by arrival overdispersion that the standard deterministic-rate Poisson assumption cannot represent. It extends exact analysis to marked Hawkes input and general service and excitation settings, and derives computational and asymptotic results.
1 Introduction
- Overdispersion—arrival-count variance exceeding its expected value—indicates that the standard Poisson assumption is not valid.This motivates studying queueing systems with overdispersed arrivals.Source: §1 · pp. 1–2
- The object of study is an infinite-server queue with Hawkes input, where customers enter service immediately and are served independently.The paper contrasts this setting with the regularity assumptions, such as Poisson or renewal arrivals, typical in the existing infinite-server queue literature.Source: §1 · p. 2
- To the authors’ knowledge, prior exact analysis [9] covered unmarked Markovian Hawkes input, while this work also considers stochastic intensity jumps and general service and excitation functions.The paper also distinguishes its self-exciting input from the Cox-process arrivals studied in.Source: §1 · pp. 2–3
- For exponential service and excitation, the paper derives equations characterizing the joint intensity-customer distribution and transient moments; more general settings yield a fixed-point equation for the customer-count transform.The Markovian analysis also gives explicit first and second transient moments, while the fixed-point approximation has explicit error bounds.Source: §1 · p. 3
- The paper derives customer-count tail asymptotics for heavy-tailed intensity jumps and asymptotics in a heavy-traffic regime.It also presents computational uses and simulation verification of its numerical results.Source: §1 · p. 3
2 Preliminaries
The preliminaries present two equivalent descriptions of Hawkes processes: a conditional-intensity definition and a branching-process cluster representation. The paper uses the first for Markovian queue analysis and the second for non-Markovian analysis.
2 Preliminaries
- A Hawkes process is defined through a conditional intensity with background level λ∞ and event contributions determined by marks B_i and excitation function h.The marks and excitation function are named in the definition; the process is also called self-exciting.Source: §2 · p. 4
- The paper calls the process marked because each event has a random mark B_i, and its kernel multiplicatively combines that mark with h(t − t_i).The initial intensity is set to the reversion level λ∞.Source: §2 · p. 4
- The cluster representation starts with Poisson immigrant events at rate λ∞ and generates later events as descendants of earlier arrivals.This is the branching-process-with-immigration representation used alongside the conditional-intensity definition.Source: §2 · p. 4
- The paper uses the conditional-intensity definition for Markovian queues and the cluster representation for non-Markovian queues.The stated reason is that the Section 3 approach does not apply to non-Markovian queues.Source: §2 · pp. 4–5
3 A Markovian Hawkes-fed infinite-server queue
Under exponential excitation and service times, the paper characterizes the joint Hawkes-intensity/customer-count dynamics through an ODE and derives transient and stationary moments. The moment analysis identifies a stability condition for finite moments.
3.1 Characterization of the queueing process
- An ODE characterizes the joint transform and uniquely determines the transient law of (N(t), Λ(t)) under exponential excitation and service times.With finite service times, the ODE variables are not separable, so the equation cannot be solved analytically.Source: §3.1 · p. 5, §3 · p. 5
3.2 Transient moments
- A recursive ODE system yields joint transient moments when E[B^g] is finite; finite moments require r−E[B]>0.If r−E[B]≤0, intensity and customer count grow indefinitely on average; µ>0 does not alter stability.Source: §3.2 · pp. 7, 10
3.3 Stationary moments
- For a stable queue, taking t→∞ gives stationary intensity moments and formulas for the means, variances, covariance, and correlation of intensity and customer count.The stated stationary intensity moment result assumes E[B^g]<∞.Source: §3.3 · p. 11
4 A non-Markovian Hawkes-fed infinite-server queue
The section extends the queue analysis to general nonnegative excitation functions and service times, using Hawkes clusters to characterize the customer-count z-transform through a fixed-point equation. The fixed-point iteration converges uniquely, and its iterates also yield bounds for computation.
4 A non-Markovian Hawkes-fed infinite-server queue
- Each immigrant seeds a branching cluster: arrivals increase future rates, children can become parents, and customers receive independent i.i.d. service requirements.A parent's children arrive according to an inhomogeneous Poisson process with rate Bh(u), conditional on its rate increment B.Source: §4 · pp. 11–12
- The z-transform of N(t) is expressed through η, the unique fixed point of φ, for general nonnegative excitation functions and service requirements.The section derives this representation by viewing Hawkes arrivals as immigrant-led branching clusters.Source: §4 · pp. 11, 13
- From any admissible initial approximation, iterating φ converges pointwise to η, including for complex z with |z| < 1.Every iterate remains in the class of possibly defective z-transforms.Source: §4 · pp. 13–14
- Iterates initialized at the extremal functions 0 and 1 provide lower and upper bounds on the CDF of the cluster-size variable.The bounds can be used to assess finite-iteration approximation error.Source: §4 · p. 14
5 Numerics and simulations
The section applies the Markovian and cluster-based methods computationally, using numerical inversion, fixed-point iteration, and simulations. In the example, estimates agree well for small customer counts, while tail estimates are less certain.
5 Numerics and simulations
- The Markovian method numerically inverts Eqn. (2), while the cluster approach iterates Eqn. (22) for complex arguments and uses bounds to control finite-iteration error.Both methods are compared under the more restrictive assumptions introduced for the Markovian setting.Source: §5 · p. 15
- Simulations validate the results by generating Hawkes arrivals and retaining each arrival with probability P(J > t − ti).The simulation procedure uses the Hawkes branching representation and thinning for inhomogeneous Poisson processes.Source: §5 · p. 16
- 10 million simulation runs were used; estimated values from the methods agree quite well for small N(10), while tail estimates become more uncertain.For larger N(10), simulation estimates are less certain and the cluster-method upper–lower bound spread increases.Source: §5 · p. 16
6 Asymptotic results
The asymptotic analysis covers heavy-tailed Hawkes jumps and heavy traffic near the stability boundary, relying on the Hawkes branching-process representation. It shows that heavy-tailed jumps transfer their tail index to the finite-time customer count.
6.1 Heavy-tailed asymptotics
- For B in R(−α), 1 < α < 2, N(t) in the Hawkes/G/∞ queue has index −α; by contrast, the empty-start M/G/∞ customer count is Poisson at any time t.Source: §6.1 · pp. 17–18
- For exponential h and J, the heavy-tail asymptotic coefficient integrals admit explicit expressions.The paper specializes to h(u)=e^-ru and J(u)=e^-μu.Source: §6.1 · p. 19
6.2 Heavy-traffic asymptotics
- For the stationary Hawkes intensity, the near-critical analysis assumes exponential excitation and finite first two moments of B, with κ=2r/b2.Here ρ approaches 1.Source: §6.2 · pp. 20–21
- As ρ approaches 1, the first two moments of (1−ρ)Λ and (1−ρ)μN have the same limit.The customer-count result uses exponential excitation and service, with finite first two moments of B.Source: §6.2 · pp. 20–22
7 Discussion and concluding remarks
The paper analyzes infinite-server queues with Hawkes input, deriving explicit transient and stationary moments under Markovian assumptions and fixed-point-based results when those assumptions are lifted. It identifies extensions and computational improvements as directions for further work.
7 Discussion and concluding remarks
- Markovian assumptions yield explicit transient and stationary customer-count moments; without them, results become less explicit and use a fixed-point equation for the customer-count z-transform.The fixed-point equation is also used to derive asymptotic results.Source: §7 · p. 22
- Single-server extensions lack the independent-service property used in the infinite-server analysis, so exact analysis may be prohibitively difficult; heavy-traffic analysis may remain possible.Source: §7 · p. 22
- The paper raises whether its results extend to networks of infinite-server queues with Hawkes input, using mutually-exciting arrivals.Arrivals to one queue can excite arrivals in others in that multivariate setting.Source: §7 · p. 22
- For limit-order-book models, empirically supports infinite-server queues; verifying this paper’s predictions against order-book data remains future work.Source: §7 · pp. 22–23
- The bounds of Proposition 4.2 could be improved for larger n, and better initial approximations could be determined.Source: §7 · p. 23
- Open heavy-traffic directions include extending Theorem 6.6 to general J and studying heavy-tailed jumps.The heavy-tailed case concerns the setting of Section 6.1.Source: §7 · p. 23