Importance sampling for Markovian tandem queues using subsolutions: exploring the possibilities

Abstract

We consider importance sampling simulation for estimating the probability of reaching large total number of customers in an $M|M|1$ tandem queue, during a busy cycle of the system. Our main result is a procedure for obtaining a family of asymptotically efficient changes of measure based on subsolutions. We explicitly show these families for two-node tandem queues and we find that there exist more asymptotically efficient changes of measure based on subsolutions than currently available in literature.

1. Introduction

In this paper, we explore possibilities for importance sampling in a Markovian tandem queue. With importance sampling, the underlying probability distributions are changed to speed up a simulation. This change of the probability distributions is also called a change of measure. When exploring the possibilities for a change of measure, we focus on the probability of total buffer overflow during a busy cycle of an $M|M|1$ tandem queue.

This problem was first studied by Parekh and Walrand, ¹ where a state-independent change of measure is suggested based on heuristics. In that paper, the authors note that their change of measure performs poorly in practice in some cases. Afterwards, in Glasserman and Kou, ² necessary and sufficient conditions have been determined for d-node $M|M|1$ tandem queues in order for the same change of measure to be asymptotically efficient (which means that the relative error of the estimator grows less than exponentially fast). These conditions have been extended in the work of de Boer ³ for the case d = 2 and, in that paper, it also has been shown that the change of measure from Parekh and Walrand ¹ is the only state-independent change of measure that may be asymptotically efficient when d = 2. The conclusion of these two papers is that the state-independent change of measure from Parekh and Walrand ¹ for the d-node $M|M|1$ tandem queue is not asymptotically efficient for all input parameters.

To resolve this issue, in the work of Dupuis et al., ⁴ a state-dependent change of measure has been developed for the two-node $M|M|1$ tandem queue such that this change of measure is asymptotically efficient for all input parameters. This change of measure is derived using so-called subsolutions, which have been introduced (in the context of importance sampling) by Dupuis and Wang. ⁵ Afterward, the work from Dupuis et al. ⁴ has been extended to Jackson networks in the work of Dupuis and Wang, ⁶ and to non-Markovian tandem queues in the work of Buijsrogge et al. ⁷ For more details on subsolutions, see also Budhiraja and Dupuis’s, ⁸ Chapters 14 and 15.

Another approach has been developed by Blanchet, ⁹ where an algorithm is presented that gives bounded relative error. This approach uses the time reversed process of Jackson networks. While the time reversed process is known for Jackson networks, this is not the case in other contexts, e.g., for non-Markovian tandem queues. Thus, even though a more efficient simulation approach might exist for the model in the current paper, the approach that we use here is generalizable to processes where the time reversed process is unknown, see, for example, Buijsrogge et al. ⁷ Therefore, we believe that the insights obtained in this paper can be useful for those types of processes.

In addition, in the work of Sezer, ¹⁰ an approximation method has been developed for the two-node $M|M|1$ tandem queue using subsolutions. While the approximation of this probability could be very interesting in some cases, an unbiased simulation might be preferred in other cases or could be used to verify the results. Thus, in this paper, we focus on simulation.

Even though the problem that we consider has been studied previously in^1–4,6,9,11 and asymptotic efficiency of changes of measure based on subsolutions has been shown in some of these works,^4,6,11 still there are “only” three such changes of measure known that have been proven to be asymptotically efficient for the two-node $M|M|1$ tandem queue: two when queue 2 is the bottleneck queue (i.e. ${\mu }_2\le {\mu }_1$ , where ${\mu }_i$ is the service rate of queue i), and one when queue 1 is the bottleneck queue ( ${\mu }_1\le {\mu }_2$ ), see Dupuis et al. ⁴ and Dupuis and Wang. ⁶ However, in the work of Buijsrogge et al., ⁷ we have shown that there are several possible changes of measure based on subsolutions yielding an asymptotically efficient estimator for $\mathrm{GI}|\mathrm{GI}|1$ tandem queues with bounded support. Since the exponential distribution clearly does not have bounded support, this raises some thoughts on whether there exist more asymptotically efficient changes of measure based on subsolutions for the two-node $M|M|1$ tandem queue.

In this paper, we give sufficient conditions for an asymptotically efficient change of measure based on subsolutions for the $M|M|1$ tandem queue. These conditions follow naturally when using the same method as in the works of Dupuis et al. ⁴ and Dupuis and Wang, ⁶ but have never been stated as such. We show how to find changes of measure satisfying these conditions and we believe the same could be done for other models. There is no numerical section as we do not aim for more efficient simulation schemes for the particular tandem model at hand (for which we could simply follow Blanchet ⁹ ), but we aim for providing a procedure to obtain possible schemes based on subsolutions that surely lead to an asymptotically efficient estimator. For more complex models, we do have numerical results, see Buijsrogge et al. ⁷ and Buijsrogge. ¹²

Moreover, in this paper, we consider both ${\mu }_1\le {\mu }_2$ and ${\mu }_2\le {\mu }_1$ . Even though this does not affect the probability of interest, since both queues are interchangeable, ¹³ it is particularly interesting to see the possibilities for a change of measure when ${\mu }_1\le {\mu }_2$ . This is in line with Buijsrogge et al., ⁷ where we have considered both queue 1 and queue 2 being the bottleneck queue (for a two-node $M|M|1$ tandem queue this is equivalent to ${\mu }_1\le {\mu }_2$ and ${\mu }_2\le {\mu }_1$ , respectively). This is in slight contrast with most existing literature on importance sampling for two-node Markovian tandem queues, see for example,^2,3,4,11 where only the second queue being the bottleneck queue has been discussed (i.e., ${\mu }_2\le {\mu }_1$ ).

The contributions of this paper are two-fold. After summarizing the subsolution method for importance sampling and stating the results from Dupuis et al. ⁴ and Dupuis and Wang ⁶ in Section 2, our first contribution is in Section 3, where we state conditions for a change of measure for the d-node $M|M|1$ tandem queue based on subsolutions to give an asymptotically efficient estimator, and we prove that these conditions are sufficient for d = 2. The other contribution, in Section 4, is that we provide a whole family of changes of measure for the two-node $M|M|1$ tandem queue that satisfy these conditions and hence result in an asymptotically efficient estimator. We conclude this paper in Section 5.

2. Model and preliminaries

2.1. The model

In this paper, we consider a d-node $M|M|1$ tandem queue, with arrival rate $\lambda$ and service rates ${\mu }_1$ ,…, ${\mu }_d$ for queues $1,\dots ,d$ , respectively, and we are interested in estimating the probability that the total number of customers in the system reaches some high level N during a busy cycle of the system. Since the case d = 2 has been studied mostly in literature, we mainly consider this case. However, it seems likely that all of the results can also be extended to d > 2 and so we will briefly comment on these extensions when necessary. Thus, we now let d = 2.

We consider the underlying embedded discrete time Markov chain and we assume without loss of generality $\lambda +{\mu }_1+{\mu }_2=1$ . Furthermore, we assume that $\lambda <min\{{\mu }_1,{\mu }_2\}$ , so that the system is stable. As in previous works,^4,6,11 we let the state description be the number of customers in each queue, denoted by ${\mathbf{Z}}_i=(Z_{1,i},Z_{2,i})$ , where $Z_{j,i}$ is the number of customers in queue j after i transitions.

We let ${\mathbf{v}}_k$ denote the possible transitions and $\mathrm{\Theta }({\mathbf{v}}_k)$ their corresponding probabilities, i.e., ${\mathbf{v}}_0=(1,0)$ corresponds to an arrival to the first queue, and has probability $\mathrm{\Theta }({\mathbf{v}}_0)=\lambda$ . Similarly, we have ${\mathbf{v}}_1=(-1,1)$ and ${\mathbf{v}}_2=(0,-1)$ , $\mathrm{\Theta }({\mathbf{v}}_1)={\mu }_1$ and $\mathrm{\Theta }({\mathbf{v}}_2)={\mu }_2$ . The transitions ${\mathbf{v}}_1$ and ${\mathbf{v}}_2$ can only occur when $Z_{1,i}>0$ and $Z_{2,i}>0$ , respectively. If $Z_{j,i}=0$ for some queue j, thus, there are no customers in queue j, we add a self-loop transition with probability ${\mu }_j$ to make sure that the sum of all rates equals 1 (so that all rates are probabilities).

As in the work of Dupuis et al., ⁴ we let ${\mathbf{X}}_i=\frac{1}{N}{\mathbf{Z}}_i$ be the scaled state description, which has the advantage that its elements are in [0,1] and therefore do not increase as N increases. This allows us to make the following definitions:

$$\begin{array}{cc}\multicolumn{1}{c}{D}& =\{(x_1,x_2):x_j>0,x_1+x_2<1\},\hfill \\ \multicolumn{1}{c}{{\delta }_1}& =\{(0,x_2):0<x_2<1\},\hfill \\ \multicolumn{1}{c}{{\delta }_2}& =\{(x_1,0):0<x_1<1\},\hfill \\ \multicolumn{1}{c}{{\delta }_e}& =\{(x_1,x_2):x_j\ge 0,x_1+x_2=1\},\hfill \\ \multicolumn{1}{c}{{\delta }_0}& =\{(0,0)\},\hfill \end{array}$$

and this is sketched in Figure 1.

Figure 1.

A sketch of the scaled state description of the event of interest.

Using these definitions, we can define the first time that the process hits level N in a busy cycle as

$${\tau }_N=inf\{i>0:X_i\in {\delta }_e,{\mathbf{X}}_k\notin {\delta }_0\forall k=1,\dots ,i-1\},$$

and we set ${\tau }_N=\infty$ if the process hits ${\delta }_0$ before ${\delta }_e$ . Therefore, our probability of interest can be written as

$$p_N=\mathbb{P}({\tau }_N<\infty |{\mathbf{X}}_0=(\frac{1}{N},0)).$$

It is known that the asymptotic decay rate of this probability is given by

$$\begin{array}{c}\multicolumn{1}{c}{\gamma \stackrel{.}{=}-\underset{N\to \infty }{lim}\frac{1}{N}\log p_N=-\log \left(\frac{\lambda }{min\{{\mu }_1,{\mu }_2\}}\right)}\\ =min\{{\gamma }_1,{\gamma }_2\},\hfill \end{array}$$

(1)

where ${\gamma }_j=-\log (\lambda /{\mu }_j)$ , see Glasserman and Kou ² and Buijsrogge et al. ¹⁴ The queue for which we have ${\gamma }_j=\gamma$ is called the bottleneck queue. For the $M|M|1$ tandem queue, the bottleneck queue is equivalent to the queue with the largest server utilization. In most papers on similar topics, see, for example, Glasserman and Kou, ² de Boer, ³ Dupuis et al. ⁴ and de Boer and Scheinhardt, ¹¹ it is assumed that ${\mu }_2\le {\mu }_1$ , as for the probability of interest the queues are interchangeable. ¹³ In this paper, we both consider ${\mu }_2\le {\mu }_1$ and ${\mu }_1\le {\mu }_2$ .

2.2. Importance sampling simulation

To estimate our probability of interest using simulation, we use importance sampling. In importance sampling, we perform our simulation under some new measure $\mathbb{Q}$ . Under this new measure, we let $\overline{\mathrm{\Theta }}({\mathbf{v}}_k|\mathbf{x})$ denote the probability for transition ${\mathbf{v}}_k$ given that we are in state $\mathbf{x}$ . While doing the simulation, we keep track of the likelihood ratio $L(\mathcal{P})$ of a path $\mathcal{P}=({\mathbf{X}}_i,i=0,\dots ,{\tau }_N)$ :

$$L(\mathcal{P})=\underset{i=0}{\overset{{\tau }_N-1}{\Pi }}\frac{\mathrm{\Theta }({\mathbf{Y}}_i)}{\overline{\mathrm{\Theta }}({\mathbf{Y}}_i|{\mathbf{X}}_i)},$$

(2)

where ${\mathbf{Y}}_i=({\mathbf{X}}_{i+1}-{\mathbf{X}}_i)N$ if ${\mathbf{X}}_{i+1}\ne {\mathbf{X}}_i$ and ${\mathbf{Y}}_i={\mathbf{v}}_k$ if ${\mathbf{X}}_{i+1}={\mathbf{X}}_i$ and ${\mathbf{X}}_i\in {\delta }_k$ , $k=1,2$ , to include the self-loop transition when one of the queues is empty. Let $I(\mathcal{P})=\mathbb{1}\{{\tau }_N<\infty \}$ indicate whether we have reached our event of interest during a busy cycle of the system or not. Then, under the new measure $\mathbb{Q}$ , we have

$$p_N={\mathbb{E}}^{\mathbb{Q}}[L(\mathcal{P})I(\mathcal{P})],$$

