3.1. Non-Work-Conserving PMP System

Let x(t) = [x₁(t),x₂(t)]^T be the state of the system at time t, where x_i(t) is the number of customers in queue i at time t in the non-work-conserving JMCQ. {x(t)}_t≥0 evolves as an irreducible continuous-time Markov chain (CTMC) over the state space

. The transition rates for {x(t)}_t≥0 are as shown in Figure 2. Let {x_n}_n≥0, n an integer, be the jump chain (see, e.g., Asmussen [1] or Norris [16]) derived from {x(t)}_t≥0 and let {p_x:x′} be its transition probabilities.

The transition rates for {x(t)}t≥0, the CTMC for the non-work-conserving queue system. Partitions A1,…,A5 and F used in the stability analysis of Theorem 1 are also shown.

Lemma 1: If λ₁ + λ₂ > μ₁ + μ₂, then both the jump chain {x_n}_n≥0 and {x(t)}_t≥0 are transient.

Proof: Define

to be h(x) = ((μ₁ + μ₂)/(λ₁ + λ₂))^(x₁+x₂). When λ₁ + λ₂ > μ₁ + μ₂, we have h(x) bounded, h([0,0]) = 1 > h(x),x ≠ [0,0]. Also, for any state

,

can be verified. Hence, from Theorem 2 of Mertens, Samuel-Cahn, and Zamir [13], it follows that the jump chain is transient. From Theorem 3.4.1 of Norris [15], the lemma now follows. █

Theorem 1: {x(t)}_t≥0 is positive recurrent if λ₁ + λ₂ < μ₁ + μ₂.

Proof: For uniformizable CTMCs, Kingman [11] showed that Foster's criteria can be stated as follows. An irreducible CTMC is positive recurrent if and only if there exist nonnegative y_x such that

As in Kingman [11], we use a quadratic Lyapunov function y_x := x₁² + x₂². As with a typical queuing system, it can be easily verified that (1) holds when λ₁ + λ₂ < μ₁ + μ₂. The finite number of states referred to in (2) will include set F (see Fig. 2) and some more states identified below.

In region A₁ of the state space, (2) reduces to requiring −λ + 2x₂ μ₂ − μ₂ ≥ 1, which holds for all sufficiently large x₂. A similar relation is satisfied in A₂ for all but finitely many x₁. In region A₃, (2) simplifies to

Let ε₁ := μ₁ − λ₂ and ε₂ := μ₂ − λ₁. If ε_i > 0,i = 1,2, then (3) is true for all large x₁ and x₂. Suppose ε₁ > 0 and ε₂ < 0 such that ε₁ + ε₂ = μ − λ =: δ > 0. λ and μ are as defined earlier. Then, (3) reduces to

where d := λ₁ = λ₂ + μ₁ + μ₂. Since the attractor lines have positive x₁ intercepts, we have x₁ > x₂ and, hence, (4) is valid for all large x₁ and x₂. Finally, suppose ε₁ < 0 and ε₂ > 0. As in the previous case, (3) reduces to

For a given x₂, we have that x₂ ≤ x₁ ≤ x₂ + k₂, where k₂ is the intercept of the class 2 attractor line and, hence, (5) can be written as

which is true for all large x₁.

In region A₄, (2) becomes 2x₁(μ₁ − λ₁ − λ₂) + 2x₂ μ₂ − d ≥ 1. Now, let ε := μ₁ − (λ₁ + λ₂) and ε + μ₂ = (μ₁ + μ₂) − (λ₁ + λ₂) =: δ > 0. If ε ≥ 0, then (2) holds for all large x₁ and x₂. Suppose ε < 0; then, (2) reduces to

For that part of A₄ with x₂ ≥ x₁, (6) holds for large values of x₁ and x₂. If x₁ > x₂ in A₄, we have x₁ − x₂ < k₁, where k₁ is the x₁ intercept of the class 1 attractor line. In this case, (6) can be reduced to

which holds for all large values of x₁ and, hence, (2) is true in A₄ also.

In region A₅, (2) reduces to 2x₁μ₁ + 2x₂(μ₂ − λ₁ − λ₂) − d ≥ 1. If μ₂ ≥ λ₁ + λ₂, we have the desired inequality for all but finitely many states of A₅. On the other hand, if μ₂ < λ₁ + λ₂, let ε := λ₁ + λ₂ − μ₂ and μ₁ = ε + δ for some δ > 0. In this case, (2) can be written as

