Duality and other results for M/G/1 and GI/M/1 queues, via a new ballot theorem

The authors generalize the classical ballot theorem and use it to obtain direct probabilistic derivations of some well-known and some new results relating to busy and idle periods and waiting times in M/G/1 and GI/M/1 queues. In particular, they uncover a duality relation between the joint distribution of several variables associated with the busy cycle in M/G/1 and the corresponding joint distribution in GI/M/1. In contrast with the classical derivations of queueing theory, the present arguments avoid the use of transforms, and thereby provide insight and term-by-term ‘explanations’ for the remarkable forms of some of these results.