where ${\mathbb{E}}^{\mathbb{Q}}$ denotes the expectation under the new measure $\mathbb{Q}$ . Thus, $L(\mathcal{P})I(\mathcal{P})$ is the estimator for our probability of interest.

As in the work of Dupuis et al., ⁴ we construct a subsolution $W(\mathbf{x})$ – formally defined in Section 2.3 – and we use this function to specify a change of measure in the following way:

$$\overline{\mathrm{\Theta }}({\mathbf{v}}_k|\mathbf{x})=\mathrm{\Theta }({\mathbf{v}}_k)e^{-〈\mathrm{DW}(\mathbf{x}),{\mathbf{v}}_k〉}{e}^{\mathbb{H}(\mathbf{x},\mathrm{DW}(\mathbf{x}))},$$

(3)

where $\mathrm{DW}(\mathbf{x})$ denotes the gradient of $W(\mathbf{x})$ with respect to $\mathbf{x}$ , and where

$$\mathbb{H}(\mathbf{x},\mathrm{DW}(\mathbf{x}))=-\log (\sum _{k=0}^2\mathrm{\Theta }({\mathbf{v}}_k)e^{-〈\mathrm{DW}(\mathbf{x}),{\mathbf{v}}_k〉}).$$

(4)

If we compare Equation (4) with the corresponding notation in the works of Dupuis et al. ⁴ and de Boer and Scheinhardt, ¹¹ a factor 2 is missing. However, we will also scale the function $W(\mathbf{x})$ accordingly, so that the change of measure remains the same.

As we are interested in finding a change of measure that gives an asymptotically efficient estimator for $p_N$ , we need

$$\underset{N\to \infty }{limsup}\frac{1}{N}\log {\mathbb{E}}^{\mathbb{Q}}[L{(\mathcal{P})}^{2}I(\mathcal{P})]\le -2\gamma ,$$

or equivalently,

$$\underset{N\to \infty }{lim\sup }\frac{1}{N}\log \mathbb{E}[L(\mathcal{P})I(\mathcal{P})]\le -2\gamma ,$$

to hold.

In previous works,^4,6,11 a subsolution is constructed (assuming ${\mu }_2\le {\mu }_1$ in the works of Dupuis et al. ⁴ and de Boer and Scheinhardt ¹¹ ) and asymptotic efficiency is proven for a specific choice of $W(\mathbf{x})$ . In this paper, we provide conditions on $W(\mathbf{x})$ and prove that under these conditions, we get an asymptotically efficient estimator. Afterwards, we study the possibilities of the function $W(\mathbf{x})$ , and the corresponding change of measure in Equation (3).

2.3. Subsolution approach

In both Dupuis et al. ⁴ and Dupuis and Wang, ⁶ the change of measure for (two-node) tandem queues (and Jackson networks) has been studied. In those papers, the change of measure has been determined using subsolutions. We first briefly recap the ideas presented in those papers and we start with a formal definition of a subsolution, see also Dupuis et al. ⁴

Definition 2.1

A function $W(\mathbf{x})$ is a classical subsolution if:

1. W is continuously differentiable,

2. $\mathbb{H}(\mathbf{x},\mathrm{DW}(\mathbf{x}))\ge 0$ for every $\mathbf{x}\in D\cup {\delta }_1\cup {\delta }_2\cup {\delta }_e\cup {\delta }_0$ ,

3. $W(\mathbf{x})\le 0$ for $\mathbf{x}\in {\delta }_e$ .

In Dupuis et al., ⁴ there is an additional condition in this definition that needs to hold at the boundaries of the state space. Instead, we include the boundaries of the state space in $\mathbb{H}(\mathbf{x},\mathrm{DW}(\mathbf{x}))$ , i.e., $\mathbb{H}(\mathbf{x},\mathrm{DW}(\mathbf{x}))$ differs along the boundaries (which is similar as in the work of Dupuis and Wang ⁶ ).

It is known from Glasserman and Kou ² and de Boer ³ that for an asymptotically efficient change of measure it is not possible that $\mathrm{DW}(\mathbf{x})$ is constant throughout the whole state space as in the work of Parekh and Walrand, ¹ and in the work of Dupuis et al. ⁴ this is “confirmed,” since the change of measure yielding an asymptotically efficient estimator differs from the change of measure in the work of Parekh and Walrand ¹ along one of the boundaries of the state space and near the origin. Thus, to find an asymptotically efficient change of measure, we determine several (constant) changes of measure for various regions of the state space, in particular along the boundaries of the state space, and combine these so that we have a change of measure for the whole state space.

To determine such a change of measure that differs along various parts of the state space, in the work of Dupuis et al., ⁴ there are multiple – say r– affine functions $W_k^{\delta }(\mathbf{x})$ , $k=1,\dots ,r$ , considered such that for each of these functions $\mathbb{H}(\mathbf{x},{\mathrm{DW}}_k^{\delta }(\mathbf{x}))\ge 0$ for some part of the state space, so that all r functions cover the whole state space, and for at least one of these functions, we have $W_k^{\delta }(\mathbf{x})\le 0$ for $\mathbf{x}\in {\delta }_e$ . All these functions have the following form:

$$W_k^{\delta }(\mathbf{x})=〈{\mathit{\alpha }}_k,\mathbf{x}〉+c_k-d_k\delta ,$$

(5)

where ${\mathit{\alpha }}_k=({\alpha }_{k,1},{\alpha }_{k,2})$ , which we assume to be finite, specifies the gradient of $W_k^{\delta }(\mathbf{x})$ and both $c_k$ and $d_k>0$ are constants. Combining these functions to $W^{\delta }(\mathbf{x})$ by taking the minimum of these functions for all $\mathbf{x}$ , then results in a piecewise affine function, that unfortunately is not continuously differentiable. That is, we have,

$$W^{\delta }(\mathbf{x})=W_1^{\delta }(\mathbf{x})\wedge \dots \wedge W_r^{\delta }(\mathbf{x}).$$

To satisfy the continuous differentiability, which is the first requirement for a function to be a classical subsolution, the functions $W_k^{\delta }(\mathbf{x})$ are combined into a (continuous) function $W^{\epsilon ,\delta }(\mathbf{x})$ by a similar mollification procedure as in the works of Dupuis et al. ⁴ and Dupuis and Wang, ⁵ where in this case we obtain

$$W^{\epsilon ,\delta }(\mathbf{x})=-\epsilon \log \sum _{k=1}^r{e}^{-W_k^{\delta }(\mathbf{x})/\epsilon },$$

(6)

such that $W^{\epsilon ,\delta }(\mathbf{x})$ converges to $W^{\delta }(\mathbf{x})$ when $\epsilon \to 0$ . Throughout this paper, we make the following assumptions on $\epsilon$ and $\delta$ (that depend on N), which also have been made in previous works.^4,6,11 For convenience, we do not write the explicit dependence of $\epsilon$ and $\delta$ on N.

Assumption 2.1

We choose $\epsilon$ and $\delta$ dependent on N, such that

1. $\underset{N\to \infty }{lim}\epsilon =0$ ;  3. $\underset{N\to \infty }{lim}\epsilon N=\infty$ ;

2. $\underset{N\to \infty }{lim}\delta =0$ ;  4. $\underset{N\to \infty }{lim}\frac{\epsilon }{\delta }=0$ .

The gradient of Equation (6) is then used as change of measure in Equation (3). It can be expressed as

$$\begin{array}{c}\multicolumn{1}{c}{D{W}^{\epsilon ,\delta }(\mathbf{x})=\sum _{k=1}^r{\rho }_k(\mathbf{x}){\mathit{\alpha }}_k,}\\ \multicolumn{1}{c}{\mathrm{where}{\rho }_k(\mathbf{x})=\frac{e^{-W_k^{\delta }(\mathbf{x})/\epsilon }}{{\sum }_{j=1}^r{e}^{-W_j^{\delta }(\mathbf{x})/\epsilon }}.}\end{array}$$

(7)

The functions ${\rho }_k(\mathbf{x})$ are weight factors for the “influence” of each function $W_k^{\delta }(\mathbf{x})$ , and so of each different “regional” change of measure, in the final change of measure. They can also be used to define a change of measure slightly different than in Equation (3) as follows, see also Dupuis et al. ⁴ and de Boer and Scheinhardt ¹¹ ,

$$\overline{\mathrm{\Theta }}({\mathbf{v}}_i|\mathbf{x})=\mathrm{\Theta }({\mathbf{v}}_i)\sum _{k=1}^r{\rho }_k(\mathbf{x})e^{-〈{\mathit{\alpha }}_k,{\mathbf{v}}_i〉}{e}^{\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)},$$

(8)

which we will refer to in this paper later on. In fact, we will also show that asymptotic efficiency for the change of measure in Equation (3) implies asymptotic efficiency for the change of measure in Equation (8), similar as in the work of de Boer and Scheinhardt. ¹¹ We note that, from an implementation perspective, the change of measure in Equation (8) is preferred over the change of measure in Equation (3), see also Section 3.8.6 in the work of Dupuis et al. ⁴

2.4. Existing changes of measure

Now that the general ideas of Dupuis et al. ⁴ and Dupuis and Wang ⁶ have been presented, we will show the different functions $W^{\delta }(\mathbf{x})$ that have been used in the works of Dupuis et al. ⁴ and Dupuis and Wang ⁶ to obtain an asymptotically efficient change of measure, as well as figures of the function $W^{\delta }(\mathbf{x})$ for both bottleneck queues j, in the following sections.

2.4.1. Change of measure from Dupuis et al. ⁴

In the work of Dupuis et al., ⁴ queue 2 is always considered to be the bottleneck queue because for the probability of interest, the queues are interchangeable. In that paper, a subsolution $W^{\delta }(\mathbf{x})$ is determined by considering three functions $W_k^{\delta }(\mathbf{x})$ , $k=1,2,3$ . The three functions from Dupuis et al. ⁴ are as follows:

$$\begin{array}{cc}\multicolumn{1}{c}{W_1^{\delta }(\mathbf{x})}& =-{\gamma }_2{x}_1-{\gamma }_2{x}_2+{\gamma }_2-\delta ,\hfill \\ \multicolumn{1}{c}{W_2^{\delta }(\mathbf{x})}& =-{\gamma }_2{x}_1+{\gamma }_2-2\delta ,\hfill \\ \multicolumn{1}{c}{W_3^{\delta }(\mathbf{x})}& ={\gamma }_2-3\delta ,\hfill \end{array}$$

(9)

and the function $W^{\delta }(\mathbf{x})$ is illustrated in Figure 2. We remark that also in the functions in Equation (9), we scaled the results from Dupuis et al. ⁴ (except for the constant in front of $\delta$ ) by a factor 1/2, but this does not influence the resulting changes of measure in Equations (3) and (8).

Figure 2.

The function $W^{\delta }(\mathbf{x})$ from Equation (9). Queue 2 is the bottleneck queue (so ${\gamma }_2\le {\gamma }_1$ ).

2.4.2. Changes of measure from Dupuis and Wang. ⁶

In the work of Dupuis and Wang, ⁶ the work of Dupuis et al. ⁴ is extended to Jackson networks and hence in the work of Dupuis and Wang, ⁶ all queues being the bottleneck queue are considered, as in this paper. Not only the probability that the total number of customers in the system reaches some high level N during a busy cycle of the system is considered in the work of Dupuis and Wang, ⁶ but the authors also consider buffer overflow in a single queue or in several queues at the same time. If we consider a two-node tandem queue with queue 2 being the bottleneck queue, we find that the following four functions are used in Dupuis and Wang ⁶ :

$$\begin{array}{c}{W}_1^{\delta }(\mathbf{x})=-{\gamma }_1{x}_1-{\gamma }_2{x}_2+{\gamma }_2-\delta ,\hfill \\ W_2^{\delta }(\mathbf{x})=-{\gamma }_2{x}_1-{\gamma }_2{x}_2+{\gamma }_2-2\delta ,\hfill \\ W_3^{\delta }(\mathbf{x})=-{\gamma }_1{x}_1+{\gamma }_2-3\delta ,\hfill \\ W_4^{\delta }(\mathbf{x})={\gamma }_2-4\delta ,\hfill \end{array}$$

(10)

and $W^{\delta }(\mathbf{x})$ is illustrated in Figure 3.

Figure 3.

The function $W^{\delta }(\mathbf{x})$ from Equation (10). Queue 2 is the bottleneck queue (so ${\gamma }_2\le {\gamma }_1$ ).

In the work of Dupuis and Wang, ⁶ the authors do not explicitly mention by which constant $\delta$ is multiplied, though implicit requirements with a proof for asymptotic efficiency are given. For simplicity, we use $k\delta$ throughout this paper. It turns out that these values are sufficient for asymptotic efficiency, as we show later in this paper, but we will also see that they are by no means unique.

