3.3.1. Average scheme

A queueing process in the average normalized scheme is considered in the following normalization:

[3.6]

That is, the generator of Markov process ν^ε(t) has the following representation:

[3.7]

The main condition in the average approximation scheme is imposed on the asymptotical behavior of the first moment of jumps.

THEOREM 3.1.– (Averaging). Let the following approximation condition hold:

[3.8]

with a negligible residual term

[3.9]

and suppose the existence of a positive solution of equation

[3.10]

Then the normalized queueing process [3.6] converges in distribution, as ε → 0, to a solution ρ(t) of equation [3.10] with initial value ρ₀ = P lim_ε→0 εν^ε(0)

[3.11]

COROLLARY 3.1.- Let the initial value ρ₀ ≥ 0 be an equilibrium point for the velocity C(u):

Then the queueing process in the average normalized scheme has an equilibrium point as well:

uniformly on every finite time interval t ∈ [0,T].

PROOF.- (Proof of theorem 3.1). Under the approximation condition [3.8], the generator [3.7], acting on the continuously differentiable function φ(u), has the following asymptotic representation:

[3.12]

where the generator

[3.13]

determines the evolutional equation [3.10]. The residual termθ^ε(u) in [3.12] (different from the term in [3.8]) satisfies the negligible condition [3.9]. Now using martingale characterization of Markov process

[3.14]

and asymptotical representation [3.12], we get the following asymptotical form for martingale [3.14]:

where the residual term ψ_t^ε satisfies the condition

[3.15]

It is easy to verify that the square characteristic of martingale [3.14] admits the representation

[3.16]

with a random function ζ^ε(s), s ≥ 0, satisfying the condition

[3.17]

Hence, in the previous study (Korolyuk and Korolyuk 1999, theorem 3.4), the weak convergence [3.11] takes place. The limit process ρ(t) is defined by a solution of equation

[3.18]

which is equivalent to evolutional equation [3.10] for the limit process ρ(t).

3.3.2. Diffusion approximation scheme

A Markov queueing process in a diffusion approximation scheme is considered in the following centered and normalized form:

[3.19]

where the Markov jump process ν^ε(t) is determined by generator

[3.20]

The centered function ρ(t) is defined by a solution of evolutional equation

[3.21]

The more general centering scheme with the velocity C^ε(u) that depends on a series parameter ε is motivated by a real queueing system with bounded input. In spite of the fact that the Markov jump process ν^ε(t) is homogeneous in time, the normalized centered process [3.19] is heterogeneous, but in a special way, due to the deterministic centered function ρ(t). Meanwhile, the two components, homogeneous in time Markov process ζ^ε(t), ρ(t), t ≥ 0, can be used in the diffusion approximation scheme.

LEMMA 3.1.- The generator of the coupled Markov process ζ^ε(t), ρ(t), t ≥ 0, has the following representation:

[3.22]

where

[3.23]

and the generator Q^ε(v) acts in the following way:

[3.24]

PROOF OF LEMMA 3.1.-The increments of the first component in [3.19] have the following representation:

According toequation[3.21], one has

Hence

Now the conditional expectation

can be estimated as follows:

[3.25]

Note that, under the condition ζ^ε(t) = u, ρ(t) = v, according to the definition of normalized centered process [3.19], we have:

Therefore, the first term in [3.25] can be estimated as follows:

[3.26]

with generator Q^ε(v) defined in [3.24]. The relations [3.25] and [3.26] imply [3.22]−[3.24]. Note that the intensity kernel Q^ε(u, dz) defines the intensity of jump values for the process ν^ε(t) under the condition

for a fixed parameter u. The diffusion approximation for a normalized centered queueing process [3.19] is realized under asymptotical representation for infinitesimal characteristics, defined by generator [3.22]-[3.24].

THEOREM 3.2.– (Diffusion Approximation). Let the intensity of jump values of Markov queueing process ν^ε(t) admit asymptotical representation of the first and second moments, as ε → 0:

[3.27]

[3.28]

where the residual terms θ^ε(v, u) in both formulas satisfy the negligibility condition

