Abstract
We introduce an efficient MCMC sampling scheme to perform Bayesian inference in the M/G/1 queueing model given only observations of interdeparture times. Our MCMC scheme uses a combination of Gibbs sampling and simple Metropolis updates together with three novel "shift" and "scale" updates. We show that our novel updates improve the speed of sampling considerably, by factors of about 60 to about 180 on a variety of simulated data sets.
Introduction
Queueing models are fundamental to operations research, telecommunications, and computer science. The M/G/1 queue—where arrivals follow a Poisson process (M), service times follow a general distribution (G), and there is a single server (1)—is a cornerstone of this field.
A significant challenge in applying these models is inference: estimating arrival rates and service time distributions when only the times at which customers leave the system (interdeparture times) are observable. This is a latent variable problem because the actual arrival times are unobserved. Previous approaches often relied on Approximate Bayesian Computation (ABC), which is easier to implement but does not converge to the exact posterior distribution. Standard Markov Chain Monte Carlo (MCMC) can provide exact results but is notoriously slow because parameters and latent arrival times are tightly coupled; changing one often makes the other logically impossible, causing the sampler to stall.
Methodology
The proposed MCMC scheme treats unobserved arrival times ($V_i$) as latent variables. The scheme integrates several layers of updates:
- Standard Gibbs Updates: Sampling each arrival time $V_i$ given the others.
- Standard Metropolis Updates: Sampling the model parameters $\theta$ (arrival rate and service time bounds).
- Novel "Shift" and "Scale" Updates: This is the core contribution. Instead of updating one variable at a time, these updates propose moving parameters and latent variables simultaneously:
- Shift Update: Shifts the minimum service time and all arrival times together to maintain the physical constraints of the queue.
- Range Scale Update: Scales the "gaps" between arrival times and service bounds.
- Rate Scale Update: Scales interarrival times and the arrival rate parameter together, following the "ridge" of high probability in the posterior.
These joint updates allow the sampler to take much larger steps through the probability space without violating the strict logical constraints of the queueing model (e.g., a customer cannot depart before they arrive).
Experimental Setup
The authors evaluated their method on three simulated datasets representing different real-world scenarios, each with $n=50$ observations:
- Frequent Arrivals: The queue is almost always full, leading to high uncertainty in arrival rate but low uncertainty in service times.
- Intermediate Case: A balanced queue that fluctuates between being empty and having a backlog.
- Rare Arrivals: The queue is usually empty. Arrival times are easy to infer, but service time bounds are harder to pin down.
Key Results and Insights
The performance was measured using autocorrelation time, which indicates how many samples are needed to obtain an independent piece of information.
- Massive Speedup: The "Basic + All" scheme outperformed standard MCMC by factors of 60 to 180.
- Scenario-Specific Effectiveness: The Rate Scale update was particularly effective for frequent arrivals, helping navigate high uncertainty in the arrival rate. Conversely, the Shift and Range Scale updates were critical for rare arrivals, helping resolve service time parameters when the queue was mostly empty.
- Accuracy: All schemes eventually converged to the same posterior means, proving that the novel updates maintain the mathematical integrity of the Bayesian inference.
The "aha moment" of this research is that to move efficiently through the parameter space, one must change the latent history of the queue at the same time as the parameters. While these novel updates are not enough on their own to explore the entire space (they are not "ergodic"), pairing them with simple Gibbs updates ensures the sampler visits every possible state.
Conclusion and Future Work
This study demonstrates that joint parameter and latent variable updates can dramatically improve the efficiency of Bayesian inference for queueing models. While this paper utilized a Uniform distribution for service times to simplify the mathematics, the approach can be extended to other location-scale families. Future research may involve comparing this method with Particle MCMC (PMCMC) for models with more complex time-series structures.
Summary updated