Asymptotic distributions and chaos for the supermarket model. (English) Zbl 1131.60005

Luczak, Malwina J.; McDiarmid, Colin

Electron. J. Probab. 12, 75-99 (2007).

Summary: In the supermarket model there are \(n\) queues, each with a unit rate server. Customers arrive in a Poisson process at rate \(\lambda n\), where \(0 < \lambda < 1\). Each customer chooses \(d\geq 2\) queues uniformly at random, and joins a shortest one.
It is known that the equilibrium distribution of a typical queue length converges to a certain explicit limiting distribution as \(n\to \infty \). We quantify the rate of convergence by showing that the total variation distance between the equilibrium distribution and the limiting distribution is essentially of order \(n^{-1}\); and we give a corresponding result for systems starting from quite general initial conditions (not in equilibrium). Further, we quantify the result that the systems exhibit chaotic behaviour: we show that the total variation distance between the joint law of a fixed set of queue lengths and the corresponding product law is essentially of order at most \(n^{-1}\).

MSC:

60C05	Combinatorial probability
68R05	Combinatorics in computer science
90B22	Queues and service in operations research
60K25	Queueing theory (aspects of probability theory)