[3.29]

Let the velocity of the centered function C^ε(v) admit asymptotical representation

[3.30]

with a negligible term θ^ε( v):

Then, under the additional balance condition

[3.31]

the normalized centered queueing process ζ^ε(t), defined in [3.19], converges, in distribution, to a diffusion:

The generator of the limit process ζ⁰(t) is then defined as:

[3.32]

where the centered function ρ(t) is defined by a solution of evolutional equation

[3.33]

with initial value

[3.34]

The initial value of the limit diffusion is defined by the condition

COROLLARY 3.2.-Let the intensity kernel have the following asymptotical representation:

[3.35]

and the kernel Q⁰(v, dz) be differentiable by v. Then the asymptotical representation [3.27] has the following form:

[3.36]

COROLLARY 3.3.- Let the velocity C (v) of the centered function have an equilibrium point ρ₀ ≥ 0: C (ρ₀) = 0. Then under the initial conditions [3.34] and [3.35], the limit diffusion of the Ornstein-Uhlenbeck type process is defined by generator

[3.37]

where the drift function is linear with respect to u:

[3.38]

and the covariance matrix is constant:

[3.39]

PROOF.- (Proof of theorem 3.2). The asymptotic representation of generators [3.22]−[3.24] is considered on the set D of real-valued, twice continuously differentiable functions φ(u,v) with compact support.

Taking into account asymptotical representations [3.27] and [3.28] of the first two moments of the jump component and [3.30] for the velocity of centered function, we obtain

[3.40]

As before, the residual term θ^ε(u, v) satisfies the negligiblility condition [3.29]. The balance condition [3.31] yields the following asymptotical representation for generator [3.22]:

Now the martingale characterization of the coupled Markov process ζ^ε(t), ρ(t), t ≥ 0, is the following:

[3.41]

which can be transformed into

with a residual negligible term satisfying the condition

[3.42]

One has to place the following representation of the square characteristic of martingale [3.41]:

[3.43]

with a random function ζ^ε(s), s ≥ 0, which satisfies the compactness condition: for every fixed T , there exists δ > 0 such that

[3.44]

Hence, by the Pattern theorem (Korolyuk and Korolyuk 1999, Theorem 3.4), the following weak convergence (in distribution) takes place:

The limit two-component Markov process ζ⁰(t), ρ(t), t ≥ 0, is determined by the generator

[3.45]

To complete the proof of theorem 3.2, note that the coupled Markov process ζ⁰(t), ρ(t), t ≥ 0, with the first component determined by generator [3.32], is defined by generators [3.37] and [3.45]. □

NOTE 3.1.-Using the centered drift function ρ^ε(t), that depends on the series parameter ε, the drift term in [3.32], which is not dependent on u, can be removed. But it is not possible to remove the drift part of the limit diffusion completely.

NOTE 3.2.- The considered class of Markov processes contains “density-dependent population processes” for which the diffusion approximation without a drift component was investigated in the book by Ethier and Kurtz (1986). The limit diffusion is not ergodic despite the fact that the initial process is ergodic.

3.3.3. Stationary distribution

The diffusion approximation of stationary Markov jump processes provides the approximation of their stationary distributions. It means that the stationary distribution density π^ε(du), ε > 0 , of a normalized and centered queueing process weakly converges, as ε → 0, to stationary distribution density π⁰(du) of the limit diffusion process.

Essential aspects of this problem are considered in the book by Ethier and Kurtz (1986, Section 4.9). The main idea is to verify the relative compactness of stationary densities π^ε(du), ε > 0. The most useful approach involves Lyapunov functions V (u), which satisfy the following conditions:

• – V (u) > 0 in some vicinity of zero point u = 0;
• – V(0) = 0;
• – V(u) → ∞ as ∥u∥ → ∞.

In addition, V (u) is an excessive function for generator of the limit diffusion process:

For a given diffusion process, the Itô formula provides a more direct approach (Ethier and Kurtz 1986, Section 4.9, Problem 35).

