5.2.1. The differential equation

Let z be a shorthand notation for the vector (z₁,..., z_n)^T. The following theorem describes a PDE for f (s, z, t) := .

THEOREM 5.1.– The joint transform f (s, z, t) satisfies the following PDE with boundary condition f (0, 1, t) = 1:

[5.1]

PROOF.– We exploit the fact that {(Λ(t),X₁(t),...,X_n(t)), t ≥ 0} is a Markov process. At some given time t, let us assume X_i (t) = k_i for each i, and Λ (t) = λ. In [t, t + h),h ↓ 0, three things can occur: a customer completes phase i of its service at rate k_iμ_i; a customer arrives at rate λ; the arrival parameter resamples at rate γ. Hence

Straightforward calculations now yield

Dividing by h and letting h ↓ 0 leads to the PDE [5.1].

Let the vector (Λ, X₁,..., X_n) be the steady-state version of the time-dependent (Λ(t),X₁(t) ,..., X_n(t)) and write f(s,z) := . The following corollary then immediately follows from Theorem 5.1.

COROLLARY 5.1.-

[5.2]

with f (0,1) = 1.

Solving either of the equations [5.1] or [5.2] is no easy task. Both are in the class of semilinear first-order PDEs. The usual solution approach would therefore be the method of characteristics (see, for example, (Salih 2016)). However, the appearance of f (0, z, t) (and f (0, z)) also makes it a delay equation. Hence, we cannot use standard techniques to compute an exact solution.

Numerical approaches for solving partial delay differential equations have been considered, though most often for very specific types. Finding a suitable method seems hard, and it remains a problem to solve [5.1] and [5.2] either analytically or numerically.

NOTE 5.1.- Taking z₁ = ... = z_n = 1, equation [5.1] becomes = 0 Therefore, the marginal transform is independent of t − and hence so is the distribution ofΛ(t). For each point in time t, Λ(t) has distribution GΛ. Of course, considering Λ(t) is still valuable for analyzing correlations with Λ(t′) or X_i(t′) for some t ′ ∈ IR. From now on, when we are not concerned with such correlations, we simply write Λ instead of Λ(t).

NOTE 5.2.- Taking s = 0 in [5.2] yields

Although this equality does not seem to have a direct interpretation, it does when we take z₁ = ... = z_n and subsequently take z = 1. We then get

[5.3]

with S representing the sojourn time, one could compare this to Little’s formula λ = E(X)/E(S) for any standard queue. Since the sojourn time equals the service time in our infinite-server setting, is the rate at which a service is completed. Note that

so that Little’s formula indeed holds with λ replaced by E(Λ).

5.2.2. Calculating moments

One important feature of a generating function or Laplace–Stieltjes transform is the ability to quickly extract any moments for the corresponding random variable. In this section, we show that the PDE [5.1] provides enough information to do just that. More specifically, it allows us to calculate any moment of (Λ (t), X₁(t), ... ,X_n (t)) by solving a recursion.

Let k denote the vector (k₁,..., k_n)^T . If we would have an expressionforf (s, z, t), then the (l, k)^th moment could be calculated by

[5.4]

NOTE 5.3.– Formally the moment should be defined as rather than . However, the former can easily be obtained from the latter.

Applying these same differentiations to PDE [5.1] yields, with denoting the mth derivative w.r.t. x:

Now define E (l, k₁ ,..., k_n, t) := as a shorthand notation for the joint moment. When we take s = 0, z = 1and use [5.4], we obtain

[5.5]

our aim is to show that the recursive formula [5.5] allows one to iteratively compute all moments of(Λ (t), X₁(t) ,..., X_n(t)), assuming all moments of G_Λ are known. Let us first make the assumption that the system is empty at t = 0. If not, we split X_j(t) into the customers who arrived before or after t = 0. The contribution to X_j(t) of arrivals before time 0 can be calculated if we know (X₁(0), ..., X_n(0)),by finding the probabilities p_ij(t) that a customer who was in phase i at time 0 is in phase j at time t. Conditioning on the case that it takes exactly u time to move from phase i to phase j,

Here, and is the density of a hypoexponential distribution (see (Ross 2010, p. 310)). Recall that a hypoexponential random variable is a sum of independent exponentials (in our case j − i exponentials with rates μ_i,...,μ_j−1, respectively). It can also be seen as a Coxian random variable for which all continuation probabilities p_k = 1.