and (2) follows from the fact that x₁ > x₂. █

3.2. Work-Conserving Tirupati System

Recall that in the work-conserving system the capacity of an empty queue is distributed among the nonempty queues. Let

be the state of the system at time t, where

is the number of customers in queue i at time t. Under the model assumptions,

evolves as an irreducible CTMC over the state space

, also denoted by

. The transition rates for

is as shown in Figure 3.

The transition rates for , the CTMC for the evolution of the work-conserving JMCQ. Observe that the departure rates for states on the axes are μ = μ1 + μ2.

Consider a process

such that

.

satisfies the conditions for Theorem 2.4 of Bremaud [5, Chap.9] and is, hence, identical to an M/M/1 queue with arrival rate λ₁ + λ₂ and service rate μ₁ + μ₂. Thus, from the stability conditions of the M/M/1 queue, we can state the following theorem.

Theorem 2:

is

4.1. Non-Work-Conserving System

Consider the PMP system first. Define δ_x^j to be the queue that an arriving class j customer to state x will join. For example, when the system is in state x = [x₁,x₂], δ_x¹ = 1 if ψ_j(c₁,x₁) ≤ ψ_j(c₂,x₂) and δ_x¹ = 2 otherwise. The transition rate matrix Q_x = {q_x:x′} is easily determined. The previous section contains sufficient conditions for the ergodicity of this Markov chain, and in the following, we assume that they hold. Let π = {π_x} be the stationary distribution of this Markov chain. The revenue rate

and the per class rate of social cost are obtained from the Law of Large Numbers (see Serfozo [18]) as follows:

Closed-form expressions for

are difficult to obtain and we look for approximate results in the form of computable bounds. First, consider the revenue rate,

. We use the framework of van Houtum et al. [20] to obtain computable bounds by considering systems on a truncated state space.

Denote the original non-work-conserving JMCQ system defined over the state space

by

and let {x(t)}_t≥0 be the CTMC of this system. Further, let {x_n}_n≥0 be the corresponding uniformized jump chain of the

system obtained from a uniformizing Poisson process of rate d := μ₁ + μ₂ + λ₁ + λ₂ (see Bremaud [5]). Since the steady state distribution is the same both in the CTMC and its corresponding uniformized chain, we work with {x_n}_n≥0 in the rest of this section.

Let

be the indicator variable which captures the queue from which ith customer has departed and let

be the number of departures from the system up to time t. Let

be the revenue rate accrued if each customer is charged while departing from the system (instead of charging while entering the system). We claim that

almost surely. We first note that the following two limits exist almost surely:

Let {τ_n}_n≥0 ↑ ∞ be the sequence of the end of busy periods of the stable system (i.e., return times to 0). Then, for the system that starts empty,

for each n. Since

exist, we can divide the above by τ_n and take limits along this subsequence, to have

almost surely. So, (7) can be written as, almost surely,

We rewrite (9) as

where c(x) is the revenue rate in state x given by

Following [20], we now establish precedences between states of {x_n}_n≥0. These precedences are defined on the basis of the n-period revenue v_n(x), which denote the expected revenue in the first n ≥ 0 periods when starting from state x. We say that the state

has precedence over state

, if m and n satisfy the precedence relation

Denote the unit vectors [1,0] and [0,1] by e₁ and e₂, respectively. We claim that state m has precedence over its neighboring states m + e₁ and m + e₂ for all

. Also, note that the ≤ operation is transitive.

Let P be the set of all ordered pair of states (m,m + e₁) and (m,m + e₂),

. We want to prove for all n = 0,1,2,…,

We use induction over n to prove (12). Taking n = 1 in (12) leads to

We can easily verify that (13) holds. Assume that (12) holds for n and we prove it from n + 1. To establish (12) for n + 1, we have to show for each (m,n) ∈ P,

where p(m,n) denotes the corresponding transition probabilities of {x_n}_n≥0. From (13), it suffices to show that

In the non-work-conserving system, we can check (15) for all (m,n) ∈ P. A convenient method of checking is by grouping terms corresponding to the same event (such as an arrival or departure). The attractor lines of the different customer classes divide the state space into many regions, and the transition probabilities depend on the region in which the state is located. Thus, we will have to verify (15) for the various regions. We illustrate this for the region A₃ in Figure 2. Let n = m + e₁ in (15). The left-hand side of (15) is

