Analysis of A Two-queue Discrete-time Model with Random Alternating Service Under High Occupancy in One Queue

Abstract

We investigate a discrete-time two-queue system with a single server. At the beginning of every time slot, the single server randomly selects either queue 1 or queue 2 to serve. The decision of the server to select either queue 1 or queue 2 in each time slot is independent of the state of the system and is determined by a single parameter. The service times of the customers are deterministically equal to 1 time slot. The numbers of arrivals into both queues during consecutive slots are characterized by a joint probability generating function. By extending prior research, we analyze the behavior of the system as the number of customers in the first queue approaches infinity, thereby obtaining exact asymptotics for the stationary joint probability distribution of customer numbers in both queues.

1 Introduction

This paper studies the stationary joint distribution of the system contents of a discrete-time two-queue system with one server that uses a randomly alternating scheduling discipline.

A randomly alternating scheduling discipline means that the server randomly switches between queues, independent of the number of customers present at each queue. Multi-queue systems where a single server selects a queue for service according to some rule are commonly referred to as polling systems. There is a substantial body of literature on various polling mechanisms; for comprehensive reviews and applications (up to 2021), see (Borst 2018; Vishnevsky and Semenova 2021). However, studies of polling systems with a randomly alternating service discipline are relatively scarce. To the best of our knowledge, the first analysis of such a polling system appeared in de Haan et al. (2009). In that study, the authors investigated a continuous-time multi-queue system where the server remains at each queue for an exponentially distributed time before switching, regardless of the number of customers, and allows for generally distributed switch-over times. This type of scheduling discipline was initially referred to as the autonomous-server discipline (Al Hanbali et al. 2012), and later as the pure (exponential) time-limited policy (De Haan et al. 2020). This model has been primarily motivated by the need to evaluate the performance of (mobile) ad hoc networks. In Saxena et al. (2017); Kapodistria et al. (2023), the authors have focused on the two-queue version of de Haan et al. (2009) but without switch-over times.

The motivation to study the discrete-time queueing model of the present paper stems from earlier work, starting with Devos et al. (2019). In our model, the server randomly alternates between serving queue 1 and queue 2 in the following way. In each discrete time step, the server is allocated to queue 1 or queue 2 with probabilities denoted as $\alpha$ and $1 - \alpha$, respectively. The service time of any customer in either queue is equal to 1 time slot, ensuring that service is non-preemptive. The arrival process is characterized by specifying the numbers of arrivals, in both queues during consecutive slots, instead of the discrete inter-arrival times. It is assumed that the numbers of arrivals in both queues during consecutive slots are i.i.d. with any given joint probability generating function, denoted as A(x, y). Note that the numbers of arrivals in both queues during a slot may be dependent.

We assume that the two queues, which are $Geo^X/D/1$ queues with Bernoulli interruptions when viewed in isolation (Bruneel and Kim 1993, Ch. 3.2), are stable. We focus on the stationary joint distribution of the system contents. However, an exact analysis of this model is extremely hard for a general joint arrival distribution because the system contents in this queueing model correspond to a two-dimensional random walk in the positive quadrant. Notice that this random walk has state transitions between non-neighboring states since an arbitrary number of customers can arrive in any slot in each of the two queues for general joint arrival distribution. Interested readers are directed to Cohen and Boxma (1983); Fayolle et al. (2017) for both an overview and a thorough examination of this topic. The most prominent techniques to date for computing the steady-state joint distribution of the system contents (if possible) include the boundary-value approach, the compensation method, the uniformization method, and the power-series technique. A recent overview of these four approaches is given in the introduction of Bruneel and Devos (2023).

This paper’s contribution is finding the exact asymptotics of the stationary joint distribution of the system contents. Therefore, the results presented in this work are closely related to the asymptotic analysis of two-dimensional Markov chains. One of the main challenges in this analysis is that, in general, no analytical expression for the joint probability generating function is available. Despite this difficulty, the tail asymptotic problem for two-dimensional queueing models has been extensively investigated over the past two decades, particularly in the context of nearest-neighbor random walks. There are mainly three alternative methods to study tail asymptotics for stationary distributions, namely large-deviations theory, matrix-analytic methods, and complex-function methods. Readers interested in a more exhaustive review of the literature are directed to Miyazawa (2011), which provides an extensive survey up to 2011, complemented by recent advancements discussed in Ozawa (2022) and Zhao (2022).

Our approach in the present paper relies on ideas developed by Bruneel and Devos (2023), who studied a system of two parallel queues, each having their dedicated server, and where arrivals in both queues during consecutive slots are i.i.d. with a common probability generating function denoted as A(x, y). The approach in Bruneel and Devos (2023) considers the steady-state behavior of the system under the condition that the content of queue 1 becomes very high (approaches infinity). This conditional system, referred to as the “asymptotic system” in Bruneel and Devos (2023), turns out to be nearly identical to the original (unconditional) system, but with a modified joint arrival probability generating function that can be explicitly computed from A(x, y). This approach yielded exact asymptotics for the stationary joint distribution of the system contents. The approach avoids the intricacies of analytic continuation, as seen in complex-function methods (Li and Zhao 2011, 2018; Zhao 2022), by focusing on the conditional asymptotic behavior of the two-queue system when one queue becomes temporarily overloaded. Standard singularity analysis is then applied to the resulting conditional transforms.

A significant distinction between Bruneel and Devos 2023 and the current study is the presence of an additional stochastic process, namely the state of the single server determining which queue gets access to the server during each slot. Whereas Bruneel and Devos (2023) involves a single source of coupling between the two queues, the current study deals with two sources of coupling. Despite this additional difficulty, we are able to obtain a similar result to that presented in Bruneel and Devos (2023), namely that the asymptotic behavior of our system remains of the same type as the original system: independent arrivals from slot to slot and independent server allocations from slot to slot, but with modified parameters that can be explicitly calculated from the original system parameters. Furthermore, in this asymptotic system, the arrival process and the state of the server remain statistically independent. This is the main motivation and novelty of this paper, namely to show that the technique in Bruneel and Devos (2023) can be extended to coupled queues involving also stochasticity at the output of the system.

The paper is structured as follows: Section 2 presents preliminary results for the model. Section 3 outlines the mathematical focus, proving our main result, detailed in Section 4. Section 5 discusses the conditions under which this result holds true. Section 6 illustrates our methodology through specific examples of arrival distributions. Finally, Section 7 concludes by suggesting further extensions of our approach.

2 Preliminaries

2.1 Mathematical Model and Basic Notations

In the present paper we aim to study a discrete-time queueing model with two queues with infinite capacity and sharing one server, shown in Fig. 1. Since time is assumed to be discrete, the time axis is divided into fixed-length intervals referred to as (time) slots. Within each slot, the server is exclusively available to one of the two queues. We assume that the server is available to queue 1 during a slot with probability $\alpha$, independently from slot to slot. Consequently, the server is available to queue 2 during a slot with probability $1-\alpha$. Finally, we assume that each customer’s service requires precisely one slot.