Let Y_ij (t) ~ Bernoulli(p_ij (t)) for i ≤ j, and let Y_ij,m (t), m = 1, 2,... be i.i.d. copies of Y_ij (t). Then the fraction of customers from X_j (t) that arrived before t = 0 equals

Now that we have found the fraction of customers from X_j (t) that arrived before t = 0, let us assume for the remainder of the section that the system is empty at time 0.

THEOREM 5.2.– All moments of (Λ (t), X₁ (t),...,X_n (t)) can be computed using [5.5], and have the form

[5.6]

for some constants a₁ ,..., a_N and non-negative constants N, b₁ ,..., b_N.

PROOF.– We provide an inductive argument. In remark 5.1, we have seen that the distribution of Λ (t) is independent of t. In particular, E(Λ^l (t)) is constant in t, so the statement is true when taking k₁ = ... = k_n = 0.

Let us take a look at the structure of the recursion [5.5]. The derivative of the moment with (l, k₁ ,..., k_n) equals a linear function consisting of four unknown components: (1) the moment itself, (2) the same moment with k₁ − 1 and l + 1, (3) the same moment with k_j − 1 and k_{j− 1} + 1 for some j = 1, ..., n − 1, and (4) the same moment with l = 0.

Let . We have shown above that the statement is true for . The inductive step is split into two parts. First, assume we know all moments of order (l, K − 1) and we want to calculate all moments of order (0, K). Note that when substituting (0, K), component 4 coincides with component 1, and component 2 is known by assumption. From E (1, K − 1, 0,..., 0, t), we can calculate an arbitrary moment E (0, k₁,..., k_n, t) oforder(0,K) with the following scheme:

Note that for each arrow, a differential equation needs to be solved.

For the second part of the induction step, we assume that all moments of order (l′, K − 1) and (0, K) are known, and want to calculate all moments of order (l, K). In this case, both components 2 and 4 are known by assumption. The arbitrary moment E (l, k₁,..., k_n, t) of order (l, K) can now be calculated using the following scheme:

Combining both schemes, we can iteratively find an expression for any moment E (l, k₁ ,..., k_n, t). All that remains is to show that the moments take the form of [5.6]. This will be done by induction on the number of iterations.

Assume all moments calculated thus far take the form of [5.6]. Note that each iteration requires the differential equation [5.5] to be solved. This differential equation has the form

where C, M, are constants of which C, M are non-negative and g_m (t) are known functions from previous iterations. Since the g_m (t) have the required form by assumption, it holds that

[5.7]

for some constants of which are non-negative. Solving this differential equation quickly leads to the result of the theorem.□

NOTE 5.4.- It is an interesting question how many different terms a moment consists of, given its order (l, k₁, ..., k_n). In other words, how large is N in [5.6]? To answer this, note that when wesolve the differential equation [5.7] the only exponent we have not seen in previous iterations is −Ct. So N is at most the number of possible values of C. Checking with [5.5], we conclude that .

In terms of computational complexity, observe that [5.5] has O(n) terms, each one consisting of one momert. Since a moment has terms, one iteration requires operations. Note also that we need one iteration for each moment of lesser order. Therefore, the calculation of a moment of order (l, k₁ ,..., k_n) requires operations.

Now that we have seen that all moments can be retrieved, and which form they have, let us calculate some of these moments. This gives an idea how the system behaves in general and presents a quantitative way to compare our queue to other models.

One can check that expressions from higher moments become very large and complicated, requiring much computational effort and making analysis difficult. However, for some lower moments and special cases, we can derive “nicer” expressions. This enables us to give intuitive explanations and perform proper analyses on the formulas we used.

We start with an expression for the mean number of customers.

THEOREM 5.3.– Let . Given that the system is empty at t = θ, the mean number of customers in phase j at time t equals

[5.8]

PROOF.– Let us first consider the case j = 1. Substituting k₁ = 1 and l = k₂ = ... = k_n = 0 gives the differential equation

With E (X₁(0)) = 0, its solution is

[5.9]

Therefore, [5.8] holds for j = 1.

Now let j ∈ {2, ..., n}. The differential equation corresponding to k_j = 1 is

[5.10]

To show that [5.8] is indeed a solution to this equation, we differentiate [5.8] and rearrange terms, using that

To verify that solution [5.8] to differential equation [5.10] is the desired solution, we need to show that [5.8] satisfies the boundary condition E (X_j(0)) = 0. So what remains is to check that C_i,j = 1. We can do this by observing that

