Activities per year
Abstract
In this paper we describe a perfect simulation algorithm for the stable M/G/c queue. Sigman (2011: Exact Simulation of the Stationary Distribution of the FIFO M/G/c Queue. Journal of Applied Probability, 48A, 209213) showed how to build a dominated CFTP algorithm for perfect simulation of the superstable M/G/c queue operating under First Come First Served discipline, with dominating process provided by the corresponding M/G/1 queue (using Wolff's sample path monotonicity, which applies when when service durations are coupled in order of initiation of service), and exploiting the fact that the workload process for the M/G/1 queue remains the same under different queueing disciplines, in particular under the Processor Sharing discipline, for which a dynamic reversibility property holds. We generalize Sigman's construction to the stable case by comparing the M/G/c queue to a copy run under Random Assignment. This allows us to produce a naive perfect simulation algorithm based on running the dominating process back to the time it first empties. We also construct a more efficient algorithm that uses sandwiching by lower and upper processes constructed as coupled M/G/c queues started respectively from the empty state and the state of the M/G/c queue under Random Assignment. A careful analysis shows that appropriate ordering relationships can still be maintained, so long as service durations continue to be coupled in order of initiation of service. We summarize statistical checks of simulation output, and demonstrate that the mean runtime is finite so long as the second moment of the service duration distribution is finite.
Original language  English 

Pages (fromto)  10391063 
Number of pages  24 
Journal  Advances in Applied Probability 
Volume  47 
Issue number  4 
DOIs  
Publication status  Published  21 Mar 2016 
Keywords
 coalescence; coupling; coupling from the past (CFTP); dominated coupling from the past; dynamic reversibility; exact simulation; First Come First Served discipline [FCFS]; First In First Out discipline [FIFO]; KieferWolfowitz workload vector; pathwise domination; perfect simulation; Processor Sharing discipline [PS]; M/G/c queue; Random Assignment discipline [RA]; sandwiching; stable queue; stochastic ordering; superstable queue; time reversal
Profiles

Omnithermal Perfect Simulation for Multiserver Queues
Stephen Connor (Invited speaker)
23 Nov 2018Activity: Talk or presentation › Invited talk

(Omnithermal) Perfect Simulation for M/G/c Queues
Stephen Connor (Speaker)
20 Oct 2017Activity: Talk or presentation › Invited talk

61st World Statistics Congress
Stephen Connor (Invited speaker)
16 Jul 2017 → 21 Jul 2017Activity: Participating in or organising an event › Conference participation
Projects
 1 Finished

Probabilistic coupling: coadaptedness, maximality and efficiency
27/02/12 → 26/02/14
Project: Research project (funded) › Research