ON THE ANALYSIS OF APPROXIMATION ALGORITHMS FOR CLOSED QUEUEING NETWORKS M. M. SRINIVASAN Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109, USA K. Kant Department of computer Science The Pennsylvania State University University Park, Pennsylvania University Park, Pennsylvnia 16802 Technical Report 86-34 Revised September, 1986

On the Analysis of Approximation Algorithms for Closed Queueing Networks M.M.Srinivasan Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 K. Kant Department of Computer Science The Pennsylvania State University University Park, Pennsylvania 16802 Technical Report 86-34 Revised September 1986

On the Analysis of Approximation Algorithms for Closed Queueing Networks ABSTRACT The Linearizer and the Schweitzer algorithms are well known approximation algorithms for solving product form queueing networks. For a network consisting only of fixed rate servers and delay servers and with a single class of customers, it has been shown that the system of equations defining the algorithm of Schweitzer have a unique solution, and that the resulting cycle time estimate is an upper bound. The purpose of this paper is to complement the work on analysis of these approximate algorithms. We provide simple proofs of the existence and uniqueness of a solution for both the Schweitzer algorithm and the Linearizer, in the case of a network having only fixed rate and delay servers and with a single customer class. A simpler proof of the fact that the cycle time estimate obtained by the Schweitzer algorithm is an upper bound, is also presented. Some other properties of these heuristics are also discussed.

1. Introduction: The use of closed queueing networks to model computer systems and flexible manufacturing system is widespread. A class of these networks, known as product form (PF) networks is often used in these models for reasons of tractability. Quite often, however, the computational effort required to analyze even these products form networks exactly may be either quite high, or unnecessary. This has motivated research in approximation algorithms/bounds for obtaining the performance measures. The Schweitzer algorithm [5] and the Linearizer [11] are well known heuristic algorithms which obtain approximate performance measures for such networks. The Linearizer in turn uses the Schweitzer heuristic to obtain its performance measures. We shall henceforth refer to the Schweitzer heuristic as the first order heuristic, and the Linearizer as the second order heuristic. In the ensuing discussion, we restrict our attention to PF networks consisting only of fixed rate and delay (infinite) servers, and with a single class of customers. It has been shown [2] that for such networks, the first order heuristic defines a system of equations which have a unique solution. Moreover, the resulting cycle time estimate was shown to be an upper bound on the exact cycle time. In this paper, we provide simple proofs which show the existence and uniqueness of solutions for both the first order heuristic as well as the second order heuristic. A simple proof of the fact that the cycle time estimate of the first order heuristic is an upper bound, is presented. In addition, it is shown that the estimate of the mean queue length at the bottleneck node obtained by the first order heuristic is an upper bound on the exact mean queue length at this node. Under some restrictive assumptions, lower bounds for the cycle times are obtained. 1

2. Preliminaries: For the class of networks considered here, the only input parameters required are the mean service time demands (loads) at the nodes, and the customer population, N. For computing the exact performance measures, all delay nodes can be replaced by a single delay node with a suitably chosen load. Thus, let this delay node, if present, be indexed by 0, and let there by M fixed rate nodes, indexed 1 through M. Let Lm, m = O,...,M be the loads at the nodes, and without loss of generality assume that the nodes are indexed so that LM >-*. ' L1,. Denote the exact mean residence time at node m as Wm (N), the exact mean queue length as Qm(N), and the exact cycle time as C(N). The corresponding estimates for the first order heuristic (respectively, second order heuristic) will be denoted as WFm(N),QFm(N), and CF(N) (respectively, WSm(N), QSm(N), and CS(N)). Unless otherwise specified, the index for summation is henceforth assumed to be over the range 1 through M. We also assume that M 2, N >1. The Mean Value Analysis (MVA) algorithm [4] obtains exact values of the mean residence times by iteratively solving the system of equations (2.1a) W (N) L (+Q (N-l) =l,.. M.,,,nit=~~ m-0, ~(2.1b) L^, m=0, with M Q(l)= L /, L, m=l,...,M (2.2) M,m m — n '" (2.2) n=0 Then, the cycle time is given by M C(N) = ' W (N)= L + W (N). (23) _- m o -- m/n m = 0 m The rest of this paper is organized as follows: 2