As has been proven (Ross 2010, pp. 309-310), the integrand is a density function of a random variable on [0, ∞). It follows that Ci,j = 1, which concludes the proof.

For further moments, it is necessary to find E (Λ (t)X₁(t)) first. So with l = k₁ = 1 and k₂ = ... = k_n = 0, [5.5] gives

Here, we used the E(X₁(t)) we found in [5.9]. Combined with the boundary condition E(Λ (0)X₁(0)) = 0, the solution equals

[5.11]

Next, we use the same trick for E (X₁(t)(X₁(t) − 1)). The differential equation for k₁ = 2 and l = k₂ = ... = k_n = 0 is

with E (X₁ (0) (X₁ (0) − 1)) = 0. This has the solution

[5.12]

and it follows that

[5.13]

It is easily verified that γ = μ₁ is not a singularity.

The correlation between Λ(t) and X₁(t) follows from [5.11] and [5.13]

[5.14]

where is the dispersion index. Interestingly, the arrival process manifests itself only through D_Λ. The positive correlation that the formula indicates makes sense, since correlation between Λ(t) and X₁(t) can only occur when Λ (t) shows variability.

As it is visible in Figure 5.1, there appears to be a time where the correlation is maximal. This will be the time t_max that enough customers could have arrived to show correlation, buta large fraction of X₁ (t_max) still originates from the current Λ (and not from previous ones).

5.2.3. Steady state

In this section, we consider the steady-state behavior of the infinite-server queue, again focusing on a recursion for the joint moments of arrival rate and numbers of customers in phases 1,....,n.Let Letting t →∞in [5.5] yields the following steady-state recursion:

[5.15]

Note that an iteration step only requires some basic operations, whereas in the transient case each iteration required a differential equation to be solved.

Let us find the steady-state mean number of customers in phase j. Taking k_j = 1 (and everything else 0) yields

This simple recursion results in

[5.16]

which of course we could also have found from [5.8] letting t → ∞.

NOTE 5.5.- Recall that the mean number of customers in an ordinary M/M/∞- queue is , the arrival rate divided by the departure rate. Formula [5.16] represents something similar: the expected arrival rate over the departure rate in phase j.To see this, note that with being the probability that a customer reaches phase j, is the expected arrival rate of phase j.

With the steady-state mean at hand, formula [5.8] has a nice interpretation. We consider the steady-state number of customers who are in phase j (given in [5.16]), and distinguish the fraction that has been in the system for at least t time, and the fraction that has not. Where the steady-state mean consists of both fractions, the transient mean [5.8] only consists of the second (assuming an empty system at time 0). Now note that a customer in phase j has gone through j exponential phases (1 up to j − 1 completely and the past part of an exponential phase j). So the second fraction is proportional to the probability that j exponential phases are traversed before time t. According to formula [5.8], this probability should be . Indeed, this is precisely the distribution function of a hypoexponential random variable.

Another quantity that is greatly simplified by considering steady state is Cov(Λ, X_j). For this, we take l = k_j = 1 in [5.15] and find

such that

returns a simple recursion. We also observe that

hence the solution is

[5.17]

This formula also provides an interesting interpretation. Recall that is the probability that an exponential time with rate μ is shorter than an exponential time with rate γ. Therefore, is the probability that a customer traverses j − 1 service phases before the arrival parameter resamples. The appearance of this probability is intuitive, since the current Λ can only influence the current X_j if customers generated from this Λ arrive in phase j before a new Λ is drawn.

Next, we check the variance of the number of customers in phase 2. To do this, we substitute k₂ = 2 in[5.15]. In the calculation, we also use[5.17]forj = 2 and [5.12] for t → ∞

so that

[5.18]

Let us state the variance of the steady-state number of customers in phase 1:

[5.19]

(t → ∞ in [5.13]). It is easy to check that E(X₂) = E (X₁) and Var (X₂) ≤ Var (X₁) when p₁ = 1 and μ₁ = μ₂ = μ. A numerical result shown next will elaborate on this last remark.