Since there is no limitation to queue 2 being the bottleneck queue in Dupuis and Wang, ⁶ we also present the result from Dupuis and Wang ⁶ when queue 1 is the bottleneck queue. The result from Dupuis and Wang, ⁶ when queue 1 is the bottleneck queue, is different compared with when queue 2 is the bottleneck queue, even though for the probability of interest both queues are interchangeable. When queue 1 is the bottleneck queue, the following three functions are derived by Dupuis and Wang ⁶ :

$$\begin{array}{c}{W}_1^{\delta }(\mathbf{x})=-{\gamma }_1{x}_1-{\gamma }_2{x}_2+{\gamma }_1-\delta ,\hfill \\ W_2^{\delta }(\mathbf{x})=-{\gamma }_1{x}_1+{\gamma }_1-2\delta ,\hfill \\ W_3^{\delta }(\mathbf{x})={\gamma }_1-3\delta ,\hfill \end{array}$$

(11)

and the resulting function $W^{\delta }(\mathbf{x})$ is illustrated in Figure 4. These subsolutions are very similar to the ones in Equation (10), but with one function less. Also here, the multiplication factor of $\delta$ is not explicitly mentioned, but we use the values above which are sufficient for asymptotic efficiency, as we will show later in this paper.

Figure 4.

The function $W^{\delta }(\mathbf{x})$ from Equation (11). Queue 1 is the bottleneck queue (so ${\gamma }_1\le {\gamma }_2$ ).

2.4.3. Comparison of the existing changes of measure

In this section, we briefly comment on the similarities and differences of the changes of measure from Dupuis et al. ⁴ and Dupuis and Wang. ⁶ We will do so by comparing the functions $W^{\delta }(\mathbf{x})$ for all different cases (see Figures 2–4).

When queue 2 is the bottleneck queue, we see from Figures 2 and 3 that along the x₂-axis the function $W^{\delta }(\mathbf{x})$ is roughly the same. The only difference is that in Figure 3 the function, along the x₂-axis, is $\delta$ lower. In particular, this part of the state space covers the most likely path. In all other parts of the state space, the function $W^{\delta }(\mathbf{x})$ in Figure 3 is slightly steeper than in Figure 2 since ${\gamma }_2<{\gamma }_1$ . These observations suggest that any change of measure based on some function $W^{\delta }(\mathbf{x})$ that somehow lies “in between” the functions in Figures 2 and 3 is also asymptotically efficient. In Section 4, we show that this is indeed the case.

When queue 1 is the bottleneck queue, there is not much to compare. However, since there are already two possibilities for the change of measure based on subsolutions to be asymptotically efficient, and even more to expect, when queue 2 is the bottleneck queue, also the case when queue 1 is the bottleneck queue is studied in Section 4.

3. Sufficient conditions for asymptotic efficiency

Similar to Dupuis et al. ⁴ and Dupuis and Wang, ⁶ the construction of the changes of measure in this paper is based on finding appropriate subsolutions $W^{\epsilon ,\delta }(\mathbf{x})$ . We start with a general proof for asymptotic efficiency for a change of measure based on the subsolution approach and the mollification procedure that is explained in Section 2.3. In our theorem, we provide sufficient conditions for the subsolution yielding an asymptotic efficient change of measure, which we use later for the derivation of the possibilities for the change of measure. Afterwards, we discuss some general observations with respect to some of the conditions in our theorem.

3.1. Main result

Theorem 3.1

Consider a two-node $M|M|1$ tandem queue. Let $W_k^{\delta }(\mathbf{x})$ be affine functions for all $k=1,\dots ,r$ , as in Equation (5), and let the classical subsolution $W^{\epsilon ,\delta }(\mathbf{x})$ be constructed using Equation (6). Then, using the gradient of the function $W^{\epsilon ,\delta }(\mathbf{x})$ as change of measure in Equations (3) and (8) results in an asymptotically efficient estimator if there exist functions $f(N)$ , $g(N)$ , and $h(N)$ with $\underset{N\to \infty }{lim}f(N)=\underset{N\to \infty }{lim}g(N)=\underset{N\to \infty }{lim}h(N)=0$ , such that:

1. $\sum _{k=1}^r{\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)\ge f(N)$ ;

2. $W^{\epsilon ,\delta }(\mathbf{x})\le g(N)$ , for all $\mathbf{x}\in {\delta }_e$ ;

3. $W^{\epsilon ,\delta }(0)\ge \gamma +h(N)$ .

Proof

We start by showing that under the above conditions the change of measure in Equation (3) is asymptotically efficient, after which it follows that also the change of measure in Equation (8) is asymptotically efficient using a similar argument as in Theorem 2 from de Boer and Scheinhardt. ¹¹

From Equations (2) and (3), it follows that the likelihood ratio of a path $L(\mathcal{P})$ is given by

