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

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}\).


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