Figure 5.2 visualizes the results of a simulation, where the service time distribution is taken to be Erlang with a large number of phases. The results give an impression of how the distribution of X_i evolves for growing i. Each line represents the distribution of the number of customers in the service phase corresponding to its color. Clearly, higher phases show less variability (while the mean remains unchanged due to p₁ = ... = p_n = 1 and μ₁ = ... = μ_n = μ, see [5.16]). It should also be noted that the distribution of the number of customers in phase i tends to a Poisson distribution for large i. This can be explained by the fact that consecutive customers spread out over different phases. The effect of the mixed arrival rate then slowly decays for increasing phase numbers, and eventually the stream of customers from phase i − 1 to i barely differs from a Poisson process. Therefore, it is intuitive that X_i converges to a Poisson random variable with mean .

Using the variance of X₂, we now calculate the correlation

In the special case that μ₁ = μ₂ = μ, we have

To compare, we let t → ∞ in [5.14] to get Cor(Λ, X₁):

[5.20]

In cases where the service rates are equal (i.e. μ1 = μ2 = μ), it holds that

because p₁ ≤ 1. An immediate consequence from this calculation is that Cor(Λ ,X₁) ≥ Cor(Λ, X₂) when the service rates are equal. This is not surprising, since customers “generated” by the current arrival rate Λ immediately arrive in phase 1, but take some time before entering phase 2 (if they remain in the system after phase 1). So earlier phases have a more direct connection with the current arrival rate.

The inequality does not necessarily hold for different service rates. To see this, note that when p₁ is high and μ₁ is high compared to μ₂ and γ, customers spend more time in phase 2 than in phase 1 before the arrival parameter resamples.

Let us finally take a look at X₁ + X₂, which is the total number of customers for n = 2. Its mean and variance can easily be computed, but its correlation with Λ is less straightforward. To find it, we first have to determine Cov(X₁, X₂). This is done by taking k₁ = k₂ = 1 in [5.15], and using the moments given in [5.17], [5.12] and [5.16]:

[5.21]

Then with [5.17], [5.13], [5.18] and [5.21], we find

[5.22]

Note that when p₁ = 0, customers never reach phase 2. It is easy to check that in that case, it indeed holds that Cor(Λ, X₁ + X₂) = Cor(Λ, X₁).

5.2.4. M_Λ/M/∞

In this section, we give a few results for the special Coxian case where the service time distribution is exponential with parameter μ. An easy way to recover the main results is by observing that this service time distribution can be obtained by taking p₁ = ... = p_n−1 = 0 and μ₁ = μ. We then find

[5.23]

as the PDE for the joint transform of(Λ, X) and

[5.24]

as the recursion for moments. The observant reader may have noticed that all p_i, i > 1 are irrelevant when p₁ = 0, because customers can only be in phase 1. The extended assumption is made to more easily copy results from Coxian service times.

If Λ ~ exp(θ), we can derive an expression for the form of any moment.

THEOREM 5.4.– Let Λ ~ exp (θ). Then the recursion [5.24] has solution

[5.25]

where c₀ (l, k) = 1, c_k(l,k) = and C_j (l, k) satisfies the recursion

[5.26]

For a proof by induction, we refer to (van Kreveld 2018). Let us here only check that [5.26] has a solution. The key observation is that the second argument is lowered in each step of the recursion. Note that when we express c_j (l, k) into coefficients of the form c_j′(l′, k − 1) by using [5.26], we have either j′ = 0, j′ ∈ {1,..., k − 2} or j′ = k − 1. In the first and third case, the value is given, and in the second case we can use [5.26] again. Repeating this procedure k − 1 times leaves us with only unknown terms with k = 1. Since j ≤ k, the remaining coefficients are of the form c₀(l′, 1) and c₁ (l′, 1). These are both known, so the recursion ends after k − 1 steps.

As we have seen, the mean number of customers is similar in M/M/∞ and M_Λ/M/∞, the only difference being that the fixed arrival rate λ is replaced by the expected arrival rate E(Λ). Mixing turns out to have a larger effect on the variance. Without mixing, the variance of X is equal to the mean, but our model has

[5.27]

as a consequence of [5.13] by taking μ₁ = μ and t → ∞. The first term is the variancewithoutmixing, and the second is caused by the variability of the arrival rate. It is therefore no surprise that the second term is linear in Var(Λ).

Heemskerk et al. (2017) provide another interesting comparison for the variance. They consider the same model, the only difference being deterministic resample intervals with common length Δ. For the variance of the number of customers, Heemskerk et al. (2017) obtain

[5.28]

where X_H denotes the steady-state number of customers in this model.