and the right-hand side is

Therefore, proving (15) implies proving

This is true because each term in the above inequality is nonnegative from the induction hypothesis. Similarly, we can verify (15) for the remaining regions.

Now, we propose two truncated systems and prove that the revenue rates in these systems act as bounds for the revenue rate in the

system. To motivate the truncation, we argue that π_x becomes very small for states x away from the attractor lines; hence, most of the probability mass of {π_x} is concentrated between the attractor lines and close to it and a state space truncated at some distance from the attractors will provide a good approximate solution. In the following, we show that if the truncation is done such that the transition from the states on the threshold lines are suitably modified, we can obtain bounds on the performance measures defined earlier, which can be made fairly tight. Specifically, we will consider the state space of the JMCQ truncated to contain only those states for which T_l ≤ x₁ − x₂ ≤ T_r, where T_l and T_r are integers with T_l ≤ 0 and T_r ≥ ((1 − a₂)/a₂)(c₂ − c₁) > 0. T_l and T_r will be called the left and right truncation thresholds, respectively. Denote by

the state space obtained after truncation. Also, let

be the states on the left threshold line (x₁ − x₂ = T_l), except the state [0,|T_l|]. Further, let

be states on the right threshold line (x₁ − x₂ = T_r), except the state [T_r,0], and

. Figure 4 shows this truncation.

The truncated state space for the systems. The modified transitions rates for states on are shown. The transition rates for the states between the truncation lines are the same as that of system shown in Figure 2. (a) Transition rates for the system. For states in , transitions due to departures from queue 1 (2) are disallowed. (b) Transition rates for the system. For states , there is a diagonal transition with a rate μ1 (μ2).

Denote the original work-conserving JMCQ system defined over the state space

by

. We define systems

over

as follows. For system

, let Q^(u) = {q_x:x′^(u)} be its transition rate matrix obtained from Q as follows:

From the above, for

an arrival will move

toward the attractor line of its class (the attractor lines of all the classes are included in the truncated state space) and will not cause the system to go out of

. For

, a departure from queue 1 is disallowed, whereas for

a departure from queue 2 is disallowed to keep the system in

. Other transition rates are the same as that in

.

The transition rate matrix Q^(l) = {q_x:x′^(l)} for system

is obtained from Q as follows. As with

, the transition rates from states

are the same as that in

. The departures from the states on the threshold lines are modified such that a departure from one queue that might lead to a state out of

will take away one more customer from the other queue also and, hence, keep the system state in

.

Let π_x^(u) and π_x^(l) be the stationary distributions of

, respectively. For the following, we will assume that both of these systems are stable and, hence, that their stationary distributions exist. We will discuss the stability of these systems in Section 5.

Let {x_n^(u)}_n≥0 and {x_n^(l)}_n≥0 be the uniformized jump chains of the

systems obtained from a uniformizing Poisson process of rate d := μ₁ + μ₂ + λ₁ + λ₂. For these systems, we can write the revenue rate as

In our truncation model, we observe that {x_n^(u)}_n≥0 is obtained by redirecting transitions to preceding states and {x_n^(l)}_n≥0 is obtained by redirecting transitions to succeeding states. Thus, from Theorem 1 in [20], we have the following result.

Theorem 3: If systems

, start empty at t = 0, we have

Now, consider the bounds on the mean queue lengths. Choosing c(x) = x₁ in (10), we get the expression for the mean number in queue 1: x₁. Similarly, choosing c(x) = x₂ gives the expression for the mean number in queue 2: x₂. Using induction, we can again prove that m precedes m + e₁ and m + e₂. Let x_i^(u) and x_i^(l) be the mean queue lengths in queue i for the

systems, respectively. Thus, we have the following result.

Theorem 4: Let x_i, x_i^(u), and x_i^(l) exist for i = 1,2. Then,

Further, if we take c(x) = 1 for x₁ > M and zero otherwise, where

, then [sum ]_x c(x)π_x is the tail probability that the total number of customers in queue 1 exceeds M. As a result, the stationary number in queue 1 in the

system is stochastically bounded between the stationary number in queue 1 of the

systems. We have a similar result for the stationary number in queue 2 in the

system. In fact, we can show that if all systems start in the same feasible state, say (0,0), then at any jump epoch, the number in a queue of the

system is stochastically bounded by the number in the corresponding queues of the