In section 3, some properties of the first order heuristic are obtained. Specifically, it is shown here that (i)a unique solution exists for the first order heuristic, (ii) the cycle time estimate obtained is an upper bound on the exact cycle time, and (iii) the mean queue length estimate for the bottleneck node is an upper bound on the exact mean queue length at this node. It is also shown how a simple relation exists between the expressions for the mean queue length estimates and the exact mean queue lengths. Finally, under some restrictive conditions, a simple lower bound on the exact cycle time is obtained. Section 4 presents some results for the second order heuristic. It is shown (i) that a unique solution exists for the second order heuristic, and (ii) that it returns a lower cycle time estimate compared to the first order heuristic. A lower bound is also presented on this cycle time estimate under some restrictive conditions. 3.0 Properties of the first order heuristic: The first order heuristic approximates the mean residence times by solving the system of equations: / N-i \ WF (N) = L 1 + QF (N) m M N l / and using Little's law [3], this gives N-I N WF (N) = L + WF (N). m mn N n CF(N) Simplifying the above expression, we have L ni WF (N) = (1 Nm -(N- )L /CF(N) (3.1) m Hence, L - 1 -(N- )L /CF(N) (3.2) nm m 3

The other desired performance measures, namely, the thoroughput and mean queue length estimates are now obtained easily using Little's rule [3]. For example, a simple application of Little's rule to equation (3.1) gives NL QF (N)= -n Ini CF(N)-(N- 1 )L Jtl 3.1 Existence and uniqueness of a solution: We can immediately observe that the solution to equation (3.2), if it exists, is unique. To see this, suppose equation (3.2) has two solutions CF1 and CF2 such that CF2<CF1. Then L CF = L + N' m 2 o I - (N- l )L ICF, nm n I2 > L + X-' - n =CF 0 -1 —N-I)L / CF which is a contradiction. Hence, equation (3.2) provides a unique solution, if it exists. Note then, that from equation (3.1), the mean residence times, WFm (') are uniquely determined. It is also clear from equations (3.1) and (3.2) that CF(N)>0. Lemma 1 now demonstrates the existence of a solution for CF(N) such that all mean residence times are non-negative. This would then complete the proof of existence and uniqueness for the performance measure estimates provided by the first order heuristic. Lemma 1: There exists a unique solution to the system of equations for the mean residence times,WFm (.), m = 1,..., M, such that WF (E )O0, m=l,...,M. mrt 4

Proof: Consider the behavior of equation (3.2) where we replace CF(N) by a parameter y. We need to find a solution to the equation y = g(y), where YL"y g(y) L + y (33) o - -(N-1)L (3.3) m m Differentiating g(y) with respect to y, we have (y-(N- i)L )L -yLI g'(y) = ~ 2 (m - (N-1)L )2 (N- 1)l,2 y n — -- )r 3_f.(3.4) m (y-(N-I)L)i.e. g'(y)<O for all y. Now, consider the function, g(y), only in the region where y7 (N-1) LM. Equation (3.4) shows that g(y) is a monotonically decreasing function of y in this region with g (y) -A as y-+(N-1)LM. (refer to Figure 3.1).. To complete the proof, we now only need to obtain a point y2>yl, such that g(y2)<y2. For this, note that as y-+os, g(y) -v Lm< <.r m=O Thus, we can choose Y2, to be arbitrarily large, to satisfy g (Y2)< Y2 Hence, there exists a unique point, yo, y1 <YO< Y2, such that yo = g(yo). Noting that yo>(N-1)LM, it is seen that every term in the summation in equation (3.3) is positive. Hence, setting CF(N) = yo in equation (3.1) givesthe desired result. 5

3.2The cycle time estimate of the first order heuristic is an upper bound: Here we present a simple proof that the cycle time estimate CF(N), provided by the first order heuristic, is an upper bound on C(N). This requires the following: Lemma 2: Consider the function (K) = \p Q (K), nl where pm, - - p, 0. Then O(N) e(N-1) ---- >0. N N-1 A proof of Lemma 2 is given in [6]. Lemma 3 The cycle time estimate provided by the first order heuristic is an upper bound on the exact cycle time. Proof: Equation (3.2) for CF(N) can be rewritten as L-2 CF(YN) =- + ' L + (N-l) - no '- m -CF(N()-(N-1 )L nl n! nl Without loss of generality, assume that L, + X I, 1. 0 -t m Hence L2 Ch('(N) = 1 + (N-1) \ n - (F(N)-(N- 1)L (5 -, (3.5) We now prove, by contradiction, that CF(N) >C(N). Suppose, otherwise, that C(N) >CF(N). Then, from equation (3.5), 6

L2 CF(N) > I + (N-) -(Nm mn From equations (2.1a) and (2.3), we have (3.6) C(N) = I + )(N-l), (3.7) where we have set 4(K) = L Q n(K). n n From equations (3.6) and (3.7), after some straightforward algebra we get, (N- I )L -(D(N- 1) CF(N) > 1 + (N- 1)) NL2 +( 'N-1) v L2 -L m m C()-(N-) mIm rr (3.8) From Lemma 2, with Lm in place of Pm, we get Qm(N) C(N)< +(N- 1) L N m N m W (N) =I + (N-1)-'L m "- C(N) nl 1+Q (N-l) =1+ (N-I)VL2 {-. - m +()(N-I) m =1+ (N-1) L2 +(N-l) 2) L2 m m Qn(N- 1) - ((N- 1)1 1 + 4(N- 1) Hence, I + (N-I) -L2 2 C(N) -(N-)L2{ Q (N- 1) - )(N- 1) L2 2 C(N)-(N-N1)-)L2 - m _ m I + ()(N-1) m nm (3.9) From equations (3.8) and (3.9), (N-L -((N-) -(N-I) CF(N) > C(N) + (N-1) - L2 C(N)- (N-1 )L mnr m and this simplifies to the inequality Q, (N-1 )- (N-I ) C(N)' 7

(N-1)C(N) W (A)/C(N)-Q (N-1)/(N- 1 ) l {C(N)- N- 1), ~-L} C(N) Hence, noting that Wm(N)/C(N) = Qm(N)/N, we have Q (N) Q (N- 1) CF'(N) - C((N) > (N- 1 )2 ' g ---- 171 - II IN N-i nI where L2 n' "' C(N) - (N-1 )I 1 It is clear that gM g l. Hence setting gm = pm in Lemma 2 gives CFI'(N) - C(N)>O. This is a contradiction to our original premise that C(N) >CF(N), and hence the result is proved. LI 3.3The mean queue length estimates: An expression for the exact mean queue length at any fixed rate node, m, in a network N can be obtained as follows: For each such fixed rate node, m, consider an alternate network N' which is identical to network N except that it has an additional fixed rate node with load Lm. Let C(m)(N) denote the cycle time for this network. Then it can be shown that [7]: NL Q (N) ( -- - CQ\RI-) L (3.10) Comparing equations (3.3) and (3.10), the similarity of the two equations is quite striking. We use equation (3.10) to prove that QFM(N) --- QM(N). This fact, expressed as Lemma 4, had been stated without proof in [2]. 8

Lemma 4: ~QF ~(N}~) ^~Q. ~3.11 QFM,(N) QM,( Proof: Since LM:-... - L1, it can be easily shown that a direct application of the results on monotonicity of throughputs in such networks [8] gives C M '(N)... > C'(N)M. (3.12) It is now shown that there exists a k — M such that C "l )(N) CF(N), k < m C< M. Suppose otherwise that CF(N) >C(M)(N). This implies that for all m, we must have NL NL Q (N) > MF-N- >N Qn CF(N)-NL CF(N)-(N-1 )L ni -n = QF(N). Noting that M MAl, Q (N) = _ QF (N) = N, =0 mn =0 we must then have QIF (N) = \F(N) L > X.N). L Q (N). o 0 0 0 This is clearly a contradiction to the result shown in Lemma 3 on the cycle time estimate being an upper bound. El As pointed out in [2], in general, the mean queue length estimate at nodes with higher loads is an overestimate while it is an underestimate at nodes with lower loads. Now, suppose that for some K, we have QM(K) -I K/2. Under this somewhat restrictive condition, Lemma 5 obtains a lower bound on C(N). It is noted, however, 9

that at large population values, the mean queue length at the bottleneck node dominates the mean queue lengths at all other nodes to a considerable extent, and that this restriction is then satisfied, at least asymptotically with N. Lemma 5: N-i C(N) CF(N-1), if QM(N-1) 2 Proof: By contradiction. Suppose otherwise, that C(N)<CF(N-1). Then from equation (3.5), setting L, + N\ L-=1 as before, we have n l m L2 CF(N-1) < l +(N-2) ( C(N) - (N- 2)L and so L'2 C(N)- CF(N- 1) > L QN1)- (N-)(-2) ' N)-(N-2 N- C() - -C(N - N-2 )L ntm nl L Q t(N-l) 1 Q(N-1) a= Q(N)Qf- C(N)- (N-2)L C()-(N)-N-2)L Q (N-1 ) mrn rl m,= L m- - C(N)Q (N-1 )-(N-2)W (N) - C(N)-(N-2)L m n m m m L (3.13) = O - m (NQ (N-I)-(N-2)Q i(N ) A(N) - - C(N)-(N- 2)L n Now, it is easy to show that QM(N) '...- QI(N). Hence a lower bound on the expression on the right hand side of (3.13) is given by setting Qm(N) = Ql(N- I), m= 1,..., M-1, and Qm(N) = Qm(N-1)+1, m= M, 10

to give 1 M-1 L C(N)-CF(N-1) > --- 2Q (N- ) (N) — C(N)- (N- 2)L M=1 m I LM ) + NQ MN-I)-(N-2) QM(N-I)+ X(N) c(N) -(N- 2 )LM ) >L (N2 -(N-2) N-AX(N)(N-2)L, 2 0, which is a contradiction to our earlier assumption, proving the result. [ 4. The second order heuristic: In this section, we derive some properties of the second order heuristic. These properties are expressed as Lemmas 6 through 9JThese Lemmas require a few preliminary results expressed below as Propositions 1 through 4. Proof of these Propositions are given in the Appendix. Proposition 1: XF(N) AF(N- 1). Proposition 2: Let AWF (N) WF (N)-WF W((N-1), =l,...,M. (4.1) m m rn '"' Then A WFM (N) ~ ~ WF (N) > O. (4.2) Proposition 3: (4.3) CF(N)- CF(N-1) < 1,,.l Proposition 4: For m>n, 11

(a) AWFI (N)F ( (b) AWF (N1) <(L ) ( m m 2M (C) Lnz QhE fit(N-1) (4.4) AQF (N) < - N _ - -L ( Qn ~(N-1)L, (N-_)2 where QF (N) QF (N- 1) AQFM(N) = { N - N — (4.5) 4.1 Existence and uniqueness of a solution for the second order heuristic: The second order heuristic obtains estimates of the mean residence times by solving the following system of equations; for m-1,..., M: N-I WS (N) = LQ I + QS (N)-(N- )AQF (N) (. m m N m (4.6) This, therefore requires solutions to the first order heuristic at population N and (N-1). Equation (4.6) can be rewritten, using Little's rule, as N-I N WS (N)= L 1 + -— WS (N) -(N-)AQF (N) tm m N,. CS(N) m from which we get L 1 -(N- 1 )AQF (N) m m WS (N) =I-(N-I)L /CS(N) (4.7) The cycle time estimate is then obtained from L (l-(N-I)AQ (N)) CS(N) = L + N (4.8) 0 - 1-(N-1)L /CS(N) m m Noting that the values of QFm(N) and QFm(N-1) exist and are unique, it is clear that the AQFm(N)s as defined by equation (7) exist and are unique. Now, Lemma 6 12

establishes existence and uniqueness for the system of equations defining the second order heuristic: Lemma 6: There exists a unique solution to the system of equations for the mean residence times, WSm('), m = 1,...,M, such that WS ( ) > 0, m = 1,..,M Proof: Let K (N)= L (l-(N-1)AQF (N)), m-I,...,M. (4.9) ni M M Note that from proposition (4), Km(N)- 0, for all m. Then we can rewrite equation (4.8) as CS(N)K (N) CS(N) = L + n m 0 - CS(N)-(N-1)L (4.10) 1 m As before, replacing CS(N) by a parameter y, we need a solution to the equation y = g(), where Y KM(N) g(y) = L + ' m y- -(N-I)L (4.11) m m Differentiating g (y) with respect to y, we have -y(N-I)L K(N)- K K(N) g'(y) = {} m y-(yN- I)L 2 which is negative for all values of y. The remainder of the proof is now identical to that of Lemma 1. - It is next shown in Lemma 7 that the second order heuristic returns a cycle time estimate that is less than that returned by the first order heuristic. 13

Lemma 7: CS(N) < CF(N) Proof: By contradiction. Assume that CS(N) >CF(N). Then, from equations (3.2) and (4.8), 1L Lm( 1-(N-1)AQF,'(N) ) CFN -CS(N)l- = " I2 _- lI-(N- I- -(N-1)L /CS(N) - 1-(N-1)L /CS(N) mI P11 rl imr where ni (N- 1) L, a' a, AQF=(N)' m- I-(N- ICS(N) (4.12) nl It is clear from equation (4.12) that (M... ai. Further from Lemma 6, am 0 for all m. Now, the function AQFm(N) can be rewritten, after some algebra, as 1, (C(N-)+ -Ch(NK)) AQF (.) =;-. CF(N) - (N- 1 )L C)F(N- 1 )-(N-2)L ) where L /(CF(N)-(N-I ) CF(N-I )-(N-2) ), and ACF(N) = C CN) - CF(N-1). 14

Note that fM -... P1 0. Since N AQF (N)>O it is thus clear that there rn m exists a k<: M, such that AQFM(N) * ~ >AQFk(N) O. Hence k-i1 M O<a > AQF (N) = a AQF (N)+ N a AQF (N) --, — - _ -~ k m -' k mn mn m = I n = k k-i M -< _ a AQF (N) + a A QF (N) l — = I 1 = — k k-I M < ' a AQF_ (N) + ' aAQfi (N).n- =1 ol -n k m n= 1 m = k = CF(N) - CS(N). This is a contradiction to our earlier assumption, and so the proof is complete. LI To conclude this section, it is shown that under some restrictive conditions, a lower bound on the cycle time estimate provided by the second order heuristic can be given: Lemma 8: N-I CS(N)>CF(N- 1), ifQFIN-Il)>- Proof: By contradiction. Assume, otherwise, that CS(N)<CF(N-1). Then K (N)CS(N) CS(N) = L + n" 0 -- CS(N)- (N- 1)L m nt K (N) CF(N-1) > L + — ' H0 CF(N-1)- (N-I)L,.mHence, nI Hence, 15

K (N) CF (N-I) L CF(N-1) m CS(N)- CF(N- 1 ) ---, - CF(N- 1)-(N- 1)L CF(N- 1)-(N- 2)L m m mn Substituting for Km(N) using equation (4.9), the above inequality reduces to L - (N-I)AQFM (N(CF(N ) - (N- 2)L CS(N)-CF(N- 1) - L CF(N- 1) - )(4.13) m -CF(N- 1)-(N- l)L ) CF(N- 1)-(N-2)L, WF (N-1)/CF(N-1) - (N- ) AQF (N-l) CF(N-1) - (N-1)L L lN- I N = QF (N) - - QF (N-l 1) -CF(N-I1)-(N-I1)L N m N-1 m The rest of the proof is now very similar to the proof of Lemma 5. I For the general case, a looser bound is provided by Lemma 9. The proof involves some straightforward albeit tedious algebra, and is omitted. here Lemma 9: M-1 L 1 I CS(N)>CF( I --- M + - + -- (4.14) 4M M CF(N) M-l 5. Conclusions This paper has extended previous work on the analysis of approximation algorithms for closed queueing networks. Simple proofs have been provided on the existence and uniqueness of a solution for both the Schweitzer heuristic as well as the Linearizer heuristic. Simple proofs have also been obtained showing that the cycle time estimate returned by the Schweitzer heuristic is an upper bound on both the exact cycle time as well as the cycle time estimate returned by the Linearizer heuristic. It has been shown that under some restrictive conditions, the cycle time estimate provided by the Schweitzer heuristic at population N-1 serves as a lower bound for both the exact cycle time as well as the Linearizer estimate of cycle time 16

at population N. The restriction, specifically, is that the mean queue length at the bottleneck node account for at least half the network population. This condition is usually observed to be satisfied for large values of N. The similarity of the expressions for the exact mean queue length and the corresponding Schweitzer estimate was exhibited. This similarity was used to show that the Schweitzer estimate of the mean queue length at the bottleneck node is an upper bound of the exact mean queue length at this node. 17

REFERENCES 1. CHANDY, K.M., and NEUSE, D., "Linearizer: A Heuristic Algorithm for Queueing Network Models of Computer Systems," Communications of the ACM, v 25, no. 3, 1982, pp. 126-134. 2. EAGER, D.L., and SEVCIK, K.C., "An Analysis of an Approximation Algorithm for Queueing Networks," Performance Evaluation, v 4,1984, pp. 275-284. 3. LITTLE, J.D.C., "A Proof of the Queueing Formula L = XW," Operations Research, v 9, 1961, pp. 383-387. 4. REISER, M., and LAVENBERG, S.S., "Mean Value Analysis of Closed Multichain Queueing Networks," Journal of the ACM, v 27, no 2, April 1980, pp. 313-322. 5. SCHWEITZER, P., "Approximate Analysis of Multiclass Closed Networks of Queues," Proc. International Conference on Stochastic Control and Optimization, Amsterdam, 1979. 6. SRINIVASAN, M.M., "Successively Improving Bounds on Performance Measures for Single Class Product Form Queueing Networks," (to appear in IEEE Transactions on Computers) 7. SRINIVASAN, M.M., "On Extending the Scope of a Bounding Technique for Closed Queueing Networks," Technical Report 85-25, Department of Industrial and Operations Engineering, The University of Michigan, 1985. 8. SURI, R., "A Concept of Monotonicity and its Characterization for Closed Queueing Networks," Operations Research, May/June 1985, v33, no 3, pp. 606 -624.

gev) 1k I I I I I I I I I I I I I I I I I I (N- 1)LM -- Y Figure 3.1: Plot of the function g(y)

APPENDIX Proofs of Propositions 1 through 4 Proposition 1: Consider the throughout estimates xF(N) and xF(N-1), obtained by the first order heuristic at populations N and N-1. Then XF(N) > X'(N- ). (A1) Proof: First, note that for all m = 1,...,M, WF (N) L (A2),,,,,, (A2) <1. CF(N) CF(N) -(N- )L nl Using equation (3.2) at populations N and N-1, we have L L ChF(N)- C(N- 1) = " - - L 1 — -(N-1)L /CF(N) 1- (N-2)L /C(N- I ) ml ll ml Y= 2 (N- 1)CF(N-1)-(N-2)CF(N) (CF(N) -(N- 1)I )(CF(N- I)-(N-2)L ) < (N- 1) CF(N- 1) - (N- 2) CF(N), where the last inequality follows from (A2). Hence, we have (A3) (N- 1) CF(N) <N CF (N-1). Noting that xF(n) = n/CF(n), for n - 0, this gives the desired result. C Proposition 2: Let A WA.. - _I,, /., I....t., 1 (A4) LA w P l ) w r (v) — Y P UV - I, z - i,,IV. nl m nz ' Then

AWF,, (N)M > AWFI(N)-0. Proof: Applying equation (3.1) at populations N and (N-1), we can write WF (N)-WF (N-l) = 1 nm I m n -(N- 1 )L /CF(N) I -(N- 2)L /CF(N- 1) m m = L" -(N-1)L I/CF'(N)} -(N-2)L /CF(N-1) | I-(N-I )1 nCF(N) { I-(N-2 ) L II/CFRN - 1) (A5) It is clear that the denominator of equation (A5) is positive (refer the proof of Lemma 1). Also, from equation (A3) we see that the numerator of equation (A5) is positive. Thus, we get 2j =(N- )/CF(N - (N- 2)/CF(N-\ ) I - (N- 1) L I/C(N) I - (N- 2)L /CF(N- 1) (A6) > 0. It may easily be observed from equation (A6) that since LMA- *- - L1, hence AWFM(N)> A -AVF (N) O. [ Proposition 3: CF(N) - CF'(N- 1) L, Proof: The term AQFm(N) can be expressed as L I CF(N- 1) +L -CF(N) I AQF (N) = - (A7) (CF(N) - ( N-I ) CF(N- 1) -(N-2) 1I,( It is clear that AQF I(N) o0, (A8) since we have

AQF n(N) + AQF(N) = 0, and QFo(N) QF'(N-1) 1 AQF (N) = - =L 0. = N N-I o WF (N) WF(N-I) 0 o It is also clear that the numerator in equation (A7) increases monotonically with Lm. The denominator always remains positive. Hence in order for the inequality in (A8) to hold, the numerator must become non-negative for some value of m - M. E Proposition 4: Form >n, AWF (.N t(a) -- _-> IL), (A9) AWF (N) ( '1 (b) AWF (N)! L2/!,, n nz nm m M ' (A10) L QF (N-1) (c) AQF (N) < - - ' (N^-)Ll, (N- 1)2 Proof: From equations (3.1) and (4.1),.: = (L/LI AWF (N) [fCF(N)-(N-1)L I [CF(N-I)-(N-2)L 1 = (IL Np ()Np (N-l), lM f 7n II n mn '1 It where CF(N)- (N- 1)L (N- 1)(L -L ) tw (N) = 1+ m1n1 CF(N)- N- 1)L CFN)- (N - )L

Hence the inequality (A9) follows. From Propositions 2 and 3, we have AWF (N) 0, m=1,...,M, and CF(N)-CF(N-1)= AN v WF (N) L L. nz M Hence it follows that m AWFM(N) < LM So, from the inequallity (A9), AWF' (N) I, /LM ) M(N) L2 n C LM Now, WN-I WFi (N) =L + N-QF n(N), m "' N,n and N-2 WF (N-1) = Ln I +- QF (N-1) nz N~ So VN-I N-2 AWF (N) = L -N QF (N) - QF (N-1) Fm lZ N m N- 1 m QF nl(-1) =(N-1)L 1AQF (N) + L - ml m n N_ 1 Noting, from (A10), that AWFm(N) <Lm2/LM, itfollowsthat L QF (N-l) Qk' (N) < l (N-1) L (N 1)2 Af D]