3.1. The Discrete-Time Markov Chain Case

Consider a discrete-time Markov chain Y = {Y_n, n ≥ 0}. Let P = (p_i,j) be the transition probability matrix of Y.

Let λ be the initial probability distribution of the Markov chain Y. Let E_λ(·) be the expectation of Y when the initial distribution of Y is λ. Define

for function f(·) defined on Z₊. Let h_f = (h_f(0),h_f(1),···). Then Eq. (6) can be rewritten as h_f^T = Pf^T − f^T, where T denotes the transpose of the vector. It is readily seen that h_f(i) is the mean drift of the Markov chain Y with respect to function f(·) at the state i. Thus, we call h_f the mean-drift function of Y with respect to f(·).

For the Markov chain Y with transition matrix P, it is well known that P{Y_n = i} = (λPⁿ)(i), i ≥ 0. Thus, we have E_λ [f(Y_n)] = 〈λPⁿ,f〉. In this article we study the monotonicity and convexity of the function E_λ [f(Y_n)] for the Markov chain Y with an initial distribution λ. The objective is to find conditions under which the function E_λ [f(Y_n)] is increasing, decreasing, convex, or concave in n. For the continuous-time Markov chain {X(t),t ≥ 0}, we want to find conditions under which the function E_λ [f(X(t))] is increasing, decreasing, convex, or concave in t. The relationship between the functions E_λ [f(X(t))] and E_λ [f(Y_n)] is given in Section 3.2.

For example, consider an M/M/1 queue (see Section 4.1). The queue length process X = {X(t), t ≥ 0} is a birth-and-death process. The mean queue length E_λ [X(t)] at time t is depicted in Figure 1 for different initial distributions λ. Figure 1 shows that the function E_λ [X(t)] can be monotone, convex, or concave if the initial distribution λ is chosen properly (curves 1 and 2). Figure 1 also shows that, in general, the function E_λ [X(t)] may not be monotone, convex, or concave (curve 3). Thus, some conditions must be imposed on λ to ensure desired properties on E_λ [X(t)].

The mean queue length curves for an M/M/1 queue with ρ = 0.8.

In general, to ensure monotonicity, convexity, or concavity on the function E_λ [f(Y_n)], certain conditions must be imposed on the transition matrix P, the initial distribution λ, and the function f(·). The conditions considered in this article are closely related to the stochastic dominance of measures. Formally, we state the conditions as follows:

The following theorem shows the monotonicity, convexity, and concavity of the function E_λ [f(Y_n)] under the above conditions. The theorem also explains why the above conditions are utilized in this article.

Theorem 3.1: Consider an irreducible and aperiodic discrete-time Markov chain Y with transition matrix P. Let λ be the initial distribution of Y. Function f(·) is defined on Z₊. We assume that E_λ [f(Y_n)] is finite for n ≥ 0.

Proof: We only give a proof of (iii). Others can be proved similarly. Since λ and P satisfy Conditions I and II in Eq. (7), by Proposition 2.1 we have λPⁿ⁺¹ ≥_d λPⁿ for all n ≥ 0. In view of the monotonicity of the mean-drift function h_f, we obtain 〈λPⁿ⁺¹,h_f〉 ≤ 〈λPⁿ,h_f〉. Hence, 〈λPⁿ⁺²,f〉 + 〈λPⁿ,f〉 ≤ 2〈λPⁿ⁺¹,f〉; that is, E_λ [f(Y_n)] is concave in n. █

Remark 3.1: Assume that f(·) defined on Z₊ is increasing. f(·) satisfies Condition III in Eq. (7) if and only if the function Δf is excessive (see Çinlar [1, p.204]), where the function Δf is defined by Δf(i + 1) = f(i + 1) − f(i),i ≥ 0.

In general, it is not straightforward to check the conditions required in Theorem 3.1. Nonetheless, for some interesting special cases, these conditions can be checked (see Sections 4 and 5 for examples). We also point out that, in Theorem 3.1, the Markov chain Y does not have to be recurrent. Thus, in later sections, we do not require the Markov chains to be recurrent or the queueing models to be stable, unless stated otherwise.