We are concerned with the system contents in both queue 1 and queue 2, where the system content refers to the number of customers in the queue, including the customer currently being served (if any). The system contents at the beginning of slot k are denoted by $u_{1,k}$ and $u_{2,k}$, with the first index $*$ of $u_{*,k}$ distinguishing between the two queues. The evolution of $\{u_{1,k}, u_{2,k} \}$ is defined by the system equations:

$$\begin{aligned} u_{1,k+1}&= a_{1,k} + (u_{1,k} - r_{k})^+ \;, \end{aligned}$$

(1)

$$\begin{aligned} u_{2,k+1}&= a_{2,k} + (u_{2,k} - 1 + r_{k})^+ \;. \end{aligned}$$

(2)

In our notation, $(x)^+$ denotes $\max (0, x)$, and $\{a_{1,k}, a_{2,k}\}$ represents a sequence of i.i.d. nonnegative discrete random vectors. These vectors share a common joint probability generating function (PGF) denoted as $A(z_1, z_2)$., i.e.,

$$ A(z_1,z_2) := \text {E}[z_1^{a_{1,k}} z_2^{a_{2,k}}] \;. $$

Additionally, $\{r_k\}$ constitutes a sequence of i.i.d. Bernoulli random variables with parameter $\alpha$. The random variable $r_k$ models the number of available servers (0 or 1) for queue 1 during slot k. The random variables $a_{1,k}$ and $a_{2,k}$ are to be understood as the numbers of arrivals during slot k at queue 1 and queue 2, respectively. Notice that we incorporate the possibility that the numbers of arrivals in different queues (within a slot) are correlated. We furthermore define the marginal PGF of the number of arrivals in queue j per slot as

$$ A_j(z) := {\left\{ \begin{array}{ll} A(z,1), & j=1 \;, \\ A(1,z), & j=2 \;. \end{array}\right. } $$

We also denote the mean number of arrivals in queue j per slot by $\lambda _j = A_j^{\prime }(1)$.

Fig. 1

The randomly alternating service model

To ensure stability, it is assumed that

$$\begin{aligned} \lambda _1<\alpha \quad \text {and} \quad \lambda _2 < 1 - \alpha \;. \end{aligned}$$

(3)

The stability conditions are intuitively clear. The average number of customers entering a queue should be strictly less than the average number of customers that can be served from the queue, per slot. These stability conditions can for instance be found in Chapter 3.2 of Bruneel and Kim (1993).

Finally, denote with

$$\begin{aligned} U(z_1,z_2) := \lim _{k \rightarrow \infty } \text {E}[z_1^{u_{1,k}} z_2^{u_{2,k}}] \end{aligned}$$

(4)

the steady-state joint PGF of the process $\{u_{1,k},u_{2,k}\}$. By $(u_1,u_2)$ we denote a pair of random variables with this joint PGF.

2.2 Known Results for the Single-queue Model

In Kendall notation, queue 1 (resp. queue 2) is a discrete-time $Geo^X/D/1$ queue with Bernoulli interruptions, with the PGF of the number of arrivals in a slot equal to $A_1(z)$ (resp. $A_2(z)$) and single-slot service times. Let us denote the PGF of the stationary system content $u_j$ by $U_j(z)$. The PGF $U_j(z)$ can be expressed as (see for instance Chapter 3.2 of Bruneel and Kim (1993))

$$\begin{aligned} { U_j(z) = } \frac{[\alpha - \lambda _1](z-1) A_1(z)}{z-[\alpha +(1-\alpha )z]A_1(z)},&j=1 \;, \end{aligned}$$

(5)

$$\begin{aligned} \frac{[1-\alpha - \lambda _2](z-1) A_2(z)}{z-[1-\alpha + \alpha z]A_2(z)},&j=2 \;. \end{aligned}$$

(6)

The objective of this paper is to examine the joint system under the condition that the first queue is heavily populated. Consequently, our initial focus is on the probabilities $\Pr [u_1=n]$ as $n \rightarrow \infty$. To establish a formal proof, we introduce the following assumption:

Assumption 1

(Well-behaved distribution). The PGF $A_1(z)$ has a radius of convergence $\Omega _1>1$ and $\lim _{z\rightarrow \Omega _1} A_1(z) = +\infty$.

It is noteworthy that this assumption holds for a wide range of commonly encountered discrete probability distributions, such as the Poisson, Bernoulli, binomial, and geometric distributions. Throughout the remainder of this paper, we refer to PGFs that satisfy Assumption 1 as “well-behaved” PGFs.

Thanks to Assumption 1, it can be shown that the denominator of Eq. 5 has exactly one real positive zero, defined as $\tau _1$, such that $1<\tau _1<\Omega _1$, which has multiplicity 1. In general, the value of $\tau _1$ is implicitly defined by the equation and constraint:

$$\begin{aligned} \tau _1 = [(1-\alpha )\tau _1 + \alpha ]A_1(\tau _1), \quad 1<\tau _1 < \Omega _1 \;. \end{aligned}$$

(7)

Using classical arguments, it follows that the dominant singularity of $U_1(z)$ is $\tau _1$ and that this singularity is a simple pole. The negative of the residue at this pole is given by

$$\begin{aligned} b_1&:= - \lim _{z \rightarrow \tau _1} (z-\tau _1) U_1(z)\nonumber \\&\; = \frac{(\tau _1 -1)A_1(\tau _1)(\alpha -\lambda _1)}{(1-\alpha )A_1(\tau _1)+[(1-\alpha )\tau _1 + \alpha ] A_1^{\prime }(\tau _1) -1} \;. \end{aligned}$$

(8)

Hence, it follows that as $n \rightarrow \infty$

$$\begin{aligned} \Pr [u_1 =n] \sim b_1 \tau _1^{-(n+1)} \;, \end{aligned}$$

(9)

where $\sim$ means that

$$ \lim _{n \rightarrow \infty } \frac{\Pr [u_1= n]}{ b_1 \tau _1^{-(n+1)}} =1 \;. $$

The approximation (9) is commonly referred to as the “dominant-pole approximation” of $\Pr [u_1 =n]$, see for example Van Mieghem 1996.

3 Conditional Arrival Process and Service Process

It is clear that an extreme length of queue 1 is due to either a high number of arrivals and/or limited service in queue 1 during the previous slots. Both scenarios affect the evolution of queue 2.

To study the behavior of the second queue under the condition that the first queue is large, we first concentrate on obtaining the joint arrival and service process conditioned on the event that the content of queue 1 is large. The rationale behind this approach is that the system content in queue 2 at the beginning of a slot is a function of the arrivals and services before this slot.

More specifically, consider an arbitrary slot S in a steady state. A formal proof will be given below to show that for every natural number m,

$$\begin{aligned} \lim _{n \rightarrow \infty } \text {E} \left[ \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \; \big | \; u_{1,S} = n \right] = \prod _{j=1}^{m } \frac{A(x_j \tau _1,y_j)}{A_1(\tau _1)} R(w_j)\;, \end{aligned}$$

(10)

where

$$\begin{aligned} R(w_j) :=(1-\alpha )A_1(\tau _1) + [1-(1-\alpha )A_1(\tau _1)]w_j \;. \end{aligned}$$

(11)

The result (10) shows that the numbers of arrivals in both queues follow a modified joint distribution with PGF $\tfrac{A(x \tau _1,y)}{A_1(\tau _1)}$ and the states of the server follow a modified Bernoulli distribution with PGF R(w), both of which are independent and identically distributed. Additionally, the arrival process and service process are mutually independent.

3.1 A Useful Recurrence Relation

For brevity, let us define for any natural number $m$ and $j\in \{1,2,\ldots ,m\}$:

• $\textbf{w}_{j:m} = (w_j, w_{j+1}, \ldots , w_m)$ the vector of $w$ values with indices ranging from j to $m$,

• $\textbf{x}_{j:m} = (x_j, x_{j+1}, \ldots , x_m)$ the vector of $x$ values with indices ranging from j to $m$,

• $\textbf{y}_{j:m} = (y_j, y_{j+1}, \ldots , y_m)$ the vector of $y$ values with indices ranging from j to $m$.

In the remainder, we will always assume that

$$\begin{aligned} |w_j|\le 1, |x_j|\le 1, |y_j| \le 1, \quad \forall j \;. \end{aligned}$$

(12)

Let us now introduce the joint PGF $V_{m,S}$ of the random variables $r_{S-\ell }, a_{1, S-\ell }, a_{2, S-\ell }$, $\ell =1$, $\ldots ,m$ and $u_{1,S}$:

$$\begin{aligned} V_{m,S}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z) := \text {E}\left[ \left( \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \right) z^{ u_{1,S} }\right] \;. \end{aligned}$$

