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.