Although the Markov chain Y in Theorem 3.1 is not required to be positive recurrent, some of the conditions in Eq. (7) have a close relationship with the positive recurrence of Y. For instance, if Y is positive recurrent, then Condition II implies λ ≤_d π, where π is the steady state distribution of Y. If the mean-drift function h_f is negative and decreasing, then the Markov chain Y is positive recurrent by Foster's criterion (see Cohen [2]). Such relationships are useful when we choose the initial distribution λ for our examples in Sections 4.

3.2. The Continuous-Time Markov Chain Case

Based on the above results for discrete-time Markov chains, we can obtain similar results for continuous-time Markov chains by using the uniformization technique.

Let X = {X(t), t ∈ R₊} be a homogeneous and continuous-time Markov chain. Let Q = (q_i,j) be the infinitesimal generator of X. Then Markov process X is said to be uniformizable if

If the Markov chain X is uniformizable, then for any ν ≥ sup_i≥0(−q_i,i), we define

where I is the identity matrix. Note that P defined by Eq. (8) is a stochastic matrix. We have (Medhi [14])

To study functions associated with X, we make use of a Markov chain with transition matrix P given in Eq. (8). We denote the Markov chain as Y. Assume that X and Y have the same initial distribution λ. Let

Suppose that the function g(λ,t) in Eq. (10) has derivative of order 2. Then by Eqs. (8) and (9), we can establish the following relationships between X and Y:

where E_λ [f(Y_n)] is defined for the Markov chain Y.

Equation (11) indicates that to study functions associated with X, it is sufficient to study functions associated with Y. More specifically, by Eq. (11), we know that the convexity of the function E_λ [f(Y_n)] implies the convexity of the function E_λ [f(X(t))]. Similarly, the monotonicity of the function E_λ [f(Y_n)] implies the monotonicity of the function E_λ [f(X(t))]. Counterparts of conditions in Eq. (7) are given as follows:

We state the monotonicity, convexity, and concavity of the function E_λ [f(X(t))] in the following theorem; it can be proved by combining Theorem 3.1 and Eq. (11). We omit its proof.

Theorem 3.2: Consider a continuous-time Markov chain X with infinitesimal generator Q. Suppose that X is uniformizable, and let ν ≥ sup_i(−q_i,i). We assume that Markov chain Y with transition matrix P given by Eq. (8) is irreducible and aperiodic. Suppose that X and Y have the same initial distribution λ. We assume that E_λ [f(X(t))] is finite for t ≥ 0.

4.1. The M/M/1 Queue

Consider an M/M/1 queue with an infinite number of waiting rooms, a first-in–first-served service discipline, arrival rate α, and service rate β (see Cohen [2]). We assume that α > 0 and β > 0. Let X(t) represent the number of customers in the system at time t. It is well known that the queue length process X = {X(t), t ∈ R₊} is a continuous-time Markov chain with an infinitesimal generator

The Markov chain X with generator Q given by Eq. (13) is a special continuous-time Markov chain. The Markov chain X is irreducible and its discrete counterpart P defined by Eq. (8) is irreducible and aperiodic if α > 0 and β > 0. Let ν ≥ α + β and define ρ = α/β. Conditions in Eq. (12) can be simplified to the following:

Note that for Conditions M/M/1(III) and M/M/1(III′), we assume that Δf(0) = 0, where Δf is a function defined in Remark 3.1.

To interpret the above conditions probabilistically, we use the following generalized likelihood ratio order defined for nonnegative measures. For two measures λ and μ, we say λ ≤_lr μ if λ(i + 1)μ(i) ≤ λ(i)μ(i + 1) for i ≥ 0. For more about the likelihood ratio order for random variables, see Shaked and Shanthikumar [18]. Let

. If the queuing system is stable (i.e., ρ < 1),

can be normalized to a probability measure π = (1 − ρ, (1 − ρ)ρ, (1 − ρ)ρ²,…), which is the steady state distribution of X. If

can be normalized to a probability measure π⁻¹ = (ρ − 1)(1/ρ, 1/ρ², 1/ρ³,…).

Proposition 4.1: Condition M/M/1(I) in Eq. (14) is satisfied for all ν ≥ α + β. Condition M/M/1(II) in Eq. (14) holds if and only if