(13)

The multivariate functon $V_{m,S}$ has $3m +1$ arguments. Using the system equation (1), we get the following recursive relation:

$$\begin{aligned}&V_{m,S}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z) \\ =&\text {E} \left[ \left( \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \right) z^{u_{1,S}} \right] \\ =&\text {E} \left[ \left( \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \right) z^{a_{1,S-1} + (u_{1,S-1} - r_{S-1})^+ } \right] \\ =&A(x_1 z, y_1) \text {E} \left[ w_1^{r_{S-1}} \left( \prod _{j=2}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \right) z^{ (u_{1,S-1} - r_{S-1})^+ } \right] \\ =&A(x_1 z, y_1) \left\{ \alpha w_1 \text {E} \left[ \left( \prod _{j=2}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \right) z^{ (u_{1,S-1} - 1)^+ } \right] \right. \\&\left. + (1-\alpha ) \text {E} \left[ \left( \prod _{j=2}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \right) z^{u_{1,S-1} } \right] \right\} \\&= A(x_1 z, y_1) \bigg \lbrace \alpha w_1 \frac{V_{m-1,S-1}(\textbf{w}_{2:m},\textbf{x}_{2:m},\textbf{y}_{2:m},z) \!+\! (z-1) V_{m\!-\!1,S\!-\!1}(\textbf{w}_{2:m},\textbf{x}_{2:m},\textbf{y}_{2:m},0)}{z} \\&+ (1-\alpha ) V_{m-1,S-1}(\textbf{w}_{2:m},\textbf{x}_{2:m},\textbf{y}_{2:m},z) \bigg \rbrace . \end{aligned}$$

Because the slot S is a random slot in steady state, the function $V_{m,S}$ does not explicitly depend on the choice of the slot S (Bruneel and Devos 2023). Consequently, the functions $V_{m,S_1}$ and $V_{m,S_2}$ are identical for any slots $S_1$ and $S_2$ in steady state. Therefore we may omit the subscript S, i.e.,

$$\begin{aligned} V_{m} \equiv V_{m,S} \quad \text {for any slot}\, S\, \text {in steady state} \;. \end{aligned}$$

(14)

In view of Eq. 14, we obtained the following recursive relation:

$$\begin{aligned} \begin{aligned} V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z) =&\frac{A(x_1 z, y_1)}{z} \\&\times \lbrace [\alpha w_1 +(1-\alpha )z ]V_{m-1}(\textbf{w}_{2:m},\textbf{x}_{2:m},\textbf{y}_{2:m},z) \\&+ \alpha w_1 (z-1) V_{m-1}(\textbf{w}_{2:m},\textbf{x}_{2:m},\textbf{y}_{2:m},0) \rbrace \;. \end{aligned} \end{aligned}$$

(15)

3.2 Dominant Singularity of $V_m$ and its Residue

Recall that by definition, see Eq. 13,

$$ V_1(w_1,x_1,y_1,z) = \text {E}[w_1^{r_{S-1}} x_1^{a_{1,S-1}} y_1^{a_{2,S-1}} z^{u_{1,S}}] \;. $$

The functon $V_1$ can be explicitly computed using the same technique as to derive the recurrence relation for $V_m$. One finds that

$$ V_1(w_1,x_1,y_1,z) = A(x_1 z, y_1) \left( \alpha w_1 \text {E}[ z^{(u_{1,S-1}-1)^+}] + (1-\alpha ) \text {E}[ z^{u_{1,S -1}}] \right) . $$

Now since $S-1$ is a slot in steady state, the PGF of $u_{1,S-1}$ is given by Eq. 5. We find that

$$\begin{aligned} V_1(w_1,x_1,y_1,z) = \frac{ (\alpha \!-\! \lambda _1) A(x_1z,y_1)(z\!-\!1)\{(1\!-\!\alpha )A_1(z) \!+\! [1\!-\!(1\!-\!\alpha )A_1(z)]w_1)\}}{z\!-\![(1-\alpha )z+\alpha ]A_1(z)} \;. \end{aligned}$$

(16)

Consider the variables $w_1$, $x_1$ and $y_1$ fixed such that $|w_1|\le 1$ $|x_1|\le 1$, $|y_1|\le 1$. In this case, Eq. 16 implies that the univariate function $z \mapsto V_1(w_1,x_1,y_1,z)$ admits $\tau _1$ as unique dominant singularity. This singularity is a simple pole. We can compute the negative of the residue at this pole:

$$\begin{aligned} C_{1}(w_1,x_1,y_1)&:= - \lim _{z \rightarrow \tau _1} (z-\tau _1)V_1(w_1,x_1,y_1,z) \nonumber \\&\; \!=\! \frac{A(x_1 \tau _1, y_1)(\alpha \!-\! \lambda _1) (\tau _1 \!-\!1)\{(1\!-\!\alpha )A_1(\tau _1) \!+\! [1\!-\!(1\!-\!\alpha )A_1(\tau _1)]w_1)\}}{(1\!-\!\alpha )A_1(\tau _1)\!+\![(1\!-\!\alpha )\tau _1 \!+\! \alpha ] A_1^{\prime }(\tau _1) \!-\!1} \nonumber \\&\; = \frac{A(x_1 \tau _1, y_1)(\alpha - \lambda _1) (\tau _1 -1) R(w_1)}{(1-\alpha )A_1(\tau _1)+[(1-\alpha )\tau _1 + \alpha ] A_1^{\prime }(\tau _1) -1} \;, \end{aligned}$$

(17)

where the function R is defined in Eq. 11.

