Nonparametric inference from possibly unstable M/G/1 workload observations

Abstract

Hansen and Pitts (2006) introduced the problem of nonparametric estimation of the service-time distribution of an M/G/1 queue observed through its workload process at discrete times $t=0,1,\dots ,n$. Despite its seemingly simple formulation, obtaining an estimator with sharp risk guarantees for this observation model has remained an open challenge for nearly two decades. In this paper, we construct such an estimator and prove that its $L^1$-risk is $\mathcal{O}\left(\frac{\log n}{\sqrt{n}}\right)$ as $n\to \infty$. Remarkably, this nearly parametric convergence rate is achieved without assuming stationarity, stability, or knowledge of the arrival rate. Our approach is based on a two-stage screening procedure that uncovers a hidden conditionally independent compound Poisson structure within the dependent workload observations. This probabilistic reduction transforms the original estimation problem into a classical decompounding problem, making it possible to leverage existing nonparametric estimation techniques despite the complex dependence induced by the reflected workload process. More broadly, we hope that the proposed screening methodology will provide a useful framework for statistical inference from dependent stochastic systems beyond the classical assumption of stability.