. Condition M/M/1(II′) in Eq. (14) holds if and only if

. Condition M/M/1(III) in Eq. (14) holds if and only if

, where the function Δ²f is defined by Δ²f(i + 1) = Δf(i + 1) − Δf(i) for i ≥ 0. Condition M/M/1(III′) in Eq. (14) holds if and only if

.

Proof: It is clear that the first conclusion holds. The second and third conclusions hold by the definition of the generalized likelihood ratio order defined earlier. The last two conclusions are true since, by Eq. (14), ρΔ²f(i + 2) ≤ (≥)Δ²f(i + 1) for i ≥ 0. █

Using Proposition 4.1, it is easy to check the conditions for the monotonicity and convexity of the function E_λ [f(X(t))]. For Condition M/M/1(II) or M/M/1(II′) in Eq. (14), we consider the following initial distributions:

By Proposition 4.1, it can be verified that

satisfies Condition M/M/1(II) in Eq. (14) for all

satisfy Condition M/M/1(II) if

satisfy Condition M/M/1(II) if

satisfy Condition M/M/1(II′) in Eq. (14) if

satisfy neither Condition M/M/1(II) nor Condition M/M/1(II′).

For Condition M/M/1(III) in Eq. (14), we consider the function f(i) = i^k, i ≥ 0, where k = 1,2,…. By Proposition 4.1, if k = 1, Condition M/M/1(III) in Eq. (14) holds for all ρ > 0; if k = 2, Condition M/M/1(III) in Eq. (14) holds for

and Condition M/M/1(III′) in Eq. (14) holds for ρ ≥ 1; if k = 3, Condition M/M/1(III) in Eq. (14) holds for

, Condition M/M/1(III′) in Eq. (14) holds for ρ ≥ 1; and if k = 4, Condition M/M/1(III) in Eq. (14) holds if

and Condition M/M/1(III′) in Eq. (14) holds for ρ ≥ 1. Details for cases with k > 4 are omitted.

For the above initial distributions and function f(·), the monotonicity, convexity, and concavity of the function E_λ [f(X(t))] can be obtained immediately from Theorem 3.2. Details are as follows:

Case 1. Suppose that f(i) = i, i ≥ 0. The mean queue length

is increasing and concave in t. In addition, if ρ ≥ 1, then

is increasing and concave in t. Figure 2 depicts the two functions

for ρ = 1 (curves 1 and 2); we can get similar curves for ρ = 1.05, and ρ = 1.35. Note that the queues are unstable for ρ = 1, 1.05, and 1.35.

The mean queue length curves for an M/M/1 queue with ρ = 1.

Case 2. Suppose that f(i) = i, i ≥ 0, and ρ < 1. Then the mean queue length

is equal to a constant ρ/(1 − ρ);

is decreasing and convex in t. Since

does not satisfy Condition M/M/1(II) or Condition M/M/1(II)′ in Eq. (14),

does not have the monotonicity and convexity (curve 3 in Fig. 1).

Case 3. Suppose that

.

satisfies Condition M/M/1(II) and

satisfies Condition M/M/1(II′). The function f(·) does not satisfy Condition M/M/1(III),

do not have the monotonicity and convexity (curves 1 and 2 in Fig. 3). However, if

, then

is increasing and concave and

is decreasing and convex.

The fourth moment of queue length curves for an M/M/1 queue with ρ = 0.8.

Case 4. The functions

are not monotone, convex, or concave (curves 3 and 4 in Fig. 3).

Remark 4.1: We point out that similar results can be obtained for the M/M/c(c ≥ 1) queue with an infinite number of waiting rooms, a first-in–first-out served discipline, and c parallel servers. The only necessary change in Proposition 4.1 is that the vector

is changed to

Details are omitted.

4.2. The M/G/1 Queue

Consider an M/G/1 queue where customers arrive according to a Poisson process with parameter α (α > 0) and the service times are independent and identically distributed (i.i.d.) random variables and follow a general distribution G(·). We further assume that the mean and second moment of service times exist; the mean and variance of service times are denoted by E [S] and Var[S] = E [S²] − (E [S])², respectively. Assume that service times are independent of the interarrival times and customers are served according to the order of their arrival (see Cohen [2]). Let Y_n denote the number of customers left in the system right after the nth customer departs from the system. Then Y = {Y_n, n ≥ 0} is a discrete-time Markov chain, for which the transition probability matrix P is given by

