Diffusion approximation error for queueing systems with general primitives
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908513154891776 |
|---|---|
| author | Braverman, Anton Scully, Ziv |
| author_facet | Braverman, Anton Scully, Ziv |
| contents | We investigate the steady-state diffusion-approximation error for continuous-time queueing systems with generally distributed primitives. Across four canonical systems -- the $G/G/1$ and $G/M/\infty$ queues, the join-the-shortest-queue system, and a two-station tandem queue -- a common picture emerges: 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12716 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Diffusion approximation error for queueing systems with general primitives Braverman, Anton Scully, Ziv Probability Primary 60J25, 60F99, secondary 60K25, 60J60 We investigate the steady-state diffusion-approximation error for continuous-time queueing systems with generally distributed primitives. Across four canonical systems -- the $G/G/1$ and $G/M/\infty$ queues, the join-the-shortest-queue system, and a two-station tandem queue -- a common picture emerges: 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 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. |
| title | Diffusion approximation error for queueing systems with general primitives |
| topic | Probability Primary 60J25, 60F99, secondary 60K25, 60J60 |
| url | https://arxiv.org/abs/2407.12716 |