We have demonstrated that the dominant singularity of $V_1$ is $\tau _1$, a simple pole. We prove by induction that this is also the case for $V_m$, for every m. Suppose that this is true for $n=1,2,\ldots , m-1$. Considering the recurrence relation (15) we see that the possible singularities of $V_m$ are the singularities of $V_{m-1}$ and $A(x_1z, y_1)$. Notably, it is worth mentioning that $z=0$ is a removable singularity of $V_m$ due to $\lim _{z \rightarrow 0} z V_m(z) = 0$. Because of the induction hypothesis, $\tau _1$ is a singularity of $V_{m-1}$. Hence, $\tau _1$ is a singularity of $V_{m}$ as well. This singularity is the dominant singularity of $z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)$ since

$$ | V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z) | \le V_{m}(1,\ldots , 1,|z|) = U_1(|z|)< \infty \quad \text {if } |z|<\tau _1 \;. $$

We now calculate the negative of the residue of $z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)$ at $\tau _1$. We begin with

$$\begin{aligned} C_m(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m})&:= -\lim _{z \rightarrow \tau _1} (z-\tau _1) V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)\nonumber \\&= \frac{A(x_1 \tau _1,y_1)}{\tau _1} [\alpha w_1 + (1-\alpha ) \tau _1 ] C_{m-1}(\textbf{w}_{2:m},\textbf{x}_{2:m},\textbf{y}_{2:m}) \nonumber \\&= \frac{A(x_1 \tau _1,y_1)}{A_1(\tau _1)} R(w_1) C_{m-1}(\textbf{w}_{2:m},\textbf{x}_{2:m},\textbf{y}_{2:m}) \;, \end{aligned}$$

(18)

where, in the first equality we applied (15), and in the last equality, we multiplied the numerator and denominator by $A_1(\tau _1)$ and used the fact that, cf. Eq. 7:

$$\begin{aligned} \tau _1 = [(1-\alpha )\tau _1 + \alpha ]A_1(\tau _1) \quad \Leftrightarrow \quad 1 - (1-\alpha )A_1(\tau _1)= \frac{\alpha A_1(\tau _1)}{\tau _1} \;. \end{aligned}$$

(19)

Solving the recursive equation (18) yields

$$\begin{aligned} C_m(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m})&= \left( \prod _{j=1}^{m-1 } \frac{A(x_j \tau _1,y_j)}{A_1(\tau _1)} R(w_j) \right) C_1(w_m,x_m,y_m)\; \nonumber \\&= \left( \prod _{j=1}^{m} \frac{A(x_j \tau _1,y_j)}{A_1(\tau _1)} R(w_j) \right) \frac{A_1(\tau _1)(\alpha - \lambda _1) (\tau _1 -1) }{(1-\alpha )A_1(\tau _1)+[(1-\alpha )\tau _1 + \alpha ] A_1^{\prime }(\tau _1) -1} \nonumber \\&= \left( \prod _{j=1}^{m} \frac{A(x_j \tau _1,y_j)}{A_1(\tau _1)} R(w_j) \right) b_1 \;, \end{aligned}$$

(20)

where $b_1$ is defined in Eq. 8.

3.3 Asymptotics

From Section 3.2, it follows that for fixed $|w_j|\le 1$ $|x_j|\le 1$, $|y_j|\le 1$, the principal part at $z=\tau _1$ of the function $z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)$ is given by

$$ \frac{C_m(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m})}{\tau _1 - z}\;, $$

implying that the coefficients $\{[z^n] V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z) \}_{n=0}^{\infty }$ of the power series expansion of the function $z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)$ satisfy

$$\begin{aligned} [z^n] V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z) \sim C_m(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m}) \tau _1^{-(n+1)} \qquad \text {as}\, n \rightarrow \infty \;. \end{aligned}$$

(21)

By applying the law of total expectation, it is apparent that

$$\begin{aligned} [z^n] V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)&= [z^n]\text {E} \left[ \left( \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \right) z^{u_{1,S} }\right] \\&= \Pr [u_{1,S} = n ]\text {E} \left[ \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \; \big | \; u_{1,S} = n \right] \;, \end{aligned}$$

Hence, in view of (21),

$$\begin{aligned} \Pr [u_{1,S} = n ]\text {E} \left[ \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \; \big | \; u_{1,S} = n \right] \sim C_m(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m}) \tau _1^{-(n+1)} \;, \end{aligned}$$

(22)

as $n \rightarrow \infty$. By combining (20) and (22) with

$$ \Pr [u_{1,S} = n ] \sim b_1 \tau _1^{-(n+1)} \qquad \text {as}\, n \rightarrow \infty \;, $$

as shown in (9), we derive our main result:

$$\begin{aligned} \lim _{n \rightarrow \infty } \text {E} \left[ \prod _{j=1}^{m} w_j^{r_{S-j}} x_j^{a_{1,S-j}} y_j^{a_{2,S-j}} \; \big | \; u_{1,S} = n \right] = \prod _{j=1}^{m} \frac{A(x_j \tau _1,y_j)}{A_1(\tau _1)} R(w_j)\;. \end{aligned}$$

(23)

3.4 Summary of the Results

To begin, let us define the following notations:

$$\begin{aligned} A^*(x,y)&:= \frac{A( \tau _1 x,y)}{A_1(\tau _1)} \end{aligned}$$

(24)

$$\begin{aligned} \alpha ^*&:= \frac{\alpha A_1(\tau _1)}{\tau _1}\;. \end{aligned}$$

(25)

Using Eq. 19, we can now express R(w), as defined in Eq. 11, as follows:

$$ R(w) = 1 - \alpha ^* + \alpha ^* w \;. $$

Conditioned on $u_{1,S} \rightarrow \infty$, our analysis yields the following notable results:

• 1. The arrivals into the two queues during the slots preceding slot S are independent and identically distributed with common joint PGF $A^*(x,y)$.

• 2. The states of the server during the slots preceding slot S are independent and identically distributed with common Bernoulli distribution with parameter $\alpha ^*$.

• 3. The state of the server is independent of the arrivals into the two queues during the slots preceding slot S.

4 Main Result for the System Contents in the Alternating Service Model

In the preceding section, we established that when the system content $u_1$ at the beginning of a random slot in steady state is sufficiently large, the arrivals into the two-queue system in previous slots are (approximately) independent from slot to slot. Moreover, the arrival process is characterized by a joint PGF $A^*(x,y)$, as defined in Eq. 24. Additionally, the server’s state during previous slots follows a Bernoulli process with parameter $\alpha ^*$, as defined in Eq. 25, and this service process is independent of the arrival process. Hence, this implies that conditioned on $u_{1,S}\rightarrow \infty$, the arrival process to the second queue is described by an independent arrival process characterized by the PGF $A^*(1,y)$ and the interruptions constitute a Bernoulli process with parameter $1-\alpha ^*$, for an infinite number of slots preceding slot S. We thus observe that the conditional system content in queue 2 in our queueing system is equal to the system content in an equivalent queueing system. This equivalent system is also a discrete-time $Geo^X/D/1$ queue with Bernoulli interruptions but with an adjusted arrival and interruption process. This equivalent queueing system can be stable or unstable. Let us denote