systems.

Remark 1: We can also show that the number in each queue of

almost surely bound the number in the

system at every jump epoch. The proof technique is similar to that used to show such bounds for the work-conserving system, which we discuss next.

4.2. Work-Conserving System

We now obtain results similar to those in the previous subsection for the work-conserving system. We will use the same notation for the parameters and performance measures as in the previous subsection except that they will have a tilde to differentiate them from the corresponding variables of the non-work-conserving system. For example,

will be the queue occupancy in queue i at t_k.

We first show that for the work-conserving system, we cannot obtain the bounds for the performance measures by proceeding exactly as in the previous section and applying the method of [20]. To see this, consider bounds for the revenue rate. As in the non-work-conserving system, we can write the revenue rate for the

system as

This can be written in terms of μ as

where

represents the cost per period in state

given by

In the work-conserving system, the cost function on the axes is forced to be c_i μ, where μ = μ₁ + μ₂. For our truncation model to yield bounds for the revenue rate, the precedence relation mentioned in the previous subsection must hold here also; that is, the state

must precede the states

for all

. Suppose that the above-mentioned precedence relations hold. Let

be the set of all

. Then, for all t = 0,1,2,…,

Specifically, this must hold for t = 1. Taking t = 1 in (19) leads to

However,

contradicting (20). Thus, the assumed precedence relations are false and the proposed truncation model will not yield bounds using the techniques in [20]. We take an alternate approach to prove the bounds for the revenue rate of the

system.

4.3. Sample-Path Approach

Let

be the CTMC of the

systems, respectively. Let

be the corresponding uniformized jump chains of the

systems, respectively, obtained from a uniformizing Poisson process of rate d := μ₁ + μ₂ + λ₁ + λ₂ (see [5]). Now, consider the uniformized systems

evolving in parallel and driven by the same event sequence determined by the Poisson process. We now present a forward induction type of proof (see Walrand [22, Chap.8]) to show that system

(resp.

) componentwise dominates

(resp.

) for all n.

Let t₁ < t₂ < t₃ < ··· be the event epochs of the uniformizing Poisson process. Every jump of this Poisson process corresponds to either an arrival of class j, j = 1,2 with probability λ_j /d, or a potential service completion from queue i, with probability μ_i /d. An arrival will join the queue that minimizes its cost, possibly different queues in different systems. The work-conserving property leads to the following queue dynamics at potential service completion instants. A potential service completion time from queue i is an actual service completion from that queue if it is nonempty, and it is an actual service completion in the “other” queue if queue i is empty and the other is nonempty. Because the service and interarrival times are exponentially distributed, we just disallow departures when actual departures are not possible at potential departure times. Let

be the state of

“just after” t_n and let

be the sample path of

up to time t_N⁺. Reference [22] has more details on the development of the sample paths. Denote the evolution paths by

in the

system and by

in the

system and let

.

Theorem 5: If the system starts empty at k = 0, then for any k ≥ 0,

Proof: Assume that (a) and (b) have not failed till t_k. Both (a) and (b) cannot fail for the first time simultaneously and we consider the events that might lead to them failing separately. We will consider (a) alone first. For (a) to fail before (b) at t_k′+1, we require that

. We consider the possible events at t_k′ with this condition. If the event at t_k′ is a potential departure, the following subcases arise:

1. Potential departure from queue 1: Because

will behave identically with respect to queue 1 when

. If

, a departure from queue 1 is disallowed in

and allowed in

, and (a) is maintained.

2. Potential departure from queue 2:

is necessary to cause an actual departure from queue 1. By assumption that (b) has not failed until t_k′,

implying

.

will behave identically with respect to queue 1.

Now, consider the case when the event at t_k′+1 is an arrival. For (a) to fail, the arrival must join queue 1 in

and queue 2 in

. For this to happen,

must be on the right-hand side of the attractor line for the class of the arrival, and

must be on its left-hand side. This is clearly not possible because

and the attractor line has a positive slope.

Similar arguments show that (b) cannot fail before (a) at t_k′+1.

Now, consider (c) and (d). Once again, they cannot fail for the first time simultaneously. We proceed as above and look at events at t_k′+1 when

, which is required for (c) to fail for the first time and before (d) at t_k′+1.

As previously, first consider a potential departure at t_k′:

1. Potential departure from queue 1: Because

will behave identically with respect to queue 1 when