$$\begin{array}{c}\multicolumn{1}{c}{\log L(\mathcal{P})=N\sum _{j=0}^{{\tau }_N-1}〈D{W}^{\epsilon ,\delta }({\mathbf{X}}_j),{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉}\\ -\sum _{j=0}^{{\tau }_N-1}\mathbb{H}({\mathbf{X}}_j,D{W}^{\epsilon ,\delta }({\mathbf{X}}_j)).\hfill \end{array}$$

We find, using Equation (7), that for all states $\mathbf{x}$ we have

$$\mathbb{H}(\mathbf{x},D{W}^{\epsilon ,\delta }(\mathbf{x}))\ge \sum _{k=1}^r{\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k),$$

due to concavity of $\mathbb{H}(\mathbf{x},D{W}^{\epsilon ,\delta }(\mathbf{x}))$ in its second argument, see Proposition 3.2 in the work of Dupuis et al. ⁴ Combining the two expressions above, we arrive at

$$\begin{array}{c}\multicolumn{1}{c}{\log L(\mathcal{P})\le N\sum _{j=0}^{{\tau }_N-1}〈D{W}^{\epsilon ,\delta }({\mathbf{X}}_j),{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉}\\ -\sum _{j=0}^{{\tau }_N-1}\sum _{k=1}^r{\rho }_k({\mathbf{X}}_j)\mathbb{H}({\mathbf{X}}_j,{\mathit{\alpha }}_k)\hfill \end{array}$$

(12)

$$\le N\sum _{j=0}^{{\tau }_N-1}〈D{W}^{\epsilon ,\delta }({\mathbf{X}}_j),{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉-f(N){\tau }_N,$$

(13)

where the last inequality follows from Condition 1.

Similar to Lemma 2 in the work of de Boer and Scheinhardt, ¹¹ also when using r regions, we can obtain the following bound. The idea of this Lemma in de Boer and Scheinhardt ¹¹ is to replace the summation in Equation (13) by $W^{\epsilon ,\delta }({\mathbf{X}}_{{\tau }_N})-W^{\epsilon ,\delta }(0)$ and to give an upper bound on the error that is introduced. Thus, since ${\mathit{\alpha }}_k$ is finite by construction, and hence $|{\mathit{\alpha }}_k|\le c$ for some $0\le c<\infty$ , we find

$$\begin{array}{c}|N\sum _{j=0}^{{\tau }_N-1}〈D{W}^{\epsilon ,\delta }({\mathbf{X}}_j),{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉\hfill \\ \multicolumn{1}{c}{-N(W^{\epsilon ,\delta }({\mathbf{X}}_{{\tau }_N})-W^{\epsilon ,\delta }(0))|\le \frac{5c^2}{\epsilon N}{\tau }_N.}\end{array}$$

(14)

Next, we follow similar steps as in Theorem 1 of the same paper. By combining Equations (13) and (14) we have

$$\begin{array}{c}\multicolumn{1}{c}{\log L(\mathcal{P})\le N(W^{\epsilon ,\delta }({\mathbf{X}}_{{\tau }_N})-W^{\epsilon ,\delta }(0))+\frac{5c^2}{\epsilon N}{\tau }_N-f(N){\tau }_N}\\ \le (g(N)-h(N)-\gamma )N+(\frac{5c^2}{\epsilon N}-f(N)){\tau }_N,\hfill \end{array}$$

where the second inequality follows from Conditions 2 and 3 when ${\mathbf{X}}_{{\tau }_N}\in {\delta }_e$ , and thus, we find, as in de Boer and Scheinhardt, ¹¹

$$\begin{array}{c}\frac{1}{N}\log \mathbb{E}[L(\mathcal{P})I(\mathcal{P})]\hfill \\ =\frac{1}{N}\log (\mathbb{E}[L(\mathcal{P})|I(\mathcal{P})=1]·\mathbb{P}(I(\mathcal{P})=1))\hfill \\ \le \frac{1}{N}\log \left(\mathbb{E}[e^{(g(N)-h(N)-\gamma )N+(\frac{5c^2}{\epsilon N}-f(N)){\tau }_N}|{\tau }_N<\infty ]p_N\right)\hfill \\ =g(N)-h(N)-\gamma +\frac{1}{N}\log \mathbb{E}[e^{(\frac{5c^2}{\epsilon N}-f(N)){\tau }_N}|{\tau }_N<\infty ]\hfill \\ +\frac{1}{N}\log p_N.\hfill \end{array}$$

(15)

To conclude the proof, we need Lemma 3 from de Boer and Scheinhardt, ¹¹ which states that for any sequence ${\theta }_N\ge 0$ such that $\underset{N\to \infty }{lim}{\theta }_N=0$ , we have

$$\underset{N\to \infty }{lim}\frac{1}{N}\log \mathbb{E}[e^{{\theta }_N{\tau }_N}|{\tau }_N<\infty ]=0.$$

(16)

Thus, taking limits in Equation (15) gives

$$\begin{array}{c}\underset{N\to \infty }{lim\sup }\frac{1}{N}\log \mathbb{E}[L(\mathcal{P})I(\mathcal{P})]\hfill \\ \le \underset{N\to \infty }{lim\sup }(g(N)-h(N)-\gamma \hfill \\ \multicolumn{1}{c}{+\frac{1}{N}\log \mathbb{E}[e^{(\frac{5c^2}{\epsilon N}-f(N)){\tau }_N}|{\tau }_N<\infty ]+\frac{1}{N}\log p_N)}\\ =-2\gamma ,\hfill \end{array}$$

(17)

where the last equation follows using Equation (1), $\underset{N\to \infty }{lim}g(N)=\underset{N\to \infty }{lim}h(N)=0$ and since $(\frac{5c^2}{\epsilon N}-f(N))\to 0$ when $N\to \infty$ , we can apply Equation (16) to the fourth term of Equation (17). This concludes the proof for the change of measure in Equation (3).

For the change of measure in Equation (8), we note that similar to de Boer and Scheinhardt, ¹¹ we have

$$\begin{array}{c}\multicolumn{1}{c}{\log L(\mathcal{P})=\log \underset{j=0}{\overset{{\tau }_N-1}{\Pi }}\frac{1}{\sum _{k=1}^r{\rho }_k({\mathbf{X}}_j)e^{-〈{\mathit{\alpha }}_k,{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉}{e}^{\mathbb{H}({\mathbf{X}}_j,{\mathit{\alpha }}_k)}}}\\ =-\sum _{j=0}^{{\tau }_N-1}\log (\sum _{k=1}^r{\rho }_k({\mathbf{X}}_j)e^{-〈{\mathit{\alpha }}_k,{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉}{e}^{\mathbb{H}({\mathbf{X}}_j,{\mathit{\alpha }}_k)})\hfill \\ \le \sum _{j=0}^{{\tau }_N-1}\sum _{k=1}^r{\rho }_k({\mathbf{X}}_j)〈{\mathit{\alpha }}_k,{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉\hfill \\ -\sum _{k=1}^r{\rho }_k({\mathbf{X}}_j)\mathbb{H}({\mathbf{X}}_j,{\mathit{\alpha }}_k)\hfill \\ =\sum _{j=0}^{{\tau }_N-1}〈D{W}^{\epsilon ,\delta }({\mathbf{X}}_j),{\mathbf{X}}_{j+1}-{\mathbf{X}}_j〉\hfill \\ -\sum _{k=1}^r{\rho }_k({\mathbf{X}}_j)\mathbb{H}({\mathbf{X}}_j,{\mathit{\alpha }}_k),\hfill \end{array}$$

where the inequality follows by concavity of the logarithm and the last equality follows by definition of $D{W}^{\epsilon ,\delta }(\mathbf{x})$ , see Equation (7). Thus, we have the same bound as in Equation (12) and so we also find that the change of measure in Equation (8) is asymptotically efficient.□

Remark 3.1

In Equation (17), we see that we end up with some term $g(N)-h(N)-\gamma$ , which goes to $-\gamma$ as $N\to \infty$ . This term arises from bounding $W^{\epsilon ,\delta }({\mathbf{X}}_{{\tau }_N})-W^{\epsilon ,\delta }(0)$ on a path that leads to the overflow level. However, we cannot have $W^{\epsilon ,\delta }({\mathbf{X}}_{{\tau }_N})-W^{\epsilon ,\delta }(0)<-\gamma$ when $N\to \infty$ , since this would contradict with Jensen’s inequality:

$$\underset{N\to \infty }{liminf}\frac{1}{N}\log \mathbb{E}[L(\mathcal{P})I(\mathcal{P})]\ge -2\gamma .$$

That is, it is impossible to obtain a tighter bound. As a result, we find that for an asymptotically efficient change of measure we need $W^{\epsilon ,\delta }({\mathbf{X}}_{{\tau }_N})-W^{\epsilon ,\delta }(0)\to -\gamma$ when $N\to \infty$ on at least one path that leads to reaching the overflow level, e.g., the most likely path, see also Dupuis and Wang. ⁶ Thus, on such a path, we need $\underset{N\to \infty }{lim}{W}^{\epsilon ,\delta }(\mathbf{x})=0$ for $\mathbf{x}\in {\delta }_e$ and $\underset{N\to \infty }{lim}{W}^{\epsilon ,\delta }(0)=\gamma$ .

Remark 3.2

In the sequel, we use a slightly stronger condition than Condition 1 of Theorem 3.1, namely that for each k separately, we have ${\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)\ge f_k(N)$ , where $\underset{N\to \infty }{lim}{f}_k(N)=0$ .

Remark 3.3

It seems likely that Theorem 3.1 can also be extended to a d-node $M|M|1$ tandem queue (and Jackson networks), with the same sufficient conditions as in the current statement for d = 2. To do so, observe that in the proof of Theorem 3.1, Lemma 3 from de Boer and Scheinhardt ¹¹ is the only part that restricts to d = 2 (and hence to tandem queues). Thus, one could either extend this result to d > 2 (and Jackson networks), or use similar techniques as in the works of Dupuis et al. ⁴ and Dupuis and Wang ⁶ in order to show that the theorem holds in a more general setting.

3.2. General observations

Now that we have shown under which conditions we obtain an asymptotically efficient change of measure based on subsolutions, it remains to find ${\mathit{\alpha }}_k$ , $c_k$ and $d_k$ for all $k=1,\dots ,r$ such that Conditions 1, 2, and 3 of Theorem 3.1 are satisfied.

In this section, we make some general observations with respect to Conditions 1 and 3 of Theorem 3.1 when considering a two-node $M|M|1$ tandem queue, that are used later to construct the possibilities for the change of measure. These observations are independent of the bottleneck queue.

3.2.1. Observations with respect to Condition 1 of Theorem 3.1

We recall that the first condition is $\sum _{k=1}^r{\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)\ge f(N)$ for some $f(N)$ with $\underset{N\to \infty }{lim}f(N)=0$ . In this section, we state some observations with respect to $\mathbb{H}(\mathbf{x},\mathit{\alpha })$ for some general $\mathit{\alpha }$ , independent of k, after which we present some observations with respect to ${\rho }_k(\mathbf{x})$ .

By considering all possibilities for $\mathbb{1}\{x_j>0\}$ , $j=1,2$ , in a busy cycle of the system, we find from Equation (4) that

$$\begin{array}{c}\mathbb{H}(\mathbf{x},\mathit{\alpha })=\hfill \\ \{\begin{array}{c}-\log (\lambda e^{-{\alpha }_1}+{\mu }_1{e}^{{\alpha }_1-{\alpha }_2}+{\mu }_2{e}^{{\alpha }_2})\mathrm{if}{x}_1>0,x_2>0,\hfill \\ \multicolumn{1}{c}{-\log (\lambda e^{-{\alpha }_1}+{\mu }_1{e}^{{\alpha }_1-{\alpha }_2}+{\mu }_2)\mathrm{if}{x}_1>0,x_2=0,}\\ \multicolumn{1}{c}{-\log (\lambda e^{-{\alpha }_1}+{\mu }_1+{\mu }_2{e}^{{\alpha }_2})\mathrm{if}{x}_1=0,x_2>0,}\end{array}\hfill \end{array}$$

(18)

We start by finding solutions to $\mathbb{H}(\mathbf{x},\mathit{\alpha })\ge 0$ , for particular parts of the state space, or equivalently to

$$\lambda e^{-{\alpha }_1}+{\mu }_1{e}^{({\alpha }_1-{\alpha }_2)\mathbb{1}\{x_1>0\}}+{\mu }_2{e}^{{\alpha }_2\mathbb{1}\{x_2>0\}}\le 1.$$

(19)

In Lemma 3.2, we consider $x_j>0$ for $j=1,2$ . We fix either ${\alpha }_1$ or ${\alpha }_2$ , and we show for which values of ${\alpha }_2$ or ${\alpha }_1$ Equation (19) holds. In Lemma 3.3, we state two relations considering Equation (19), at one of the boundaries (either $x_1=0$ or $x_2=0$ ) that will be used several times later in this paper. In Sections 4.1–4.4, we use the results of these Lemmas to lower bound $\sum _{k=1}^r{\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)$ , such that Condition 1 of Theorem 3.1 is satisfied.

Lemma 3.2

Suppose $x_j>0$ for $j=1,2$ . We prove the following statements:

• If ${\alpha }_2=-{\gamma }_2$ , then Equation (19) holds iff ${\alpha }_1\in [-\underset{j}{max}{\gamma }_j,-\underset{j}{min}{\gamma }_j]$ ;

• If ${\alpha }_1=-{\gamma }_1$ , then Equation (19) holds iff ${\alpha }_2\in [-{\gamma }_2,0]$ ;

• If ${\alpha }_1=-{\gamma }_2$ , then Equation (19) holds iff ${\alpha }_2\in [-{\gamma }_2,{\gamma }_1-{\gamma }_2]$ ;

• If ${\alpha }_1=0$ , then Equation (19) holds iff ${\alpha }_2\in [0,{\gamma }_1-{\gamma }_2]$ .

Proof

For the first statement, let ${\alpha }_2=-{\gamma }_2$ and $x_j>0$ for $j=1,2$ . Then, Equation (19) reduces to $\lambda e^{-{\alpha }_1}+({\mu }_1{\mu }_2/\lambda )e^{{\alpha }_1}+\lambda \le 1$ which holds if and only if

$$(1-{\mu }_1-{\mu }_2{)}^2{x}^2-({\mu }_1+{\mu }_2)(1-{\mu }_1-{\mu }_2)x+{\mu }_1{\mu }_2\le 0,$$

where we let $x=e^{-{\alpha }_1}$ . Using elementary calculus we find that ${\alpha }_1\in [-\underset{j}{max}{\gamma }_j,-\underset{j}{min}{\gamma }_j]$ . The other statements follow similarly.□

As a result of Lemma 3.2, we can sketch the level set for all ${\alpha }_1$ , ${\alpha }_2$ such that $\mathbb{H}(\mathbf{x},\mathit{\alpha })=0$ for all $\mathbf{x}>0$ , using the concavity of the function shown in the work of Dupuis et al., ⁴ see Figures 5 and 6.

Figure 5.

Sketch of the level set for which $\mathbb{H}(\mathbf{x},\mathit{\alpha })=0$ (i.e., Equation (19) holds with equality) for $\mathbf{x}>$ 0, when queue 2 is the bottleneck queue (and so ${\gamma }_2\le {\gamma }_1$ ).

Figure 6.

Similar to Figure 5, but when queue 1 is the bottleneck queue (and so ${\gamma }_1\le {\gamma }_2$ ).

In the following lemma, we consider Equation (19) at one of the boundaries given a certain choice for either ${\alpha }_1$ or ${\alpha }_2$ . The first equation considers $x_1>0$ , $x_2=0$ and ${\alpha }_1=-{\gamma }_1$ , and the second equation considers $x_1=0$ , $x_2>0$ and ${\alpha }_2=-{\gamma }_2$ .

Lemma 3.3

${\mu }_1+\lambda e^{-{\alpha }_2}+{\mu }_2\le 1$ iff ${\alpha }_2\ge 0$ , and $\lambda e^{-{\alpha }_1}+{\mu }_1+\lambda \le 1$ iff ${\alpha }_1\ge -{\gamma }_2$ .

Proof

The statements follow directly by elementary calculus, combined with $\lambda +{\mu }_1+{\mu }_2=1$ and $\lambda >0$ .□

We conclude this section with a remark on ${\rho }_k(\mathbf{x})$ . Using Equation (7) we find that

$${\rho }_k(\mathbf{x})=\frac{e^{-W_k^{\delta }(\mathbf{x})/\epsilon }}{{\sum }_{i=1}^r{e}^{-W_i^{\delta }(\mathbf{x})/\epsilon }}\le \frac{e^{-W_k^{\delta }(\mathbf{x})/\epsilon }}{e^{-W_{\ell }^{\delta }(\mathbf{x})/\epsilon }}=e^{(W_{\ell }^{\delta }(\mathbf{x})-W_k^{\delta }(\mathbf{x}))/\epsilon },$$

(20)

for any $\ell$ , where the inequality follows trivially.

3.2.2. Observations with respect to Condition 3 of Theorem 3.1

In Remark 3.1, it is noted that we need $\overline{h}(N)\le W^{\epsilon ,\delta }(0)-\gamma \le h(N)$ such that $\underset{N\to \infty }{lim}h(N)=\underset{N\to \infty }{lim}\overline{h}(N)=0$ . This is satisfied when $W_k^{\delta }(0)-\gamma \ge {\overline{h}}_k(N)$ , such that $\underset{N\to \infty }{lim}{\overline{h}}_k(N)=0$ for all k and $W_k^{\delta }(0)-\gamma \le h_k(N)$ , such that $\underset{N\to \infty }{lim}{h}_k(N)=0$ for some k, see Equation (6). By Equation (5), we have $W_k^{\delta }(0)=c_k-d_k\delta$ . Therefore, we find

$$c_k=\gamma \mathrm{for}\mathrm{all}k,$$

as a sufficient condition to satisfy Condition 3 since $\delta \to 0$ when $N\to \infty$ by Assumption 2.1.

As a result of the observations above, to construct the possibilities for the change of measure, it remains to find ${\mathit{\alpha }}_k$ and d_k for all $k=1,\dots ,r$ that satisfy Conditions 1, 2, and 3 of Theorem 3.1. This is the topic of the next section.

4. Construction of the subsolution $W^{\epsilon ,\delta }(\mathbf{x})$

In this section, we construct possible subsolutions, based on the approach mentioned in Section 2.3, that satisfy the conditions in Theorem 3.1 and thus yield an asymptotically efficient estimator. It may not be clear at first sight that the method below results in subsolutions that satisfy all these conditions, since the construction is partly based on intuition. However, we conclude all sections by showing that the conditions are indeed satisfied.

For the two-node $M|M|1$ tandem queue, we consider both possibilities for the bottleneck queue, i.e., we consider both queue 1 and queue 2 as bottleneck queue. In addition, we focus on a maximum of four different regions. More regions may or may not be possible. However, this is undesirable from a practical point of view and does not contribute to an easier implementation of the change of measure.

We start using three regions and queue 2 being the bottleneck queue, since this case has been studied most in literature. Afterwards, we consider three regions and queue 1 the bottleneck queue. We conclude this section with four regions, for which we again consider both queue 2 and queue 1 as the bottleneck, respectively. For brevity, when considering four regions, we will only state the result of the construction (which is similar to the construction when having three regions) and show that indeed the conditions in Theorem 3.1 are satisfied.

4.1. Three regions and queue 2 bottleneck

In this section, our starting point is to consider three functions $W_k^{\delta }(\mathbf{x})$ , $k=1,2,3$ , and we let queue 2 be the bottleneck queue, thus ${\gamma }_2\le {\gamma }_1$ . As the boundaries turned out to be crucial in designing an asymptotically efficient change of measure, we consider the following regions: (i) $x_2>0$ , which also covers $x_1=0$ ; (ii) $x_1>0$ , which also covers $x_2=0$ ; and (iii) $x_1\ge 0$ and $x_2\ge 0$ , so that we have covered the whole state space. All regions overlap in the sense that they all cover the case in which both $x_1>0$ and $x_2>0$ . However, by construction of the continuously differentiable subsolution, in that part of the state space the function $W_k^{\delta }(\mathbf{x})$ of only one of the three regions will be used since we use the minimum of the functions $W_k^{\delta }(\mathbf{x})$ . Clearly, the third region covers the whole state space, but it is important to note that there is no non-trivial solution that satisfies Condition 1 from Theorem 3.1 for the whole state space. The most important part of region three is that it covers $x_1=x_2=0$ .

It turns out that the zero change of measure can be used when both $x_1=x_2=0$ . This may seem strange at first sight, since simulating under the zero change of measure is the same as simulating the original system. However, using this as a starting point for this part of the state space turns out to be a good choice (which is the same choice as in the works of Dupuis et al. ⁴ and Dupuis and Wang ⁶ ). In particular, the condition in Equation (19) for this part of the state space is equivalent to ${\alpha }_{3,1}\ge 0$ . The zero change of measure gives us ${\mathit{\alpha }}_3=({\alpha }_{3,1},{\alpha }_{3,2})=(0,0)$ and hence satisfies the condition mentioned.

The ordering of the regions that we assign can be found in Table 1, the reasons for this ordering will become clear later in this section.

Table 1.

Overview of proposed regions for the case r = 3.

Region	k
$x_2>0$	1
$x_1>0$	2
$x_1\ge 0$ , $x_2\ge 0$	3

4.1.1. Finding ${\mathit{\alpha }}_1$

To find ${\mathit{\alpha }}_1$ , we start with Condition 2, which is $W^{\epsilon ,\delta }(\mathbf{x})\le g(N)$ for all $\mathbf{x}\in {\delta }_e$ , where $\underset{N\to \infty }{lim}g(N)=0$ . In Remark 3.1, it is noted that for the most likely path equality should hold. Trivially, we have $W^{\epsilon ,\delta }(\mathbf{x})\le W_1^{\delta }(\mathbf{x})$ , with equality on the most likely path when $N\to \infty$ , since $W_1^{\delta }(\mathbf{x})$ covers the most likely path. As a result, taking into account Section 3.2.2 and recalling that ${\mathit{\alpha }}_k=({\alpha }_{k,1},{\alpha }_{k,2})$ for all k, we must have ${\alpha }_{1,2}=-{\gamma }_2$ .

Using Condition 1, we can now determine ${\alpha }_{1,1}$ . We only consider the term of the summation from this condition that involves $k=1$ , i.e., ${\rho }_1(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_1)$ should be non-negative for large enough N. As $W_1^{\delta }(\mathbf{x})$ is not designed for $x_2=0$ , the intuition is that the weight factor ${\rho }_1(\mathbf{x})$ tends to 0 for large enough N for all states $\mathbf{x}$ such that $x_2=0$ , see also Equation (28). Thus, using Equation (18) for $\mathit{\alpha }={\mathit{\alpha }}_1$ , we see that for all $\mathbf{x}$ such that $x_2>0$ , we can only satisfy Condition 1, if we have

$$\lambda e^{-{\alpha }_{1,1}}+\frac{{\mu }_1{\mu }_2}{\lambda }{e}^{{\alpha }_{1,1}}+\lambda \le 1,$$

(21)

$$\lambda e^{-{\alpha }_{1,1}}+{\mu }_1+\lambda \le 1,$$

(22)

where we used ${\alpha }_{1,2}=-{\gamma }_2$ . As a result of Lemma 3.2, the first bullet, we find that Equation (21) is satisfied when ${\alpha }_{1,1}\in [-{\gamma }_1,-{\gamma }_2]$ . Using Lemma 3.3, we find that ${\alpha }_{1,1}\ge -{\gamma }_2$ is necessary to satisfy Equation (22), and hence, we must have ${\alpha }_{1,1}=-{\gamma }_2$ . Therefore, we need

$${\mathit{\alpha }}_1=(-{\gamma }_2,-{\gamma }_2),$$

to get an asymptotically efficient change of measure based on Theorem 3.1. For future reference, we remark that as a result of this condition on ${\mathit{\alpha }}_1$ we find, using Equation (18),

$$\begin{array}{c}{\rho }_1(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_1)=\hfill \\ \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0,\hfill \\ \multicolumn{1}{c}{-{\rho }_1(\mathbf{x})\log ({\mu }_1+2{\mu }_2)\mathrm{if}{x}_1>0,x_2=0,}\\ 0\mathrm{if}{x}_1=0,x_2>0,\hfill \end{array}\hfill \end{array}$$

(23)

since $\lambda +{\mu }_1+{\mu }_2=1$ .

4.1.2. Finding ${\mathit{\alpha }}_2$

Using the underlying idea of the construction of the subsolution – i.e., the idea to construct several functions, each for different parts of the state space, that are combined through mollification to obtain a classical subsolution – we determine conditions on ${\mathit{\alpha }}_2$ and d_k for $k=1,2,3$ . For some parts of the state space, it is known which function $W_k^{\delta }(\mathbf{x})$ has to be the minimum of the three functions or cannot be the minimum of the three. For example, when $x_1=0$ , it follows that $W_2^{\delta }(\mathbf{x})$ cannot be the minimum function, since it is designed for $x_1>0$ . As a result, we find that for some parts of the state space, some weight factors ${\rho }_k(\mathbf{x})$ must tend to 0 as $N\to \infty$ .

To start with, we consider the origin of the state space, i.e., $x_1=x_2=0$ . Here, we want $W_3^{\delta }(\mathbf{x})$ to be the minimum function, since this is the only function that is designed for this part of the state space. Thus, we need both $W_3^{\delta }(\mathbf{x})<W_1^{\delta }(\mathbf{x})$ and $W_3^{\delta }(\mathbf{x})<W_2^{\delta }(\mathbf{x})$ for $\mathbf{x}=0$ . Trivially, these inequalities result in

$$d_1<d_3\mathrm{and}{d}_2<d_3.$$

(24)

Second, we consider the boundary $x_2=0$ (and so $x_1>0$ ). At this part of the state space, we want $W_2^{\delta }(\mathbf{x})$ to be the minimum function. Thus, we want to have both

$$W_2^{\delta }(\mathbf{x})<W_1^{\delta }(\mathbf{x})\iff ({\alpha }_{2,1}-{\alpha }_{1,1})x_1<(d_2-d_1)\delta ,$$

(25)

$$\begin{array}{c}\multicolumn{1}{c}{W_2^{\delta }(\mathbf{x})<W_3^{\delta }(\mathbf{x})\iff {\alpha }_{2,1}{x}_1<(d_2-d_3)\delta ,}\end{array}$$

(26)

for all $\mathbf{x}$ such that $x_2=0$ . Clearly, the first inequality holds for all $x_1$ whenever

$${\alpha }_{2,1}\le {\alpha }_{1,1}=-{\gamma }_2\mathrm{and}{d}_1<d_2.$$

(27)

As a result, we immediately have, for all $\mathbf{x}$ such that $x_2=0$ , using Equation (20) for $k=1$ and $\ell =2$ ,

$${\rho }_1(\mathbf{x})\le e^{(({\gamma }_2+{\alpha }_{2,1})x_1+(d_1-d_2)\delta )/\epsilon }\le e^{(d_1-d_2)\delta /\epsilon },$$

(28)

for all ${\alpha }_{2,1}\le -{\gamma }_2$ and since $d_1<d_2$ , the right-hand side tends to 0 as N tends to infinity. This intuitively implies that the weight factor ${\rho }_1(\mathbf{x})$ for $\mathbf{x}$ such that $x_2=0$ tends to 0 when $N\to \infty$ , as suggested in Section 4.1.1, and thus, the change of measure that is designed for $x_2>0$ hardly has any influence when $x_2=0$ .

The second inequality, Equation (26), is satisfied for all $x_1>\frac{(d_3-d_2)\delta }{-{\alpha }_{2,1}}$ , which is positive because ${\alpha }_{2,1}\le -{\gamma }_2<0$ , see Equation (27), and d₂ < d₃. Thus, $W_2^{\delta }(\mathbf{x})$ is the minimum function for all $x_1>\frac{(d_3-d_2)\delta }{-{\alpha }_{2,1}}$ , and note that the right-hand side of this inequality tends to zero as $N\to \infty$ . For all other (very small) $x_1$ , the function $W_3^{\delta }(\mathbf{x})$ is the minimum function. It turns out in the sequel that this is not a problem for the resulting change of measure to be asymptotically efficient, since the function $W_3^{\delta }(\mathbf{x})$ can be used throughout the whole state space. More importantly, $W_1^{\delta }(\mathbf{x})$ is not the minimum function for all $\mathbf{x}$ such that $x_1>0$ and $x_2=0$ whenever Equation (27) holds.

Combining all conditions on d_k, see Equations (24) and (27), we find $d_1<d_2<d_3$ . Here, we see that the choice d_k = k, as in the work of Dupuis et al., ⁴ satisfies all requirements that we have imposed until now to get an asymptotically efficient change of measure based on Theorem 3.1, but it is by no means unique.

Next, we consider the boundary $x_1=0$ (and so $x_2>0$ ). Here, we want $W_1^{\delta }(\mathbf{x})$ to be the minimum function, since all other functions are not designed for this part of the state space. Thus, for all $\mathbf{x}$ such that $x_1=0$ , we want to have both

$$W_1^{\delta }(\mathbf{x})<W_2^{\delta }(\mathbf{x})\iff ({\alpha }_{1,2}-{\alpha }_{2,2})x_2<(d_1-d_2)\delta ,$$

(29)

$$\begin{array}{c}\multicolumn{1}{c}{W_1^{\delta }(\mathbf{x})<W_3^{\delta }(\mathbf{x})\iff {\alpha }_{1,2}{x}_2<(d_1-d_3)\delta }\end{array}.$$

(30)

The first inequality is equivalent to

$$({\alpha }_{2,2}+{\gamma }_2)x_2>(d_2-d_1)\delta ,$$

which unfortunately holds only for $x_2>(d_2-d_1)\delta /({\alpha }_{2,2}+{\gamma }_2)$ , provided that ${\alpha }_{2,2}>-{\gamma }_2$ . Since we do not want $W_2^{\delta }(\mathbf{x})$ to be the minimum function for $\mathbf{x}$ such that $x_1=0$ and $x_2\le (d_2-d_1)\delta /({\alpha }_{2,2}+{\gamma }_2)$ , we need $W_3^{\delta }(\mathbf{x})<W_2^{\delta }(\mathbf{x})$ for those states $\mathbf{x}$ . This condition is equivalent to

$${\alpha }_{2,2}{x}_2>(d_2-d_3)\delta ,$$

(31)

and if ${\alpha }_{2,2}\ge 0$ this inequality holds for all $x_2$ , so in particular for $x_2\le (d_2-d_1)\delta /({\alpha }_{2,2}+{\gamma }_2)$ . So we need

$${\alpha }_{2,2}\ge 0.$$

(32)

As a result, using Equation (20) for $k=2$ and $\ell =3$ , we find for all $\mathbf{x}$ such that $x_1=0$

$${\rho }_2(\mathbf{x})\le e^{(-{\alpha }_{2,2}{x}_2+(d_2-d_3)\delta )/\epsilon }\le e^{(d_2-d_3)\delta /\epsilon }.$$

(33)

Since $d_2<d_3$ , the right-hand side tends to 0 as $N\to \infty$ and this implies that the weight factor ${\rho }_2(\mathbf{x})$ for all $\mathbf{x}$ such that $x_1=0$ tends to 0 as $N\to \infty$ . Therefore, the change of measure that is designed for $x_1>0$ , has hardly any influence when $x_1=0$ .

The second inequality, Equation (30), is satisfied for all $x_2>(d_3-d_1)\delta /{\gamma }_2$ . Thus, $W_1^{\delta }(\mathbf{x})$ is smaller than $W_3^{\delta }(\mathbf{x})$ for all $x_2>(d_3-d_1)\delta /{\gamma }_2$ . As a result, for all $x_2\le (d_3-d_1)\delta /{\gamma }_2$ we have that $W_3^{\delta }(\mathbf{x})$ is the minimum function (which is not a limitation for the resulting change of measure to be asymptotically efficient since this function can be used for the whole state space). Recall that it is more important that $W_2^{\delta }(\mathbf{x})$ is not the minimum function for all $x_1=0$ and $x_2>0$ , and this requirement is satisfied.

To derive a lower bound on ${\alpha }_{2,1}$ and an upper bound on ${\alpha }_{2,2}$ , in contrast to the bounds in Equations (27) and (32), we use Condition 1 of Theorem 3.1. In this case, we only consider the term of the summation from this condition that considers k = 2, since this involves ${\mathit{\alpha }}_2$ . That is, ${\rho }_2(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_2)$ should be non-negative for large enough N. Recall that we have derived an upper bound for ${\rho }_2(\mathbf{x})$ for all $\mathbf{x}$ such that $x_1=0$ , see Equation (33), that tends to 0 as $N\to \infty$ . Thus, for all $\mathbf{x}$ such that $x_1>0$ we see that, using Equation (18) for $\mathit{\alpha }={\mathit{\alpha }}_2$ , we can only satisfy Condition 1, if we have

$$\lambda e^{-{\alpha }_{2,1}}+{\mu }_1{e}^{{\alpha }_{2,1}-{\alpha }_{2,2}}+{\mu }_2{e}^{{\alpha }_{2,2}}\le 1,$$

(34)

$$\lambda e^{-{\alpha }_{2,1}}+{\mu }_1{e}^{{\alpha }_{2,1}-{\alpha }_{2,2}}+{\mu }_2\le 1.$$

(35)

It is clear that, as we have ${\alpha }_{2,2}\ge 0$ from Equation (32), the second inequality is implied by the first inequality. Using Lemma 3.2, Figure 5, and Equations (27) and (32), we find that the first inequality can only be satisfied when

$${\alpha }_{2,1}\in [-{\gamma }_1,-{\gamma }_2]\mathrm{and}{\alpha }_{2,2}\in [0,{\gamma }_1-{\gamma }_2].$$

Clearly, ${\alpha }_{2,1}$ and ${\alpha }_{2,2}$ have a dependence, e.g., ${\alpha }_{2,1}=-{\gamma }_1$ implies ${\alpha }_{2,2}=0$ and ${\alpha }_{2,1}=-{\gamma }_2$ implies ${\alpha }_{2,2}\in [0,{\gamma }_1-{\gamma }_2]$ , see Lemma 3.2 and Figure 5. The dependence can be found in Equation (34), however, this equation cannot be simplified. For future reference, we remark that as a result of these conditions on ${\mathit{\alpha }}_2$ , we find from Equation (18), using ${\alpha }_{2,1}\ge -{\gamma }_1$ and ${\alpha }_{2,2}\le {\gamma }_1-{\gamma }_2$ , that

$${\rho }_2(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_2)\ge \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0,\hfill \\ \multicolumn{1}{c}{0\mathrm{if}{x}_1>0,x_2=0,}\\ \multicolumn{1}{c}{-{\rho }_2(\mathbf{x})\log (3{\mu }_1)\mathrm{if}{x}_1=0,x_2>0,}\end{array}$$

(36)

since $\lambda +{\mu }_1+{\mu }_2=1$ .

4.1.3. Summary and proof that all conditions are satisfied

To summarize, we have found the following values for ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , and ${\mathit{\alpha }}_3$ that intuitively satisfy all conditions for an asymptotically efficient change of measure based on Theorem 3.1, see Table 2.

Table 2.

Possibilities for ${\mathit{\alpha }}_k$ when queue 2 is the bottleneck queue, provided that d₁ < d₂ < d₃.

	${\alpha }_{k,1}$	${\alpha }_{k,2}$	k	Condition
$x_2>0$	$-{\gamma }_2$	$-{\gamma }_2$	1	Equation (34)
$x_1>0$	$[-{\gamma }_1,-{\gamma }_2]$	$[0,{\gamma }_1-{\gamma }_2]$	2
$x_1\ge 0$ , $x_2\ge 0$	0	0	3

We show that these possibilities for ${\mathit{\alpha }}_k$ , $k=1,2,3$ , indeed give an asymptotically efficient change of measure, by considering all conditions in Theorem 3.1. Recall that $\lambda +{\mu }_1+{\mu }_2=1$ implies $\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_3)=0$ . To start with Condition 1, using Equations (23), (28), (33), and (36), we find the following lower bound

$$\begin{array}{c}\multicolumn{1}{c}{\sum _{k=1}^3{\rho }_k(\mathbf{x})(\mathbf{x},{\alpha }_k)}\\ \multicolumn{1}{c}{\ge \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0\hfill \\ \multicolumn{1}{c}{-e^{(d_1-d_2)\delta /\epsilon }\log ({\mu }_1+2{\mu }_2)\mathrm{if}{x}_1>0,x_2=0}\\ \multicolumn{1}{c}{-e^{(d_2-d_3)\delta /\epsilon }\log (3{\mu }_1)\mathrm{if}{x}_1=0,x_2>0}\end{array}}\\ \multicolumn{1}{c}{\ge -e^{max\{d_1-d_2,d_2-d_3\}\delta /\epsilon }\log (3{\mu }_1),}\end{array}$$

where the last step follows since queue 2 is the bottleneck queue, and thus, ${\mu }_2\le {\mu }_1$ . It follows that Condition 1 is satisfied. For Condition 2, we note that for all $\mathbf{x}\in {\delta }_e$ we have $W_1^{\delta }(\mathbf{x})=-d_1\delta$ , and thus, Condition 2 is satisfied since $W^{\epsilon ,\delta }(\mathbf{x})\le W_1^{\delta }(\mathbf{x})$ . To conclude with Condition 3, we find

$$\begin{array}{c}{W}^{\epsilon ,\delta }(0)\ge -\epsilon \log (3e^{-W_3^{\delta }(0)/\epsilon })=-\epsilon \log 3+W_3^{\delta }(0)\hfill \\ =-\epsilon \log 3+{\gamma }_2-d_3\delta ,\hfill \end{array}$$

(37)

which goes to ${\gamma }_2$ as $N\to \infty$ and hence all conditions are satisfied. Therefore, the change of measure for the given possible values of ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , ${\mathit{\alpha }}_3$ and d_k, $k=1,2,3$ , is asymptotically efficient. Note that also the conditions in Remark 3.1 are satisfied, based on the construction.

4.1.4. Discussion

It is clear that the choice of ${\mathit{\alpha }}_2=(-{\gamma }_2,0)$ results in the change of measure from Dupuis et al., ⁴ using d_k = k for $k=1,2,3$ . For this case, $W^{\delta }(\mathbf{x})$ is illustrated in Figure 2. We show some other examples of the piecewise affine function $W^{\delta }(\mathbf{x})$ below, where we let ${\mathit{\alpha }}_2=(-{\gamma }_1,0)$ in Figure 7 and ${\mathit{\alpha }}_2=(-{\gamma }_2,{\gamma }_1-{\gamma }_2)$ in Figure 8. In both cases, we choose d_k = k, $k=1,2,3$ .

Figure 7.

Display of $W^{\delta }(\mathbf{x})$ when queue 2 is the bottleneck queue, ${\mathit{\alpha }}_2=(-{\gamma }_1,0)$ and d_k = k, $k=1,2,3$ .

Figure 8.

Display of $W^{\delta }(\mathbf{x})$ when queue 2 is the bottleneck queue, ${\mathit{\alpha }}_2=(-{\gamma }_2,{\gamma }_1-{\gamma }_2)$ and d_k = k, $k=1,2,3$ .

Choosing ${\alpha }_{2,2}=0$ , we find ${\alpha }_{2,1}\in [-{\gamma }_1,-{\gamma }_2]$ , and thus, $W^{\delta }(\mathbf{x})$ can be “anything in between”Figures 2 and 7. That is, the narrow area next to the $x_1$ -axis in Figure 2 can be as steep as in Figure 7, and anything in between, while the resulting change of measure still gives an asymptotically efficient estimator. Choosing ${\alpha }_{2,1}=-{\gamma }_2$ , we find ${\alpha }_{2,2}\in [0,{\gamma }_1-{\gamma }_2]$ , and thus, $W^{\delta }(\mathbf{x})$ can be “anything in between”Figures 2 and 8. That is, the narrow area next to the $x_1$ -axis in Figure 2 can be slightly tilted, while the resulting change of measure still gives an asymptotically efficient estimator.

We remark that the change of measure that is used for $x_2>0$ is the state-independent change of measure from Parekh and Walrand. ¹ The changes of measure that are found here, can be interpreted as “protecting” the $x_1$ -axis in the sense that we have to apply a different change of measure in that part of the state space. In Figure 7, we protect the $x_1$ -axis quite a lot, rather than in Figure 8, where we only protect it slightly. Recall that the most likely path goes along the $x_2$ -axis, where we have to apply the change of measure from Parekh and Walrand, ¹ which also follows from the subsolution approach. It turns out that the change of measure along the most likely path is very important in the construction of an asymptotically efficient change of measure based on subsolutions and that along the most likely path there is no variation possible for the change of measure. However, it turns out that for all other parts of the state space it is possible to apply a (slightly) different change of measure than the one from Dupuis et al. ⁴ As we have seen in the work of Dupuis and Wang ⁶ and as we will see in Section 4.3, it is also possible to apply a different change of measure in the interior of the state space, rather than the same change of measure as along the most likely path or the change of measure that is applied along the $x_1$ -axis.

4.2. Three regions and queue 1 bottleneck

In this section, we again consider three functions $W_k^{\delta }(\mathbf{x})$ , $k=1,2,3$ , but in contrast to Section 4.1, we now let queue 1 be the bottleneck queue, so ${\gamma }_1\le {\gamma }_2$ . The regions that we consider in this section are the same as in the previous section (see Table 1). By changing the bottleneck queue, the most likely path also changes and, therefore, we start the construction of an asymptotically efficient change of measure based on Theorem 3.1 by finding ${\mathit{\alpha }}_2$ .

4.2.1. Finding ${\mathit{\alpha }}_2$

To find ${\mathit{\alpha }}_2$ , we start with Condition 2, as in Section 4.1.1, and we use Remark 3.1 to determine ${\alpha }_{2,1}$ . When queue 1 is the bottleneck queue, the most likely path is covered by $W_2^{\delta }(\mathbf{x})$ . Therefore, we find ${\alpha }_{2,1}=-{\gamma }_1$ .

Next, we use Condition 1 to determine ${\alpha }_{2,2}$ . Considering the term of the summation in this condition that involves k = 2, we need ${\rho }_2(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_2)$ to be non-negative for large enough N. For those parts of the state space where $x_1=0$ , we will find in the sequel that the weight factor ${\rho }_2(\mathbf{x})$ tends to 0 as $N\to \infty$ . Since the function $W_2^{\delta }(\mathbf{x})$ is designed for $x_1>0$ , it is expected that in that case the weight factor ${\rho }_2(\mathbf{x})$ does not tend to 0 as $N\to \infty$ . Thus, using Equation (18) for $\mathit{\alpha }={\mathit{\alpha }}_2$ , for all $\mathbf{x}$ such that $x_1>0$ we see that we can only satisfy Condition 1 from Theorem 3.1 if we have

$$\begin{array}{c}{\mu }_1+\lambda e^{-{\alpha }_{2,2}}+{\mu }_2{e}^{{\alpha }_{2,2}}\le 1,\hfill \\ {\mu }_1+\lambda e^{-{\alpha }_{2,2}}+{\mu }_2\le 1,\hfill \end{array}$$

where we used ${\alpha }_{2,1}=-{\gamma }_1$ . Using the second bullet of Lemma 3.2 and Lemma 3.3, we find that both of the above conditions hold when ${\alpha }_{2,2}=0$ . Thus, to get an asymptotically efficient change of measure based on Theorem 3.1, we need

$${\mathit{\alpha }}_2=(-{\gamma }_1,0).$$

For future reference, we remark that as a result of this condition we find, using Equation (18) and $\lambda +{\mu }_1+{\mu }_2=1$ ,

$$\begin{array}{c}{\rho }_2(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_2)=\hfill \\ \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0,\hfill \\ \multicolumn{1}{c}{0\mathrm{if}{x}_1>0,x_2=0,}\\ \multicolumn{1}{c}{-{\rho }_2(\mathbf{x})\log (2{\mu }_1+{\mu }_2)\mathrm{if}{x}_1=0,x_2>0.}\end{array}\hfill \end{array}$$

(38)

4.2.2. Finding ${\mathit{\alpha }}_1$

As in Section 4.1.2, we use the underlying idea of the construction of subsolutions to determine conditions on ${\mathit{\alpha }}_2$ and d_k for $k=1,2,3$ . Since this approach has been fully explained in Section 4.1.2, we will skip most of the details and highlight the results.

By considering the origin of the state space, i.e., $x_1=x_2=0$ , we immediately find the same result as in Equation (24), since that result is independent of ${\mathit{\alpha }}_1$ and ${\mathit{\alpha }}_2$ .

Next, we consider the boundary $x_2=0$ (and so $x_1>0$ ) and recall that in that case, we want $W_2^{\delta }(\mathbf{x})$ to be the minimum function. The conditions that follow from this observation can be found in Equations (25) and (26). Since we have determined that ${\mathit{\alpha }}_2=(-{\gamma }_1,0)$ , these conditions are equivalent to

$$\begin{array}{l}({\alpha }_{1,1}+{\gamma }_1)x_1>(d_1-d_2)\delta ,\\ {\gamma }_1{x}_1>(d_3-d_2)\delta .\end{array}$$

(39)

The first condition is satisfied when

$${\alpha }_{1,1}\ge -{\gamma }_1\mathrm{and}{d}_1<d_2,$$

(40)

since then the right-hand side of the inequality is negative. Similarly to Equation (28) we find

$${\rho }_1(\mathbf{x})\le e^{((-{\gamma }_1-{\alpha }_{1,1})x_1+(d_1-d_2)\delta )/\epsilon }\le e^{(d_1-d_2)\delta /\epsilon },$$

(41)

and so the weight factor ${\rho }_1(\mathbf{x})$ for $\mathbf{x}$ such that $x_2=0$ tends to zero when $N\to \infty$ .

For the second condition, see Equation (39), we find that this is satisfied for all $x_1>\frac{(d_3-d_2)\delta }{{\gamma }_1}$ , and so for small values of $x_1$ the function $W_3^{\delta }(\mathbf{x})$ is the minimum function. It turns out that this is not a problem for the resulting change of measure to be asymptotically efficient, since the function $W_3^{\delta }(\mathbf{x})$ can be used throughout the whole state space and since $W_2^{\delta }(\mathbf{x})<W_1^{\delta }(\mathbf{x})$ for all $\mathbf{x}$ such that $x_2=0$ . Therefore, it is ruled out that $W_1^{\delta }(\mathbf{x})$ is the minimum function for these $\mathbf{x}$ , as desired.

At the boundary $x_1=0$ (and so $x_2>0$ ), we want $W_1^{\delta }(\mathbf{x})$ to be the minimum function. As a result, we want Equations (29) and (30) to hold. These conditions are equivalent to

$$\begin{array}{c}{\alpha }_{1,2}{x}_2<(d_1-d_2)\delta ,\hfill \\ {\alpha }_{1,2}{x}_2<(d_1-d_3)\delta .\hfill \end{array}$$

Clearly, both conditions are satisfied when the second condition holds, since d₂ < d₃. In particular, we need

$${\alpha }_{1,2}<0,$$

since d₁ < d₃, so that both conditions are satisfied for all $x_2>\frac{(d_3-d_1)\delta }{-{\alpha }_{1,2}}$ . To prevent $W_2^{\delta }(\mathbf{x})$ from being the minimum function for $\mathbf{x}$ such that $x_1=0$ and $x_2\le \frac{(d_3-d_1)\delta }{-{\alpha }_{1,2}}$ , we need $W_3^{\delta }(\mathbf{x})<W_2^{\delta }(\mathbf{x})$ for those states $\mathbf{x}$ . This condition is equivalent to Equation (31), and since ${\alpha }_{2,2}=0$ and d₂ < d_3, this condition is always satisfied. As a result, we find for all $\mathbf{x}$ such that $x_1=0$ that Equation (33) holds.

To get a tighter condition for ${\alpha }_{1,2}$ we use Condition 2 from Theorem 3.1. That is, for all $\mathbf{x}$ on the exit boundary we need to have $W^{\epsilon ,\delta }(\mathbf{x})\le g(N)$ such that $g(N)\to 0$ when $N\to \infty$ . As we have $W^{\epsilon ,\delta }(\mathbf{x})\to W^{\delta }(\mathbf{x})$ when $N\to \infty$ , we in particular need $W_1^{\delta }(\mathbf{x})$ to be non-positive for large enough N when $x_1=0$ and $x_2=1$ , since $W_1^{\delta }(\mathbf{x})$ is designed to be the minimum function at the boundary $x_1=0$ (and so $x_2>0$ ). Therefore we find

$${\alpha }_{1,2}\le -{\gamma }_1.$$

(42)

Using the same condition of Theorem 3.1, we also derive an upper bound on ${\alpha }_{1,1}$ . Consider $W_2^{\delta }(\mathbf{x})=-{\gamma }_1{x}_1+{\gamma }_1-d_2\delta$ , which is non-positive for all $x_1\ge ({\gamma }_1-d_2\delta )/{\gamma }_1$ . Thus, for all $x_1<({\gamma }_1-d_2\delta )/{\gamma }_1$ , we need $W_1^{\delta }(\mathbf{x})$ to be non-positive for all $\mathbf{x}\in {\delta }_e$ . On the exit boundary we have $x_1+x_2=1$ , so we find that for all $\mathbf{x}\in {\delta }_e$ , using Equation (42),

$$\begin{array}{c}\multicolumn{1}{c}{W_1^{\delta }(\mathbf{x})={\alpha }_{1,1}{x}_1+{\alpha }_{1,2}(1-x_1)+{\gamma }_1-d_1\delta }\\ \le ({\alpha }_{1,1}+{\gamma }_1)x_1-d_1\delta ,\hfill \end{array}$$

which goes to zero as $N\to \infty$ if and only if ${\alpha }_{1,1}\le -{\gamma }_1$ . Combining with Equation (40) we find

$${\alpha }_{1,1}=-{\gamma }_1.$$

To conclude, we derive a lower bound on ${\alpha }_{1,2}$ using Condition 1. We only consider the term of the summation in Condition 1 that involves k = 1. That is, ${\rho }_1(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_1)$ should be non-negative for large enough N. We do not expect that ${\rho }_1(\mathbf{x})\to 0$ when $N\to \infty$ for all $\mathbf{x}$ such that $x_2>0$ , as $W_1^{\delta }(\mathbf{x})$ is designed for $x_2>0$ . Thus, using Equation (18) for $\mathit{\alpha }={\mathit{\alpha }}_1$ , for all $\mathbf{x}$ such that $x_2>0$ , we see that we can only satisfy Condition 1, if we have

$${\mu }_1+\lambda e^{-{\alpha }_{1,2}}+{\mu }_2{e}^{{\alpha }_{1,2}}\le 1,$$

(43)

$${\mu }_1+{\mu }_1+{\mu }_2{e}^{{\alpha }_{1,2}}\le 1,$$

(44)

where we have used that ${\alpha }_{1,1}=-{\gamma }_1$ . Using Equation (42), it follows that the second inequality is implied by the first inequality. Using Lemma 3.2, the second bullet, we find that Equation (43) is satisfied when ${\alpha }_{1,2}\in [-{\gamma }_2,-{\gamma }_1]$ , and so is Equation (44). For future reference, we remark that as a result of this condition we find, using Equation (18) and ${\alpha }_{1,2}\ge -{\gamma }_2$ ,

$$\begin{array}{c}{\rho }_1(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_1)\ge \hfill \\ \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0,\hfill \\ \multicolumn{1}{c}{-{\rho }_1(\mathbf{x})\log ({\mu }_1+2{\mu }_2)\mathrm{if}{x}_1>0,x_2=0,}\\ \multicolumn{1}{c}{0\mathrm{if}{x}_1=0,x_2>0,}\end{array}\hfill \end{array}$$

(45)

since $\lambda +{\mu }_1+{\mu }_2=1$ .

4.2.3. Summary and proof that all conditions are satisfied

Summarizing, we have found the following values for ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , and ${\mathit{\alpha }}_3$ that intuitively satisfy all conditions for an asymptotically efficient change of measure based on Theorem 3.1, see Table 3.

Table 3.

Possibilities for ${\mathit{\alpha }}_k$ when queue 1 is the bottleneck queue, provided that d₁ < d₂ < d₃.

	${\alpha }_{k,1}$	${\alpha }_{k,2}$	k
$x_2>0$	$-{\gamma }_1$	$[-{\gamma }_2,-{\gamma }_1]$	1
$x_1>0$	$-{\gamma }_1$	0	2
$x_1\ge 0$ , $x_2\ge 0$	0	0	3

Again, we show by considering all conditions in that theorem, indeed these possibilities for ${\mathit{\alpha }}_k$ , $k=1,2,3$ , give an asymptotically efficient change of measure. We start with Condition 1. First, recall that $\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_3)=0$ , since ${\mathit{\alpha }}_3=0$ and $\lambda +{\mu }_1+{\mu }_2=1$ . Then, from Equations (33), (38), (41), and (45), we find

$$\begin{array}{c}\sum _{k=1}^3{\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)\hfill \\ \ge \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0\hfill \\ \multicolumn{1}{c}{-e^{(d_1-d_2)\delta /\epsilon }\log ({\mu }_1+2{\mu }_2)\mathrm{if}{x}_1>0,x_2=0}\\ \multicolumn{1}{c}{-e^{(d_2-d_3)\delta /\epsilon }\log (2{\mu }_1+{\mu }_2)\mathrm{if}{x}_1=0,x_2>0}\end{array}\hfill \\ \ge -e^{max\{(d_1-d_2),(d_2-d_3)\}\delta /\epsilon }\log (3{\mu }_2),\hfill \end{array}$$

where the final inequality follows since ${\mu }_1\le {\mu }_2$ and so Condition 1 of Theorem 3.1 is satisfied. For Condition 2, we note for all $\mathbf{x}\in {\delta }_e$ we have $W_1^{\delta }(\mathbf{x})\le -d_1\delta$ , and thus, Condition 2 is satisfied, since $W^{\epsilon ,\delta }(\mathbf{x})\le W_1^{\delta }(\mathbf{x})$ . To conclude with Condition 3, we find a similar lower bound to $W^{\epsilon ,\delta }(0)$ as in Equation (37), with ${\gamma }_2$ replaced by ${\gamma }_1$ , since queue 1 is the bottleneck queue. Therefore, the change of measure for the given possible values of ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , ${\mathit{\alpha }}_3$ , and d_k, $k=1,2,3$ is asymptotically efficient.

4.2.4. Discussion

For d_k = k for $k=1,2,3$ , it is clear that choosing ${\mathit{\alpha }}_1=(-{\gamma }_1,-{\gamma }_2)$ results in the change of measure from Dupuis and Wang ⁶ and, for this case, $W^{\delta }(\mathbf{x})$ is illustrated in Figure 4. Another example for $W^{\delta }(\mathbf{x})$ , where we choose ${\mathit{\alpha }}_1=(-{\gamma }_1,-{\gamma }_1)$ , is illustrated in Figure 9.

Figure 9.

Display of $W^{\delta }(\mathbf{x})$ when queue 1 is the bottleneck queue, ${\mathit{\alpha }}_1=(-{\gamma }_1,-{\gamma }_1)$ and d_k = k, $k=1,2,3$ .

As can be seen in Table 3, ${\alpha }_{1,2}$ can range from $-{\gamma }_2$ to $-{\gamma }_1$ , and thus, $W^{\delta }(\mathbf{x})$ can be “anything in between”Figures 4 and 9. That is, the area next to the $x_2$ -axis and in the interior in Figure 9 can be as steep as in Figure 4 and anything in between. Note that Figure 9 is very similar to Figure 2 in the sense that ${\gamma }_2$ is replaced by ${\gamma }_1$ , and so in particular when ${\gamma }_1={\gamma }_2$ the change of measure based on this function $W^{\delta }(\mathbf{x})$ can be used.

When queue 1 is the bottleneck queue, we find that the state-independent change of measure from Parekh and Walrand ¹ is only used around $x_2=0$ . While when queue 2 is the bottleneck queue, the change of measure based on $W^{\epsilon ,\delta }(\mathbf{x})$ can be interpreted as that we have to “protect” the $x_1$ -axis, see also Section 4.1, it seems natural that we have to “protect” the $x_2$ -axis when queue 1 is the bottleneck queue. Looking at Figures 4 and 9, we see that this is clearly not the case. One could argue that in this way we are “overprotecting” the $x_2$ -axis. However, it turns out that for an asymptotically efficient change of measure based on subsolutions we only need to have the state-independent change of measure from Parekh and Walrand ¹ along the most likely path, which in this case is along the $x_1$ -axis.

4.3. Four regions and queue 2 bottleneck

In this section, the starting point is to use four functions $W_k^{\delta }(\mathbf{x})$ , $k=1,2,3,4$ , and we let queue 2 be the bottleneck queue, thus ${\gamma }_2\le {\gamma }_1$ . The regions that we consider can be found in Table 4, and the only difference compared with Section 4.1, where we considered three regions, is that we now have a dedicated region in case $x_j=0$ for some queue j.

Table 4.

Overview of proposed regions for the case r = 4.

Region	k
$x_1>0$ , $x_2>0$	1
$x_1=$ , $x_2>0$	2
$x_1>0$ , $x_2=$	3
$x_1\ge 0$ , $x_2\ge 0$	4

The zero change of measure is used when both $x_1=x_2=0$ , for similar reasons as in Section 4.1. The only difference is that we now set ${\mathit{\alpha }}_4=0$ , instead of ${\mathit{\alpha }}_3=0$ as in Section 4.1.

The derivation for using four regions is very similar as when using two regions and, therefore, it is omitted in this paper. A detailed derivation can be found in Buijsrogge. ¹²

4.3.1. Summary and proof that all conditions are satisfied

We have found the following values for ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , ${\mathit{\alpha }}_3$ , and ${\mathit{\alpha }}_4$ that intuitively satisfy all requirements for an asymptotically efficient change of measure based on Theorem 3.1, see Table 5.

Table 5.

Possibilities for ${\mathit{\alpha }}_k$ when queue 2 is the bottleneck queue, provided that d₁ < d₂ < d₃ < d₄.

	${\alpha }_{k,1}$	${\alpha }_{k,2}$	k	Conditions
$x_1>0$ , $x_2>0$	$[-{\gamma }_1,-{\gamma }_2]$	$-{\gamma }_2$	1
$x_1=$ , $x_2>0$	$-{\gamma }_2$	$-{\gamma }_2$	2
$x_1>0$ , $x_2=$	$[-{\gamma }_1,{\alpha }_{1,1}]$	$[0,{\gamma }_1-{\gamma }_2]$	3	$\begin{array}{c}\lambda e^{-{\alpha }_{3,1}}+{\mu }_1{e}^{{\alpha }_{3,1}-{\alpha }_{3,2}}+{\mu }_2{e}^{{\alpha }_{3,2}}\le 1\hfill \\ {\alpha }_{3,1}+{\alpha }_{3,2}\ge {\alpha }_{1,1}-{\gamma }_2\hfill \end{array}$
$x_1\ge 0$ , $x_2\ge 0$	0	0	4

We show that these possibilities for ${\mathit{\alpha }}_k$ , $k=1,2,3,4$ , indeed give an asymptotically efficient change of measure, by considering all conditions in Theorem 3.1. Recall that $\lambda +{\mu }_1+{\mu }_2=1$ implies $\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_4)=0$ . To start with Condition 1 of Theorem 3.1, we find that

$$\begin{array}{c}\sum _{k=1}^4{\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)\hfill \\ \ge \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0\hfill \\ \multicolumn{1}{c}{-e^{(d_1-d_3)\delta /\epsilon }\log (2{\mu }_1+{\mu }_2)}\\ \multicolumn{1}{c}{-e^{(d_2-d_3)\delta /\epsilon }\log ({\mu }_1+2{\mu }_2)\mathrm{if}{x}_1>0,x_2=0}\\ \multicolumn{1}{c}{-e^{(d_1-d_2)\delta /\epsilon }\log (2{\mu }_1+\lambda )}\\ \multicolumn{1}{c}{-e^{(d_3-d_4)\delta /\epsilon }\log (3{\mu }_1)\mathrm{if}{x}_1=0,x_2>0}\end{array}\hfill \\ \ge -2e^{max\{(d_2-d_3),(d_1-d_2),(d_3-d_4)\}\delta /\epsilon }\log (3{\mu }_1),\hfill \end{array}$$

where the first step follows by conveniently substituting the upper and lower bounds on ${\mathit{\alpha }}_k$ from Table 5 and the last step follows since queue 2 is the bottleneck queue, and hence $\lambda <{\mu }_2\le {\mu }_1$ , and since d₁ < d₂ < d₃ < d₄. It follows that Condition 1 is satisfied. For Condition 2, we note that for all $\mathbf{x}\in {\delta }_e$ we have $W_2^{\delta }(\mathbf{x})=-d_2\delta$ , and thus, Condition 2 is satisfied since $W^{\epsilon ,\delta }(\mathbf{x})\le W_2^{\delta }(\mathbf{x})$ . Condition 3 follows similarly as in Equation (37). Therefore, the change of measure for the given possible values of ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , ${\mathit{\alpha }}_3$ , ${\mathit{\alpha }}_4$ , and $d_k$ , $k=1,2,3,4$ , is asymptotically efficient.

4.3.2. Discussion

From Table 5, we again see that the change of measure from Parekh and Walrand ¹ is used for $x_1=0$ and $x_2>0$ , as expected, since it is the region in which the most likely path lies. Clearly, the result in the work of Dupuis and Wang ⁶ satisfies the conditions in Table 5. Recall that in that paper also different overflow probabilities are considered, which imposes additional constraints for an asymptotically efficient change of measure based on subsolutions. The change of measure from Dupuis and Wang, ⁶ where in particular ${\mathit{\alpha }}_1=(-{\gamma }_1,-{\gamma }_2)$ and ${\mathit{\alpha }}_3=(-{\gamma }_1,0)$ , can be found in Figure 3.

From the results in Table 5, it is also clear that we could adapt Figure 3 such that along the $x_1$ -axis we have a similar affine function as in Figure 7 or Figure 8. However, when choosing ${\mathit{\alpha }}_3=(-{\gamma }_2,{\gamma }_1-{\gamma }_2)$ , as we did for ${\mathit{\alpha }}_2$ in Figure 8, we need ${\alpha }_{1,1}=-{\gamma }_2$ and so the functions $W_1^{\delta }(\mathbf{x})$ and $W_2^{\delta }(\mathbf{x})$ are almost the same. That is, only their constants d₁ and d₂ would differ.

Summarizing, at the $x_1$ -axis, we can make similar adaptations as when we considered three regions in Section 4.1. The difference is that now also in the interior we can “push” the function a bit more toward the origin when we compare with Figure 2.

4.4. Four regions and queue 1 bottleneck

In this section, we again consider four functions $W_k^{\delta }(\mathbf{x})$ , $k=1,2,3,4$ , but in contrast to Section 4.3, we let queue 1 be the bottleneck queue, i.e., ${\gamma }_1\le {\gamma }_2$ . The regions that we consider in this section are the same as in the previous section (see Table 4). Again, the derivation for using four regions is very similar as when using two regions and therefore it is omitted in this paper. Recall that a detailed derivation can be found in the work of Buijsrogge. ¹²

4.4.1. Summary and proof that all conditions are satisfied

We have found the following values for ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , ${\mathit{\alpha }}_3$ , and ${\mathit{\alpha }}_4$ that intuitively satisfy all conditions for an asymptotically efficient change of measure based on Theorem 3.1, see Table 6.

Table 6.

Possibilities for ${\mathit{\alpha }}_k$ when queue 1 is the bottleneck queue, provided that d₁ < d₂ < d₃ < d₄. There is no simple expression for the maximum value that ${\alpha }_{2,1}$ could possibly attain and it is therefore denoted with *. It should satisfy the conditions stated (see also Figure 6).

	${\alpha }_{k,1}$	${\alpha }_{k,2}$	k	Conditions
$x_1>0$ , $x_2>0$	$-{\gamma }_1$	$[-{\gamma }_2,-{\gamma }_1]$	1
$x_1=$ , $x_2>0$	$[-{\gamma }_1{,}^{*}]$	$[-{\gamma }_2,{\alpha }_{1,2}]$	2	$\begin{array}{c}\lambda e^{-{\alpha }_{2,1}}+{\mu }_1{e}^{{\alpha }_{2,1}-{\alpha }_{2,2}}+{\mu }_2{e}^{{\alpha }_{2,2}}\le 1\hfill \\ {\alpha }_{2,1}+{\alpha }_{2,2}\ge -{\gamma }_1+{\alpha }_{1,2}\hfill \end{array}$
$x_1>0$ , $x_2=$	$-{\gamma }_1$	$0$	3
$x_1\ge 0$ , $x_2\ge 0$	0	0	4

Again, we show by considering all conditions in that theorem, indeed these possibilities for ${\mathit{\alpha }}_k$ , $k=1,2,3,4$ , give an asymptotically efficient change of measure. We start with Condition 1, and recall that $\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_4)=0$ . Then, we find that

$$\begin{array}{c}\sum _{k=1}^4{\rho }_k(\mathbf{x})\mathbb{H}(\mathbf{x},{\mathit{\alpha }}_k)\hfill \\ \ge \{\begin{array}{c}0\mathrm{if}{x}_1>0,x_2>0\hfill \\ \multicolumn{1}{c}{-e^{(d_1-d_3)\delta /\epsilon }\log ({\mu }_1+2{\mu }_2)}\\ \multicolumn{1}{c}{-e^{(d_2-d_3)\delta /\epsilon }\log ({\mu }_1+({\mu }_1{\mu }_2/\lambda )e^{*}+{\mu }_2)}\\ \multicolumn{1}{c}{\mathrm{if}{x}_1>0,x_2=0}\\ \multicolumn{1}{c}{-e^{(d_1-d_2)\delta /\epsilon }\log (2{\mu }_1+{\mu }_2\lambda /{\mu }_1)}\\ \multicolumn{1}{c}{-e^{(d_3-d_4)\delta /\epsilon }\log (2{\mu }_1+{\mu }_2)\mathrm{if}{x}_1=0,x_2>0}\end{array}\hfill \\ \ge -2e^{max\{(d_1-d_2),(d_2-d_3),(d_3-d_4)\}\delta /\epsilon }·\hfill \\ \log (max\{3{\mu }_2,2{\mu }_2+{\mu }_2^2{e}^{*}/\lambda \}),\hfill \end{array}$$

where the first step follows by conveniently substituting the upper and lower bounds on ${\mathit{\alpha }}_k$ from Table 6 and the final inequality follows since queue 1 is the bottleneck queue, and thus, ${\mu }_1\le {\mu }_2$ . It follows that Condition 1 is satisfied. For Condition 2, we note that for all $\mathbf{x}\in {\delta }_e$ we have $W_1^{\delta }(\mathbf{x})\le -d_1\delta$ , and thus, Condition 2 is satisfied since $W^{\epsilon ,\delta }(\mathbf{x})\le W_1^{\delta }(\mathbf{x})$ . Condition 3 follows similarly as in Equation (37), with ${\gamma }_2$ replaced by ${\gamma }_1$ , since queue 1 is the bottleneck queue. Therefore, the change of measure for the given possible values of ${\mathit{\alpha }}_1$ , ${\mathit{\alpha }}_2$ , ${\mathit{\alpha }}_3$ , ${\mathit{\alpha }}_4$ , and d_k, $k=1,2,3,4$ , is asymptotically efficient.

4.4.2. Discussion

From Table 6, we see that for $x_1>0$ and $x_2=0$ the change of measure from Parekh and Walrand ¹ is used, as expected. The difference compared with using three regions in Section 4.2 is that there is a possibility to apply a slightly different change of measure for $x_1=0$ and $x_2>0$ . In Figure 10, we show an example when choosing ${\mathit{\alpha }}_1=(-{\gamma }_1,-{\gamma }_1)$ , ${\mathit{\alpha }}_2=(0,-{\gamma }_1)$ and ${\mathit{\alpha }}_3=(-{\gamma }_1,0)$ . These values for ${\mathit{\alpha }}_2$ can only occur when $-{\gamma }_1\ge {\gamma }_1-{\gamma }_2$ .

Figure 10.

Display of $W^{\delta }(\mathbf{x})$ when queue 1 is the bottleneck queue, ${\mathit{\alpha }}_1=(-{\gamma }_1,-{\gamma }_1)$ , ${\mathit{\alpha }}_2=(0,-{\gamma }_1)$ and d_k = k, $k=1,2,3,4$ .

Comparing with Figure 9, we see that in the area close to the $x_2$ -axis, we can apply a slightly different change of measure. Of course, there are several other possibilities.

5. Conclusion

In this paper, we determined sufficient conditions for subsolution-based changes of measure to give asymptotically efficient estimators. As a result, for the two-node $M|M|1$ tandem queue, we explicitly gave a whole family (continuum) of changes of measure that all lead to asymptotically efficient estimators, and the previously known changes of measure are just three members of this family. For d-node tandem queues, it seems likely that we can use a similar analysis to find a family of changes of measure that are asymptotically efficient.

For the case d = 2, we like to highlight one particular change of measure based on the subsolution $W^{\epsilon ,\delta }(\mathbf{x})$ in Equation (6) (via either Equation (3) or Equation (8)), that uses the following three functions:

$$\begin{array}{c}{W}_1^{\delta }(\mathbf{x})=-\gamma x_1-\gamma x_2+\gamma -\delta ,\hfill \\ W_2^{\delta }(\mathbf{x})=-\gamma x_1+\gamma -2\delta ,\hfill \\ W_3^{\delta }(\mathbf{x})=\gamma -3\delta ,\hfill \end{array}$$

where we recall that $\gamma =min\{{\gamma }_1,{\gamma }_2\}$ . We note that this is the same subsolution as in the work of Dupuis et al. ⁴ if queue 2 is the bottleneck queue, while it also works when queue 1 is the bottleneck queue (with ${\gamma }_2$ replaced by ${\gamma }_1$ ). This matches nicely with the known fact that interchanging the queues leaves our probability of interest unchanged.

From an implementation point of view with respect to subsolutions, in general, it makes sense to use as few regions as possible, i.e., three regions (or d + 1 in the d-node case). However, when the event of interest is not total buffer overflow, but, e.g., individual buffer overflow or simultaneous buffer overflows, it may be more useful to implement the change of measure from Dupuis and Wang ⁶ that is based on four regions.

Finally, we mention that future work could aim at investigating whether or not the method generalizes to more general models, which we expect to be the case. In the work of Buijsrogge et al., ⁷ something similar has already been done for non-Markovian tandem queues, but one could also think about more general (non-Markovian) networks, for which we expect similar results to hold.