{
  "id": "2006.03621",
  "version": "v1",
  "published": "2020-06-05T18:27:46.000Z",
  "updated": "2020-06-05T18:27:46.000Z",
  "title": "Near Equilibrium Fluctuations for Supermarket Models with Growing Choices",
  "authors": [
    "Shankar Bhamidi",
    "Amarjit Budhiraja",
    "Miheer Dewaskar"
  ],
  "comment": "45 pages with a 4 page Appendix",
  "categories": [
    "math.PR"
  ],
  "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 \\le 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 $\\frac{d_n}{\\sqrt{n}\\log n} \\to \\infty$ 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-05T18:27:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K25",
      "68Q87"
    ],
    "keywords": [
      "supermarket model",
      "equilibrium fluctuations",
      "suitable functional limit theorems",
      "growing choices",
      "ordinary differential equations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 45,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}