UDC 519.21

MATHEMATICS

Corresponding Member of the Academy of Sciences of the USSR A. A. BOROVKOV

ERGODIC THEOREMS FOR MULTICHANNEL SERVICE SYSTEMS

1. Let, on the underlying probability space \((\Omega,\mathfrak F,P)\), a sequence of pairs of random variables \(\{\tau_j^e,\tau_j^s;\ j \geqslant \infty\}\) be given. We shall say that an \(m\)-channel service system with losses is governed by this sequence if calls enter the system at the times \(0,\tau_1^e,\tau_1^e+\tau_2^e,\ldots\), and the servicing of the \(j\)-th call (if such servicing takes place) requires time \(\tau_j^s\). If an arriving call finds all \(m\) channels busy, then it is refused and drops out of consideration. If, however, the number \(q_n\) of busy channels at the moment just before the arrival of the \(n\)-th call is less than \(m\), then the call is accepted for service by one of the free channels. Thus, for the systems under consideration one always has \(q_n \leqslant m\). For simplicity we shall assume that \(q_1=0\) (see Sec. 4).

Along with the “occupancy” \(q_n\), we shall consider more precise characteristics of the systems—the processes \(\{q_n(x);\ n\geqslant 1,\ x\geqslant 0\}\), where the value \(q_n(x)\) indicates how many of those calls that were in the system before the moment
\(t_n=\tau_1^e+\cdots+\tau_{n-1}^e\) of arrival of the \(n\)-th call will remain in it after time \(x\) (i.e., at the moment \(t_n+x\)), so that \(q_n=q_n(0)\).

Suppose that the governing sequence is strictly stationary. Then, without loss of generality, one may assume that on \((\Omega,\mathfrak F,P)\) there is given a “two-sided infinite” stationary sequence

\[ \{\tau_j^e,\tau_j^s;\ -\infty<j<\infty\}, \tag{1} \]

by which the system is governed.

1. Let first the number of channels be \(m=\infty\). Denote by \(I(A)\) the indicator of the event \(A\),

\[ \begin{aligned} q^k(x)={}&I(\tau_k^s>\tau_k^e+x)+I(\tau_{k-1}^s>\tau_{k-1}^e+\tau_k^e+x)+{}\\ &{}+I(\tau_{k-2}^s>\tau_{k-2}^e+\tau_{k-1}^e+\tau_k^e+x)+\cdots \end{aligned} \tag{2} \]

Theorem 1. If the sequence (1) is strictly stationary, \(\mathbf M\tau^s<\infty\), and the sequence \(\{\tau_j^e;\ -\infty<j<\infty\}\) is, moreover, metrically transitive, then the distribution of the processes

\[ \{q_{n,k}(x);\ k\geqslant 0;\ x\geqslant 0\} = \{q_{n+k}(x);\ k\geqslant 0,\ x\geqslant 0\} \]

converges monotonically, as \(n\to\infty\), to the distribution of a proper stationary process in \(k\),

\[ \{q^k(x);\ k\geqslant 0,\ x\geqslant 0\}. \]

More precisely: for every \(n\) there exists a process \(\tilde q^k(x)\) with the same distribution as \(q^k(x)\), and such that \(q_{n+k}(x)\leqslant \tilde q^k(x)\), it increases with \(n\), and as \(n\to\infty\)

\[ \mathbf P\left(\bigcup_{k=0}^{\infty}\ \bigcup_{x\geqslant 0}\{q_{n+k}(x)\ne \tilde q^k(x)\}\right)\to 0. \]

The proof of this theorem is not difficult to obtain, using the stationarity of the governing sequence and the representation

\[ q_n(x)=I(\tau_1^s>\tau_1^e+\ldots+\tau_{n-1}^e+x)+I(\tau_2^s>\tau_2^e+\ldots+\tau_{n-1}^e+x)+\ldots \]

\[ \ldots+I(\tau_{n-1}^s>\tau_{n-1}^e+x). \]