For a fair comparison between [5.27] and [5.28], we take , such that the mean resample interval lengths of both models agree. It clearly holds that Var (X) > Var (X_H) if and only if . Hence

[5.29]

One might expect that randomness of resample interval lengths leads to more variability in X. Surprisingly, this result shows that is not always true.

For a good image of the distribution of X, we use a simple simulation, ofwhich the details can be found in (van Kreveld 2018). Keeping track of the number of customers in the M_Λ/M/∞, the results for simulating up to t = 10⁶ can be seen in Figure 5.3.

Note that with Λ ~ U (0, 6) and γ = μ = 1, we have E (X) = 3 and Var (X) = 4.5. On a single run, the simulation rarely returns an error of more than 0.01 foreach quantity.

To investigate the role of the resample rate γ for the distribution of X, we make a plot for several values of γ (Figure 5.4). Although the mean number of customers is the same for each value, we see that the variance decreases when γ increases. This observation is in line with formula [5.27].

A particularly noteworthy case is γ → ∞. It then follows from [5.27] that Var (X) → E (X). In fact, looking at Figure 5.4 we may even suspect that X converges to a Poisson random variable. This is intuitively explained as follows: when the number of resamples between two arrivals grows to infinity, the arrival process behaves like a Poisson process with rate E (Λ).

The last quantity we analyze regarding the steady-state vector (Λ, X) is the correlation between Λ and X. It is given by [5.20], replacing μ₁ by μ as is explained at the start of this section.

In Figure 5.5, we see that the correlation is low both when the service rate is very low or very high. This can be explained as follows: for the correlation to be high, on the one hand the service rate should not be too high since we want customers generated by the current Λ to stay as long as possible. On the other hand, the service rate should not be so low that “old” customers from previously sampled Λ stay in the system for too long. The correlation turns out to be maximal for attaining the value

Notice its dependence only on D_Λγ.

We conclude this section with a brief discussion of scaling limits. We consider a scaling of the arrival rate Λ (t) with a factor N together with a scaling of the resample rate γ with factor N^α. The value of α determines which rate speeds up faster. If α > 1, the arrival rate changes very often, while if α < 1, the arrival rate rarely changes relative to the number of arrivals. We check the behavior of the M_Λ/M/∞ under this scaling and discuss the effect of the value of α. We follow the idea of Heemskerk et al. (2017, pp. 8-12), in which they consider a model with the arrival parameter resampling aftera fixed time Δ.

Let X^(N) be the steady-state number of customers under the corresponding scaling. Then we easily see that

and from [5.27] that

[5.30]

when N tends to infinity. This can be compared to the asymptotic variance of Heemskerk et al. (2017). Denoting by the number of customers in their model, they find

[5.31]

In both models, the variance increases as the average length of a resample interval increases. However, for the variances to be equal, it must be that In other words, our more random model needs twice as many resamples to obtain the same asymptotic variance.

From [5.30], the limiting behavior of the variance is

[5.32]

Let β = max {1, 2 − α}. The asymptotic behavior suggests the following central limit theorem.

CONJECTURE 5.1.- Assume all moments of Λ are finite. If N → ∞, then

[5.33]

with .

The statement of the conjecture is very similar to theorem 2.1 from Heemskerk et al. (2017). However, in the proof they use they remark that the resample interval lengths are constant. This property is critical in the proof, making it hard to prove our conjecture using the same idea. Nonetheless, it is expected that the statement holds in our model as well.

5.3.1. The differential equation

We follow a similar approach as in Blom et al. (2014, section 3). Let S(t) ∈ N be the state of the Markovian background process at time t. Also, let be the number of customers at time t given X (0) = 0, S (0) = i and Λ (0) = λ. Assuming an empty system at time zero is, for the same reason as in section 5.2.2, not very restrictive. Say for example that there are m customers at time zero. Each of those can be characterized by the state it arrived in and its residual service time. With this information, we can calculate the probabilities q1, ..., q_m that the corresponding customer is still in the system at time t. Let Z_j(t) ~ Bernoulli(q_j) for j = 1,..., m. Then the total number of customers at time t equals

Consider the small time interval (0, h). Define f_i,λ (z, t) := To remove the condition Λ (0) = λ, we define as the number of customers at time t given X (0) = 0 and S (0) = i. Moreover, let f_i (z,t) = = be the corresponding generating function. It is easily seen that

which yields the differential equation

[5.34]