$$\begin{aligned} \lambda _2^*&:=\frac{\partial A^*}{\partial y} (1,1) \nonumber \\&= \frac{1}{A_1(\tau _1)}\frac{\partial A}{\partial y} (\tau _1,1)\;, \end{aligned}$$

(26)

then the stability condition of the equivalent queueing system reads:

$$\begin{aligned} \lambda _2^*< 1 - \alpha ^* \Leftrightarrow \frac{1}{A_1(\tau _1)}\frac{\partial A}{\partial y} (\tau _1,1) <1 - \frac{ \alpha A_1(\tau _1)}{\tau _1} \;. \end{aligned}$$

(27)

If the inequality (27) is fulfilled, the conditional distribution of $u_{2,S}$ given $u_{1,S}=n$, $n\rightarrow \infty$, exists and its PGF is given by, cf. Eq. 6,

$$ \lim _{n \rightarrow \infty } \text {E}[z^{u_{2,S}} | u_{1,S} = n] = \frac{ (1-\alpha ^* - \lambda ^*_2) (z-1)A^*(1,z)}{z - [1-\alpha ^* + \alpha ^* z ]A^*(1,z)}\;. $$

In terms of $A(z_1,z_2)$ and $\alpha$, this PGF can be expressed as,

$$\begin{aligned}&\lim _{n \rightarrow \infty } \text {E}[z^{u_{2,S}} | u_{1,S} = n] \nonumber \\ =&\frac{ [(1-\alpha )A_1(\tau _1) - \frac{1}{A_1(\tau _1)}\frac{\partial A}{\partial y} (\tau _1,1) ](z-1)\frac{A( \tau _1 x,y)}{A_1(\tau _1)}}{z - [(1-\alpha )A_1(\tau _1) + \frac{\alpha A_1(\tau _1)}{\tau _1} z ]\frac{A( \tau _1 x,y)}{A_1(\tau _1)}} \nonumber \\ =&\frac{\tau _1 [(1-\alpha )A_1(\tau _1) - \frac{1}{A_1(\tau _1)}\frac{\partial A}{\partial y} (\tau _1,1) ]}{A_1(\tau _1)}\frac{ (z-1)A( \tau _1 x,y)}{\tau _1 z - [(1-\alpha )\tau _1 + \alpha z ]A( \tau _1 x,y)} \nonumber \\ =&\frac{\tau _1 - \alpha A_1(\tau _1) - [(1-\alpha )\tau _1 + \alpha ] \frac{\partial A}{\partial y} (\tau _1,1)}{A_1 (\tau _1)} \frac{ (z-1)A(\tau _1,z)}{\tau _1 z - [(1-\alpha )\tau _1 + \alpha z ]A(\tau _1,z)}\;, \end{aligned}$$

(28)

where in the last equality, we rewrote the first factor using the following identities:

$$ \tau _1 = [(1-\alpha )\tau _1 + \alpha ]A_1(\tau _1) \Leftrightarrow \tau _1(1-\alpha )A_1(\tau _1) = \tau _1 - \alpha A_1(\tau _1) \Leftrightarrow \; \frac{\tau _1}{A_1(\tau _1)} = (1-\alpha )\tau _1 + \alpha \;. $$

From the PGF (28), moments and tail probabilities can be calculated. For instance, the mean value is given by

$$\begin{aligned} \begin{aligned} \lim _{n \rightarrow \infty } \text {E}[u_2 | u_1 =n ]&= \frac{ 2 \frac{\partial A}{\partial y} (\tau _1,1) \left( \tau _1 - [(1-\alpha )\tau _1 + \alpha ] \frac{\partial A}{\partial y} (\tau _1,1) \right) }{2 A_1(\tau _1) \left[ \tau _1 - \alpha A_1(\tau _1) - [(1-\alpha )\tau _1 + \alpha ] \frac{\partial A}{\partial y} (\tau _1,1)\right] }\\&\quad + \frac{ \tau _1 \frac{\partial ^2 A}{\partial y^2} (\tau _1,1) }{2 A_1(\tau _1) \left[ \tau _1 - \alpha A_1(\tau _1) - [(1-\alpha )\tau _1 + \alpha ] \frac{\partial A}{\partial y} (\tau _1,1)\right] } \;. \end{aligned} \end{aligned}$$

(29)

Tail probabilities can be calculated using singularity analysis. The most common and easiest case is when the dominant singularity of $z \mapsto \lim _{n \rightarrow \infty } \text {E}[z^{u_{2,S}} | u_{1,S} = n]$ is given by the smallest real zero of the denominator in Eq. 28. This is the case if $A(\tau _1,z)$ is well-behaved in the sense of Assumption 1. In all the examples we have examined, $\frac{A(\tau _1 x, y)}{A_1(\tau _1)}$ has the same form as A(x, y) (by which we mean that it is the PGF of the same parametric family of distributions), ensuring that $A(\tau _1,z)$ is well-behaved in these examples.

Let us assume that $A(\tau _1, z)$ is well-behaved. In this case, we have that

$$\begin{aligned} \lim _{n \rightarrow \infty } \Pr [u_2= \ell | u_1 =n ] \sim d \sigma ^{-(\ell +1)} \end{aligned}$$

(30)

as $\ell \rightarrow \infty$, where $\sigma$ is the smallest positive real zero of $\tau _1 z - [(1-\alpha )\tau _1 + \alpha z ]A(\tau _1,z)$ and

$$\begin{aligned} d&:= - \lim _{z \rightarrow \tau _1} (z-\sigma ) \frac{\tau _1 - \alpha A_1(\tau _1) - [(1-\alpha )\tau _1 + \alpha ] \frac{\partial A}{\partial y} (\tau _1,1)}{A_1 (\tau _1)} \frac{ (z-1)A(\tau _1,z)}{\tau _1 z - [(1-\alpha )\tau _1 + \alpha z ]A(\tau _1,z)} \nonumber \\&\;= - \frac{\tau _1 - \alpha A_1(\tau _1) - [(1-\alpha )\tau _1 + \alpha ] \frac{\partial A}{\partial y} (\tau _1,1)}{A_1 (\tau _1)} \frac{ (\sigma -1)A(\tau _1,\sigma )}{\tau _1 - \alpha A(\tau _1,\sigma ) - [(1-\alpha )\tau _1 + \alpha \sigma ]\frac{\partial A}{\partial y}(\tau _1,\sigma )} \;. \end{aligned}$$

(31)

Notice that $\sim$ in (30) means

$$ \lim _{\ell \rightarrow \infty } \lim _{n \rightarrow \infty } \frac{\Pr [u_2= \ell | u_1 =n ]}{d \sigma ^{-(\ell +1)}} =1\;. $$

Finally, using the asymptotic (9) and the well-known fact that $\Pr [u_1=n, u_2 = \ell ] = \Pr [ u_2 = \ell | u_1=n] \Pr [u_1=n]$, we obtain that

