MURAL - Maynooth University Research Archive Library



    Large deviation asymptotics for busy periods


    Duffy, Ken R. and Meyn, Sean P. (2014) Large deviation asymptotics for busy periods. Stochastic Systems, 4 (1). pp. 300-319. ISSN 1946-5238

    [img]
    Preview
    Download (856kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    The busy period for a queue is cast as the area swept under the random walk until it first returns to zero. Encompassing non-i.i.d. increments, the large-deviations asymptotics of the busy period B is addressed, under the assumption that the increments satisfy standard conditions, including a negative drift. The main conclusions provide insight on the probability of a large busy period, and the manner in which this occurs. The scaled probability of a large busy period has the asymptote, for any b > 0, \begin{align*} \lim_{n\to\infty} \frac{1}{\sqrt{n}} \log P(B\geq bn) = -K\sqrt{b}, \end{align*} where \begin{align*} K = 2 \sqrt{-\int_0^{\lambda^*} \Lambda(\theta) \, d\theta}\,, \quad \hbox{with $\lambda^*=\sup\{\theta:\Lambda(\theta)\leq0\}$,} \end{align*} and with Λ denoting the scaled cumulant generating function of the increments process. The most likely path to a large swept area is found to be a simple rescaling of the path on [0, 1] given by ψ* (t) = −Λ (λ* (1 − t))/λ* . In contrast to the piecewise linear most likely path leading the random walk to hit a high level, this is strictly concave in general. While these two most likely paths have distinctly different forms, their derivatives coincide at the start of their trajectories, and at their first return to zero. These results partially answer an open problem of Kulick and Palmowski [18] regarding the tail of the work done during a busy period at a single server queue. The paper concludes with applications of these results to the estimation of the busy period statistics (λ* ,K) based on observations of the increments, offering the possibility of estimating the likelihood of a large busy period in advance of observing one.

    Item Type: Article
    Additional Information: Published under a Creative Commons Attribution License (CCAL). You are free to copy, distribute, display, and perform the work, to make derivative works, to make commercial use of the work under the following condition of Attribution: others must attribute the work if displayed on the web or stored in any electronic archive by making a link back to the website of the Journal via its Digital Object Identifier (DOI), or if published in other media by acknowledging prior publication in this Journal with a precise citation including the DOI. For any further reuse or distribution, the same terms apply. Any of these conditions can be waived by permission of The Corresponding Author.
    Keywords: Integrated random walks; busy periods; large deviations; sample paths;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 5967
    Identification Number: https://doi.org/10.1214/13-SSY098
    Depositing User: Dr Ken Duffy
    Date Deposited: 13 Mar 2015 15:27
    Journal or Publication Title: Stochastic Systems
    Publisher: Institute for Operations Research and the Management Sciences (INFORMS), Applied Probability Society
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year