Theorem 2. If \(\{\tau_j^e\}\) and \(\{\tau_j^s\}\) are two independent sequences of independent identically distributed random variables and \(\mathbf M\tau^e<\infty\), then the condition \(\mathbf M\tau^s<\infty\) is necessary and sufficient for the finiteness of \(q_n(x)\). The probabilities

\[ P_k(x)=\mathbf P(q^0(x)=k),\qquad k=0,1,\ldots, \]

satisfy the equations

\[ P_0(x)=\int_0^\infty d\mathbf P(\tau^e<t)\,\mathbf P(\tau^s<t+x)P_0(t+x), \]

\[ P_k(x)=\int_0^\infty d\mathbf P(\tau^e<t)\,\mathbf P(\tau^e\geq t+x)P_{k-1}(x)+ \]

\[ +\int_0^\infty d\mathbf P(\tau^e<t)\,\mathbf P(\tau^s<t+x)P_k(t+x),\qquad k=1,2,\ldots, \]

which, in the class of systems of functions of bounded variation possessing the properties \(P_0(x)\to 1\), \(P_k(x)\to\infty\), for \(k\geq 1\), \(x\to\infty\), have a unique solution.

Hence it is easy to obtain, in particular, that if \(\mathbf P(\tau^e\geq x)=e^{-\alpha x}\), \(\alpha>0\), then

\[ P_k(x)=\frac{1}{k!}\left(\int_x^\infty \alpha \mathbf P(\tau^s\geq t)\,dt\right)^k \exp\left\{-\int_x^\infty \alpha \mathbf P(\tau^s\geq t)\,dt\right\}. \]

The “occupancy” \(q(t,x)\) at time \(t\), i.e., the number of calls that are in the system at time \(t+x\) and whose service has already lasted more than \(x\), has analogous properties. If \(\mathbf P(\tau^e\geq x)=e^{-\alpha x}\), then the limiting distributions of \(q_n(x)\) and \(q(t,x)\), as \(n\to\infty\), \(t\to\infty\), coincide.

1. The number of channels \(m<\infty\). Keeping the notation of the governing sequence and \(q_n(x)\), we shall now denote the right-hand side in (2) by \(Q_k(x)\). This is, as we have seen, a stationary characteristic of the system governed by the same sequence (1), but with an infinite number of channels. Next denote by \(A_k\) the event consisting in the fact that, for some \(0\leq L\leq m-1\), \(l_j\geq 1\), \(j=0,L\), such that \(\sum_{j=0}^L l_j=m\), the inequalities

\[ Q_k(0)\leq m-l_0,\qquad Q_k(\tau_{k+1}^e)\leq m-l_0-l_1,\ldots,\qquad Q_k(\tau_{k+1}^e+\ldots+\tau_{k+L}^e)\leq \]

\[ \leq m-l_0-\ldots-l_L=0 \]

are satisfied.

Theorem 3. Let the sequence (1) be strictly stationary and metrically transitive. Suppose, in addition, that the condition

\[ \mathbf P(A_0)>0. \tag{3} \]

is fulfilled. Then the distribution of the processes \(\{q_{n+k}(x);\, k\geq 0,\, x\geq 0\}\), as \(n\to\infty\), converges to the distribution of some process stationary in \(k\), \(\{q^k(x);\, k\geq 0,\, x\geq 0\}\), such that

\[ \mathbf P(q^0(0)<m)<1. \]

Convergence here is understood in the same strong sense as in Theorem 1.

There exist various simple sufficient conditions ensuring the fulfillment of (3).

Consider, for example, the case when \(\{\tau_j^e\}\), \(\{\tau_j^s\}\) are composed of independent random variables. Then for (3) to hold it is sufficient that

\[ \mathbf P(\tau^s \le m\tau^e)>0,\qquad \mathbf M\tau^s<\infty . \tag{4} \]

