1 Introduction

We introduce in this paper a family of vector valued stochastic recursive equations that have the form Y n + 1 = A n ( Y n ) + B n . Y n are assumed to be non-negative. B n , which we call the “migration” term, is assumed to be stationary ergodic and A n are a sequence of i.i.d. stochastic processes. Moreover, A n are assumed to have a divisibility property: if for some k, y = y 0 + y 1 + ... + y k then A n (y) can be represented as \(A_n (y) = \sum_{i=0}^k \widehat A_n^{(i)} \big( y^i \big) \) where \( \big\{ \widehat A_n^{(i)} \big\}_{i=0,1,2,...,k}\) are identically distributed with the same distribution as A n (·), but they need not be independent.

We compute for the above model the probability distribution, the two first moments and correlations. We then apply our results to derive two types of models for the discrete time infinite server queue.

One can relax the i.i.d. assumptions on A n but working with a general stationary ergodic framework for both A n and B n does not allow one to get explicit expressions for the two first moments of Y n at stationary regime (which is the main purpose of this paper) except for some special cases, such as the case where B n  = 0 for all n. We shall treat this case briefly in Section 5.

The main contribution of the paper is in proposing a unifying framework that is general enough to include various types of processes that have so far been studied separately, and is on the other hand simple enough to allow us to derive closed form expressions for the first two moments. Our framework covers branching processes (both in discrete as well as in continuous state space), for which \( \big\{ \widehat A_n^{(i)} \big\}_{i=0,1,2,...,k}\) are independent. It also covers stochastic linear difference equations for which \( \big\{ \widehat A_n^{(i)} \big\}_{i=0,1,2,...,k} \) are equal.

1.1 Related work

As our framework covers both branching processes as well as linear stochastic difference equations, we present below some background on each of these processes. We further mention some applications to queueing networks and to network protocols.

Branching processes

Branching processes have their origins in the work of Bienaymé (1845) and Galton and Watson (1874). The first asymptotic result in the theory of branching processes was obtained by Kolmogorov in (1938). The first reference on branching with migration is Sevastyanov (1957). Overviews on branching processes can be found in Athreya and Jaggers (1997), Athreya and Vidyashankar (2001). We have studied branching processes with stationary ergodic migration in Altman (2005) and in Altman and Fiems (2007); the first reference studied the framework of discrete state space and the second studied the continuous one (see Bertoin 2002; Le Gall 2000 and references therein). For branching processes with an i.i.d. migration process, the two first moments have been derived in Quine (1970).

Stochastic linear difference equations

Stochastic difference equations of the form Y n + 1 = A n Y n  + B n have been studied extensively where (A n ,B n ) can be general stationary ergodic sequences. Stability conditions and asymptotical expressions for the stationary distributions can be found in Brandt et al. (1992), Glasserman and Yao (1995) and references therein. We are not aware however of derivations of the second moments for these equations.

Queueing applications

Branching models appear frequently in queueing theory. They are already used in the work of Borel in 1942 (Borel 1942) and of Kendal in 1951 (Kendall 1951) for the busy period of an M/G/1 queue. Connections of branching processes with the processor sharing queue have been shown in 1988 in Yashkov (1988) and further exploited by Grishechkin in (1992) (see survey on processor sharing queues in Yashkov and Yashkova (2007) for more recent related references). At 1992, Grischechkin published in Grishenchkin (1992) an analysis of retrial queues and identified an underlying branching process with immigration. Polling systems have been related to multi-type branching processes by Resing in (1993).

Applications to network protocols

Linear stochastic difference equations have been used extensively to study the TCP congestion control protocol over the internet. One and two dimensional models that describe the behavior of the protocol under a random loss process have been studied in Dumas et al. (2002), Moller et al. (2007). Models for any number of competing connections where losses are due to congestion have been studied in Baccelli and Hong (2002), Altman et al. (2006) and references therein.

Relation to our previous work

Our framework has its origin in Altman (2002), where we studied a general form of branching process with migration. We have applied successfully this methodology to study the following models:

  • (i) a single gated queue (Altman 2002) with vacations where the dynamics can be described through a one dimensional branching process,

  • (ii) A polling system with two queues with exhaustive or gated service (Groenvelt and Altman 2005),

  • (iii) A symmetric polling system with exhaustive or gated service and with any number of queues (Altman and Fiems 2007),

On the theoretical side we propose in this paper a general approach that has the branching processes as a special case. We apply our theoretical framework to derive two types of models for the discrete time infinite server queue; the first, reported already in Altman (2005) is based on using a branching process formalism and the second using linear stochastic difference equations.

1.2 Structure

The structure of the paper is as follows. We introduce the discrete time model in Section 2. The first and second moments of the corresponding state variables are introduced in Section 3. The expressions obtained are shown to further simplify for specific Markovian dynamics that creates the correlation. In Section 4 we illustrate the above results in a queueing example. We briefly consider in Section 5 the case with no migration: B n  = 0 for all n.

2 The model

Consider a column vector Y n whose entries are \(Y_n^i\), i = 1,...,d where \(Y_n^i\) take values on the nonnegative subset of \(\mathbb{R^+}\). Consider the following equation in vector form:

$$Y_{n+1} = A_n ( Y_n ) + B_n .$$
(1)

The d-dimensional column vector B n is a stationary ergodic stochastic process whose entries \(B_n^i, i=1,...,d\) are subsets of the nonnegative real numbers.

For each n, A n are non-negative vector valued random fields that are non-decreasing in their arguments. A n are i.i.d. with respect to n, and A n (0) = 0.

We shall assume that A n satisfy the following conditions:

  • A1:  A n (y) has the following divisibility property: if for some k, y = y 0 + y 1 + ... + y k where y m are vectors, then A n (y) can be represented as

    $$A_n (y) = \sum\limits_{i=0}^k \widehat A_n^{(i)} \big( y^i \big)$$

    where \( \big\{ \widehat A_n^{(i)} \big\}_{i=0,1,2,...,k}\) are identically distributed with the same distribution as A n (·). In particular, for any sequence k(n), \(\big\{ \widehat A_n^{(k(n))} \big\}_n \) are independent.

Remark 1

For a given n, we do not assume that \(\big\{ \widehat A_n^{(i)} \big\}_{i=0,1,2,...}\) are independent.

  • A2:  (i) There is some matrix \({\cal A}\) such that for every y,

    $$E [ A_n (y) ] = {\cal A} y .$$

    (ii) The correlation matrix of A n (y) is linear in yy T and in y. We shall represent it as

    $$E \left[A_n (y) A_n(y)^T\right] = F \left( y y^T \right) + \sum\limits_{j=1}^d y_j \Gamma^{(j)} \, ,$$
    (2)

    where F is a linear operator that maps d×d nonnegative definite matrices to other d×d nonnegative definite matrices and satisfies F(0) = 0.

When Y is random and independent of A n then A2 yields

