Heavy-traffic asymptotics for the single-server queue with random order of service

We consider the GI/GI/1 queue with customers served in random order, and derive the heavy-traffic limit of the waiting-time distribution. Our proof is probabilistic, requires no finite-variance assumptions, and makes the intuition provided by Kingman (Math. Oper. Res. 7 (1982) 262) rigorous.