A weak convergence of stationary distributions is considered for the normalized queueing process with equilibrium point ρ ≥ 0:

[3.46]

The generator of Markov process ζ^ε(t) has the following form:

[3.47]

where

[3.48]

The limit diffusion process in this case, under the conditions of theorem 3.2, is determined by the generator

[3.49]

where

[3.50]

THEOREM 3.3.– (Convergence of stationary distributions). Consider a Lyapunov function V (u) for generator [3.49], which satisfies the condition:

[3.51]

Then the stationary densities π^ε(du), ε > 0, of normalized queueing process [3.46], defined by generators [3.47], converge weakly to stationary density π⁰(du) of the limit diffusion process, defined by generator [3.49].

PROOF.- (Proof of theorem 3.3). At first, we establish the weak compactness of stationary densities π^ε(du), ε > 0. According to the definition of the generator, we have the following representation:

[3.52]

Under the conditions of theorem 5.2, we obtain the following asymptotical representation:

[3.53]

with negligible term θ^ε(u) that satisfies the condition [3.9].

Putting [3.51]-[3.53] together, we get the following inequality:

where o_h(ε) → 0 as ε → 0. Hence, for enough small h and ε, the following inequality takes place:

[3.54]

It follows that V(ζ^ε(t)), t ≥ 0, is a supermartingale:

for all t > 0.

Let and . Due to the property of the Lyapunov function, one obtains:

Now the weak compactness of stationary distribution π^ε, ε > 0, is a consequence of the estimate, obtained by using Chebyshev’s inequality for transition probabilities:

for all enough small ε > 0.

But by the property of stationary distribution one has:

Therefore, there exists a convergent sequence

[3.55]

We have to establish now that the measure π⁰(du) is a stationary distribution of the limit diffusion process, defined by generator [3.49].

Let be the transition probabilities of the limit diffusion process defined by generator [3.49].

According to theorem 3.2, the convergence

[3.56]

takes place uniformly for t ∈ [0, T] for any finite function with compact support. Consider a measure defined as

and the functional

The convergence [3.56] implies the following limit representation:

[3.57]

Now we calculate

[3.58]

Using the relative compactness of the densities π^ε(du), ε > 0, established above, we get by [3.55] and [3.57] the following relations:

and by [3.58]

Putting the last two limits together, we obtain

It follows that

Hence, π⁰(dz) is the stationary measure of the limit diffusion process, defined by the limit generator [3.49]. The proofof theorem 3.3 is completed.

The construction of Lyapunov function V(u) can also be realized in another way.

Let us consider the limit diffusion process, defined by generators [3.37]-[3.39] with a constant covariance matrix and linear drift function with respect to u. Such a limit diffusion process is used in numerous applications.

LEMMA 3.2.- A diffusion process on real line R has the generator

[3.59]

where the drift function has the following form:

[3.60]

Then the Lyapunov function for the generator [3.59] can be chosen as follows:

[3.61]

where the constants V₀ > 0 and V₁ satisfy the inequality

[3.62]

Here

[3.63]

PROOF.– (Proof of Lemma 3.2). Note that the integral in right-hand side of [3.62] is finite due to assumptions [3.60] and [3.63]. Using the first and second derivatives of the function [3.61], it is easy to calculate

Hence, the function V(u), given by [3.61], is excessive for the generator [3.59].

3.4.1. Collective limit theorem in R¹

Consider a normalized queueing process

[3.64]

where the queueing process ν^ε(t) determines the number of customers in the system including that which have to be served at time t.

The positive valued centering function ρ(t),t ≥ 0,is supposed to be continuously differentiable. For simplicity, assume that the customers arrive and leave the system one by one.

The basic assumption is that the intensities of input and service times, under the condition ν^ε(t) = k, depend on the parameter k in the following way:

[3.65]

with some given functions λ(v), μ(v), λ₁(v) and μ₁(v), v ∈ R¹.

Note that the connection between the variables k = ν^ε(t),v = ρ(t) and u = ζ^ε(t) is represented as follows:

Therefore, the intensities of jumps of Markov process [3.64], under the condition ζ^ε(t) = u, have the following representation:

[3.66]

THEOREM 3.4.– (Collective limit theorem). Let the intensities of input and service times of the queueing process ν^ε(t) be set by relations [3.65]-[3.66] with continuously differentiable functions λ(u) and μ(u), having a bounded first derivative, and continuous functions λ₁(u) and μ₁(u). Let there exist a positive solution of evolutional equation

[3.67]

[3.68]

with initial condition ρ(0) = ρ 0 ≥ 0. And let the initial value of the queueing process converge, in probability, as follows:

[3.69]

Then the normalized queueing process [3.64] converges weakly as ε → 0 to a diffusion process :

The generator of the limit diffusion process ζ⁰(t) is determined by the relation:

[3.70]

where

[3.71]

[3.72]

The initial condition is ζ⁰(0) = ζ⁰.

PROOF.– (Proof of theorem 3.4). First, we calculate the local characteristics of the coupled Markov process ζ^ε(t), ρ(t), t ≥ 0, using the representation [3.66] of jump intensities and the formulas [3.27] and [3.28]. The jump intensities [3.66] are transformed as follows:

with residual negligible terms θ^ε(v, u) satisfying the condition [3.29]. By formulas [3.27], [3.35] and [3.36], we obtain

By formula [3.28], we get

At last, by balance condition [3.31]

We finish the proof of theorem 5.4 by applying theorem 3.2.

NOTE 3.3.- In the stationary regime with equilibrium point ρ:

[3.73]

the limit diffusion process is of the Ornstein-Uhlenbeck type with generator

where

[3.74]

The diffusion approximation algorithm of Markov queueing systems is formulated in the collective limit theorem 3.4. Under given intensities of input and service times represented in the form [3.65], the centered function ρ(t) is determined by a solution of evolutional equation [3.67] with velocity function, defined by [3.68]. The generator of the limit diffusion is defined by [3.70] with drift function given by [3.71] and covariance function given by [3.72]. The initial value of the limit diffusion is defined by [3.69].

3.4.2. Systems of M/M type

A single queueing system with unbounded queue is defined by input intensity λ and service time μ having exponential distributions.

COROLLARY 3.4.- Under the condition of heavy traffic λ > μ, the normalized queueing process

[3.75]

with centering function

where ρ₀ is determined under the condition

[3.76]

converges weakly to a diffusion process ζ⁰ with zero mean and variance

COROLLARY 3.5.- An unbounded queueing system, with the rate of Poisson arrivals λ and the intensity of exponential distributed service time μ, has M/M/∞ type. The normalized queueing process [3.75] with centering function

[3.77]

where ρ₀ is determined by initial condition [3.76] and converges weakly, as ε → 0,to a diffusion process , is defined by generator [3.70] with drift function

[3.78]

and variance

[3.79]

3.4.3. Repairman problem

An extensive literature is devoted to this problem, for example, Iglehart (1965). There are n identical working devices that operate independently, m spare devices and r repairing facilities. If one of n operating devices fails, it transfers to a repair facility, being replaced by one of the spare devices. There are at most n devices operating at any time.

The working time of every device has exponential distribution with intensity λ. If r , or more, devices are being repaired, the failed device has to join a queue at the repair facility and wait for service. Let ν_n(t) be a number of devices undergoing or waiting for repair at a time instant t.

The diffusion approximation of queueing process ν_n(t) in the repairman problem depends on the correlations between parameters n, m and r.

There are considered to be three different variants.

COROLLARY 3.6.- (Iglehart (1965)). Let the following condition be fulfilled:

[3.80]

where m₀ and r₀ are fixed numbers and, in addition,

[3.81]

Then the normalized queueing process

[3.82]

with centering constant

converges weakly, as n → ∞, to a diffusion process ζ⁰(t) with drift function a(u) = −uλ and variance B = 2r₀μ.

PROOF.– A normalized queueing process can be represented as follows:

where κ_n(t) := ν_n(t)/n. This scaled process satisfies the inequality