$$E \left[A_n (Y) A_n(Y)^T\right] = F \left( E \left[ Y Y^T\right] \right) + \sum\limits_{j=1}^d E[Y_j] \Gamma^{(j)} \, ,$$
(3)
$$\begin{array}{lll}{\rm cov}[A_n (Y)] &=& F( cov( Y ) ) + F \left( E [Y] E\left[Y^T\right] \right) - {\cal A} E[Y] E[Y]^T { \cal A}^T + \sum\limits_{j=1}^d E[ Y_j ] \Gamma^{(j)} \nonumber \\ &=& F( cov( Y ) ) - {\cal A} E[Y] E[Y]^T { \cal A}^T + E \left[ A_n ( E[Y] ) A_n ( E[Y])^T \right] \nonumber \\ &=& F( cov( Y ) ) + cov [ A_n ( E[Y] ) ] \end{array}$$
(4)

2.1 Examples

Example 1

Linear stochastic difference equations A n (·) is assumed to be linear and thus there is a random matrix, which we denote with some abuse of notation as A n , such that A n (Y n ) can be written as A n Y n . In particular we have \(\widehat A_n^{(i)} = A_n \). Let (A n ) i be the ith row of the matrix A n . Now, A2 holds with

$$F (y y^T) = \operatorname{E} \Big( A_n (y) ( A_n (y))^T \Big) = E \Big( A_n y y^T [ A_n ]^T \Big) .$$

We present some more insight on F. Let (A n ) i denote the ith row of A n . Then

$$\left[A_n y y^T A_n^T \right]_{ij}= [A_n y ]_i [A_n y]_j = ( A_n )_i y [ ( A_n )_j y ] = y^T ( ( A_n )_i )^T [ ( A_n )_j y ]$$

Hence,

$$ \left[ F\left(yy^T\right) \right]_{ij} = y^T \operatorname{E} \left[ ( ( A_n )_i )^T ( A_n )_j \right] y .$$

Example 2

Discrete multitype branching processes with migration The ith element of the column vector A n (Y n ) is given by

$$[ A_n ( Y_n ) ]_i = \sum\limits_{j=1}^d \sum\limits_{k=1}^{Y^j_n} \xi_{ji}^{(k)} (n) $$
(5)

