State-Dependent Importance Sampling for a Slow-Down Tandem Queue; Probability rept

摘要

In this paper we investigate an advanced variant of the classical (Jackson) tandem queue, i.e., a two-node system with server slow-down. The slow-down mechanism has the primary objective to protect the downstream queue from frequent overflows, and it does so by reducing the service speed of the upstream queue as soon as the number of jobs in the downstream queue reaches some pre-specified threshold. To assess the efficacy of such a policy, techniques are needed for evaluating overflow metrics of the second queue. We focus on the estimation of the probability of the following rare event - overflow in the downstream queue before exhausting the system, starting from any given state in the state space. Due to the rarity of the event under consideration, naive, direct Monte Carlo simulation is often infeasible. We therefore rely on the application of importance sampling to obtain variance reduction. The principal contribution of this paper is that we construct an importance sampling scheme that is asymptotically efficient. In more detail, the paper addresses the following issues: (1) We rely on powerful heuristics to identify the exponential decay rate of the probability under consideration, and verify this result by applying sample-path large deviations techniques; (2) Immediately from these heuristics, we develop a proposal for a change of measure to be used in importance sampling; and (3) We prove that the resulting algorithm is asymptotically efficient, which effectively means that the number of runs required to obtain an estimate with fixed precision grows subexponentially in the buffer size. We stress that our method to prove asymptotic efficiency is substantially shorter and more straightforward than those usually provided in the literature. Also our setting is more general than the situations analyzed so far, as we allow the process to start off at any state of the state space, and in addition we do not impose any conditions on the values of the arrival rate and service rates, as long as the underlying queueing system is stable.