Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 38 · M/G/1 and Variability

Residual Life and the Inspection Paradox

Why do you always seem to wait longer than average? Learn the inspection paradox, the residual service time formula E[S²]/(2E[S]), and how it drives M/G/1 waits.

A bus runs on average every 10 minutes. You arrive at a random moment. How long do you expect to wait? "Five minutes" seems obvious, yet if the gaps between buses are uneven the answer is longer. This surprise is the inspection paradox, and it is the hidden engine of the Pollaczek-Khinchine formula.

Long intervals are easier to land in

Imagine buses whose gaps are 2 minutes half the time and 18 minutes the other half. The mean gap is 10 minutes. But a random arrival time is far more likely to fall inside an 18-minute gap than a 2-minute gap: the long gaps cover 90 percent of the clock. A random arrival lands in a long gap 90 percent of the time. This length bias means the interval you see is longer than the typical one.

In general, the interval that contains a random time has density proportional to x f(x), so its mean is E[X²]/E[X]. You arrive at a uniformly random point inside it, so the expected remaining time, the mean residual life, is half of that:

Text
E[R] = E[X²] / (2 E[X]) = (E[X]/2) (1 + c²)

where c² is the squared coefficient of variation of the interval. If intervals are perfectly regular (c² = 0), the residual is half the mean. If they are exponential (c² = 1), the residual equals the full mean: the famous memoryless property. If they are more variable still, the residual is larger than the mean.

Python Mean residual life from the interval distribution

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You wait 8.2 minutes on average at the uneven stop, but only 5 minutes where buses are perfectly regular, even though the average gap is 10 in both cases.

This is an average over random arrival times. It does not say any individual wait is exactly 8.2 minutes, and it assumes arrivals are independent of the bus schedule. Commuters who check a timetable behave differently.

Why it matters for queues

When a customer arrives at an M/G/1 queue, the delay includes the residual service time of whoever is in service, if the server is busy. By PASTA the arrival finds the server busy with probability ρ. The mean residual service seen is E[S²]/(2E[S]). So the mean work in service seen by an arrival is:

Text
W0 = ρ · E[S²]/(2E[S]) = λ E[S²] / 2

This is exactly the numerator of the P-K formula. The full wait also includes the service of every customer already waiting, which brings the factor 1/(1 - ρ):

Text
Wq = W0 / (1 - ρ)

So the Pollaczek-Khinchine result is the residual-life idea plus the work queued behind it.

Python Estimate the residual service time by simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulated residuals match the formula within sampling noise: about 0.667 for uniform and 0.82 for the two-point distribution.

Design lessons

  • To shorten average waits, reduce variability of service, not only the mean. Standardizing jobs (fixed time slots, packet size limits) pays off.
  • Mixing very short and very long jobs in one queue is costly; separate queues for short jobs (an express lane) can help short customers a lot.
  • Be wary of "average" figures: a customer's experience is dominated by the length-biased view.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Buses arrive with gaps that are regular, exactly 12 minutes. A random passenger's mean wait is

    With c² = 0 the residual is E[X]/2 = 6 minutes.
  2. 2. For exponential intervals with mean 5 minutes, the mean residual life is

    E[X²] = 2·25 = 50, so 50/(2·5) = 5. This is the memoryless property.
  3. 3. Why is the interval containing a random time longer than average?

    The chance of landing in an interval is proportional to its length (length bias).
  4. 4. In M/G/1, the mean work in service seen by an arrival is

    It is ρ times the mean residual service E[S²]/(2E[S]), which simplifies to λE[S²]/2.

Summary

  • A random observer sees a length-biased interval.
  • Mean residual life is E[X²]/(2E[X]): half the mean when regular, equal to the mean when exponential, more when variable.
  • In M/G/1 the numerator λE[S²]/2 of Pollaczek-Khinchine is the mean residual work found by an arrival.
  • Lowering variability lowers the wait.

Next: Phase-Type Service: Erlang and Hyperexponential