Departures from many queues in series (Q1182683)

Consider a series of \(n\) queues with a common service time distribution, and let \(D(k,n)\) denote the departure time of customer \(k\), assuming that initially \(k\) customers are placed in the first queue. The limiting behaviour of \(D(k,n)\) as \(n\to\infty\) is studied in various regimes for \(k\): if \(k\) is fixed, \((D(k,n)-n)/\sqrt n\) converges in distribution to a certain functional of \(k\)-dimensional Brownian motion; if \(k=k_ n\approx xn^{1-\varepsilon}\), \((D(k,n)-n)/\sqrt {nk}\) converges in probability to a constant independent of \(x\); and if \(k_ n\approx xn\), then \(D(k,n)/n\) converges in probability to a constant dependent on \(x\) (this result may be interpreted as a hydrodynamic limit). A basic observation is a duality between \(k\) and \(n\), which is obtained by expressing \(D(k,n)\) as the maximum partial sum of service times over paths of length \(k+n-1\) in a \(k\times n\) lattice of service times. The techniques involve weak convergence in function spaces, strong approximations and the subadditive ergodic theorem.