Removing the condition Λ(0) = λ then gives

[5.35]

This last formula has some interesting consequences. For example, by letting t → ∞, we find the steady-state formula

Note that after an infinite amount of time, the state of the background process at t = 0 should be irrelevant. Since . the above equality indeed holds.

Another interesting situation occurs when n = 1, so that the system is always in state 1. Note that this is a generalization of our previous model, the service times now having a fully general distribution. equation [5.35] in this case becomes

Also taking the derivative with respect to z and taking z = 1 gives

which, with the condition that , yields

Taking B₁ ~ exp(μ₁) here, for example, gives

[5.36]

This formula of course agrees with formula [5.9] for the mean number of customers in phase 1 of the queue. When only considering customers in the first phase of a Coxian distribution, successive phases are irrelevant since there are infinitely many servers. Therefore, both models describe the M_Λ/M/∞, and when the background process has only one state and B₁ ~ exp(μ₁).

5.3.2. Calculating moments

In the from section 5.2, we saw that despite being unable to find the generating function, we could use the differential equation to compute all moments. We will do the same here with the Markov-modulated queue, both with and without the initial condition on Λ(θ).

To obtain factorial moments, we take from [5.34] the kth derivative with respect to z in z = 1:

[5.37]

Doing the same with [5.35] gives

[5.38]

THEOREM 5.5.– All moments and can be iteratively computed for all k ∈ IN.

PROOF.– Note that equation [5.38] can be seen as a system of linear differential equations

[5.39]

where

• is the n-dimensional vector consisting of up to ;
• A is a matrix with entries a_ij = γ_ip_ij for i ≠ j and a_ii = γ_i (p_ii − 1);
• 

In the same way, [5.37] can be viewed as n separate differential equations

[5.40]

with

The main idea is that when we solve the equations in the right order, the c(t)_i and c(λ,t)_i are known from previous iterations. If these quantities are known, we can find any moment by solving equations [5.39] and [5.40] via ordinary differential equation methods.

We now proceed to show a sufficient calculation order to complete the proof, by induction. For k = 1, we have c(t)_i = P(B_i ≥ t)E (Λ_i), enabling us to calculate for i = 1, ...,n with [5.39]. Now, is known such that with [5.40] we can also find .

Suppose we know all moments of order k − 1. Then c(t)_i can be found by assumption, so we can solve the system [5.39] to find for i = 1, ..., n. With these quantities found and the induction hypothesis, note that now also c(λ, t)_i are known. By solving [5.40], the proof is complete. □

The next step is to calculate some specific moments with equations [5.37] and [5.38]. Specifying the service time distributions allows for expressions without integrals, so let us assume from now that B_i ~ exp(μ_i) for i = 1, ..., n. The exponential distribution is a natural choice and gives simple expressions.

Note that we already found for n = 1 in [5.36]. We proceed with finding the mean, conditioned on Λ(0) = λ, and the variance for n = 1. After that we move on to n = 2.

With k = 1 and [5.36], differential equation [5.37] reads

One can easily check that, with boundary condition ,

Some interpretation of this formula can be obtained when we write it as

[5.41]

We recognize the first term as the formula for . The second term is a non-negative number times the difference between the conditioned starting arrival parameter λ and its expectation E (Λ₁). In other words, the difference in the mean queue size conditioned on Λ (0) = λ or Λ (0) = Λ₁, is linear in λ − E(Λ₁). It is evident that when t > 0, if and only if λ ≥ E(Λ₁), with equality ifand only λ = E(Λ₁).

It also follows from [5.41] that the difference between is largest at . The existence of a maximum is intuitive: at t = 0, the system still has to set up, and when t → ∞, the value of Λ (0) has become irrelevant. In both of these cases, it holds that .

Formula [5.41] also holds for the M_Λ/COX_n/∞ setting, in the sense that (see the end of section 5.3.1). The approach of section 5.2 does not enable us to find moments conditioned on Λ(0), so this is an interesting observation.

Moving on to moments of second order, we take k = 2 in [5.38] and find

The only solution with is

[5.42]

and hence

[5.43]

This is in agreement with [5.13]; see also the end of section 5.3.1.

We proceed by studying the variance when the starting arrival rate is fixed, i.e. Λ(0) = λ. Using formula [5.38] for k = 2 yields

Observe that the latter two terms are known from [5.42] and [5.41], hence we have a solvable linear differential equation. As usual, we set the boundary condition at E(), leading to E() and subsequently to