The intensities of jumps of queueing process ν_n(t) are different on the intervals

namely

[3.83]

and

[3.84]

According to basic assumption [3.65] of theorem 3.4, the intensity functions are transformed to the next expression (considering the substitution

and

By assumptions [3.80] and [3.81] of corollary 3.6 and taking into account the condition

the normalized correlation has the form

Therefore, the intensity functions are considered on the intervals

and

The condition [3.80] of corollary 3.6 specifies the intensity functions on the interval

that is

Now, by theorem 3.4, we calculate the parameters of the limit diffusion:

with drift function

and variance

3.5.1. Collective limit theorems in R^N

A Markov network is determined by a finite number N of nodes. In every node there is a Markov queueing system. The customers are transferred from one node to another according to the marching matrix:

where p_kr is probability of a custom transference from kth node to rth node.

The queueing process

is a vector function with components ν_k(t) of customers in kth node at time instant t. So the queueing process ν(t) takes values in the Euclidean space R^N of the dimension N.

Consider an open network that means there exists at least one k for which

In other words, a customer leaves the kth node with probability p_k0. The network temporal evolution is determined by intensity vector functions λ(u) = λ_k (u); 1 ≤ k ≤ N and μ(u) = μ_k(u); 1 ≤ k ≤ N where u = (u_k): 1 ≤ k ≤ N) ∈ N. The customers arrive from outside at the kth node with exponentially distributed time intensity λ_k(u), and the exponentially distributed time of service at the kth node with intensity μ_k(u), 1 ≤ k ≤ N. Without loss of generality, assume that the virtual passages are not possible: p_kk = 0 for all k. The diffusion approximation of queueing process begins by introduction of a small series parameter ε > 0. The main assumption is that the intensity functions depend on ε in the following form:

where u=(u_n; 1 ≤ n ≤ N) is a vector of values of the queueing process ν(t). The normalized queueing process is considered in a similar form as for the queueing system

[3.85]

with some deterministic positive-valued vector function

We use the following notation. A vector with the superscript “d” is a diagonal matrix, for example:

where δ_kr = 0, if k ≠ r, and δ_kk = 1 are Kronecker symbols.

THEOREM 3.5.– (Collective). Assume the following conditions:

1. a) the vector functions λ(u) and μ(u) are continuously differentiable with bounded first derivatives;
2. b) there exists a unique positive solution of differential equation
   [3.86]

   where

   [3.87]
3. c) the marching matrix P = [p_kr ; 1 ≤ k, r ≤ N] is irreducible and invertible;
4. d) the initial values of the normalized queueing process converge in probability: ζ^ε(0) ⇒ ζ⁰ as ε → 0.

Then the normalized queueing process converges in probability

The limit ornstein-Uhlenbeck diffusion process ζ⁰(t), t ≥ 0 is defined by generator

[3.88]

The covariance matrix B (u) is determined as follows:

[3.89]

where

PROOF.^_ (Proof of theorem 3.5). First of all, it is necessary to calculate the intensities of transfers of the normalized queueing process ζ^ε(t). Let us introduce the notation

where δ_kr is the Kronecker symbol. Note that the normalized form of queueing process [3.85] determines the following relation between the variables and u = ζ^ε(t):

Now it is possible to determine the jump intensities of the normalized Markov queueing process ζ^ε(t):

[3.90]

The first formula gives the intensity of increase by one of the kth components ν_k(t): a customer arrives at the kth node of the network.

The second formula gives the intensity of decrease by one of the kth components ν_k(t): a customer leaves the network.

The third formula gives the intensity of increase by one of rth the components ν_r(t) and decrease by one of the kth components: a customer transfers from the kth node to the rth node of the network.

So the first two moments of jumps of the normalized queueing process [3.85] can be calculated. Using formula [3.27], the first moment in the following form is obtained:

Transforming the second term, one has

So the first moment has the following representation:

or, using notation [3.87], in the vector form:

Using Taylor’s formula, the asymptotic representation of the first moment is:

where ∣∣θ_ε(v,u)∣∣ → 0 as ε → 0.

