In this paper, we study a functional equation for generating functions of the form \(f(z) = g(z) \sum _{i=1}^M p_i f(\alpha _i(z)) + K(z)\), viz. a recursion with multiple recursive terms. We derive and analyze the solution of this equation for the case that the \(\alpha _i(z)\) are commutative contraction mappings. The results are applied to a wide range of queueing, autoregressive and branching processes.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
In many applied probability models, in particular in queueing models, the following type of recursion describes the behavior of a key performance measure:
where the involved random variables are nonnegative and integer valued. Under certain independence assumptions and ergodicity conditions, this gives rise to the following type of functional equation for the probability generating function (pgf) f(z) of the steady-state distribution of the \(X_n\) process:
An example of such a model is a branching process with immigration (BPI). In that case, the function f(z) represents the pgf of the steady-state distribution of the number of individuals and the function \(\alpha (z)\) the pgf of the offspring distribution. If in all states except state 0 the pgf of the immigration distribution is given by g(z) while in the special state 0 the pgf of the immigration distribution is given by \(g_0(z)\), then the function f(z) satisfies (1) with \(K(z)=f(0)\left( g_0(z)-g(z)\right) \). Remark that in the special case that \(g_0(z)=g(z)\), we have that \(K(z)=0\).
The solution of (1) is given by an expression containing an infinite product and an infinite sum (see Eq. (13) later on in this paper) which is obtained after iteration of Eq. (1). Branching processes with immigration appear for example in the analysis of the M/G/1 queue with (single or multiple) gated vacations (see Takagi [18], Sect. 2.5 of Chapter 2), the M/G/1 queue with permanent customers (see Boxma and Cohen [3]) and, a multi-type variant, in the analysis of polling systems (see Resing [15]).
Anzeige
In the case that the branching process with immigration evolves in an i.i.d. random environment (BPIRE) in which the environment can be in M different states, the corresponding functional equation is of the form
where \(p_i\) is the probability that the environment is in state i and \(\alpha _i(z)\) is the pgf of the offspring distribution when the environment is in state i, \(i=1,2,\dots ,M\).
In this paper, we obtain the solution of functional equation (2) in the particular case that the functions \(\alpha _1 (z), \ldots , \alpha _M (z)\) are commutative contraction mappings on the closed unit disk. Although (2) with multiple recursive terms is a natural extension of (1) with only a single recursive term, it is hardly studied in the queueing literature, probably because the number of different terms after the nth iteration of (2) grows exponentially. That is also the reason why in this paper we restrict ourselves to the case in which the functions \(\alpha _1 (z), \ldots , \alpha _M (z)\) are commutative.
In Adan et al. [1], a specific example of (2) was analyzed in detail in the study of a queueing system with two classes of impatient customers. The main goal of the present paper is to give a general treatment of Eq. (2) and to show how in the commutative case the growth of the number of iteration terms can be handled. An additional aim is to treat several queueing and branching-type examples in which (2) appears, also allowing complications like the occurrence of a pole in g(z) and K(z).
Organization of the paper In Sect. 2, we solve the recursion (2), both for the homogeneous case where \(K(z) \equiv 0\) (Sect. 2.1) and for the inhomogeneous case (Sect. 2.2). The results are applied in the subsequent sections. We start, in Sect. 3, with a particular queueing model. Its choice is motivated by the fact that it provides a relatively simple illustration of the theory for the homogeneous case, while still having a few features that deviate from the setting of Sect. 2. Section 4 considers a special case of the branching process with immigration in a random environment, also called random coefficient integer-valued autoregressive process of order 1, in which the offspring of an individual in each environmental state can only be equal to 0 or 1. In Sect. 5, we consider an integer-valued reflected autoregressive process, which may be viewed as a generalization of an embedded queue length process in the M/G/1 queue. Section 6 is devoted to another reflected autoregressive process, this time on \([0,\infty )\). Some topics for further research are mentioned in Sect. 7.
Anzeige
2 The recursion
In this section, we study recursion (2) for the generating function f(z) of a non-negative discrete random variable X with \(\mathbb E[X] < \infty \), where g(z) and K(z) are analytic functions (and not necessarily generating functions), \(p_1, \ldots , p_M\) is a probability distribution and \(\alpha _1 (z), \ldots , \alpha _M (z)\) are commutative contraction mappings on the closed unit disk, i.e., there is a constant \(\kappa < 1\) such that \(|\alpha _i (z) - \alpha _i (u) | \le \kappa | z - u |\) and \(\alpha _i (\alpha _j (z)) = \alpha _j (\alpha _i (z))\) for each i and j. For example, the mappings \(\alpha _i (z) = 1-a_i + a_i z\) with \(|a_i| < 1\) are contractions with \(\kappa = \max (a_1, \ldots , a_M)\), and they commute, since
Note that the commutativity property implies that the contractions \(\alpha _i(z)\) have the same fixed point a. In the example above, we have \(a = 1\). Equation (2) is suitable to iteratively determine f(z). We distinguish between the following two cases.
where \(\alpha _{i_1,\ldots ,i_M}(z) = \alpha _1^{i_1} (\alpha _2^{i_2}(\cdots (\alpha _M^{i_M} (z)) \cdots ))\) and \(\alpha _i^n (z)\) is defined as the nth iterate of \(\alpha _i(z)\). In particular, \(\alpha _{0,\ldots ,0} (z) = z\). The functions \(L_{i_1,\dots ,i_M}(z)\) are recursively defined by
with \(L_{0,\dots ,0}(z) = 1\) and \(L_{i_1,\dots ,i_M}(z) = 0\) if one of the indices equals \(-1\). These functions can be interpreted as follows. A path from \((0,\dots ,0)\) to \((i_1,\dots ,i_M)\) is defined as a sequence of grid points that starts in \((0,\dots ,0)\) and ends in \((i_1,\dots ,i_M)\) by only taking unit steps \((0, \ldots , 1, \ldots , 0)\) with 1 at position \(k = 1, \ldots , M\). Figure 1 shows a path from (0, 0) to (3, 2). Clearly, there are \(\left( {\begin{array}{c}i_1+\dots +i_M\\ i_1,\dots ,i_M\end{array}}\right) \) paths leading from \((0,\dots ,0)\) to \((i_1,\dots ,i_M)\). Now assign weight \(g(\alpha _{i_1,\ldots ,i_k-1, \ldots i_M}(z))\) to a step from any grid point \((i_1,\dots ,i_k-1,\dots ,i_M)\) to \((i_1,\dots ,i_M)\) and define the weight of a path as the product of weights of all steps in that path (cf. Fig. 1). Then, \(L_{i_1,\dots ,i_M}(z)\) can be interpreted as the total weight of all \(\left( {\begin{array}{c}i_1+\dots +i_M\\ i_1,\dots ,i_M\end{array}}\right) \) paths from \((0,\dots ,0)\) to \((i_1,\dots ,i_M)\).
Fig. 1
Path from (0, 0) to (3, 2) consisting of the sequence of grid points (0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2). Its path weight is the product of the step weights \(g(\alpha _{0,0}(z))g(\alpha _{1,0}(z))g(\alpha _{1,1}(z))g(\alpha _{2,1}(z))g(\alpha _{3,1}(z)) \)
×
To handle (4), we proceed as follows. Note that, when \(i_1+\dots +i_M=n\),
For given z, the second term in the right-hand side of (8) converges to zero for \(n \rightarrow \infty \). This can be seen as follows. By substituting \(z=a\) in (3), we get \(g(a)=1\). Hence, from (6), step weight \(g(\alpha _{i_1,\ldots ,i_M}(z))\) with \(i_1+\cdots +i_M = n\) is close to \(g(a)=1\) for all n sufficiently large, say \(|g(\alpha _{i_1,\ldots ,i_M}(z)) - 1|< \epsilon < \kappa ^{-1} - 1\). In other words, the weight of sufficiently long paths grows at most with \(1+\epsilon \) per step. So there is a constant C such that for all n, the weight of a path from \((0,\dots ,0)\) to \((i_1,\dots ,i_M)\) with \(i_1+\cdots +i_M=n\) is bounded by \(C(1+\epsilon )^{n}\), implying that \(L_{i_1,\dots ,i_M}(z)\) is bounded by \(\left( {\begin{array}{c}i_1 + \dots + i_M\\ i_1,\dots ,i_M\end{array}}\right) C (1+\epsilon )^{n}\). Then, from (7), we can conclude that the second term in (8) is bounded by \(C (1+\epsilon )^{n+1}\kappa ^{n+1} |z-a|\mathbb E[X]\), which goes to zero for \(n \rightarrow \infty \). We have thus proven the following theorem.
Theorem 1
(Homogeneous case) The generating function f(z) is given by
The first term in the right-hand side of (8) is a sum of \(\left( {\begin{array}{c}M+n\\ M-1\end{array}}\right) \) terms. This number is \(O(n^{M-1})\), which grows quickly (polynomially) in n for already moderate values of M. However, this is not as quickly as in the non-commutative case, in which case we would have \(M^{n+1}\) terms, growing exponentially in n.
Remark 3
Above we have seen that the second term in the right-hand side of (8) converges to zero geometrically fast (with rate \((1+\epsilon )\kappa \)). Hence, the first term in the right-hand side of (8) will provide an accurate approximation for f(z) already for small values of n.
2.2 The inhomogeneous case \(K(z)\ne 0\)
We now consider inhomogeneous Eq. (2) and obtain after n iterations,
The first term of (10) is the same as in the homogeneous case. For given z, we proved that it converges if \(g(a) = 1\). For convergence of the second term, we need that either \(K(\alpha _{i_1,\ldots ,i_M}(z)) \rightarrow 0\) (Case 1) or \(p_1^{i_1} \dots p_M^{i_M} L_{i_1,\dots ,i_M}(z) \rightarrow 0\) (Case 2) as \(i_1+\cdots +i_M \rightarrow \infty \). In this subsection, we successively consider both cases.
Case 1 Since \(K(\alpha _{i_1,\ldots ,i_M}(z)) \rightarrow K(a)\), in this case we basically assume that \(K(a) = 0\). Note that, by substituting \(z=a\) in (2), this assumption implies that \(g(a) =1\) if \(f(a) \ne 0\) and thus that the first term in (10) converges. We now show that it also implies convergence of the second term. Similar to (7), we have for \(i_1+\cdots +i_M = n\),
where D is the maximum value of \(|K'(u)|\) in the closed disk with center a and radius \(|z-a|\) (intersected with the closed unit disk). Then, the kth term in the double sum appearing in (10) is bounded by \(C (1+\epsilon )^k \kappa ^k |z-a| D\), and hence, the double sum converges for \(n \rightarrow \infty \). We conclude that the following holds.
Theorem 2
(Inhomogeneous case) Provided \(K(a)=0\) and \(f(a) \ne 0\), the generating function f(z) is given by
The infinite product \(\prod _{n=0}^\infty g(\alpha _n (z))\) converges iff \(\sum _{n=0}^\infty (1-g(\alpha _n(z))\) converges (cf. Chapter I of [19]). Since \(g(\alpha _n(z))\) and \(K(\alpha _k(z))\) converge geometrically fast to \(g(a)=1\) and \(K(a)=0\), respectively [cf. (11)], we conclude that both the infinite product and the infinite sum of products in (13) converge.
Case 2 We now assume that \(p_1^{i_1} \dots p_M^{i_M} L_{i_1,\dots ,i_M}(z) \rightarrow 0\) and show that the assumption \(|g(a)|<1\) is sufficient for convergence of this term to zero. For all n sufficiently large, step weight \(g(\alpha _{i_1,\ldots ,i_M}(z))\) with \(i_1+\cdots +i_M = n\) is close to g(a), say \(|g(\alpha _{i_1,\ldots ,i_M}(z)) - g(a)|< \epsilon \) with \(|g(a)| +\epsilon < 1\). Hence, the weight of sufficiently long paths grows at most with \(|g(a)|+\epsilon \) per step. So there is a constant C such that for all n, the weight of a path from \((0,\dots ,0)\) to \((i_1,\dots ,i_M)\) with \(i_1+\cdots +i_M=n\) is bounded by \(C(|g(a)|+\epsilon )^{n}\), implying that \(L_{i_1,\dots ,i_M}(z)\) is bounded by \(\left( {\begin{array}{c}i_1 + \dots + i_M\\ i_1,\dots ,i_M\end{array}}\right) C (|g(a)|+\epsilon )^{n}\). Then, indeed, \(p_1^{i_1} \dots p_M^{i_M} L_{i_1,\dots ,i_M}(z) \rightarrow 0\) as \(n \rightarrow \infty \). Further, since \(K(\alpha _{i_1,\ldots ,i_M}(z)) \rightarrow K(a)\), these terms are bounded, say by constant D. Hence, we can conclude that the kth term of the double sum in (10) is bounded by \(C (|g(a)|+\epsilon )^k D\), and thus the double sum converges. The first term in (10) is bounded by \(C (|g(a)|+\epsilon )^{n+1}\) which converges to zero as \(n \rightarrow \infty \). This is summarized in the following theorem.
Theorem 3
(Inhomogeneous case) Provided \(|g(a)|<1\), the generating function f(z) is given by
In this section, we studied Eq. (2) for a generating function f(z) of a non-negative discrete random variable X. It is readily seen that Theorems 1–3 are also valid in case f(z) is the Laplace–Stieltjes transform (LST) of a non-negative continuous random variable X. Of course, then \(\alpha _1 (z), \ldots , \alpha _M (z)\) are assumed to be contraction mappings on the closed positive half space (instead of the closed unit disk).
3 The \(D_M/G/1\) shot-noise queue
In this section, we consider the workload at arrival epochs for a specific queue. The analysis of the LST of the workload gives rise to a simple recursion that has the form (2), in the homogeneous variant. This section thus provides a relatively simple illustration of our theory for the homogeneous case—while still having a few features that deviate from the setting of Sect. 2. The model under consideration is the \(D_M/G/1\) shot-noise queue; we refer to [7] for a recent survey on shot-noise queueing models. The \(D_M/G/1\) shot-noise queue is a single server queue, in which the successive interarrival times \(A_1,A_2,\dots \) of customers are i.i.d., with the distribution of a generic interarrival time A being given by
The service requirements of successive customers \(B_1,B_2,\dots \) are i.i.d. with finite mean, and with LST \(\beta (\cdot )\); all interarrival times and service times are independent. The special feature of the model is that the server speed is workload proportional (shot noise): when the workload is x, the service speed is rx. Let \(X_n\) denote the workload just before the arrival of the nth customer. It is well known [2] that, in between arrivals, the workload decreases exponentially; hence,
It is readily verified that, due to the workload-proportional decrease, the steady-state distribution of the \(\{X_n, n=1,2,\dots \}\) process exists. Stability conditions for queueing and storage models with more general workload-dependent decay have been discussed, a.o., by Brockwell et al. [10] and Cinlar and Pinsky [11] .
Let X denote a random variable distributed as the steady-state distribution of the process \(\{X_n,n=0,1,\dots \}\), with LST \(\xi (\cdot )\), then
with \(a_i := \mathrm{e}^{-rt_i}\), \(i=1,\dots ,M\). Observe the differences with (3): we are now considering an LST instead of a generating function, and \(\beta (a_is)\) is inside the summation.
Let us first briefly consider the case of the D/G/1 shot-noise queue, i.e., \(M=1\). In that case, iterating (17) n times gives, with \(a=a_1\):
Thirdly, \(\prod _{i=1}^{\infty } g_i\) converges iff \(\sum _{i=1}^{\infty } (1 - g_i)\) converges (cf. Chapter I of [19]); hence, the convergence of the product in (18) follows from
Some thought will make it clear that the ith term in this infinite product represents the contribution to X from an arrival that occurred i arrivals before the present one.
Let us now turn to the general \(D_M/G/1\) shot-noise case, cf. (15). After n iterations, (17) gives (very similarly to the analysis in Sect. 2.1)
Notice that an \((i_1,\dots ,i_M)\) term corresponds to a contribution to the workload (just before an arrival epoch) from an arrival that occurred \(i_1+\dots + i_M\) arrivals before the present one, the total interval consisting of \(i_k\) interarrival times of length \(t_k\), \(k=1,\dots ,M\), in any of \(\left( {\begin{array}{c}i_1+\dots +i_M\\ i_1,\dots ,i_M\end{array}}\right) \) orders. It is readily seen that
and hence, the sum in (22) is bounded by one. Furthermore, letting \(a_0 := \mathrm{max}(a_1,\dots ,a_M)\) and observing that \(a_0 = \mathrm{e}^{-r \mathrm{min}(t_1,\dots ,t_M)} < 1\), it is seen in a similar way as above and as in Sect. 2 that \(\xi (a_1^{i_1} \dots a_M^{i_M}s)\) converges geometrically fast to \(\xi (0)=1\). Hence, rewriting (22) as
One could subsequently derive the steady-state workload LST at an arbitrary epoch by averaging over one arrival interval, and using a stochastic mean-value theorem.
4 The BPIRE or RCINAR(1) process
In this section, we consider a branching process with immigration in a random environment (BPIRE process, see [14, 16]), also known as random coefficient integer-valued autoregressive process of order 1 (RCINAR(1) process, see [17, 20]). This process \(\{X_n, n=0,1,\dots \}\) is defined as follows:
where the \(Z_n\) are nonnegative integer-valued random variables with finite mean. The \(Y_{k,n}\) are Bernoulli random variables with parameter \(\xi _n\), i.e., \(\mathbb P(Y_{k,n}=0) = 1-\xi _n\) and \(\mathbb P(Y_{k,n}=1) = \xi _n\); but we assume the special feature that the \(\xi _n\) are themselves random variables, independent and identically distributed with \(\mathbb P(\xi _n=a_i)=p_i\), \(i=1,\dots ,M\). Hence, in generation n it holds with probability \(p_i\), \(i=1,\ldots ,M\), for all \(Y_{k,n}\) that they are 1 with probability \(a_i\) and 0 with probability \(1-a_i\). All \(Z_j\) and \(Y_{k,m}\) are also assumed to be independent. In Sect. 4.1, we consider the steady-state distribution of the process \(\{X_n,n=0,1,\dots \}\), and in Sect. 4.2 we do this for the generalization in which the BPIRE process behaves differently at zero, i.e., when \(X_n=0\) for some n.
4.1 The steady-state case
The generating function, f(z), of the stationary distribution of the process \(\{X_n, n=0,1,\dots \}\) satisfies the recursion
where g(z) is the pgf of the random variable \(Z_n\). Hence, we are in the homogeneous case (3) with contraction mappings \(\alpha _i(z) = 1- a_i+a_i z\). In this case, the functions \(\alpha _{i_1,\ldots ,i_M}(z) =\)\( \alpha _1^{i_1} (\alpha _2^{i_2}(\cdots (\alpha _M^{i_M} (z)) \cdots ))\) are given by
Define the functions \(L_{i_1,\dots ,i_M}(z)\) again recursively by (5) and use that the contraction mappings \(\alpha _i(z)\) have fixed point \(a=1\) in this case, and hence, \(f(a)=f(1)=1\). Theorem 1 now implies the following theorem.
Theorem 5
The steady-state probability generating function f(z) of the BPIRE process is given by
with \(V_0,V_1,\dots \) i.i.d. nonnegative integer random variables, with pgf \(g_0(z)\). \(V_n\) is assumed to be independent of all \(Y_{i,m}\), \(Z_m\) and \(X_m\), \(m=0,1,\dots ,n\). It is readily seen that the steady-state pgf f(z) in this case satisfies the recursion
Hence, we are in the inhomogeneous case of Eq. (2) with \(K(z) := f(0) [g_0(z)-g(z)]\). For future use we observe, by substituting \(z=0\) in (37), that
with \(L_{i_1,\dots ,i_M}(z)\) recursively defined by (5) with \(L_{0,\dots ,0}(z) = 1\) and \(L_{i_1,\dots ,i_M}(z) = 0\) if one of the indices equals \(-1\). The constant f(0), featuring in K(z), is determined by substituting \(z=1-a_i\) for \(i=1,\dots ,M\) into (39), multiplying both sides by \(p_i\), summing over i and using (38).
5 A reflected autoregressive process and an M/G/1 queue generalization
In this section, we consider an integer-valued stochastic process \(\{X_n, ~n=0,1,\dots \}\) that is very similar to the autoregressive process of the previous section, but includes a negative component and has reflection at zero. It is determined by the following relation:
with \([x]^+ = \mathrm{max}(0,x)\), \(Z_1,Z_2,\dots \) i.i.d. nonnegative integer-valued random variables with pgf C(z) and where \(Y_{k,n}\) are i.i.d. Bernoulli distributed random variables: \(\mathbb P(Y_{k,n}=1) = \xi _n\), \(\mathbb P(Y_{k,n}=0)=1-\xi _n\). In addition, we (again) assume the special feature that the \(\xi _n\) are themselves random variables, independent and identically distributed with \(\mathbb P(\xi _n = a_i)=p_i\), \(i=1,\dots ,M\), where \(\sum _{i=1}^M p_i =1\). Hence, in generation n it holds with probability \(p_i\), \(i=1,\dots ,M\), for all \(Y_{k,n}\) that they are 1 with probability \(a_i\) and 0 with probability \(1-a_i\). All \(Z_j\) and \(Y_{k,m}\) are also assumed to be independent of each other and of all preceding \(X_r\).
If all \(Y_{k,n}\) are equal to one, then (40) can be interpreted as follows. Consider the number of waiting customers in the M/G/1 queue, just after the beginning of thenth service. Let \(X_n\) denote this number, and let \(Z_n\) denote the number of arrivals during the nth service. Then, \(X_{n+1} = [X_n+Z_n-1]^+\). If, in addition, each of the \(X_n\) customers becomes impatient with probability \(1-a\) during the nth service and leaves, then the sequence \(\{X_n\}\) satisfies (40) with \(p_1=1\) and \(a_1=a\), i.e., with \(\xi _n \equiv a\).
Without the maximum operator, we have the defining recursion of an INAR(1) (integer-valued autoregressive) process, cf. Weiss [21]. We impose the stability condition that both \(a_i < 1\) for all \(i=1,\dots ,M\) and \(\mathbb E[\mathrm{log} (1+Z)] < \infty \), cf. [6] for the case \(M=1\).
Below we show how the pgf f(z) of the steady-state distribution of the \(\{X_n, ~n=0,1,\dots \}\) process can be obtained. It follows from (40), with \([x]^- = \mathrm{min}(0,x)\) and X denoting a generic random variable with pgf f(z), that
which makes sense probabilistically; the right-hand side represents the probability that both \(Z=0\) and \(\sum _{k=1}^X Y_k =0\). We observe that (41) can be rewritten in the form
where \(g(z) = C(z)/z\) and \(K(z) = q_{-1}(1 - \frac{1}{z})\). Hence, we have the exact same form as (2). Furthermore, the fixed point of the iterates \(\alpha _i(z) = 1-a_i+a_iz\) is \(z=1\), and we have that \(K(1)=0\). Hence, f(z) is given by Theorem 2.
Remark 8
It should be noticed that now g(z) and K(z) have a pole at zero. The iterate \(K(1 -a_1^{i_1} \dots a_M^{i_M}(1-z))\) has a pole inside the unit circle if \(a_1^{i_1} \dots a_M^{i_M} \in (\frac{1}{2},1)\). Typically, this will only be the case for the first few iterations. In [6], where the case \(M=1\) is treated, it is shown that the singularities do not pose a real problem, as they are all removable singularities which are exactly compensated. In the present more general case, this can be shown in a similar way, but that is beyond the scope of the present paper.
6 An M/G/1-type reflected autoregressive process
In this section, we consider the following extension of a model of an autoregressive process, studied in [8]:
where \(R_0=z\) and where, for \(n=0,1,\ldots \), \(G_n = Y_n - B_n\) with all \(B_n\) independent random variables which are \(\mathrm{exp}(\lambda )\) distributed, and all \(Y_n\) non-negative i.i.d. random variables with distribution \(F_Y(\cdot )\) and LST \(\phi _Y(\cdot )\). In [8], one has \(A_n \equiv a\) with \(a \in (0,1)\), but we now take \(A_0,A_1,\dots \) i.i.d., with the following discrete distribution:
In [8], both the transient behavior and steady-state behavior of the \(R_n\) process with \(A_n \equiv a\) are studied, via a Wiener–Hopf technique (cf. [12]) that leads to a recursion. We apply the same tools in the extension defined by (43), (44). Below we first follow the approach of [8]. Introduce \(U_n := \mathrm{min}(A_nR_n+G_n,0)\) for \(n=0,1,\dots \), and the transforms
The first transform is analytic for \(\mathrm{Re} ~s \ge 0\) and the second one for \(\mathrm{Re} ~s \le 0\). Observing that \(1 + \mathrm{e}^x = \mathrm{e}^{\mathrm{max}(x,0)} + \mathrm{e}^{\mathrm{min}(x,0)}\), we have for \(n=0,1,\dots \):
Restricting ourselves at this stage to \(\mathrm{Re} ~s =0\) ensures that all terms are properly defined. Multiplying both sides by \(\lambda -s\), one obtains:
Because all \(a_i < 1\), the steady-state distribution of the \(\{R_n, n=0,1,\dots \}\) process always exists [13]. We shall restrict ourselves to the steady-state case. (The transient case can in principle be studied in a similar way. Here it should be observed that, with fixed point \(a=0\), we have \(K(0) = 1 + \frac{r}{1-r} - rU_z(r,0) = 1 \ne 0\). We are now in Case 2 of Sect. 2.2; \(|r|<1\) will guarantee the convergence of the corresponding \(p_1^{i_1} \ldots p_M^{i_M} L_{i_1,\ldots ,i_M}(z)\) as \(i_1+\cdots +i_M=n \rightarrow \infty \).)
Let \(R(s) = \mathbb E[\mathrm{e}^{-sR}]\), with R a random variable with the steady-state distribution of the \(R_n\) process. \(U(s) = \mathbb E[\mathrm{e}^{-sU}]\) is similarly defined. After multiplying both sides of (48) by \(1-r\) and letting \(r \rightarrow 1\), an Abelian theorem for generating functions implies that
The left-hand side of (49) is analytic in \(\mathrm{Re}~s > 0\), and continuous in \(\mathrm{Re} ~s \ge 0\).
The right-hand side of (49) is analytic in \(\mathrm{Re}~s < 0\), and continuous in \(\mathrm{Re} ~s \le 0\).
R(s) is for \(\mathrm{Re}~s \ge 0\) bounded by 1, and hence, the left-hand side of (49) behaves at most as a linear function in s for large s, \(\mathrm{Re}~s > 0\).
U(s) is for \(\mathrm{Re}~s \le 0\) bounded by 1, and hence, the right-hand side of (49) behaves at most as a linear function in s for large s, \(\mathrm{Re}~s < 0\).
Liouville’s theorem [19] now implies that both sides of (49), in their respective half-planes, are equal to the same linear function in s. We focus on the left-hand side of (49):
Substituting \(s=0\), we see that \(C_0=0\). Taking \(s \rightarrow \infty \), we see that \(C_1 = - \mathbb P(R=0)\), but that does not yet determine \(C_1\). Taking \(s=\lambda \), we observe that
In fact, it is not hard to interpret this relation (replacing \(C_1\) by \(-\mathbb P(R=0)\)), using (43) and the fact that \(\phi _Y(\lambda ) = \mathbb P(B > Y)\) and \(R(a_i \lambda ) = \mathbb P( B > a_i R)\).
Equation (52) has exactly the same form as (2). Observe that the fixed point of the iterates \(\alpha _i(z) = a_iz\) is \(z=0\) and that \(K(0)=0\). Hence, Theorem 2 applies. It follows that
We finally need to determine the constant \(C_1 = - \mathbb P(R=0)\), that features in K(s). This is done by taking \(s=a_i \lambda \), for \(i=1,\dots ,M\), in (54), and adding the resulting M expressions, using (51):
Just like in [8], the removable singularity \(s=\lambda \) requires some extra care, but poses no real problems.
7 Conclusion and suggestions for further research
In this paper, we have developed a method for treating recursions between random variables that lead to functional equations of the form (2). We have also presented several examples of branching processes, queueing processes and autoregressive processes, where such recursions and ensuing functional equations naturally occur. A brief (by no means exhaustive) collection of other queueing models which can be analyzed with the approach of the present paper (and for which the special case of Eq. (1) is treated in the following references) is (i) the M/G/1 queue with vacations [18], (ii) the globally gated polling model [5], (iii) the ASIP tandem model [4], and (iv) a vacation plus retrials model [9].
Several interesting research questions present themselves. We mention the following ones.
In [1], a vector version of (2) for the LST of the virtual workload has been treated, for a specific queueing system with impatience. It would be interesting to study such a vector version in more generality. Interestingly, in [1], the mappings \(\alpha _i (z)\) are of the form \(\alpha _i (z) = z + \theta _i\). These commutative mappings, however, are not contractions.
In this paper, we have restricted ourselves to commutative contraction mappings. In the noncommutative case, one has an explosion of terms which no longer can be grouped so neatly as in the analysis in Sect. 2. It would be interesting to investigate what can still be accomplished in the noncommutative case.
Acknowledgements
The research of Onno Boxma is partly funded by the NWO Gravitation Programme NETWORKS (Grant No. 024.002.003).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