[5.44]

Note here that the initial arrival intensity only appears as λ − E (Λ₁), and that γ = μ₁ and γ = 2μ₁ are removable singularities.

So far, we have only obtained explicit expressions for moments in the Markov-modulated queue with the background process having only one state. In order to better analyze the effect of the background process on the queue, we now consider an example with n = 2. This should give an impression of the behavior of the Markov-modulated queue with multiple states.

For n = 2, k = 1, [5.39] takes the form

since p₁₁ − 1 = −p₁₂ and p₂₂ − 1 = −p₂₁. We can solve this system with the eigenvalue method (see, for example, (Shen 2013)). Define π := γ₁p₁₂+γ₂p₂₁ as the sum of the state transition rates. It is easily seen that the eigenvectors of the system are and with eigenvalues 0 and -π, respectively. Therefore, the solution is

with

The latter is a pair of separate linear differential equations. Solving these, substituting in the above solution and again using the boundary condition , yields

[5.45]

Quantities in [5.45] that should be recognized are

• and , the long-term fractions of finding the Markov process in states 1 and 2, respectively;
• , the mean number of customers when the Markov process is always in state i (i = 1, 2);
• , a non-negative quantity that increases whenever π or μ_i increases (i = 1, 2).

With these equations we can also find some other relevant quantities. For example, suppose that the state at time 0 is not known, but the background process is in steady state. Then and , so it follows that the mean number of customers at time t is

[5.46]

Another consequence of [5.45] is the steady-state mean

[5.47]

Keep in mind that there is no subscript needed, since in steady state it does not matter in which state we started. In the formula, we see the steady-state mean of each individual state, multiplied by the fraction that the corresponding state was active. The fact that the steady-state mean is just the sum of these parts underlines that customers from different states do not interfere with each other.

Let us now consider : the steady-state expected number of customers given the background process is in state 1. Before we can give an expression, we have to define as the portion of the current customers who arrived when the state was i. Distinction between and is relevant because customers who arrived in a different state will have a different service rate. For instance, the first term of [5.47] is the mean number of customers with service rate μ₁ .

Now define T₁ as an arbitrary time in steady state when the background process moves from state 1 to state 2. Also, let T_2→1 be the last time before T₁ that the state changed from 2 to 1. We split into the customers who arrived before or after T_2→1 , and then condition on the value of T₁ − T_2→1 . It holds that

Let T₂ and T_1→2 be the symmetric versions of T₁ and T_2→1. We then have

A useful observation here is that and , since in each case, both times represent a steady-state time at the end of a period of one state. As a result, we have a system of two linear equations. The solution is

[5.48]

Note the absence of E(Λ2) and μ₂ caused by the fact that customers from different states do not influence each other.

Let T_S = 1 be an arbitrary steady-state time with S(T_S=1 ) = 1. We will show that . Note that we can view the Markov background process as a Poisson process with rate γ₁p₁₂, and we can view its events as periods where the state is 2. We assume those periods take 0 time, so that the rate at which an event happens is always γ₁p₁₂. A nice property of the Poisson process is that when we pick an arbitrary point in time (T_s=1 ), the amount of time since the last event is exponentially distributed with parameter γ₁p₁₂. The same holds for T₁, so , hence in particular E .

As a quick sanity check, we calculate E(), the steady-state mean number of customers who arrived when the background process was in state 1 (i.e. the customers who have service rate μ₁). As mentioned, this should give the first term of [5.47]. The calculation below verifies this:

For symmetry reasons, [5.48] can be transformed into

[5.49]

Now we are finally ready to find the mean total number of customers conditioned on the current state:

[5.50]

and analogously,

[5.51]

Given the complexity of calculations with two states, formulas for general n will be costly to derive analytically. However, if one assumes that the Markov process is in steady state at time 0, one can use a shortcut found by Blom et al. (2014) for the mean number of customers. It is based on the well-known rate-in = rate-out balance equation , being the steady-state probabilities for each state.

To find the mean number of customers in this case, we take k = 1 in [5.38], multiply by π_i and sum over i. This results in

and hence

[5.52]

With relatively easy methods, we found a general formula for the mean. For instance, n = 2 and exponential service times yields [5.46], which was more difficult to find as we had to solve a system of differential equations. The disadvantage of the quicker method is that it gives no information about the case where the starting state S(0) is fixed.