Hence, according to the notation in [3.27],

By theorem 3.2, it can be concluded that the centering function ρ(t) is determined by the solution of equation [3.86] and the drift function of the limit diffusion process is b(v, u) = u ∗ c′(v). The second moment of jumps of the normalized queueing process [3.85] with intensities of jumps [3.90] is calculated in a more complicated way. Using formula [3.28]

The second term is transformed as follows:

So the second moment has the following form:

or, using notation [3.89], the second moment is:

Applying the Taylor formula, it is seen that asymptotic representation of the second moment has the following expression:

Using theorem 3.2, the covariance matrix of the limit diffusion process is defined by relation >[3.89]. The proof of theorem 3.5 is completed.□

3.5.2. Markov queueing networks

Two types of Markov queueing networks and a superposition of independent Markov processes on a finite-dimensional phase state space are considered.

Network of [M |M| ∞]^N type: the Markov queueing systems of type M ∣M ∣∞ are considered in each of N nodes of the network. Let the intensities of arrival times at the nodes of the network be determined by a vector λ(u) = (λ_k ; 1 ≤ k ≤ N) and let the intensities of service times in nodes of the network be determined by a vector μ(u) = (μ_k 1 ≤ k ≤ N).

COROLLARY 3.7.– The normalized queueing process of a network of [M ∣ M∣ ∞]^N type

with the centering function is determined by the solution of the equation

[3.91]

where

[3.92]

under the conditions (c) and (d) of theorem 3.5 weakly converges as ε → 0 to an Ornstein–Uhlenbeck diffusion process with drift function

[3.93]

and covariance matrix

[3.94]

PROOF.˗ For the network of [M | M∣ ∞]^N type, the intensity functions λ(u) and μ(u) in theorem 3.5 are determined as follows:

So, by formulas [3.86], [3.87], [3.91] and [3.92] one obtains [3.93] and [3.94], taking into account [3.88] and >[3.89]. □

Network of [M | M | 1| ∞]^N type: the Markov queueing systems of M | M ∣1∣ ∞ type with intensities of arrival times λ_k and service times μ_k, 1 ≤ k ≤ M, are located in the nodes of the network.

COROLLARY 3.8.˗ The normalized queueing process of [M | M|∞]^N type network

with centering function ρ(t) = ρ₀ + Ct, C = λ + μ∗Q, where Q := [P − I], weakly converges, as ε → 0, to a diffusion process with zero mean and covariance matrix

[3.95]

PROOF.˗ By theorem 3.5, using the intensity vector function

according to formulas [3.86] and [3.87], the equation for the centered function is

Hence, the centering function is determined as ρ(t) = ρ₀ + Ct. By formulas [3.88] and >[3.89], we can conclude that the drift function of the limit diffusion process is identically equal to zero, and the covariance matrix is given by [3.95]. □

3.5.3. Superposition of Markov processes

There are n independent ergodic Markov processes κ_i(t), 1 ≤ i ≤ n on a finite state space {0, 1,..., N } with generator matrix

Introduce the counting process:

with components , which describe the number of Markov processes κ_i(t), 1 ≤ i ≤ n in the state (k , 1 ≤ k ≤ N). Let ρ =(ρ_k, 1 ≤ k ≤ N) be the stationary distribution of Markov processes:

Introduce the notations:

COROLLARY 3.9.˗ The normalized counting process

[3.96]

weakly converges, as n →∞, to an Ornstein–Uhlenbeck diffusion process with drift function

[3.97]

and covariance matrix

[3.98]

PROOF.˗ The counting process [3.96] can be considered as a normalized queueing process for a Markov network with marching matrix

Consider the normalized counting process [3.96] in the following form:

Note that

Hence, the following relation exists between the two variables u = ζ⁽ⁿ⁾(t) and κ = K⁽ⁿ⁾(t):

or

Besides, , i.e. . Now determine the intensities of jumps of Markov process [3.96] under the condition

We leave it to the readers to complete the proof of corollary 3.9 similarly as in the proof of theorem 3.5.