Diffusion Approximation Error for Queueing Systems with General Primitives

Abstract

We investigate the steady-state diffusion-approximation error for continuous-time queueing systems with generally distributed primitives. A common picture emerges after analyzing a number of canonical systems: the error decomposes into interior and boundary terms. The former are simpler to handle and can be bounded using only low-order moments of the system’s primitives — when the approximation error is measured using the Wasserstein distance, three moments suffice. The boundary terms are inherently more delicate: while crude bounds are easy to obtain, sharper (e.g., order optimal) bounds require deeper, model specific, insights. Methodologically, we extend the generator comparison approach of Stein's method to piecewise-deterministic Markov processes (PDMPs). The discontinuous nature of the PDMP at jump times necessitates using the basic adjoint relationship (BAR), instead of the infinitesimal generator, to characterize the stationary distribution. A second-order Taylor expansion of the BAR’s jump terms, coupled with a Palm-inversion step that converts event-averaged quantities into time averages, yields the candidate diffusion generator and a transparent interior/boundary error decomposition. In parallel, we show how the prelimit generator approach — working with the Poisson equation of the queueing system instead of the diffusion process — offers a promising avenue for bounding the challenging boundary terms.