where

for k ≥ 0. It is easy to see that the Markov chain Y is aperiodic and irreducible if α > 0. Let

. For the M/G/1 queue, conditions in Eq. (7) can be further simplified to the following:

First, it is clear that the matrix P is always monotone; that is, Condition M/G/1(I) in Eq. (18) always holds for the M/G/1 queue. Second, by routine calculations, it is easy to verify that λ = (1,0,0,…) and λ = (a₀²/(1 − a₁),a₀(1 − a₀)/(1 − a₁),(1 − a₀ − a₁)/(1 − a₁),0,…) satisfy Condition M/G/1(II) in Eq. (18). It can also be verified that λ = (0,0,0,π₀,π₁,π₂,…) satisfies Condition M/G/1(II′) in Eq. (18), where π = (π₀,π₁,π₂,…) is the steady state distribution of the Markov chain Y if ρ < 1. Third, it can be shown that Condition M/G/1(III) in Eq. (18) always holds for f(i) = i, since the mean-drift function h_f is given by (ρ,ρ − 1,ρ − 1,…). Condition M/G/1(III) in Eq. (18) holds for f(i) = i² if ρ ≤ 1 and for f(i) = i³ if 2ρ + ρ²(1 + Var[S]) ≤ 2.

For the queuing system, the mean queue length E_λ [Y_n] (i.e., f(i) = i) is increasing and concave in n if λ = (1,0,0,…) or λ = (a₀²/(1 − a₁),a₀(1 − a₀)/(1 − a₁), (1 − a₀ − a₁)/(1 − a₁),0,…). For λ = (0,0,0,π₀,π₁,π₂,…), if the queuing system is stable, the mean queue length E_λ [Y_n] is decreasing and convex in n. Furthermore, for higher moments of the queue length, E_λ [Y_n²] (i.e., f(i) = i²) is increasing and concave in n if λ = (1,0,0,…) or λ = (a₀²/(1 − a₁),a₀(1 − a₀)/(1 − a₁), (1 − a₀ − a₁)/(1 − a₁),0,…) and ρ ≤ 1 and E_λ [Y_n³] (i.e., f(i) = i³) is increasing and concave in n if λ = (1,0,0,…) or λ = (a₀²/(1 − a₁),a₀(1 − a₀)/(1 − a₁),(1 − a₀ − a₁)/(1 − a₁),0,…) and 2ρ + ρ²(1 + Var[S]) ≤ 2.

Remark 4.2: Note that for f(i) = i², the condition for the mean-drift function h_f to be decreasing is ρ ≤ 1 for the M/G/1 case. For the M/M/1 case, that condition is

. The reason is that we only consider the queue length at departure epochs for the M/G/1 case, whereas the queue length at an arbitrary time is considered for the M/M/1 case.

Remark 4.3: Condition III′ in Eq. (7) does not hold for f(i) = i^k,k ≥ 1, in the M/G/1 queue, since f(0) ≥ f(1) is not satisfied in this case.

4.3. The GI/M/1 Queue

Consider a GI/M/1 queue. Assume that the interarrival times are i.i.d. random variables, where the common distribution is A(·) and the mean interarrival time equals

. The service times are independent exponential random variables with parameter β (β > 0). Assume that service times are independent of interarrival times and that customers are served according to their order of arrival (see Cohen [2]). Let Y_n denote the number of customers seen by the nth customer at its arrival epoch. Then {Y_n, n ≥ 0} is a discrete-time Markov chain with a transition probability matrix P given by

where

. It is easy to verify that the Markov chain Y is irreducible and aperiodic if β > 0. Conditions in Eq. (7) can be simplified as follows:

Similar to the M/G/1 queue, Condition GI/M/1(I) in Eq. (20) always holds for the GI/M/1 queue. For the initial distribution λ, it can be verified that λ = (1,0,0,…),

