Large deviations without principle: join the shortest queue (Q811979): Difference between revisions

Let \(y_n = (y_n (t):t \in [0,T])\) for \(n = 0,1,\dots\) be stochastic processes with sample paths in \(D([0,T],R_+^K)\) (right continuous functions \([0,T] \to R_ + ^K \) with left limits; the space is equipped with the Skorokhod metric). The sequence \(\{ y_n \} \) is said to satisfy the large deviation principle with rate function \(I( \cdot )\) if \(I\) is nonnegative, lower semicontinuous, and for all \(x \in R_ + ^K \) and for all closed \(C \subset D([0,T],R_+^K)\): \[ \lim \sup_{n \to \infty } \frac{1} {n}\log P_x (y_n \in C) \leqslant -\inf_{\varphi \in C:\varphi (0) = x} I(\varphi ), \] and for all \(x \in R_+^K \) and for all open \(G \subset D([0,T],R_+^K)\): \[ \lim \inf_{n \to \infty } \frac{1} {n}\log P_x (y_n \in G) \geqslant -\inf_{\varphi \in G:\varphi (0) = x} I(\varphi ). \] (The subscript \(x\) means conditioning on \(y_n (0)\) so that \(\lim_{n \to \infty } y_n (0) = x\)). The paper studies a system of queues with exponential servers, which share an arrival stream. Arrivals are routed to the (weighted) shortest queue. The goal is to derive large deviation type estimates for the most likely behavior, the most likely path to overflow and the probability of overflow.