Some Reflections on the Renewal-Theory Paradox in Queueing Theory
The classical renewal-theory (waiting-time, or inspection) paradox
states that the length of the renewal interval that covers a
randomly-selected time epoch tends to be longer than an ordinary
renewal interval. This paradox manifests itself in numerous
interesting ways in queueing theory, a prime example being the
celebrated Pollaczek-Khintchine formula for the mean waiting time
in the M/G/1 queue. In this expository paper, we give
intuitive arguments that "explain" why the renewal-theory paradox
is ubiquitous in queueing theory, and why it sometimes produces
anomalous results. In particular, we use these intuitive arguments
to explain decomposition in vacation models, and to derive formulas
that describe some recently-discovered counterintuitive results for
polling models, such as the reduction of waiting times as a
consequence of forcing the server to set up even when no work
is waiting.