Large deviation asymptotics for the supermarket model with growing choices

We consider the Markovian supermarket model with growing choices, where jobs arrive at rate <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n lamda Subscript n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:msub> <mml:mi> λ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">n\lambda _{n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and each of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> parallel servers processes jobs in its queue at rate <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1"> <mml:semantics> <mml:mn>1</mml:mn> <mml:annotation encoding="application/x-tex">1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Each incoming job joins the shortest among <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript n Baseline element-of StartSet 1 comma ellipsis comma n EndSet"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo> ∈ </mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">d_{n} \in \{1,\dotsc ,n\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> randomly selected queues. Under the assumption <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript n Baseline right-arrow normal infinity"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false"> → </mml:mo> <mml:mi mathvariant="normal"> ∞ </mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">d_{n} \to \infty</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda Subscript n Baseline right-arrow lamda element-of left-parenthesis 0 comma normal infinity right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi> λ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false"> → </mml:mo> <mml:mi> λ </mml:mi> <mml:mo> ∈ </mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi mathvariant="normal"> ∞ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda _{n} \to \lambda \in (0,\infty )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> as <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n right-arrow normal infinity"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo stretchy="false"> → </mml:mo> <mml:mi mathvariant="normal"> ∞ </mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n\to \infty</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript n Baseline right-arrow normal infinity"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false"> → </mml:mo> <mml:mi mathvariant="normal"> ∞ </mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">d_{n} \to \infty</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript n Baseline right-arrow normal infinity"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false"> → </mml