Minimax Estimation of Queue Service-Time Distributions

Definitions and mathematical statement

Under the usual meaning of an $M/G/\infty$ queue, customers arrive according to a homogeneous Poisson process of rate $\lambda>0$. Their service times are independent and identically distributed nonnegative random variables, independent of the arrival process, with distribution function \[ G(t)=\mathbb{P}(S\leq t),\qquad t\geq0. \] There are infinitely many servers, so each customer begins service immediately. Let $X(t)$ denote the number of customers in service at time $t$. The observations concern this queue-length process; the record does not specify continuous observation, discrete sampling, the observation horizon, or the initial state.

A conditional mathematical formulation of the requested minimax problem is as follows. Once an observation scheme indexed by $r$, a parameter class $\Theta$, and a nonnegative loss function $L$ have been specified, let $Y_r$ denote the observed queue-length data and let $\mathbb{P}_{\theta,r}$ be their law for $\theta\in\Theta$. Write $G_\theta$ for the service-time distribution function associated with $\theta$; the parameter $\theta$ also includes any unknown arrival-rate or initialization parameters. Define \[ R_r^*(\Theta,L) = \inf_{\widehat G_r}\sup_{\theta\in\Theta} \mathbb{E}_{\theta,r}\!\left[ L\left(\widehat G_r(Y_r),G_\theta\right) \right], \] where the infimum is over measurable estimators of the service-time distribution based on $Y_r$.

Problem. Determine the optimal achievable minimax accuracy for estimating $G$ from queue-length observations of the $M/G/\infty$ queue, expressed through $R_r^*(\Theta,L)$ for a specified statistical experiment. The supplied record does not determine that experiment, the parameter class, the loss, or an asymptotic regime. Consequently, this formula describes the requested family of problems, but the record does not specify a single minimax risk or rate to determine. No stationarity, finite-mean, smoothness, or tail assumption is imposed here on behalf of the source.

Short English statement

Estimate the service-time distribution of an $M/G/\infty$ queue using observations of how many customers are in service, and determine the best possible worst-case estimation accuracy. A precise accuracy statement requires an observation scheme, an admissible distribution class, and a loss function, which the supplied record leaves unspecified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002889$, title Minimax Estimation of Queue Service-Time Distributions, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2015.
• Supplied report citation: Probabilistic Techniques in Modern Statistics (2016), Oberwolfach Reports, pp. 1449--1498, DOI 10.4171/owr/2015/26. https://doi.org/10.4171/owr/2015/26. The report title's year is retained as supplied, alongside the 2015 proposed year and DOI year component; their relationship is unresolved in this record.
• Goldenshluger, Advances in Applied Probability, supplied literature reference: https://doi.org/10.1017/apr.2016.67.
• Goldenshluger, Bernoulli, supplied literature reference: https://doi.org/10.3150/17-BEJ936.
• Adaptive minimax estimation, Queueing Systems, supplied literature reference: https://doi.org/10.1007/s11134-024-09921-2.
• Supplied literature assessment, checked at 2026-08-21: the registry labels the problem partially solved and reports rate-optimal nonparametric estimation for several observation schemes and smoothness classes, including queue-length and arrival-departure data. It also states that there is no single universal accuracy statement without an observation model and parameter class. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment; the cited claims and time-sensitive status require independent verification.