$$\begin{aligned} \lim _{\ell \rightarrow \infty } \lim _{n \rightarrow \infty } \frac{\Pr [u_1=n, u_2 = \ell ] }{b_1 \tau _1^{-(n+1)} d \sigma ^{-(\ell +1)}} =1 \;. \end{aligned}$$

(32)

Hence for large $\ell$ and n we can approximate the joint stationary distribution of the system contents as

$$ \Pr [u_1=n, u_2 = \ell ] \approx \frac{b_1 }{\tau _1^{n+1} } \frac{d}{\sigma ^{\ell +1}} \;. $$

Concluding this section, it is important to note that the two limits in (32) do not commute. Interchanging the roles of queue 1 and queue 2, by conditioning on the event $u_{2,S}= \ell$ as $\ell \rightarrow \infty$, leads to a different outcome. Assuming a similar condition for $A_2(z)$ as Assumption 1, one obtains that

$$ \begin{aligned}&\lim _{ \ell \rightarrow \infty } \text {E}[z^{u_{1,S}} | u_{2,S} = \ell ] \\ =&\frac{\tau _2 - (1-\alpha ) A_2(\tau _2) - [\alpha \tau _2 + 1-\alpha ] \frac{\partial A}{\partial x} (1,\tau _2)}{A_2 (\tau _2)} \frac{ (z-1)A(z,\tau _2)}{\tau _2 z - [(1-\alpha )z + \alpha \tau _2 ]A(z,\tau _2)}\;, \end{aligned} $$

where $\tau _2$ is the smallest positive real zero of the denominator of $U_2(z)$ given in Eq. 6. Now it can be seen that the dominant singularity of the function above is in general not the same as the function (28). In the most common case, assuming that $A_1(z)$ satisfies Assumption 1, the former is given by the smallest positive real zero, say $\delta$, of $\tau _2 z - [(1-\alpha )z + \alpha \tau _2 ]A(z,\tau _2)$. Without any symmetry, for example if $\alpha =1/2$ and $A(z_1,z_2)=A(z_2,z_1)$ there is no reason that $\delta$ is the same as $\sigma$. Hence, for some constant e, we have that

$$ \lim _{n \rightarrow \infty } \lim _{\ell \rightarrow \infty } \frac{\Pr [u_1= n | u_2 =\ell ]}{e \delta ^{-(n +1)}} =1 \;, $$

and for some constant $b_2$, cf. (9),

$$ \lim _{\ell \rightarrow \infty } \frac{\Pr [u_2 =\ell ]}{b_2 \tau _2^{-(n +1)}} =1 \;, $$

implying

$$ \lim _{n \rightarrow \infty } \lim _{\ell \rightarrow \infty } \frac{\Pr [u_1= n , u_2 =\ell ]}{e \delta ^{-(n +1)}b_2 \tau _2^{-(\ell +1)}} =1 \;. $$

Assuming that the order of the limits is irrelevant, then this would yield a different result than (32), which is impossible. Hence, we can conclude that the limits do not commute.

5 Discussion of the Asymptotic Stability Condition

The asymptotic stability condition (27) is always fulfilled when the numbers of arrivals in both queues are independent, i.e. $A(z_1,z_2)=A_1(z_1)A_2(z_2)$. Indeed, in this case we have that

$$\begin{aligned} \lambda _2^* = \frac{1}{A_1(\tau _1)}\frac{\partial A}{\partial y} (\tau _1,1) = \lambda _2< 1-\alpha < 1-\frac{\alpha A_1(\tau _1)}{\tau _1} = 1 - \alpha ^*\;, \end{aligned}$$

(33)

where we used the stability condition (3) of the original system in the first inequality, and in the last inequality we used the fact that $A_1(\tau _1)<\tau _1$, which follows from Eq. 7.

When the numbers of arrivals in both queues are dependent, i.e. $A(z_1,z_2)$ is not of a product form, it is not possible to draw general conclusions. In the case of negative correlation between the arrivals in queue 1 and queue 2, and given that the server can only serve one queue at a time, we expect queues 1 and 2 to exhibit complementary behavior, in the sense that $u_2$ typically takes small values when $u_1$ takes high values, and vice versa. Consequently, it is plausible to conjecture that the asymptotic stability condition (27) is always fulfilled for negatively correlated arrivals. However this conjecture is incorrect. A counter-example is given by the following PGF:

$$ A(z_1,z_2)= 0.655 + 0.1635z_1 + 0.125z_2 + 0.055z_2^2 + 0.0015z_1^5 z_2^5 \quad \text {and} \quad \alpha = 0.5 \;. $$

The idea in the construction of this counterexample was to include a small probability that there can occur a large number of arrivals in both queues, but that the covariance is still negative. Additionally, for the sake of completeness, it is also possible to find examples with positive correlation between the arrivals in queue 1 and queue 2 that violate condition (27), such as:

$$ A(z_1,z_2) = 0.95 + 0.05 z_1^5 z_2^5 \quad \text {and} \quad \alpha = 0.5 \;. $$

Finally, we note that even if the stability condition (27) is not met, meaningful statements about the system contents can still be made, albeit in less detail. One approach, consistent with the methodology of this paper, involves utilizing singularity analysis to approximate transient characteristics in queueing systems (Walraevens et al. 2009). In Bruneel (1991), the transient system content at the beginning of slots is analyzed for a discrete-time $Geo^X/D/1$ queue with Bernoulli interruptions. By applying the approach of Walraevens et al. (2009) to the formulas available in Bruneel (1991), we can for example derive approximate results for the mean system content in an unstable system as the number of slots goes to infinity. However, we believe that the case where the stability condition is met is the most interesting to consider. Therefore, our focus in the examples below will exclusively be on scenarios where the stability condition is satisfied.

6 Examples and Discussion

The main result (28) in this paper can be applied to various types of PGFs $A(z_1,z_2)$, provided that Assumption 1 and stability condition (27) are satisfied. Below, we will discuss some specific applications of the method in detail, focusing on particular choices of the distribution of the arrivals. We investigate three types of arrival processes: independent Bernoulli arrivals, independent geometric arrivals, and independent Poisson arrivals. The first two examples are selected to facilitate the analytical calculation of $\tau _1$. However, while this analytical approach is not obligatory, it is advantageous for the exposition of the results. The third type of arrival process is included to demonstrate that, while numerical work is required, it remains minimal.

6.1 Independent Bernoulli Arrivals

Let us assume that the arrivals $a_{1,k}$ and $a_{2,k}$ constitute two independent sequences of independent and identically Bernoulli distributed random variables such that

$$ A(z_1,z_2) = (1-\lambda _1 + \lambda _1 z_1) (1 - \lambda _2 + \lambda _2 z_2) \;. $$

The value $\tau _1$, defined in Eq. 7, is in this case given by

$$ \tau _1 = \frac{\alpha }{1-\alpha } \frac{1-\lambda _1}{\lambda _1} \;. $$

It is then an easy exercise to compute the adjusted arrival PGF $A^*(x,y)$ from Eq. 24:

$$ \frac{A(\tau _1 x,y)}{A_1(\tau _1)} = \left( 1-\alpha + \alpha x \right) \left( 1-\lambda _2 +\lambda _2 y\right) \;. $$