A condition in a certain sense opposite will also be sufficient: for all \(x\ge x_0\), \(\Delta>0\),

\[ \mathbf P(\tau^s\in(x,x+\Delta))>0,\qquad \mathbf M\tau^s<\infty \tag{5} \]

for some \(x_0>0\).

We now describe, for independent \(\tau_j^e,\tau_j^s\), the limiting distribution \(q_n(x)\). The trajectory of the nondecreasing step process \(q^0(x)\) is, evidently, completely described by the positions of its jumps. Denote by

\[ \mu\bigl(\underbrace{0,\ldots,0}_{j\ \text{times}},\,dx_{j+1},\ldots,dx_m\bigr) \]

the probability that \(q^0(0)=m-j\), and that the \((m-j)\) jumps of the process \(q^0(x)\) are contained respectively in the intervals \(dx_k=(x_k,x_k+dx_k)\), \(k=j+1,\ldots,m\) (the use of the symbol \(dx_k\) simultaneously to denote a scalar quantity and an interval will not lead to misunderstandings).

Theorem 4. If (4) or (5) holds, the stationary distribution \(\mu(0,\ldots,0,dx_{j+1},\ldots,dx_m)\), \(j=0,\ldots,m\), satisfies the equation

\[ \begin{aligned} \mu(0,\ldots,0,dx_{j+1},\ldots,dx_m) &= \sum_{k=j+1}^{m}\int_{0}^{\infty} \mathbf P(\tau^e\in dt)\,\mathbf P(\tau^s\in t+dx_k)\,M_{1,k} \\ &\quad+ \int_{0}^{\infty}\mathbf P(\tau^e\in dt)\,\mathbf P(\tau^s\le t)\,M_2 + \int_{0}^{\infty}\mathbf P(\tau^e\in dt)\,M_3, \end{aligned} \tag{6} \]

where

\[ M_{1,k}= \int_{0\le y_2\le y_3\le\cdots\le y_{j+1}\le t} \cdots\int \mu(0,dy_2,\ldots,dy_{j+1},dx_{j+1}+t,\ldots,dx_{k-1}+t, \]

\[ \qquad\qquad\qquad +t,\,dx_{k+1}+t,\ldots,dx_m+t). \]

\[ M_2= \int_{0\le y_2\le y_3\le\cdots\le y_j\le t} \cdots\int \mu(0,dy_2,\ldots,dy_j,dx_{j+1}+t,\ldots,dx_m+t), \]

\[ M_3= \int_{0<y_1\le y_2\le\cdots\le y_j\le t} \cdots\int \mu(dy_1,\ldots,dy_j,dx_{j+1}+t,\ldots,dx_m+t). \]

This equation has a unique solution satisfying the condition

\[ \int_{0\le x_1\le\cdots\le x_m} \cdots\int \mu(dx_1,\ldots,dx_m)=1. \]

In these formulas, by the interval \(dy\) when \(y=0\) one should understand the point \(0\). Thus the integrals \(M_{1,k}\) and \(M_2\) also include “discrete” values, such as \(\mu(0,\ldots,0,dx_{j+1}+t,\ldots,dx_m+t)\) (in \(M_2\)) and others. They do not enter into \(M_3\).

In the equation for \(\mu(0,\ldots,0)\), the terms containing \(M_{1,k}\) will be absent on the right-hand side; in the equation for \(\mu(dx_1,\ldots,dx_m)\) with \(x_1>0,\ldots,x_m>0\), the term containing \(M_2\) will be absent. The integral \(M_3\) in this equation becomes \(\mu(dx_1+t,\ldots,dx_m+t)\).

By direct verification one can establish, for example, that in the case

\[ \mathbf{P}(\tau^{e} \ge x)=e^{-\alpha x}, \qquad M\tau^{s}=a<\infty \]

\[ \mu(0,\ldots,0,dx_{j+1},\ldots,dx_m) = ca^{m-j}\mathbf{P}(\tau^{s}\ge x_{j+1})\cdots \mathbf{P}(\tau^{s}\ge x_m)\,dx_{j+1}\cdots dx_m, \]

