Derive the Pollaczek–Khinchine formula via mean residual work

ProofAdvanced⏱ 3 hoursAI SystemsM/G/1residual lifeinspection paradoxvariance

Problem

For an M/G/1 queue with arrival rate $\lambda$ and service time $S$ , $\rho = \lambda\E[S]<1$ .

Show that the mean residual service time observed at a random instant, given the server is busy, is $\E[S^2]/(2\E[S])$ .
Using PASTA and Little's law, derive $\E[W_q] = \lambda\E[S^2]/(2(1-\rho))$ .
Rewrite in terms of the coefficient of variation $c_s$ and evaluate the ratio of M/D/1 to M/M/1 mean wait at the same $\rho$ .
Explain what goes wrong when $\E[S^2] = \infty$ , and give a service-time distribution for which this happens while $\E[S]$ is finite.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints — 0 of 2 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
The Δ²/12 noise variance	Quantization	Proof	Beginner	15 min
Derive the M/M/1 queue from detailed balance	AI Systems	Proof	Intermediate	1 hour
Mini-batching and the compute budget	SGD	Numerical	Intermediate	30 min
Simulate M/M/1 and verify the utilisation wall run	AI Systems	Coding	Intermediate	1 hour
The 1/n variance rate requires uncorrelated samples	Probability	Numerical	Intermediate	30 min