Duality and Other Results for M/G/1 and GI/M/1 Queues, Via a New Ballot Theorem

We 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, we 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, our arguments avoid the use of transforms, and thereby provide insight and term-by-term “explanations” for the remarkable forms of some of these results.