\[ c=\left[\sum_{k=0}^{m}\frac{(a\alpha)^k}{k!}\right]^{-1}, \]

satisfies equation (6) and, consequently, is the stationary distribution \(q^{k}(x)\).

As in the case \(m=\infty\), here one can also establish that, for the exponential distribution of \(\tau^e\), the limiting distributions \(q_n(x)\) and \(q(t,x)\) as \(n\to\infty\), \(t\to\infty\) coincide. From this, in particular, will follow Sevast'yanov’s theorem concerning Erlang’s formulas for the limiting, as \(t\to\infty\), distribution \(q(t,x)\).

When \(\tau_j^e,\tau_j^s\) are independent, one can also estimate the rate of convergence of the distribution \(q_n(x)\) to the stationary one. If, for example, \(\mathbf{P}(\tau^s\le \tau^e)>0\) and \(Me^{\lambda\tau^s}<\infty\) for some \(\lambda>0\), then this rate of convergence is related to an exponential one.

For \(m=1\), Theorem 3 implies

Theorem 5. If the sequence (1) is strictly stationary and metrically transitive and

\[ \mathbf{P}\bigl(\tau_0^s\le \tau_0^e,\ \tau_{-1}^s\le \tau_{-1}^e+\tau_0^e,\ \tau_{-2}^s\le \tau_{-2}^e+\tau_{-1}^e+\tau_0^e,\ldots\bigr)>0, \]

then there exists

\[ p(x)=\lim_{n\to\infty}\mathbf{P}(q_n(x)=1). \tag{7} \]

If the vectors \((\tau_i^e,\tau_i^s)\) are independent and \(d\) is the greatest common divisor of the numbers \(k\) for which

\[ r_k=\mathbf{P}(\tau_1^s\in (X_{k-1},X_k))>0,\qquad X_k=\sum_{j=1}^{k}\tau_j^e, \]

then, for the existence of (7), it is necessary and sufficient that \(d=1\). If this condition is fulfilled,

\[ p(x)=\left(\sum_{k=1}^{\infty}kr_k\right)^{-1} \sum_{j=1}^{\infty}\mathbf{P}(\tau_1^s>X_j+x). \]

4. The theorems on the existence of a stationary limiting distribution for the sequence \(\{q_{n+k}(x);\ k\ge 0,\ x\ge 0\}\) as \(n\to\infty\), formulated above, admit generalization in the following three directions simultaneously:

1) For arbitrary proper initial conditions (at time \(0\), \(q_0\) channels are busy and the service times of the “initial” calls are equal to \(\rho_1,\ldots,\rho_{q_0}\)).

2) Calls may arrive in batches. In this case, on \((\Omega,\mathfrak{F},P)\) one should consider strictly stationary sequences, say, of the form
\(\{\tau_j^e,\nu_j^e,\tau^s;\ -\infty<j<\infty\}\), where \(\nu_j^e\) is the number of calls arriving in the \(j\)-th batch, \(\tau^s=(\tau_{j,1}^s,\ldots,\tau_{j,\nu_j^e}^s)\) is the vector of service times of the calls in the \(j\)-th batch. In this case the condition \(M\tau^s<\infty\) in Theorem 1 must be replaced by the requirement \(M[\tau^s]<\infty\), where \([\mathbf{x}]\) denotes the sum of the coordinates of the vector \(\mathbf{x}\).

3) For the existence of the limiting distribution \(q_{n+k}(x)\), the sequence (1) need not be stationary at all. It is sufficient only that, in a certain sense, the sequences \(\{\tau_j^e,\tau_j^s;\ j\ge 0\}\) converge as \(n\to\infty\) to a stationary one.

Institute of Mathematics
Siberian Branch of the Academy of Sciences of the USSR
Novosibirsk

Received
21 V 1970