. If

, an actual departure takes place from both the queues in the

system and the inequality is maintained.

2. Potential departure from queue 2:

is necessary to cause an actual departure from queue 1 in

. However, by assumption that (d) had not failed until

and, hence,

.

will behave identically with respect to queue 1.

For an arrival of class j at t_k′+1, arguments identical to that from the first part are used to show that (c) does not fail at t_k′+1.

Similar arguments are constructed to show that

could not have happened at t_k′ and, hence, (d) could not have failed before (c) for the first time at t_k′+1. █

Let

be the mean queue lengths in queue i for the

systems, respectively. Also, let

be the mean waiting times in queue i of the

, and the

systems, respectively.

Theorem 6: Let

exist for i = 1,2. Then,

for i = 1,2, where λ_i is the long-run arrival rate into queue i in the

system.

Proof: From Wolff [23],

systems are regenerative and, hence, the mean queue lengths are also time averages. Hence,

Similarly we can prove the left half of (a).

From Little's law, we write (b) as

Dividing throughout by λ_i, we get (b). █

Now, we find the bounds on the revenue rate. In this case, we choose T_l = 0 and, hence, the left truncation threshold is the line

. The revenue processes in

are modified as follows. The

systems will earn revenue exactly like the

system, except for the following cases. We stipulate that when the system is in a state in

will “gain revenue” (c₂ − c₁) and

will “lose revenue” c₁ according to the rate μ₂. When the system is in a state in

, only

will “lose revenue” c₂ according to the rate μ₁. Let

be the revenue rates so earned in systems

, respectively. Then, from the Law of Large Numbers,

Observe that the expressions for

are similar to that for

in (17) except that they are defined on the corresponding

systems, respectively, and the “revenue earnings” are modified for the states on the threshold line as discussed in the previous paragraph. Let

denote the cumulative revenue in

, respectively, until time t_N.

Theorem 7: If the

systems start empty at time t = 0, then for all N ≥ 0,

Proof: Let

be the revenue “earned” in the transition at t_k+1 from

in the

system. We can write the left-hand side of Eq. (22) as

We will show that the following holds for all t_k, the epochs of the uniformizing process:

For an arrival at

. A similar expression is written for

and (24) is satisfied. Now, consider potential departures. We consider four cases corresponding to the state of the queues in

.

Case 1: Both queues are empty. Irrespective of the state of

, the first term on the right-hand side of (24) is zero, the second term is nonnegative, the left-hand side is zero, and (24) is satisfied.

Case 2: Queue 1 is empty and queue 2 is nonempty. This cannot happen because we choose T_l = 0 in our truncation of the state space.

Case 3: Queue 1 is nonempty and queue 2 is empty. For a potential departure from queue 1, queue 1 in

is also nonempty and there is an actual departure from queue 1 in both

and (24) is satisfied. For a potential departure from queue 2, the following subcases need to be considered:

1. Queue 2 in

is empty. By Theorem 5, queue 1 in

is necessarily nonempty. There will be an actual departure from queue 1 (because of work-conserving service) in both

and (24) is satisfied.

2. Queue 2 in

is nonempty. This means that there will be an actual departure from queue 1 in

and an actual departure from queue 2 in

. In this case, the left-hand side in (24) is zero and the right-hand side is c₂ − c₁ and the inequality is satisfied.

Case 4: Both queues are nonempty. In this case, both queues of

will be nonempty by Theorem 5. First, consider a potential departure from queue 1 (resp. queue 2). If

is not on the left (resp. right) truncation threshold, then in both the systems, there is an actual departure from queue 1 (resp. queue 2) and (24) is satisfied. If it is on the left (resp. right) threshold, left-hand and right-hand sides will both be −c₂ (resp. −c₁) and the inequality of (24) is satisfied.

Thus, the inequality of (24) holds, and substituting (24) in the right-hand side of (23), we get (22) if we start from an empty system. █

To obtain upper bounds on the cumulative revenue, consider the

systems together. Let

(resp.

) be the revenue earned in the transition from

(resp.

) in the

(resp.

) system at time t_k+1. For an event of the uniformizing process at time t_k, the difference in the behavior between the

systems depends on the slope of the line joining the points

(state of

at t_k) and

(state of

at t_k). To capture the dependence on this slope, let

. The slope of the line joining the points

is less than (resp. greater or equal to) one if τ_k < 0 (resp. τ_k ≥ 0).

