A Unified Approach to the Heavy-Traffic Analysis of the Maximum of Random Walks

Abstract

For families of random walks $\{S_k^{(a)}\}$ with $\mathbf E S_k^{(a)} = -ka < 0$ we consider their maxima $M^{(a)} = \sup_{k \ge 0} S_k^{(a)}$. We investigate the asymptotic behavior of $M^{(a)}$ as $a \to 0$ for random walks from the domain of attraction of a stable law. This problem appeared first in the 1960s in the analysis of a single-server queue when the traffic load tends to 1, and since then it is referred to as the heavy-traffic approximation problem. Kingman and Prokhorov suggested two different approaches which were later followed by many authors. We give two elementary proofs of our main result, using each of these approaches. It turns out that the main technical difficulties in both proofs are rather similar and may be resolved via a generalization of the Kolmogorov inequality to the case of an infinite variance. Such a generalization is also obtained in this paper.