The adjusted PGF $A^*(1,z)$ defined in Eq. 24 equals of course $A_2(z)$, because the numbers of arrivals in queue 1 and queue 2 are independent. The adjusted interruption parameter $\alpha ^*$ defined in Eq. 25 is now given by

$$ \alpha ^* = \lambda _1 \;. $$

We can observe that the arrival rate $\lambda _1$ and the interruption parameter $\alpha$ are simply interchanged. This result, which may seem simple, has already been long discovered for the continuous-time M/M/1 queue. An example of this can be found in Shwartz and Weiss (1995): The way an M/M/1 queue becomes saturated is that for a long time, the arrival rate and service rate are interchanged. In our case, since the single-queue Bernoulli model with single-slot service times can also be seen as a single-queue model with geometric service times, the first queue is a discrete-time Geo/Geo/1 queue. Therefore, we observe that we have the same remarkable property as its continuous-time equivalent: the way the first queue builds up is by changing the arrival probability and successful transmission probability for an infinite duration of time.

Furthermore, by simply replacing $\alpha$ by $\lambda _1$ in Eq. 6, we obtain the following expression for the asymptotic conditional PGF:

$$ \lim _{n \rightarrow \infty } \text {E}[z^{u_{2}} | u_{1} = n] = \frac{[1-\lambda _1 - \lambda _2](z-1)(1-\lambda _2 + \lambda _2 z)}{z-[1-\lambda _1 + \lambda _1 z](1-\lambda _2 + \lambda _2 z)} \;. $$

By canceling the common factor $(z-1)$ in numerator and denominator, writing down the corresponding Taylor series expansion and by equating coefficients, it follows that

$$ \lim _{n\rightarrow \infty } \Pr [u_2 = \ell |u_1 = n] = \frac{1-\lambda _1-\lambda _2}{\lambda _1(1-\lambda _1)} \left( \frac{\lambda _1 \lambda _2 }{(1-\lambda _1)(1-\lambda _2)} \right) ^{\ell }, \quad \ell =1,2,\ldots $$

Hence, as $n \rightarrow \infty$, we get for $\ell = 1,2,\ldots$

$$\begin{aligned} \Pr [u_1 = n, u_2 = \ell ] \sim \frac{(\alpha -\lambda _1)(1-\lambda _1-\lambda _2)}{\alpha (1-\alpha )\lambda _1(1-\lambda _1)}\left( \frac{(1-\alpha )\lambda _1 }{\alpha (1-\lambda _1)} \right) ^{n} \left( \frac{\lambda _1 \lambda _2 }{(1-\lambda _1)(1-\lambda _2)} \right) ^{\ell } \;. \end{aligned}$$

(34)

As mentioned in the introduction, it is worth noting that there are very few cases where an explicit expression for the joint PGF of $u_1$ and $u_2$ can be derived, and the case of independent Bernoulli arrivals is one of them (see Devos et al. (2020)). Equation (54) of Devos et al. (2020) provides the expression for the joint distribution of $u_1$ and $u_2$. By using this equation, we can obtain the same asymptotic as Eq. 34, which is expected. The high accuracy of formula Eq. 34 for large n, is demonstrated through a specific example shown in Fig. 2, where it is compared against the exact results from Devos et al. (2020).

Fig. 2

Tail approximation (34) for $\Pr [u_1=n, u_2 =\ell ]$ versus exact results, for fixed $\ell =1,2,3,4$ and $\lambda _1=0.2$, $\lambda _2=0.5$, $\alpha =0.3$

Table 1 summarizes various results for $\Pr [u_1=n, u_2 = \ell ]$ with the parameters $\lambda _1 = 0.2$, $\lambda _2 = 0.5$, and $\alpha = 0.3$.

Table 1 Various results for $\Pr [u_1=n, u_2 =\ell ]$ with $\lambda _1=0.2$, $\lambda _2=0.5$, $\alpha =0.3$

6.2 Independent Geometric Arrivals

Let us assume that the arrivals $a_{1,k}$ and $a_{2,k}$ constitute two independent sequences of independent and identically geometrically distributed random variables such that

$$ A(z_1,z_2) = \frac{1}{(1+\lambda _1 - \lambda _1 z_1)(1+\lambda _2 - \lambda _2 z_2) }\;. $$

We emphasize that, in contrast to the previous example, no explicit expression is known for $U(z_1,z_2)$ for this specific $A(z_1,z_2)$.

The value $\tau _1$ defined in Eq. 7 and the adjusted interruption parameter $1-\alpha ^*$ from Eq. 25 are given by

$$ \tau _1 = \frac{\alpha }{\lambda _1} \;, $$

and

$$ 1-\alpha ^* = \frac{1-\alpha }{1+\lambda _1 - \alpha } $$

respectively. Since $A^*(1,z)=A_2(z)$, we obtain the asymptotic conditional PGF of interest by simply replacing $1-\alpha$ with $1-\alpha ^*$ in Eq. 6, yielding

$$ \lim _{n \rightarrow \infty } \text {E}[z^{u_{2}} | u_{1} = n] = \frac{1-\alpha - \lambda _2 (1 -\alpha + \lambda _1 )}{1-\alpha -\lambda _2 (1 -\alpha + \lambda _1)z} \;. $$

The expression above is the PGF of a geometrically distributed random variable with parameter $\tfrac{\lambda _2}{1-\alpha }(1 -\alpha + \lambda _1)$. Hence we immediately obtain that

$$ \lim _{n\rightarrow \infty } \Pr [u_2 \!=\! \ell |u_1 \!=\! n] \!=\! \left( 1 \!-\! \tfrac{\lambda _2}{1\!-\!\alpha }\left( 1 \!-\!\alpha \!+\! \lambda _1 \right) \right) \left( \frac{\lambda _2}{1-\alpha }\right) ^{\ell } \left( 1 \!-\!\alpha + \lambda _1 \right) ^{\ell } , \quad \ell =0,1,2,\ldots $$

Furthermore, as $n \rightarrow \infty$, we get for $\ell = 0,1,2,\ldots$

Fig. 3

Tail approximation (35) for $\Pr [u_1=n, u_2 =\ell ]$ versus simulation results, for fixed $\ell =1,2,3,4$ and $\lambda _1=0.25$, $\lambda _2=0.6$, $\alpha =0.3$

$$\begin{aligned} \Pr [u_1 \!=\! n \!=\! u_2 \!=\! \ell ] \sim \left( 1\!-\!\frac{\lambda _1}{\alpha }\right) \left( 1 \!-\! \tfrac{\lambda _2}{1\!-\!\alpha }\left( 1 \!-\!\alpha \!+\! \lambda _1 \right) \right) \left( \frac{\lambda _1}{\alpha }\right) ^n \left( \frac{\lambda _2}{1\!-\!\alpha }\right) ^{\ell } \left( 1\!-\!\alpha \!+\! \lambda _1\right) ^{\ell } \;. \end{aligned}$$

(35)