satisfy Condition GI/M/1(II) in Eq. (20), where r is the unique root of the equation s = A*(β − βs) that is inside the circle

. The vector λ = (0,0,1 − r,(1 − r)r,(1 − r)r²,…) satisfies Condition GI/M/1(II′) in Eq. (20). For Condition GI/M/1(III) in Eq. (20), it always holds for f(i) = i. For f(i) = i², Condition GI/M/1(III) in Eq. (20) holds if 3b₀ + b₁ ≤ 1. For f(i) = i³, Condition GI/M/1(III) in Eq. (20) holds if 7b₀ + b₁ < 1 and 19b₀ + 7b₁ + b₂ ≤ 7.

For the queue length at arrival epochs, it is easy to see that E_λ [Y_n] is increasing and concave if λ = (1,0,0,…),

For those λ, E_λ [Y_n²] is increasing and concave if 3b₀ + b₁ ≤ 1 and E_λ [Y_n³] is increasing and concave if b_i,i ≥ 0, satisfy 7b₀ + b₁ < 1 and 19b₀ + 7b₁ + b₂ ≤ 7. E_λ [Y_n] is decreasing and convex if λ = (0,0,1 − r,(1 − r)r,(1 − r)r²,…).

The results of the monotonicity and convexity of functions associated with queue length for the GI/M/1 queue can be generalized to the GI/M/c(c ≥ 1) queue in a straightforward manner, although formulas can be much more involved.

Remark 4.4: Condition III′ in Eq. (7) does not hold for f(i) = i in the GI/M/1 queue since b₀ + b₁ ≤ 1 always holds; that is, Condition GI/M/1(III) in Eq. (20) always holds for k = 0.

4.4. A Queuing System with Batch Service

Consider a single-server processor sharing queuing system in which the the interarrival times are i.i.d. random variables, where the common distribution is A(·). Let τ_n denote the arrival epoch of the nth customer, let Q(t) be the number of customers in the system at time t, and let Y_n ≡ Q(τ_n−) denote the number of customers seen by the nth customer at its arrival epoch. We assume that if Y_n = i, the arrival of the next customer causes all customers to leave the system (so that the queue becomes empty) with probability σ_i (0 < σ_i < 1),i = 0,1,…. We call such a customer a negative customer. Thus, the queuing system becomes empty if a service is completed or a negative customer arrives. The service times are i.i.d. exponential random variables with parameter β (β > 0). Assume that service times are independent of interarrival times. Then {Y_n, n ≥ 0} is a discrete-time Markov chain. The transition probability matrix P of Y = {Y_n, n ≥ 0} is given by

where

. The Markov chain Y is aperiodic and irreducible. Conditions in Eq. (7) can be further simplified as follows:

Thus, Condition Batch(I) in Eq. (22) holds if and only if the sequence {θ_i, i ≥ 0} is increasing in i. For Condition Batch(II) in Eq. (22), it holds if λ(i + 1) ≤ λ(i)θ_i, for all i ≥ 0. By the definition of the generalized likelihood ratio order defined in Section 4.1, Condition Batch(II) in Eq. (22) holds if λ ≤_lr μ, where μ = (μ(0),μ(1),…) is a measure defined on

. The measure μ can be normalized to a probability measure by taking

. Similarly, Condition Batch(II′) in Eq. (22) holds if λ ≥_lr μ. The following measures also satisfy Condition Batch(II) in Eq. (22): λ = (1,0,0,…) and

For Condition Batch(III) in Eq. (22), it is satisfied for f(i) = i if

it is satisfied for f(i) = i² if

and it is satisfied for f(i) = i³ if

Similarly, we can get the corresponding conditions under which Condition Batch(III′) in Eq. (22) holds.

Then E_λ [Y_n] is increasing and concave if

{θ_i} is increasing in i, and Eq. (23) holds. E_λ [Y_n²] is increasing and concave if

{θ_i} is increasing in i, and Eq. (24) holds. E_λ [Y_n³] is increasing and concave if

{θ_i} is increasing in i, and Eq. (25) holds.

In the literature the Markov chain with transition matrix given by Eq. (21) was called a backward recurrent time chain (see Meyn and Tweedie [15, p.64]).