where ξ (k) (n), k = 1,2,3,..., n = 1,2,3,... are i.i.d. random matrices of size d×d. Each of its element is a nonnegative integer. We assume further that for any l = 1,2,3,..., l′ = 1,2,3,..., k = 1,...,d, i = 1,...,d, m = 1,...,d, j = 1,...,d and \(m\not=k\), \( \xi^{(l)}_{ki} (0)\) and \( \xi^{(l')}_{mj} (0)\) are independent. Denote \(E \left[ \xi^{(k)}_{ij} (n) \right] = {\cal A}_{ji}. \left\{ \widehat A_n^{(i)} \right\}_{i=0,1,2,...,k}\) are i.i.d.

Denote \(cov( \xi )_{jk}^i = E( \xi_{ij}^{(0)} \xi_{ik}^{(0)} ) - {\cal A}_{ji} {\cal A}_{ki} \). We show that A2 holds. We have:

$$\begin{array}{lll}E[ ( A_n (y ))_i (A_n (y))_j ] &=& E \left( \sum\limits_{k=1}^d \sum\limits_{l=1}^{ y_k} \xi_{ki}^{(l)} (0) \sum\limits_{m=1}^d \sum\limits_{l'=1}^{ y_m} \xi_{mj}^{(l')} (0) \right) \\ & = & E\left( \sum\limits_{k=1}^d y_k {\cal A}_{ik} \sum\limits_{m \not=k} y_m {\cal A}_{jm} \right) +E\left( \sum\limits_{k=1}^d \sum\limits_{r=1}^{y_k} \sum\limits_{s=1}^{y_k} \xi_{ki}^{(r)} \xi_{kj}^{(s)} \right) \\ &=& \sum\limits_{k=1}^d \sum\limits_{m \not=k} {\cal A}_{ik} {\cal A}_{jm} y_k y_m + E \left( \sum\limits_{k=1}^d \sum\limits_{r=1}^{y_k} \sum\limits_{s=1,s\not=r}^{y_k} \xi_{ki}^{(r)} \xi_{kj}^{(s)} \right) \nonumber\\ &&+\, E \left( \sum\limits_{k=1}^d \sum\limits_{r=1}^{y_k} \xi_{ki}^{(r)} \xi_{kj}^{(r)}a^{(j)} \right) \\ &=& \sum\limits_{k=1}^d \sum\limits_{m \not=k} {\cal A}_{ik} {\cal A}_{jm} y_k y_m + \sum\limits_{k=1}^d \left(y_k^2 - y_k \right) {\cal A}_{ik} {\cal A}_{jk} + \sum\limits_{k=1}^d y_k E \left[ \xi_{ki}^{(0)} \xi_{kj}^{(0)} \right] \\ &=& \sum\limits_{k=1}^d \sum\limits_{m =1}^d {\cal A}_{ik} {\cal A}_{jm} y_k y_m + \sum\limits_{k=1}^d y_k cov(\xi)_{ij}^k \end{array}$$

Thus Γ(k) is given by the matrix cov( ξ)k.

Example 3

Continuous state branching processes with migration For each A n and for each y ∈ ℝ+ m, A n (y) takes values in ℝ+ m. A n is a nonnegative Additive Lévy fieldFootnote 1 We recall the definition of a K-parameter Lévy Field and then that of an additive Lévy field.

Let K be a cone in ℝd inducing an ordering ≤  K . A K-parameter Lévy process {A(s), s ∈ K } on ℝm is a collection of random variables on ℝm satisfying the following properties.

  1. (a)

    Independent increments;

  2. (b)

    Stationarity in each direction in K;

  3. (c)

    Continuity in probability: for each s ∈ K, A(s′) →A(s) in probability as |s′ − s| → 0 with s′ ∈ K;

  4. (d)

    A(0) = 0 almost surely;

  5. (e)

    Almost surely, A(s) is K-right continuous with K-left limits in s.

For precise definitions of independent increments and stationarity, the reader is referred to Sato’s monograph (Sato 1999).

We recall first some properties of the case K = ℝ +  and then use them for the definition of additive Markov fields with K = ℝ+ d. Let m denote the dimension of A(t). The characteristic function of A(t) is then given by (see a.o. Bertoin 2002; Sato 1999; Khoshnevisan et al. 2003),

$$\operatorname{E}[ e^{i < \xi , A(t) > } ] = e^{ - t \psi ( \xi ) } ,$$

for any t ∈ ℝ + , where by the Lévy-Khintchine formula,

$$\psi( \xi ) = i < a, \xi > + \int_{\mathbb{R}^m_+ } \left[ e^{i<x,\xi>} - 1 \right] L(dx) ,$$
(6)

for all ξ ∈ ℝm and for a given a ∈ ℝ+ m. Here L is a finite measure on ℝm concentrated on ℝ+ m − {0}. ψ is called the Lévy exponent of A and L is the corresponding Lévy measure (Khoshnevisan et al. 2003).

The expectation and covariance of a multivariate Lévy process have the following form:

$$E[A(t)] = t {\cal A} , \qquad {\rm cov}[A (t)] = t \Gamma$$
(7)

where \({\cal A}\) is an m-dimensional column vector and Γ is a symmetric m × m matrix. The values of \({\cal A}\) and of Γ can be obtained by differentiating Eq. 6 once and twice respectively. That is, the ith element of \({\cal A}\) and the ijth element of Γ are given by (see also Gjessing et al. 2003),

$$[{\cal A}]_i = \left. \frac{ \partial \psi( \xi ) }{ i \partial \xi_i } \right|_{\xi=0} \qquad \text{and} \qquad [\Gamma]_{ij} = - \left. \frac{ \partial \psi( \xi )^2 }{ \partial \xi_i \partial \xi_j } \right|_{\xi=0} \, .$$

We define next an Additive Lévy field with an ℝ+ d valued “time” parameter. Let A denote a Lévy field and let A [1] , ... , A [d] be d independent Lévy processes on ℝm (with scalar valued time parameters). We then assume that the random field A has the following decomposition:

$$A(y) = A^{[1]} ( y_1) + ... + A^{[d]} ( y_d )\, ,$$
(8)

for all y = (y 1 , ... , y d ) ∈ ℝ+ d. Let ψ 1 , ... , ψ d be the Lévy exponents corresponding to A [1] , ... , A [d]. Then for any y ∈ ℝd, the characteristic function of \(A(y) = \sum_{j=1}^d A^{[j]} ( y_j ) \) is given by

$$\operatorname{E} [ e^{i < \xi , A(y) > } ] = e^{ - \sum_{j=1}^d y_j \psi_j ( \xi ) } = e^{ - < y , \Psi ( \xi ) > } , \quad \xi \in \mathbb{R}^m .$$

where Ψ = ( ψ 1 , ... , ψ d ) and where < . , . > is the scalar product of two vectors.

The expectation of A(y) is given by

$$\operatorname{E}[ A (y) ] = \sum\limits_{j=1}^d y_j {\cal A}^{[j]} = {\cal A} y \, ,$$
(9)

where \({\cal A}^{[j]}=\operatorname{E}[A^{[j]}(1)]\) denotes the expectation of A (j)(1) and where \({\cal A}\) is a matrix whose jth column equals \({\cal A}^{[j]}\). Similarly, the covariance matrix of A(y) is given by,

$${\rm cov} [A(y)] = \sum\limits_{j=1}^d y_j \Gamma^{(j)} \, ,$$
(10)

where Γ(j) = cov[A [j](1)] is the corresponding covariance matrix of A [j] (1).

We next describe a hybrid model whose state has one discrete and one continuous component.

Example 4

A queue with gated service with vacations.

Consider an M/GI/1 queue with a Poisson arrival process with rate λ and i.i.d. service times with first and second moment given by s and s (2). Each time the server arrives at the queue, a gate is closed and the server begins a busy period in which it serves all those present at the moment that the gate was closed. When this period ends, the server leaves on vacation.

Denote the nth busy period duration by H n and the duration of the nth vacation as (which is the vacation taken at the end of the nth busy period) by V n . Define a cycle to be the period consisting of a busy period and the subsequent vacation and denote the duration of the nth cycle by C n  = H n  + V n . Let X n de the number of customers present at the beginning of the nth cycle. X n is a discrete branching process and C n is a continuous branching process.

Let Y n be a two dimensional vector with entries Y n,1 = X n + 1, Y n,2 = C n . Next we present Y n as a single branching process. Let \(A_n^{[1]} (t) \) denote the number of arrivals during an interval of duration t. Let \(A_n^{[2]} (k):= \sum_{i=1}^k S_n^{(i)} \) where \(S_n^{(i)}\) are i.i.d. and represent the duration of the i service time that occurred during the nth cycle. We now set

$$A_n(k,t)=A^{[1]}_n (t) (0,1)^T + A_n^{[2]} (k) (1,0)^T$$

Let \(B^1_n\) denote the number of arrivals during V n and let \(B_n = ( B_n^1 , V_n )^T \). With these definitions, the dynamics is given by Eq. 1.

The process Y n is neither a discrete nor a continuous branching process, but it is a semi-linear process. We note that A n has the structure of Eq. 8,

2.2 Stability conditions

We shall understand below \(\bigotimes_{i=n}^k A_i (x) = x \) whenever k < n, and \(\bigotimes_{i=n}^k A_i (x) = A_k ( A_{k-1} ( ... (A_n (x))..)) \) whenever k > n.

We have for j > 1

$$E \left[ \left( \bigotimes\limits_{i=1}^{j} A_i \right) ( y ) \right] ={\cal A}^j y$$
(11)

Define \({\left\|y\right\|}\) stands for the maximum absolute value of the elements of a vector y.

Let \({\left\|\cal A\right\|}\) stands for the largest absolute value of the eigenvalues of \({{\cal A}}\).

We make the following assumptions throughout

  • A3:  \({\left\|\cal A\right\|}< 1 \) and E[B 0] < ∞

Theorem 1

  1. (i)

    For n > 0 , Y n can be written in the form

    $$Y_n = \widetilde Y_n + \left( \bigotimes\limits_{i=0}^{n-1} \widehat A_i^{(0)} \right) ( Y_0) \mbox{ where } \widetilde Y_n = \sum\limits_{j=0}^{n-1} \left( \bigotimes\limits_{i=n-j}^{n-1} \widehat A_i^{(n-j)} \right) ( B_{n-j-1} )$$
    (12)

    is the solution of Eq.  1 with initial condition Y 0 = 0.

  2. (ii)

    there is a unique stationary solution \(Y_n^*\) of Eq.  1 , distributed like

    $$Y_n^* =_d \sum\limits_{j=0}^{\infty} \left( \bigotimes\limits_{i=n-j}^{n-1} \widehat A_i^{(n-j)} \right) ( B_{n-j-1} ) , \qquad n \in Z .$$
    (13)

    The sum on the right side of Eq.  13 converges absolutely P -almost surely. Furthermore, one can construct a probability space such that \( \lim_{n \to \infty} {\left\|Y_n - Y_n^*\right\|} = 0\) , P-almost surely. for any initial value Y 0.

Proof

Equation 12 is obtained by iterating Eq. 1.

Define the set of stochastic recursions on the same probability space as Y n :

$$Y_{n+1}^{ [ \ell ] }(y) = A_n \left( Y_n^{[ \ell ] }(y) \right) + B_n , \quad m \geq - \ell ,\qquad Y_{- \ell }^{ [ \ell ] } (y) = y .$$
(14)

For each n ≥ 0 , \( Y_n^{[ \ell ] }(0) \) is monotonically non-decreasing in ℓ so that the limit \(Y_n^* = \lim_{ n \to \infty } Y_n^{[ \ell ] }(0) \) is well defined. Since this is measurable on the tail σ-algebra generated by the stationary ergodic sequence { A n , B n }, it is either finite P-a.s. or infinite P-a.s. The last possibility is excluded since it follows by induction that for every ℓ ≥ 0 and n ≥ − ℓ that \(E[Y_n^{[\ell]}(0) ] \leq (I - {\cal A} )^{-1} b \), and hence \(E[Y_n^*] \leq (I - {\cal A} )^{-1} b \), which is finite.

By the definition of \(\widehat A_n^{(i)}\), by Remark 1 and by Eq. 11, we have

$$E \left[ \left( \bigotimes\limits_{i=1}^{j} \widehat A_i^{(0)} \right) ( y ) \right] ={\cal A}^j y ,$$

which converges to zero by Assumption A3. Since \( \left( \bigotimes_{i=1}^{j} \widehat A_i^{(0)} \right) ( y ) \) is non-negative, it then follows from Fatou’s Lemma that it converges to zero P-a.s. Finally, this implies that the difference

$$Y_n - Y_n^* = \left( \bigotimes\limits_{i=1}^{j} \widehat A_i^{(0)} \right) ( Y_0 ) - \left( \bigotimes\limits_{i=1}^{j} \widehat A_i^{(0)} \right) ( Y_0^* )$$

converges to 0 P-a.s. This implies also the uniqueness of the stationary regime. □

3 Computation of first and second moments

3.1 General results

Denote by \(\overline y_i\) and \(y_i^{(2)}\) the first and second moment of the ith element of \(Y^*_n\). Denote \(cov(Y)_{ij}=E[( Y_0^* )_i (Y_0^*)_j ] - \overline y_i \overline y_j \). Let b i and \(b^{(2)}_i\) denote the two first moments of \(B_n^i\). Define the following d × d matrices:

\({\cal B}(k)\) :

is the matrix whose ijth entry equals \(E\left[B_0^i B_k^j\right]\), where k is an integer.

\(\widehat B\) :

is the matrix whose ijth entry equals b i b j ,

cov(B):

is the matrix whose ijth entry equals \( E\left[B_0^i B_0^j \right] - b_i b_{j} \).

Define \(\widehat {\cal B} (k):= {\cal B} (k) - \widehat B \).

Theorem 2

  1. (i)

    The first moment of \(Y_n^*\) is given by

    $$E[Y^*_0]=(I-{\cal A})^{-1} b .$$
    (15)
  2. (ii)

    Assume that the first and second moments b i and \(b_i^{(2)}\) ’s are finite and that F satisfies

    $$\lim\limits_{n \to \infty} F^n = 0 .$$
    (16)

    Define Q to be the matrix whose ijth entry is \(Q_{ij} = \sum_{k=1}^d \overline y_k \Gamma^{(k)} \) . Then the matrix cov(Y *) is the unique solution of the set of linear equations:

    $$cov(Y) = cov(B) + \sum\limits_{r=1}^{\infty} \Big( {\cal A}^r \widehat {\cal B}(r) + \Big[ {\cal A}^r \widehat {\cal B}(r) \Big]^T \Big) + F ( cov [ Y ] ) + Q .$$
    (17)

    The second moment matrix E[YY T ] in steady state is the unique solution of the set of linear equations:

    $$ E[ Y Y^T ] = E[ B_0 B_0^T ] + \sum\limits_{r=1}^{\infty} \Big( {\cal A}^r {\cal B}(r) + \Big[ {\cal A}^r {\cal B}(r) \Big]^T \Big) + F ( E [ Y Y^T ] ) + Q .$$
    (18)

Remark 2

Note that the sums both in Eq. 17 as well as in Eq. 18 are finite since the finiteness for all i of the second moments \(b^{(2)}_i\) implies that \({\cal B}(j)\) are uniformly bounded and since \({\left\|A\right\|}<1\). Note also that if for some i, \(b^{(2)}_i\) is infinite then it follows directly from Eq. 1 that \(E([Y_n]_i^2)\) is infinite for all n > 0 and thus also in the stationary regime.

Proof of Theorem 2

  1. (i)

    We first note that \(Y^*_0\) has a finite mean. This can be seen by taking expectation in Eq. 13 and making use of assumption A3. Taking the first moment at stationary regime of Eq. 1 we obtain Eq. 15.

  2. (ii)

    To obtain the covariance, we first note that Eq. 3 implies

    $$E[ ( A_0 (Y_0 ))_i (A_0 (Y_0))_j ] = \left[ F \left( E\left[ Y_0 Y_0^T \right]\right) \right]_{ij} + \sum\limits_{k=1}^d \overline y_k \Gamma_{ij}^{(k)} $$

    and, with \( {\bf B_0^-} := ( B_0 , B_{-1} , B_{-2} , ... )\) we have

    $$\begin{array}{lll}E[ ( Y_0 )_i B_0^r ] &=& \sum\limits_{j=0}^{\infty} E \left\{ \left[ \left( \bigotimes\limits_{i=-j}^{-1} \widehat A_i^{(-j)} \right) ( B_{-j-1} ) \right]_i B_0^r \right\} \\ & = & \sum\limits_{j=0}^{\infty} E \left( \left. E \left\{ \left[ \left( \bigotimes\limits_{i=-j}^{-1} \widehat A_i^{(-j)} \right) ( B_{-j-1} ) \right]_i B_0^r \right\} \right| {\bf B_0^-} \right) \\ & = & \sum\limits_{j=0}^{\infty} E \Big( ( {\cal A}^j B_{-j-1} )_i B_0^r \Big) \\ &=& \sum\limits_{j=0}^{\infty} \sum\limits_{s=1}^d ( {\cal A}^j )_{is} {\cal B}(j+1)_{sr} \end{array}$$

    where the last equality follows from Eq. 11. Note that the last sum is finite since the finiteness for all i of the second moments \(b^{(2)}_i\) implies that \({\cal B}(j)\) are uniformly bounded and since \({\left\|A\right\|}<1\). Next we compute

    $$\begin{array}{lll}E[(A_0(Y_0))_i B_0^r ] &=& E \Big[ ((A_0(Y_0))_i B_0^r \Big| Y_0 , B_0 \Big]\\ &=& \sum\limits_{k=1}^d {\cal A}_{ik} E\left[ \left( Y_0^k \right) B_0^r \right] = \sum\limits_{j=1}^{\infty} \Big( {\cal A}^j {\cal B}(j) \Big)_{ir} \end{array}$$

    We thus obtain

    $$\begin{array}{lll}E\left[ Y_0^i Y_0^j \right] &=& E\left[B_0^i B_0^j \right] + E\left[\left(A_0(Y_0)\right)_i B_0^j \right] + E\left[(A_0(Y_0))_j B_0^i \right]\\ &&+\, \left[ F\left( E\left[ Y_0 Y_0^T \right] \right) \right]_{ij} + Q_{ij} \\ &=& E\left[B_0^i B_0^j \right] + \sum\limits_{r=1}^{\infty} \Big( {\cal A}^r {\cal B}(r) + \Big[ {\cal A}^r {\cal B}(r) \Big]^T \Big)_{i,j} + \left[ F \left( \operatorname{E}\left[Y_o Y_o^T \right] \right)\right]_{ij} + Q_{ij} \end{array}$$

    which gives in matrix notation Eq. 18.

    We now rewrite Eq. 18 as

    $$\begin{array}{lll} cov( Y ) + { \overline y } \ \overline y^T &=& cov(B) + \widehat B + \sum\limits_{r=1}^{\infty} \Big( {\cal A}^r \widehat {\cal B}(r) + \Big[ {\cal A}^r \widehat {\cal B}(r) \Big]^T \Big) \\ &&+ {\cal A} (I- {\cal A})^{-1} \widehat B + \widehat B ( I-{\cal A}^T )^{-1} {\cal A}^T + F [ cov( Y ) ] + {\cal A} { \overline y } \ \overline y^T {\cal A} + Q . \end{array}$$

    We now note that

    $${ \overline y} \ \overline y^T = \widehat B + {\cal A} (I- {\cal A} )^{-1} \widehat B + \widehat B ( I- {\cal A}^T )^{-1} {\cal A}^T + {\cal A} { \overline y} \ \overline y^T {\cal A}^T$$

    which is obtained after some elementary algebra and after substituting \( \overline y= (I-{\cal A})^{-1} b\) by Eq. 24. We conclude that cov(Y) is a solution of Eq. 17.

    Next, we show uniqueness. Let Z 1 and Z 2 be two solutions of Eq. 17 and define Z = Z 1 − Z 2 . Then Z satisfies Z = F n [Z] . Iterating that we obtain that

    $$Z = \lim\limits_{n \to \infty } F^n [ Z ] = 0$$

    where the last equality follows from Eq. 16. This implies the uniqueness of the solution for Eq. 17. The uniqueness of the solution of Eq. 18 is obtained similarly. □

Remark 3

We comment on the condition (16). It is equivalent to requesting that all eigenvalues of F have modulus smaller than one. To illustrate the necessity of this condition, consider the stochastic difference scalar equation

$$Y_{n+1} = A_n Y_n + B_n \mbox{ where } A_n = \left\{ \begin{array}{lr} 5 & w.p. \ 0.1 \\ 0.1 & w.p. \ 0.9 \end{array} \right .$$

A n are assumed to be i.i.d. and assume Y 0 = 0. Then for all n

$$E[Y_n] \leq \frac{b}{1-0.59}$$

but

$$E\left[Y_n^2\right] > b^{(2)} 2.5^n$$

which diverges. Thus Y n does converge to a stationary ergodic regime (since \({\cal A} = 0.59 < 1 \)) but this limit has an infinite second moment.

3.2 Example of a correlated processes

We assume in this Subsection that B n are random vectors whose distribution depends on an underlying ergodic Markov chain θ n taking values in a finite space Θ. We denote its transition probability by \({\cal P}\). Let π be the unique steady state probability of the Markov chain. Let \(G_r^i (\theta) := P( B_n^i = r | \theta_n = \theta )\) and \(\widehat G^i\) be a matrix of size \(|\Theta|\times \mathbb{Z^+}\) whose lrth component \(\widehat G_r^i (l) \) equals \( G^i_r (l) \pi(l)\). Let J be a row vector whose ith entry equals i, \(i\in \mathbb{Z^+}\) Then for j > 0, Our goal is to compute the quantities that appear in Eq. 17 (in particular \( {\cal B}(k) \)).

Lemma 1

In the Markov correlated model described above, we have

$$[ {\cal B}(k) ]_{ij} = E\left[B_0^i B_k^j \right] = J \widehat G^i {\cal P}^{k-1} [G^j]^T J^T .$$
(19)

If we denote by 1 the column vector with appropriate size whose entries are all ones, then we further have:

$$\left[ \widehat {\cal B}(k) \right]_{ij} = ( J - b_i {\bf 1}^T ) \widehat G^i {\cal P}^{k-1} \left[ G^j \right]^T ( J - b_j {\bf 1})^T ,$$
(20)

where \(b_i = \sum_{l\in \Theta} E\left[ B_0^i | \theta_0 = l \right] \pi(l)\).Footnote 2 Moreover.

$$[cov(B)]_{ij} = \sum\limits_{\theta \in \Theta } \pi (\theta) cor[B(\theta)]_{ij} ,$$
(21)

where \( cor[B(\theta)]_{ij} = E\left[ B_0^i B_0^j | \theta_0 = \theta \right]\).

Proof

We have

$$P\left(B_0^i = r , B_k^j=s | \theta_n = \theta \right) = G_r^i ( \theta ) \sum\limits_{\theta' \in \Theta } \left[ {\cal P}^{k-1} \right]_{ \theta \theta' } G_s^j ( \theta' )$$

which implies

$$\begin{array}{lll}P(B_0^i = r , B_k^j=s ) &=& \sum\limits_{\theta \in \Theta } \pi(\theta) G_r^i ( \theta ) \sum\limits_{\theta' \in \Theta } [ {\cal P}^{k-1} ]_{ \theta \theta' } G_s^j ( \theta' ) = \sum\limits_{\theta \in \Theta } \widehat G_r^i ( \theta ) \sum\limits_{\theta' \in \Theta } [ {\cal P}^{k-1} ]_{ \theta \theta' } G_s^j ( \theta' ) \\ &=& [ \widehat G^i {\cal P}^{k-1} (G^j)^T ]_{rs} . \end{array}$$

Hence \( \left[ { \cal B }(k) \right]_{ij} = \sum_s \sum_r rs [ \widehat G^i {\cal P}^{k-1} G^T ]_{rs} \) which gives Eq. 19. The rest is direct. □

Next, consider the special case that the \(B_n^i\)’s have only values 0 or 1. Let p and \(\widehat p\) denote the matrices whose (i,θ) entry equal, respectively, to \(p_\theta (i):= P(B_n^i=1|\theta_n=\theta) \) and \(\widehat p_\theta (i):= P(B_n^i=1|\theta_n=\theta) - P(B_n^i = 1 )\). Let g denote the matrix whose (i,θ) entry equals \(g_\theta(i)=\pi(\theta) \widehat p_\theta(i)\). Then Eq. 20 simplifies to

$$\widehat {\cal B}(k) = g {\cal P}^{k-1} \widehat p^T$$
(22)

3.3 Example: the single type discrete branching process (one dimension case)

We consider a scalar branching process, i.e. d = 1. Y n in Eq. 1 is then a scalar instead of a vector and Eq. 5 simplifies to

$$A_n ( Y_n ) = \sum\limits_{k=1}^{Y_n} \xi^{(k)} (n) .$$
(23)

ξ (k) and \({\cal A}\) are scalar too with \(E\left[\xi^{(k)}(n)\right] = {\cal A} \). Note also that \({\left\|\cal A\right\|}=|{ \cal A}|\). Theorem 2 simplifies to:

Theorem 3

  1. (i)

    The first moment of \(Y_n^*\) is given by

    $$E[Y^*_0]= \frac{ b }{1-{\cal A}} .$$
    (24)
  2. (ii)

    The variance of \(Y_n^*\) is given by

    $$var[Y^*] = E[(Y^*)^2] - (E[Y^*])^2 = \frac{ \displaystyle var[B]+ \sum\limits_{r=1}^{\infty} \Big( {\cal A}^r \widehat {\cal B}(r) + \Big[ {\cal A}^r \widehat {\cal B}(r) \Big]^T \Big) + {\cal A} b }{ 1 - {\cal A}^2 } .$$

Next, we shall further restrict to the Markovian setting of Section 3.2. We shall provide an explicit expression for \( \sum_{r=1}^\infty {\cal A}^r {\cal B}(r) \).

Lemma 2

In the case of one dimensional state space with the Markov model for correlation, we have

$$\sum\limits_{r=1}^\infty {\cal A}^r {\cal B}(r) = {\cal A} ( J - b {\bf 1}^T ) \widehat G [ I - {\cal A} {\cal P}]^{-1} G^T ( J - b )^T .$$
(25)

Proof

We get using Eq. 20

$${\cal A}^r {\cal B}(r) = {\cal A} ( J - b {\bf 1}^T ) \widehat G [ {\cal A} {\cal P}]^{r-1} G^T ( J - b )^T .$$

\( \sum_{r=1}^\infty [ {\cal A} {\cal P}]^{r-1} \) is well defined since \(|{\cal A}|< 1 \) and since \({\cal P}\) is a stochastic matrix. Define J x to be a row vector whose ith entry equals min (i,x), \(i\in \mathbb{Z^+}\). Then for any x > 0, we have by the bounded convergence theorem:

$$\sum\limits_{r=1}^\infty {\cal A} ( J^x - b {\bf 1}^T ) \widehat G [ {\cal A} {\cal P}]^{r-1} G^T ( J^x - b )^T = {\cal A} ( J^x - b {\bf 1}^T ) \widehat G [ I - {\cal A} {\cal P}]^{-1} G^T ( J^x - b )^T .$$

Equation 25 is then obtained by the monotone convergence theorem. □

We thus obtain the following:

Corollary 1

Consider the scalar case, and consider the Markov model for the correlation process of Section  3.2 . Then

$$var [Y^*] = \frac{ \displaystyle var[B]+ 2 {\cal A} ( J - b {\bf 1}^T ) \widehat G [ I - {\cal A} {\cal P}]^{-1} G^T ( J - b )^T + {\cal A} b }{ 1 - {\cal A}^2 }$$

Moreover, in the special case that the \(B_n^i\) ’s have only values 0 or 1, then we get

$$var [Y^*] = \frac{ \displaystyle var[B]+ 2 {\cal A} g ( I - {\cal A} {\cal P} )^{-1} \widehat p^T + {\cal A} b }{ 1 - {\cal A}^2 }$$
(26)

4 Application to the G/GI/∞ queue

The infinite server queue has been frequently used in networking. Some examples are Miorandi and Altman (2006), Zukerman (1989), and references therein. We use this queueing model here to provide an application to the theoretical tools that we develop.

We shall apply in this section the general theory of previous sections in order to compute the two first moments of the size of an infinite server queue in discrete time. Our model contains in particular the G/PH/ ∞ queue; we have reported on that model already in Altman (2005). We further introduce an alternative modeling approach based on stochastic linear difference equations for a discrete time infinite server queue, that contains also general bounded service times with arbitrary service time distribution.

A discrete time model of the infinite server queue, similar to the one we present here, has been studied independently in Eliazar (2008) with great generality. The derivation there does not rely on the branching framework, and is achieved using a one dimensional discrete time state model.

In this section we first show that the known results for some infinite server queue can be obtained by applying our methodology. However, the fact that we base our analysis on a multidimensional branching process approach allows us to obtain results on the infinite server queue that have not been known before: (i) we are able to analyze (in Section 4.6) a network of G/GI/ ∞ queues. Moreover, (ii) our framework allows us to obtain correlations between the number of customers in different phases for a discrete G/PH/ ∞ queue.

4.1 A discrete branching model

Service times

Service times are considered to be i.i.d. and independent of the arrival process. We represent the service time associated to any customer in the queue as the discrete time analogous of a phase type distribution: there are d possible service phases. The initial service phase of the customer k is chosen at random according to some probability p(k). If at the beginning of slot n a customer is in a service phase i then it will move at the end of the slot to a service phase j with probability P ij . With probability \(1-\sum_{j=1}^d P_{ij} \) it ends service and leaves the system at the end of the time slot.

Remark 4

A special case of our model is the one in which the service time is generally distributed over an interval [1,...,d] (for any d). We delay the discussion over this case to Section 4.7.

Modeling the service time

Let ξ (k) (n), k = 1,2,3,..., n = 1,2,3,... be i.i.d. random matrices of size d×d. Each of its element can take values of 0 or 1, and the elements are all independent. The ijth element of ξ (k) (n) has the interpretation of the indicator that equals one if at time n, the kth customer among those present at service phase i moved to phase j. Obviously, \(E \left[ \xi^{(k)}_{ij} (n) \right] = P_{ij} \). P is a sub-stochastic matrix (it has nonnegative elements and it’s largest eigenvalue is strictly smaller than 1), which means that services ends in finite time w.p. 1 and that (I − P) is invertible.

Arrivals

Let \(B_n=\left(B^1_n ,...,B^d_n\right)^T\) be a column vector for each integer n, where \(B^i_n\) is the number of arrivals at the nth time slot that start their service at phase i. B n is assumed to be a stationary ergodic sequence and that they have finite expectation.

The state and the recursive equation

Let \(Y^i_n\) denote the number of customers in phase i at time n. Then Y n satisfies the recursion (1) where A n is given in Eq. 5. In particular, \({\cal A}=P\) and indeed we have \({\left\|\cal A\right\|}<1\) so that Assumption A3 holds.

We can thus apply the results of the previous sections to get the first two moments as well as the general distribution at stationary regime.

4.2 Main results

Corollary 2

  1. (i)

    Theorems 1 and 2 hold for the G/PH/∞ queue.

  2. (ii)

    The first and second moments of the number of customers at the system in stationary regime are given respectively by \( {\bf 1}^T (I-{\cal A})^{-1} b \) and 1 T cov(Y) 1 , respectively, where 1 is a column vector with all entries 1’s.

Remark 5

We present a simple interpretation of the first moment of the number of customers at the system. Denote by λ the expected number of arrivals per slot. Clearly λ = |b| where |b| is the sum of entries of the vector b. Define ζ to be the expected service time of an arbitrary customer and let ρ = λζ. We shall first compute ζ. The ijth element of the matrix \((I-{\cal A})^{-1} \) has the interpretation of the total expected number of slots that a customer that had arrived at service phase j spent at state i. Thus the jth entry of the vector \( {\bf 1}^T (I-{\cal A})^{-1} \) has the interpretation of the total expected number of slots that a customer that had arrived at service phase j spent in the system. and let the vector β be the vector whose ithe entry is b/|b|. Then

$$\zeta = {\bf 1}^T (I-{\cal A})^{-1} \beta$$

and

$$\rho = \left( {\bf 1}^T (I-{\cal A})^{-1} \beta \right) |b| = {\bf 1}^T (I-{\cal A})^{-1} b ,$$

which is our expression for the first moment of the number of customers at the system. This relation is known to hold in fact for general G/G/ ∞ queues, see e.g. Baccelli and Brémaud (2003, p. 134).

4.3 Departure process

One can use the same methodology to describe the departure process. To do that, we can augment the system with a new “phase” which we call “D” (for Departure), and update the phase transitions as follows:

$$\begin{array}{lll} \overline P_{ij} &=& P_{ij}, \quad i,j \in \{1,...,d\} , \\ \overline P_{iD} &=& 1 - \sum\limits_{j=1}^d P_{ij} , i \in \{1,...,d \} \\ \overline P_{Di} &=& 0 , \qquad i \in \{1,...,d,D \} \end{array}$$

Quantities corresponding to the new system are denoted by adding a bar. We set \(\overline B_n^i = B_n^i \) for i = 1,...,d and \(\overline B_n^d = 0\) for all integers n. Since P is assumed to be sub-stochastic, so is \(\overline P\). Note that in our new system, only customers in phases 1,...,d correspond to those really present in the original system, whereas customers at phase D are already out of the system.

4.4 The case of geometric service times

We now study the special case of geometrically distributed service times. In other words, if at the beginning of slot n a customer is in the system then it will end service at the end of the slot with some probability p (it thus remains in the system during a geometrically distributed duration). Recall that the dimension d is determined by the number of service phases; here we have a single phase in which we remain with probability p. Thus the problem can indeed be formulated using random variables (dimension one) instead of random vectors. Y n is a scalar and denotes the number of customers in the system. \(\xi_n^{(k)}\) has the interpretation of the indicator that the kth customer present at the beginning of time-slot n will still be there at the end of the time-slot. Thus the probability that a customer in the system finishes its service within a time slot is precisely \(p=1-{\cal A}\). We apply below directly the results of Section 3.3.

To illustrate the one dimensional case obtained with service times that are geometrically distributed, we consider the following simple scenario. The arrival process depends on a Markov chain as in Section 3.2, and moreover, there can be either one or no arrival at a time slot.

We consider a Markov chain with two states {γ,δ} with transition probabilities given by

$${\cal P} = \left( \begin{array}{lr} 1- \epsilon p & \epsilon p \\ \epsilon q & 1 - \epsilon q \par \end{array} \right) $$

ϵ > 0 is a parameter that will be varied later in order to vary the correlations. The steady state probabilities of this Markov chain are

$$\pi = \left( \frac{q}{p+q} , \frac{p}{p+q} \right) .$$

Hence

$$b = E[B]= E[B^2] = \frac{ q p_\gamma + p p_\delta }{p+q} ,$$
(27)

where p γ : = P(B n  = 1 | θ n  = γ), and p δ : = P(B n  = 1 | θ n  = δ) (this is in line with the definition of p θ at the end of Section 3.2). Equation 27 then implies the following:

$$var[B]=\frac{( q p_{ \gamma} + p p_\delta )( q(1-p_\gamma) + p(1-p_\delta)) }{ (p+q)^2 }$$
(28)

Note that π, b, E[B 2] and var[B] do not depend on ϵ.

Applying the first part of Theorem 3 we get the following expression for the expected number of customers in the system in stationary regime:

$$E[Y_0^*] = \frac{1}{1-{\cal A} } \times \frac{ q p_\gamma + p p_\delta } {p+q} .$$
(29)

Next, we wish to compute the variance of Y. We have

$$\widehat p = \Big[ \frac{p (p_{\gamma} - p_{\delta})}{ p+q } , \frac{q (p_{\delta} - p_{\gamma})}{ p+q } \Big] , \qquad g = \frac{pq(p_{\gamma} - p_{\delta})}{ (p+q)^2 } \Big[ 1 , -1 \Big] ,$$
$$( I - {\cal A} {\cal P} )^{-1} = \frac{1}{ (1-{ \cal A})( 1-{\cal A} + \epsilon(p+q){\cal A} ) } \times \left( \begin{array}{lr} 1- {\cal A} + \epsilon {\cal A} q & \epsilon {\cal A } p \\ \epsilon {\cal A } q & 1- {\cal A} + \epsilon {\cal A} p \end{array} \right)$$

We thus obtain

$$g ( I - {\cal A} {\cal P} )^{-1} \widehat p^T = \frac{pq(p_\gamma - p_\delta)^2 } { (1 - {\cal A} + \epsilon(p+q){\cal A})(p+q)^2 }$$
(30)

Substituting in Eq. 26 yields the following expression for var[Y *] :

$$\begin{array}{lll}&&{\kern-18pt} \frac{1}{ ( 1 - {\cal A}^2 )( p + q )^2}\nonumber\\&&{\kern-12pt}\times\left(( q p_{ \gamma} + p p_\delta )( q(1-p_\gamma) + p(1-p_\delta))+\frac{2 {\cal A} pq(p_\gamma - p_\delta)^2 }{ 1 - {\cal A} + \epsilon(p+q){\cal A} }+ {\cal A}b (p+q)^2 \right)\end{array}$$
(31)

Remark 6

In the above expression for var[Y *], we see that the dependence on ϵ comes only through the term in Eq. 30. Moreover, we see that for any value of \({\cal A}\), this term, and hence var[Y *], decrease with ϵ. Large ϵ means that the Markov chain alternates rapidly between its two states, which results in a lower overall effect of correlation. Equation 30 can precisely be used to determine this overall effect as it can be viewed as the total weighted sum of correlations \(\widehat {\cal B}(k)\), i.e.

$$g ( I - {\cal A} {\cal P} )^{-1} \widehat p^T = \sum\limits_{k=0}^\infty g ( {\cal A} {\cal P} )^k \widehat p^T = \sum\limits_{k=1}^\infty {\cal A}^{k-1} \widehat {\cal B}(k)$$

where we used Eq. 22.

4.5 A numerical example

As a numerical example for the model introduced in the last subsection, we set the following parameters: p = q = 1, p γ  = 1, p δ  = 0.5. Substituting these parameters in Eq. 31 we obtain the following expression:

$$var[Y^*]=\frac{1}{(1-{\cal A}^2)} \left( \frac{ 3}{16} + \frac{ 2 {\cal A} }{ 1 - {\cal A} + 2 \epsilon {\cal A} } + \frac{3}{4} {\cal A} \right) . $$

In Fig. 1 we plot the variance of the steady state number of customers, var[Y *], while varying ϵ and \({\cal A}\).

Fig. 1
figure 1

var[Y *] (vertical axis) as a function of ϵ (horizontal axis) and of \({\cal A}\)

Full size image

Recall that for a fixed \({\cal A}\), the expectation of Y * does not depend on ϵ. The variance of Y * on the other hand is seen to be quite sensitive to the correlation between the B n ’s as determined by the parameter ϵ. This sensitivity is seen to increase as \({\cal A}\) increases and sensitivity is largest when \({\cal A}\) approaches 1. As already mentioned in Remark 6 we see that ϵ = 1 gives the smallest value of var[Y *] and that var[Y *] increases as ϵ decrease. For \({\cal A}=0.5\) we get a difference of around 30% between the lowest and the largest value of ϵ, where as form \({\cal A}=0.9\) we obtain a difference of 250%.

4.6 Extension to a network

Consider now M stations, each with infinite number of servers. The service time at station i has a set \({\cal N}_i\) of d i phases. Let d = d 1 + ... + d M . For any j = 1,...,d let s(j) denote the station to which j corresponds, i.e. if \(j \in {\cal N}_i\) then s(j) = i.

If at time n a customer were at phase j in station s(j) then it either moves to another phase at the same station or moves to another phase in another station; the next phase k (either at the same station or at another one) is chosen with probability P jk ; with probability \(1-\sum_{k=1}^d P_{jk}\) the customer leaves the system. Again we assume that the choice of next phase are independent.

Let \(B_n=\left(B^1_n ,...,B^d_n\right)^T\) be a column vector for each integer n, where \(B^i_n\) is the number of arrivals at the nth time slot that start their service at phase i in station s(i). B n is assumed to be a stationary ergodic sequence.

With this description we see that we can identify the whole network as a single server station problem with infinite number of servers and with d phases. Thus we can apply all previous results.

4.7 Linear difference equation model for the G/GI/∞ with general bounded service time

A special case of our model is the one in which the service time is generally distributed over an interval [1,...,d] (for any d). Indeed, this is obtained by setting

$$P_{ij}= \left\{ \begin{array}{lr} 1 & \mbox{ if $i>1$ and $j=i-1$} \\ 0 & \mbox{ otherwize.} \end{array} \right. $$

Notice that if in the beginning of a slot a customer is in phase 1, then it leaves the system at the end of the slot. With this definition of P ij we see that the probability distribution of the service duration of an arbitrary customer is given by p( ·) . A n (y) can then be represented as the product of the matrix A and the column vector \(y= (y_1 , ... , y_d )^T \) where A has the form

$$A = \left( \begin{array}{ccccccc} 0 & 1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 0 & 1 & 0 & \ldots & 0 & 0 \\ 0 & 0 & 0 & 1 & \ldots & 0 & 0 \\ 0 & 0 & 0 & 0 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & 0 & 1 \\ 0 & 0 & 0 & 0 & \ldots & 0 & 0 \end{array} \right) $$
(32)

We note the following:

  • \({\left\|A\right\|}=0 \) in agreement with Assumption A3. The dynamics is then given as a linear stochastic difference equation, which is at the same time a special degenerate case of a discrete branching process.

  • We note that A d = 0. This implies that Eqs. 12 and 13 simplify to

    $$Y_n = Y_n^* = \sum\limits_{ j=0 }^{d-1} A^j B_{n-j-1}$$

    for any n ≥ d, so that for any value of Y 0, there is coupling between the process Y n and \(Y_n^*\) after time d.

As in Section 4.3, we may augment the state if we wish to include the departure process. The state is then of dimension (d + 1) and the d + 1st element of Y n represents the number of departures at time slot n. Again A n (y) can be written as the product A y of a matrix A and the state vector y where A is a matrix of the form given in Eq. 32 whose dimensions are now (d + 1)×(d + 1).

5 The case of B n  = 0

In this Section, we study the homogeneous case, i.e. we study the dynamics Eq. 1 for the case B n  = 0 under the assumption that \(E [( \log {\left\| A_0 \right\|}) ] < \infty \) where we define

$$ {\left\|A_n\right\|} = \sup\limits_{y \not= 0 } { { {\left\| A_n (y) \right\|} } \over {{\left\|y\right\|}} }. $$

We show that this implies that Y n converges to zero. The proof is a direct extension of the one in Glasserman and Yao (1995) that treats the case where A n are linear.

We relax the assumption that A n are i.i.d., we assume instead that they are stationary ergodic (with respect to the shift in n).

Define \(\widehat P(k,n) := \bigotimes_{i=k+1}^n A_i \) for k,n ∈ Z , k < n . Then

$$ \log {\left\| \widehat P(l,n) \right\|} \leq \log {\left\| \widehat P(l,k) \right\|} + \log {\left\| \widehat P(k,n) \right\|} . $$

Combining this with the fact that \(E [( \log {\left\| A_0 \right\|}) ] < \infty \), we have by Kingman’s ergodic theorem (Carmona and Lacroix 1990; Steele 1989) (for the discrete time):

Theorem 4

Assume that A n are stationary ergodic and that \(E [( \log {\left\| A_0 \right\|}) ] < \infty \) . Then there is a finite constant γ * such that

$$\lim\limits_{n \to \infty } n^{-1} \log {\left\|\widehat P(0,n) \right\|} = \gamma^*, \quad P-a.s. $$

Noticing that

$$\left( \bigotimes\limits_{i=1}^{n} A_i \right) ( y ) \leq {\left\| \bigotimes\limits_{i=1}^{n} A_i \right\|} {\left\| y \right\|} = \left( \exp\left( \frac {1}{n} \log {\left\| \widehat P ( 0,n) \right\|} \right) \right)^n {\left\| y \right\|} $$

we obtain the following.

Corollary 3

Assume that A n are stationary ergodic, that \(E [( \log {\left\| A_0 \right\|}) ] < \infty \) , and that γ * (defined in Theorem 4) is strictly negative. Then for any initial state y , we have P-a.s.

$$\lim\limits_{n \to \infty }\left( \bigotimes\limits_{i=1}^{n} A_i \right) ( y ) = 0 .$$

6 Conclusion

In this paper we have studied a class of stochastic recursive equations and derived their first two moments for the case of (possibly non Markov) stationary ergodic migration process. The framework applies to stochastic auto regressive processes as well as to branching processes with either a discrete state space or a continuous state space. We have used the results on the second moments to investigate the discrete infinite server queue with batch arrivals where the size of the batches follow a general stationary ergodic process. We then proposed more specific Markov models for correlation that further simplify the expressions for the first two moments. Our results were illustrated through the analysis of a G/GI/ ∞ queue as well as through an extension to a network of such queues.