We demonstrate the accuracy of formula (35) for large n through a particular example depicted in Fig. 3, where a comparison is made with simulation results. We emphasize that generating simulation results for joint probabilities $\Pr [u_1 = n = u_2 = \ell ]$ with high values of n or $\ell$, or both, is extremely time-consuming due to the rarity of these events. In contrast, evaluating the closed formula (35) is instantly obtained by just substituting the parameter values into the expression.

Table 2 summarizes various results for $\Pr [u_1=n, u_2 = \ell ]$ with the parameters $\lambda _1=0.25$, $\lambda _2=0.6$, $\alpha =0.3$.

Table 2 Various results for $\Pr [u_1=n, u_2 =\ell ]$ with $\lambda _1=0.25$, $\lambda _2=0.6$, $\alpha =0.3$

6.3 Independent Poisson Arrivals

In this last example, the numbers of arrivals in both queues during consecutive slots are two independent sequences of independent and identically Poisson distributed random variables such that

$$ A(z_1,z_2) = e^{\lambda _1 (z_1-1) + \lambda _2 (z_2-1) } \;. $$

The value $\tau _1$ can only be determined numerically, as Eq. 7 is now a transcendental equation in $\tau _1$:

$$ \tau _1 = [(1-\alpha ) \tau _1 + \alpha ] e^{\lambda _1 (\tau _1-1)} \;, \quad \tau _1>1\;. $$

Once $\tau _1$ is computed numerically, $\alpha ^*$ is given by Eq. 25. Then, in the asymptotic system, queue 2 behaves as a stable single-server queue with 1-slot service times, Poisson arrivals with mean $\lambda _2$ and Bernoulli interruptions with parameter $1-\alpha ^*$, implying that the PGF of the queue-2 system content exist and is given by, see Eq. 28,

$$\begin{aligned} \lim _{n \rightarrow \infty } \text {E}[z^{u_{2}} | u_{1} = n]&= \frac{\tau _1 - \alpha e^{\lambda _1(\tau _1-1)} - [(1-\alpha )\tau _1 + \alpha ]e^{\lambda _1(\tau _1-1)}}{e^{\lambda _1(\tau _1-1)}} \nonumber \\&\quad \times \frac{ (z-1)e^{\lambda _1(\tau _1-1)} e^{\lambda _2(z-1)}}{\tau _1 z - [(1-\alpha )\tau _1 + \alpha z ]e^{\lambda _1(\tau _1-1)} e^{\lambda _2(z-1)}} \;. \end{aligned}$$

(36)

Let us take a look at the dominant singularity of this (conditional) PGF. The denominator of Eq. 36 has exactly one real positive zero in the interval $]1, \infty [$. In accordance with Section 4, we denote this zero as $\sigma$. As outlined in Section 4, we have the following approximation for the stationary joint distribution of the system contents:

$$ \Pr [u_1=n, u_2 = \ell ] \approx \frac{b_1 }{\tau _1^{n+1} } \frac{d}{\sigma ^{\ell +1}}\;, $$

where the constants $b_1$ and d are in this case given by, see Eqs. 8 and 31,

$$\begin{aligned} b_1&= \frac{(\tau _1 -1)e^{\lambda _1 (\tau _1-1)} (\alpha -\lambda _1)}{(1-\alpha )e^{\lambda _1 (\tau _1-1)} +[(1-\alpha )\tau _1 + \alpha ] e^{\lambda _1 (\tau _1-1)} \lambda _1 -1} \\ d&= \frac{\tau _1 - \alpha e^{\lambda _1 (\tau _1-1)} - [(1-\alpha )\tau _1 + \alpha ] )e^{\lambda _1 (\tau _1-1)} \lambda _2}{e^{\lambda _1 (\tau _1-1)}} \\&\quad \times \frac{ (\sigma -1)e^{\lambda _1 (\tau _1-1)} e^{\lambda _2 (\sigma -1)}}{\tau _1 - \alpha e^{\lambda _1 (\tau _1-1)} e^{\lambda _2 (\sigma -1)} - [(1-\alpha )\tau _1 + \alpha \sigma ]e^{\lambda _1 (\tau _1-1)} e^{\lambda _2 (\sigma -1)} \lambda _2} \;. \end{aligned}$$

Unlike the previous two examples,, the values $\tau _1$ and $\sigma$ have to be calculated using a numerical method, e.g. the Newton-Raphson method. However, the computational time involved in this numerical method is negligible both absolutely and relative to the time required for simulation. The approximation is again very accurate, as demonstrated in Figure 4 and Table 3, where a comparison is made with simulation. We observe that the approximation for $\Pr [u_1=n, u_2=1]$ is less accurate compared to the previous two examples of arrival PGFs. This is because, in the earlier cases, we had exact expressions for $\lim _{n \rightarrow \infty } \Pr [u_2 = \ell | u_1=n]$, whereas here we approximated this limiting probability using the dominant-pole technique, as explained in Section 4.

7 Conclusion and Further Research

We derived analytical asymptotic formulas for the stationary joint distribution of the system contents. Hereto we used and extended the ideas and techniques as in Bruneel and Devos (2023) such as first studying the arrivals and services when conditioning on one of the two queue contents. The evaluation of the expressions requires minimal effort, as only the root of a nonlinear equation needs to be calculated. As an illustration we applied our method to some specific choices of $A(z_1,z_2)$. For example, in the case where at most one customer can arrive in each queue during a slot, independently of each other, the exact joint stationary distribution has been reported previously in the literature. Our results in this case align with previous calculations, confirming the effectiveness of our approach.

Fig. 4

Tail approximation for $\Pr [u_1=n, u_2 =\ell ]$ versus simulation results, for fixed $\ell =1,2,3,4$ and $\lambda _1=0.4=\lambda _2=0.4$, $\alpha =0.5$

Table 3 Various results for $\Pr [u_1=n, u_2 = \ell ]$ with $\lambda _1=\lambda _2=0.4$, $\alpha =0.5$

A crucial step in our analysis is having the explicit expression (16), which represents the joint PGF of $r_{S-1}$, $a_{1,S-1}$, $a_{2,S-1}$ and $u_{1,S}$, with S being a random slot in steady state. This was made possible by having an explicit expression for the PGF of $u_{1,S-1}$, see Eq. 5. We believe that the basic idea of our method, which is to consider a random slot S in steady state and to analyze the underlying stochastic processes describing the queueing system in the slots preceding S, can be extended to other discrete-time two-queue models where the stationary distribution of at least one marginal system content is known.

Further research includes extending the approach to more complex coupled queues. For example, one such candidate is the randomly alternating service system with its work-conserving variant, i.e. the server is always assigned to a non-empty queue (Vanlerberghe et al. 2016; Walraevens et al. 2010). In this model, the marginal PGFs of the system content are no longer known. However, the PGF of the total system content is known due to the work-conserving property. Therefore, it may be beneficial to condition on the event that the total system content becomes large instead of focusing on a single queue. Another possible extension to explore is investigating whether the method can be extended to a system with more than two queues. However, a system with more than two queues introduces additional complexities due to the presence of multiple types of conditioning. For instance, scenarios may arise where all queues except one become saturated, or where only one queue becomes saturated. Addressing these variations would require further refinement and adaptation of the methodology, potentially involving novel analytical techniques.