# Near Equilibrium Fluctuations for Supermarket Models with Growing Choices

Shankar Bhamidi, Amarjit Budhiraja, Miheer Dewaskar

October 2020
### Abstract

We consider the supermarket model in the usual Markovian setting where jobs arrive at rate $n \lambda_n$ for some $\lambda_n>0$, with $n$ parallel servers each processing jobs in its queue at rate 1. An arriving job joins the shortest among $d_n≤n$ randomly selected service queues. We show that when $d_n \to \infty$ and $\lambda_n \to \lambda \in (0, \infty)$ under natural conditions on the initial queues, the state occupancy process converges in probability, in a suitable path space, to the unique solution of an infinite system of constrained ordinary differential equations parametrized by $\lambda$. Our main interest is in the study of fluctuations of the state process about its near equilibrium state in the critical regime, namely when $\lambda_n \to 1$. Previous papers have considered the regime $d_n \gg \sqrt{n} \log n$ while the objective of the current work is to develop diffusion approximations for the state occupancy process that allow for all possible rates of growth of $d_n$. In particular we consider the three canonical regimes (a) $d_n/\sqrt{n} \to 0$; (b) $d_n/\sqrt{n} \to c \in (0,\infty)$ and, (c) $d_n/\sqrt{n} \to \infty$. In all three regimes we show, by establishing suitable functional limit theorems, that (under conditions on $\lambda_n$) fluctuations of the state process about its near equilibrium are of order $n^{-1/2}$ and are governed asymptotically by a one dimensional Brownian motion. The forms of the limit processes in the three regimes are quite different; in the first case we get a linear diffusion; in the second case we get a diffusion with an exponential drift; and in the third case we obtain a reflected diffusion in a half space. In the special case $d_n/(\sqrt{n}\log n) \to \infty$ our work gives alternative proofs for the universality results established by Mukherjee et al in 2018.

Publication

Submitted to the Annals of Applied Probability

###### PhD Candidate

My research interests include theoretical statistics, stochastic processes, and randomized algorithms.