Large Deviation Asymptotics for the Supermarket Model with Growing Choices
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915441433116672 |
|---|---|
| author | Budhiraja, Amarjit Wu, Ruoyu |
| author_facet | Budhiraja, Amarjit Wu, Ruoyu |
| contents | We consider the Markovian supermarket model with growing choices, where jobs arrive at rate $nλ_n$ and each of $n$ parallel servers processes jobs in its queue at rate $1$. Each incoming job joins the shortest among $d_n \in \{1,\dotsc,n\}$ randomly selected queues. Under the assumption $d_n \to \infty$ and $λ_n \to λ\in (0,\infty)$ as $n\to \infty$, a large deviation principle (LDP) for the occupancy process is established in a suitable infinite-dimensional path space, and it is shown that the rate function is invariant with respect to the manner in which $d_n \to \infty$. The LDP gives information on the rate of decay of probabilities of various types of rare events associated with the system. We illustrate this by establishing explicit exponential decay rates for probabilities of large total number of jobs in the system. As a corollary, we also show that probabilities of certain rare events can indeed depend on the rate of $d_n \to \infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08586 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Large Deviation Asymptotics for the Supermarket Model with Growing Choices Budhiraja, Amarjit Wu, Ruoyu Probability Optimization and Control 60F10, 60J74, 34H05, 90B15 We consider the Markovian supermarket model with growing choices, where jobs arrive at rate $nλ_n$ and each of $n$ parallel servers processes jobs in its queue at rate $1$. Each incoming job joins the shortest among $d_n \in \{1,\dotsc,n\}$ randomly selected queues. Under the assumption $d_n \to \infty$ and $λ_n \to λ\in (0,\infty)$ as $n\to \infty$, a large deviation principle (LDP) for the occupancy process is established in a suitable infinite-dimensional path space, and it is shown that the rate function is invariant with respect to the manner in which $d_n \to \infty$. The LDP gives information on the rate of decay of probabilities of various types of rare events associated with the system. We illustrate this by establishing explicit exponential decay rates for probabilities of large total number of jobs in the system. As a corollary, we also show that probabilities of certain rare events can indeed depend on the rate of $d_n \to \infty$. |
| title | Large Deviation Asymptotics for the Supermarket Model with Growing Choices |
| topic | Probability Optimization and Control 60F10, 60J74, 34H05, 90B15 |
| url | https://arxiv.org/abs/2508.08586 |