A sequence τ₁,…,τ_N can be associated with a joint sample path in

for epochs t₁,…,t_N. Let G = (V,E) be the directed graph induced by this sequence, where the vertex set V is obtained from {τ_k} (τ_k takes values in

) and the directed edge set E = {e_k = (τ_k,τ_k+1)}. In the following, our discussion will be based on a graph so obtained from a sample path. For every e_k ∈ E, define l_k := τ_k+1 − τ_k and

. We will call l_k the length of e_k and call w_k its weight. w_k is the excess revenue earned by

over

due to the event at time t_k. Also, define S_m,n := {e_k ∈ E|τ_k = m,τ_k+1 = n}; that is, S_m,n is the set of all directed edges from

. Figure 5 shows an example of the directed graph induced by the τ_k from a sample path of the

systems.

Example sequence of τk from a sample path represented as a directed graph. For clarity in the illustration, self loops are not shown, as these do not have negative weights. The remaining edges are renumbered such that their initial order is maintained. In the example shown, m = 1 and m = 3 have edges with negative weights. Observe that the terms in (25) corresponding to these states are “canceled” as follows: [sum ]ek∈S1,−1 wk + [sum ]ek∈S−1,1 wk + [sum ]ek∈S1,0 wk = 0 and [sum ]ek∈S3,1 wk + [sum ]ek∈S2,3 wk = 0.

Now, consider the possible combination of events in

at epoch t_k. They are listed in Table 1 along with the sign of τ_k and τ_k+1 and the values of l_k and w_k. From Table 1, we see that l_k ∈ {−2,−1,0,1,2}, w_k is negative only due to events of type 2 (an arrival chooses queue 1 in

and queue 2 in

), and if w_k is negative, then τ_k > 0 and l_k = −2. Further, l_k > 0 and τ_k+1 > 0 are possible only from two events, those of type 3 and 12. A type 3 event is an arrival joining queue 2 in

and queue 1 in

. A type 12 event is a potential departure from queue 2 when

is on the right threshold and is, hence, disallowed and an actual departure from queue 2 in

. In this case, w_k = c₂ − c₁ and l_k = 1. We are now ready to state the following theorem.

Combinations of Possible Events in at Epoch tk+1 and the Corresponding τk, τk+1, lk, and wk

Theorem 8: If

start empty at time t = 0, then for all N ≥ 0,

Proof: We can write

We will use the sample-path graph G obtained as described earlier. To prove the theorem, we show that those S_m,n containing e_k for which w_k = (c₁ − c₂) < 0 are offset by edges with w_k > 0 in (25). From Table 1, these sets will be of the form S_m,m−2, with m > 0. Consider one such vertex, say m, and let there be r edges, {e_k1,e_k2,…,e_kr}, from m to m − 2 with negative weights. This means that [sum ]_{ek∈Sm,m−2} w_k ≥ r(c₁ − c₂). Without loss of generality, we can assume that k₁ < k₂ < ··· < k_r. Consider the two possibilities that arise.

Case 1: m = 1. Observe that τ₁ = 0 and τ_k1 = 1. This guarantees that there must be a right-directed edge e_k, an edge e_k with l_k > 0, with 0 < k < k₁ into vertex 1. Now, consider the edge e_kl from 1 to −1 with l > 1. Since τ_kl+1 = −1 and τ_kl+1 = 1, there must be a right-directed edge e_k into vertex 1 with k_l < k < k_l+1. The right-directed edges obtained above are due to transitions at different time epochs and, hence, are distinct. This shows the existence of at least r right-directed edges into vertex 1. There are two types of right-directed edge into vertex 1, edges due to events of types 3 and 12, each of which have w_k = c₂ − c₁. See Table 1. Thus,

Case 2: m > 1. Arguing as in Case 1, we can show that there are r right-directed edges into vertex m. The only possible right-directed edges into vertex m,m > 1, is due to an event of type 12. So, [sum ]_{ek∈Sm−1,m} w_k ≥ r(c₂ − c₁) and

See Figure 5 for an illustration of both cases.

For both of the cases, (25) can be written uniquely split into sums as in (26) and (27) and the theorem follows. █

The stationary revenue rate

defined in (17) becomes, by the Law of Large Numbers,

and from Theorems 7 and 8, we can now state the following theorem.

Theorem 9: If systems

start empty at t = 0, we have