Abstract We consider a general infinite horizon problem with stochastic data. We establish necessary and sufficient conditions under which the stochastic problem may be correctly solved using an equivalent deterministic problem. In particular, we establish conditions under which there exists an equivalent interest rate, which permits replacement of the stochastic data by their expectations. This equivalent interest rate can be approximated by a linear function of the ratio of the variance to the mean of the stochastic data. Applications to production planning are included.

DETERMINISTIC EQUIVALENCE IN STOCHASTIC INFINITE HORIZON PROBLEMS Julia L. Higle Department of Systems and Industrial Engineering The University of Arizona Tucson, Arizona 85721 James C. Bean Robert L. Smith Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 1. Introduction Stochastic infinite horizon optimization comprises an important class of dynamic sequential decision making problems, including stochastic versions of capacity expansion, equipment replacement, and production planning problems. These problems can generally be modelled as stochastic cost flow problems in which a decision maker initiates a sequence of actions which, when coupled with some underlying random occurance, gives rise to a cost flow in which either the magnitude or the timing of the costs -(or both) are not known in advance. The decision maker typically seeks to implement an action sequence with a minimum expected cost. Procedures for solving these problems generally fall into one of two classes, open loop or nonadaptive procedures, and closed loop or adaptive procedures. Nonadaptive procedures require that all decisions be made using only the distributional information that is available at the onset of the problem. Adaptive procedures allow the decision maker to use information from any realizations of

-2 - random occurances that take place prior to each decision epoch. Thus, nonadpative prodedures do not allow a decision maker to receive any information through a feedback mechanism, while adaptive procedures do. In general, the nonadaptive procedures are easier to implement, but may yield suboptimal results. Nonadaptive solutions are frequently optimal for a commonly studied class of problems which have a regenerative property, so that a single decision is implemented infinitely often (e.g. [5], [12], [13], and [14]). Problems which do not have a simplifying regenerative property often require the more difficult adaptive solution procedures. To simplify their solution, these problems are often approximated by finite horizon deterministic problems (e.g. [2], [4], and [9]). The solution to this finite horizon deterministic problem is then used as an approximate solution to the stochastic infinite horizon problem. In general, one does not know a priori the cost of the errors associated with the approximation. Alternative procedures for nonregenerating problems are treated in [1], [8], and [11]. In this paper, we develop conditions under which it is possible to replace a more general stochastic infinite horizon problem with a deterministic problem whose optimal sequence of actions is identical to that of the stochastic problem. When such a problem exists, it is said to be a deterministic equivalent problem (DEP). In particular, we develop conditions for the existence of an equivalent interest rate, which permits the replacement of stochastic data by expectations without loss of optimality. When a DEP exists, we describe a method to construct it and note that it differs from the deterministic approximation commonly used in practice.

-3 - Section 2 of this paper presents a formal statement of our general problem, including our assumptions. Section 3 includes a discussion of a deterministic equivalent problem. Section 4 introduces an equivalent interest rate. Section 5 contains an application of our results to a simple lot sizing problem with stochastic demand. Section 6 presents our summary and conclusions. 2. Problem Statement 2.1. Notation The following is a list of the notation and terms used throughout this paper. * a = (ai ), l is an infinite sequence of actions such that for all i, ai e I for some index set I. 00oo A C X I is the set of all feasible action sequences. i-=1 * is the sample space of the underlying random occurance. (fl, 0, P) is a probability space of the underlying random occurance, where L. is a a-algebra and P is a probability measure. Tr is the set of all nondecreasing right continuous functions. *: fn-Tr is a stochastic process known as the randomized time process. Thus, T maps each realization of the underlying random process, cw fl, into a nondecreasing right continuous function. To simplify notation, the dependence of the randomized time process on w will be supressed, and the time process will be written as {T (z), z >0} whenever doing so avoids ambiguity. r: fl-A is random variable, known as a strategy. In general, -r maps each realization of the underlying random process into a feasible action sequence. II is the set of all strategies. r is said to be a nonadaptive strategy if there exists an action sequence a c A such that P{ir= a }1.

-4 - I* nfII is the set of all nonadaptive strategies. * i (a) is a random variable denoting the time at which the ith action in the sequence a is implemented. * ~i(a) = T+l(a) - T,(a). * Ca: n-R is the present value of the cost of implementing the action sequence a. C: fl-+R is the composition of the functions 9r(.) and Ca, and is a random variable which represents the present value of the cost of implementing the strategy ir. 2.2. Assumptions The cost flow associated with a given action sequence, a, consists of two components: the magnitude of the costs incurred, and the times at which they are incurred. It is assumed that these components can be expressed separately in terms of a pseudo-time parameter, z. Throughout this paper, we make the following assumptions: Al. For every action sequence a, there exists a right continuous deterministic cost function, C (z), which describes the undiscounted magnitudes of the costs associated with the action sequence in terms of the pseudo-time parameter z. We assume that Ca (z) is of bounded variation for all feasible action sequences. A2. There exists a nonnegative monotonically increasing stochastic process T (z), z20}, known as the randomized time process. Its parameter, z, is called the pseudo-time parameter. It is assumed that E [T(z)] is finite for all finite z. A3. For every action sequence a, there exists a monotonically increasing deterministic sequence (z, )~ such that Tr (a) - T (zi,,).

-5 - A4. The present value of the cost of an action sequence a is given by C je- -rT ()dC (z). It is clear that the pseudo-time parameter, z, plays an important role in the problem formulation. This parameter acts as a link between the magnitude and the timing of the costs, as evidenced by assumption A4. The precise interpretation of z will be problem specific. In many cases, this pseudo-time parameter has a very natural interpretation within the context of the problem. For example, in the capacity expansion problems analyzed in [1] and [8], the authors use the cumulative demand as a pseudo-time, and formulate their problems so that assumptions A1-A4 are satisfied. In Section 5, we provide an analysis of a simple EOQ problem using the concept of a pseudo-time parameter. 2.3. Formulation Simply stated, the stochastic infinite horizon problem (P) is to find a strategy ir * to Min,,n E[C,] (P), where E [C,] = E [fcr ()dC,(z)1. 3. Deterministic Equivalent Problem We now define an equivalence between a deterministic problem and a stochastic problem, which will allow the use of deterministic problem solving techniques without loss of optimality. Definition: A deterministic problem (P) is said to be equivalent to a stochastic problem (P) if every action sequence which is optimal for (P) is also optimal for (P).

-6 - In general, the sequence of actions implemented under strategy ir is random. Thus, C,(z) is not, in general, a deterministic function and the expectation of C, may be difficult to obtain. However, if C,(z) is a deterministic function, one can invoke Fubini's Theorem and conclude that 00 E[C,] = E[e-rT(Z)]dC,(z). If ir is a nonadaptive strategy, then Ir is a deterministic action sequence and the function C,(z) is deterministic. With this observation, we can now prove conditions under which a deterministic equivalent problem exists. Lemma 1 If there exists an optimal strategy ir * IIN, then there exists a deterministic equivalent problem. Proof Suppose T(z) is a nonnegative, monotonically increasing function, 00 and r is a nonnegative number. For every a A, let CA = - -T(z)dC (z). If for every z >0, E[e-T()] = e-P(), then for every ^rElIN, C, = E[C,]. By hypothesis, there exists an optimal strategy r *EIIN. Thus, every optimal solution for the deterministic problem (P), Minn C, (P), is also an optimal solution for the stochastic problem (P). It follows that (P) is a deterministic equivalent problem (DEP) for (P). I Thus, to establish conditions under which a deterministic equivalent problem exists, it is sufficient to establish condition under which a nonadaptive strategy is optimal. The following Lemma provides sufficient conditions under which there exists an optimal strategy Ir * such that ir * II N. When this is the case, we may without loss of optimality restrict our attention to the nonadaptive strategies, and thus solve the stochastic problem by solving a deterministic problem.

-7 - Lemma 2 If {T (z), z 0} has independent increments, then there exists an optimal strategy which is nonadaptive. Proof We proceed by induction. Let Ir * be an optimal strategy for (P). Clearly, since some action must be implemented first, we can assume without loss of generality that there exists an action al such that P{lr = a } 1. Now, suppose that for every i <n, there exists ai I such that P{ri =* ai } = 1 for some n. By definition, C, = e-()dC () = A + BC, where ZIS Ir * A = e-T(z)dC (), 0 B = e-T(Zi) and C = f er[T(z)-T(znsr)IdC (Z). Z, r * By the property of independent increments, E[C,*] = E[A]+E[B]E[C] Thus, z,,r and (ir *)i 1 are the only data that are relevant when predicting the future evolution of the problem. In particular, these are the only data that are relevant when determining rn+,. But z,,,* is completely determined by (7ri*,Ji, by assumption A3, and it follows that rn l depends solely on the optimal leading subsequence, (ri,*)il.. By hypothesis, this subsequence is known, and we conclude that there exists an action an +1 e I such that Pr n +l = an,+1 } = 1. By induction, we conclude that there exists an action sequence a* A such that P{v * a* } = 1, and the result follows. *

-8 - It is not difficult to construct examples in which {T (z), z )0} does not have independent increments and a nonadaptive optimal strategy exists. These examples inevitably exploit some special structure found in the set of cost functions {C (z)}.A To obtain necessary and sufficient conditions for the existence of a nonadaptive optimal strategy that are independent of the choice of cost functions, {C. (z)}.A X we require the following lemma and corollary which are stated without proof. Lemma 3 If X and Y are dependent random variables, and if S={yy: E[eC-' I Y=y]-E[e-'x] >0},thenP{YcS}>O. Proof Omitted. U Corollary 4 If X and Y are dependent random variables and if S5 = {y:| E[c-' I Y=y]-E[c-'] >/}, then there exists c>O such that P{YeS,} > E. Proof Omitted. U Using these results, we now establish necessary and sufficient conditions under which one may, without loss of optimality, consider only nonadaptive strategies. Note that these conditions are independent of the choice of cost functions {C, (z)},,A Theorem 5 There exists for every set of cost functions, {Ca (z)} A an optimal solution which is nonadaptive if, and only if, the stochastic process {rT (a), i = 1,2,...} has independent increments for all a e A. Proof See Appendix. U By combining Lemma 1 and Theorem 5, we see that for an arbitrary set of cost functions, a deterministic equivalent problem exists whenever the stochastic

-9 - process {7i (a), i = 1,2,...} has independent increments for all a e A. Under these conditions, if r and the function T(z) are chosen so that E [e-'T(z)] = e-P(z) for all z, then the deterministic problem 00oo Min.n C, = je-'()dCr(z) (P) is equivalent to the stochastic problem Minl,n E[C,] (P). 4. Equivalent Interest Rate Because P and T (z) appear as a product, there is some degree of flexibility available when choosing these parameters for the deterministic equivalent problem. If the conditions of Theorem 5 are satisfied, then the deterministic problem in which r=r and T(z) = -lnE [I -rT (')] can be solved to obtain r an optimal solution for (P). This is precisely the DEP proposed in [8]. A more natural choice for the time function, which is independent of the interest rate, is T(z) = E [T(z)]. We now define an equivalent interest rate, which permits the replacement of stochastic times by their expectations. Definition: If there exists an interest rate r* such that E[e- T(z)] = -'*E[T(z)1 for all z, then r* is said to be an equivalent interest rate for the stochastic process { T (z), z >0}. Note that when an equivalent interest rate exists, it incorporates all of the information regarding the uncertainty in the cost flows which is relevant to the decision making process. As such, it provides the decision maker with a powerful analytic tool. For example, understanding how changes in the stochastic problem data effect the equivalent interet rate will provide the decision maker with an understanding of how these changes effect the optimal solution.

- 10 - 4.1. Conditions for the Existence of an Equivalent Interest Rate The following lemma provides necessary and sufficient conditions under which an equivalent interest rate exists. Lemma 6 Let {T (z ), z >0} be a monotonically increasing stochastic process. There exists an equivalent interest rate, r*, if, and only if, there exists functions g and h such that [e-rT()] - e-(r)h(). Proof Suppose there exist functions g and h such that E[e-rT(z)] = c-g(r)h(z). Then E[T(z)] = g'(O)h(z). If g'(0) = 0, then P{ T (z) = 0}=1 for all z, since the stochastic process increases monotonically, and the proof is trivial. Thus, we assume without loss of generality that g '(0) # 0. By hypothesis, -ln(E[e -rT()) _ g(r) E[T(z)] '(O) Thus, the equivalent interest rate exists and is given by r* = (r) Now, suppose the equivalent interest rate, r*, exists. Since r* is independent of z, by hypothesis, and E[T(z)] is independent of r, set g(r) = r*, and h(z) = E[T(z)]. The result follows. - Lemma 6 offers a characterization of stochastic processes which have an equivalent interest rate associated with them. However, it requires knowledge of the form of the Laplace transform of {T(z), z 0} before any statement regarding the existence of an equivalent interest rate can be made. A characterization which does not require knowledge of the Laplace transform would be more useful. The ability to separate the exponent of the Laplace transform of the stochastic process into functions of r and z is one characteristic of stochastic

- 11 - processes with stationary and independent increments, as the following theorem indicates. Theorem 7 If {T(u), u O} is a stochastic process with stationary and independent increments, and {T(z), z 0} is a monotonically increasing stochastic process such that T (z) = 7 (h (z)) for some nonnegative increasing function h, then there exists an equivalent interest rate for both {T (u), u )0} and {T(z), z )0}. Proof If {T(u), u )0} has stationary and independent increments, then E[e-rr(u+v)l = E[e-rr(u)]E[e-rr(P)] for all u,v O. This implies that there exists a function g (r) such that E [e-Cr(r)] - e-g(r)u for all u >0 [7]. If T(z) = (h (z)), then E[e-'rT()]=E[c-rr(h(z))] =e-g(r)h(z). By Lemma 6, an equivalent interest rate exists for both stochastic processes, and is given by *= g(r) a 9 '(0) It is important to note that under the conditions of Theorem 7, the equivalent interest rates associated with {T (u), u >0} and {T (z), z 0) are identical. Thus, knowledge of the equivalent interest rates associated with stochastic processes possessing stationary and independent increments indicates knowledge of the equivalent interest rates associated with a much larger class of stochastic processes. This is of particular interest since many practical problems can be modelled or approximated using the transformation of a stochastic process with stationary and independent increments suggested in Theorem 7. Section 5 of this paper contains an example of such a problem. The following theorem states that when E[T (z) is continuous in z, the conditions for Theorem 7 are both necessary and sufficient.

- 12 - Theorem 8 Let {T(z), z >0} be a monotonically increasing stochastic process such that E [T (z)] is continuous in z. There exists an equivalent interest rate, r*, if, and only if, there exists a stochastic process {f (u), u >0} with stationary and independent increments and a nonnegative increasing function h such that T (z) = T (h (z )). Proof Suppose E[T(z)] is continuous in z and an equivalent interest rate exists. By Lemma 6, there exist functions g and h such that E[e-rT(z)] - e-(r)^h(z). Furthermore, since E[T(z)l = g '(0)h (z), and E [T (z)] is nonnegative, increasing, and continuous, h (z) is without loss of generality, nonnegative, increasing, and continuous. Let h-1(u) = min{u:h(z)>u}. Since h is increasing and continuous, h-1 is well defined. Let T (u) = T(h-l(u)). Then Ee-r(u)] = E[e-r(h-(u))] = e-g(r)h(h-1(u)) = e-g (r)u. Thus, the stochastic process {r(u), u0)} has stationary and independent increments [7], and T (z) = 7 (h (z)). The result now follows from Theorem 7. As a result of Theorem 8, if E [T (z)] is continuous in z, the existence of an equivalent interest rate can be verified without knowing the Laplace transform of the stochastic process. 4.2. Properties of the Equivalent Interest Rate When an equivalent interest rate exists, an optimal solution to the stochastic problem (P) can be obtained by solving the deterministic equivalent problem in which T(z) = E[T(z)] and r = r*. As such, the single parameter, r*,

- 13 - contains all of the information regarding the stochastic process {T (z), z )O} which is relevant to the decision making process. It is important to understand the relationship between the original interest rate, r, and the equivalent interest rate, r*. This understanding may be gained through Jensen's Inequality, as the following theorem indicates. Theorem 9 If an equivalent interest rate exists, r* r. Proof Since c-rt is a convex function, E[e-'T ()] >. e-rE[T(z)l, by Jensen's Inequality. But [e-[T(z)] = c-t*E[T(z) by hypothesis. Thus, c-r'E[T(z)] > c-rE[T(z)] => r* < r. U We see that the stochastic nature of the time process {T (z), z >0} has the same effect on the decision making process as reducing the interest rate in a deterministic problem. Thus, one can evaluate the impact of the stochastic time process on the optimal solution in terms of this reduction in the interest rate. Such an evaluation is provided in Section 5. The following theorem provides a second order approximation of the relationship between r* and the various moments of {T (z), z )0}. Theorem 10 When it exists, r* = {1-. ar T z) ri r + o (r2) [-~~ ~2E[T (z)] Proof By Lemma 6, if r* exists, then there exist functions g and h such that E[e-rT(z)] = c-g(r)h(z) and r* = (r). By the properties of Laplace e '(0) transforms, g is an analytic function, and every derivative of g is well defined at

- 14 - all points. It follows that the Taylor series expansion of g about the point r =0 exists. Hence r* g(r) g '() ) g2(0) r2+ 0(72) i2g '(0) = V T(z)] r+ (r2) o= (i!)() +(. From Theorem 10, we see that for small values of r, r* decreases linearly as the ratio of the variance to the mean of the stochastic process {T((z),z } increases. The larger this ratio is, the larger the difference between r and r is. Similarly, the smaller this ratio is, the smaller the difference between r and r*. For larger values of r, higher order terms from the Taylor expansion can be used. This simply involves the use of higher order moments of {T (z), z >0}. 5. Applications The results developed in sections 3 and 4 can be used to efficiently solve a large class of problems which cannot be easily solved using currently available techniques. For example, consider the stochastic version of the capacity expansion problem under exponential demand in [15]. In this problem, demand is a geometric Brownian motion process and hence is nonstationary. Since this stochastic demand is a transformation of Brownian motion, a process with

- 15 - stationary and independent increments, there exists a deterministic equivalent problem and an equivalent interest rate. Thus, the deterministic turnpike results of [15] can now be used to solve the stochastic problem. This particular application is discussed in [1] and [8]. The following is a simple production planning example. While this problem can be solved by well known methods, it is presented here to emphasize the value of the insights that can be gained through the equivalent interest rate. These insights generalize to more complicated nonstationary problems. 5.1. Production Planning In this section, we consider a simple continuous review economic order quantity model in which all costs are continuously discounted using an interest rate r. We assume that there are no leadtimes, no shortages are allowed, and that the demand for product follows a stochastic process {D (t), t O}. For simplicity, we assume that the cost to place an order for Q items is given by A +pQ, where A and p are known positive constants, and that there are no physical per unit holding costs. Under these conditions, it is common to replace the stochastic demand by its expected value, and solve the resulting deterministic problem. To illustrate the qualitative characteristic of the equivalent interest rate, we consider this problem with {D(t), t0} a Poisson process with rate A, so that E[D(t)] = At. Hadley and Whitin [10] show that when a linear demand function is assumed, the 2A A classic EOQ formula Qa = gives a first order approximation to the optimal lot size in the discounted deterministic model. Since there are no leadtimes, an order would never be placed before the

- 16 - inventory on hand has been depleted. Since the demand for product is a stochastic process, it follows that the times at which orders are placed are random variables which are determined by the demand process. As such, this problem provides a very natural application of the results developed in Sections 3 and 4. Because of the stationarity of this problem, we may, without loss of optimality, restrict our attention to action sequences in which the same quantity is ordered whenever an order is placed. For every action sequence, a, let Q (a) represent the quantity ordered when a is implemented. For this problem, we can interpret the pseudo-time parameter, z, as the cumulative demand for product. To see that assumptions A1-A4 are satisfied, consider the following: i) Let Ca (z) represent the cumulative undiscounted cost of satisfying the first z units of demand when the action sequence a is used. Thus, C. (z) = [A (a), Q ](+ where [x]+ represents the smallest integer greater than or equal to z. Note that Ca (z) is right continuous, deterministic, and of bounded variation. ii) Let {T (z), z 0} be the stochastic process defined such that T(z) = inf {t:D(t)>z}. Then {T(z), z0} is nonnegative, monotonically increasing, right continuous, and E[T(z)] = [z]-, where [z ]- is the largest integer less than or equal to z +1. Note that E [T (z )]<oo for all finite z. iii) For every action sequence a, let Zi,, = (i-1)Q (a). Then (zi,a ) 1 is a monotonically increasing deterministic sequence such that T (zi, ) is

- 17 - the random time at at which the i th order is placed. iv) The present value of the cost of an action sequence a is given by i=1 00oo 00 = f,-,-'rT (z dCa (z). Because {D (t), t O} is a Poisson process, {T (z), z >0} has independent increments, and it follows that a DEP exists (Lemma 2). Moreover, A [zJ E[eT(s)] = | I-. Therefore, an equivalent interest rate exists, by Lemma 6, and is given by * -In (E [e-rT (z)) E[T(z)] = Aln(1+ -). The deterministic problem 00 M.:Q(.)>o E[C.] = Jf-'*E[T(z)JdC(z) is equivalent to the original stochastic problem. Notice that the time function E [T (z )] = zi- is equivalent to using a deterministic demand function D (t) = At. Thus, the stochastic problem is equivalent to the deterministic problem in which this linear demand is used, and costs are continuously discounted using an interest rate r*. A first order /2AA approximation of the true optimal order quantity is given by Q, = ~~~~~~~~~~~~~[10].~~~rp [10]. One can quickly compare the two quantities, Q. and Q9, since they differ

- 18 - only in the interest rate used in discounting. In particular, /2AA Qa V rp Q /2AA V r*p 7/r < 1, because r* (r. Thus, Qa Q,, and we conclude that the appropriate reaction to uncertainty in the demand process is to order somewhat larger quantities than in the absence of uncertainty. Moreover, as a result of Theorem 10, Qa 1- Var [T(z)1 QC 2E [T(z)] This suggests that even in the absence of leadtimes, a type of buffer stock is appropriate, and as the ratio of the variance to the mean increases, the buffer increases. As previously stated, a regenerative demand process is used in this example only for the clarity of presentation. To see that less restrictive demand processes may be used, suppose the demand for product, {D (t), t >} is defined so that D (t) = f (d (t)) where {d (t), t >0} is a Poisson process with rate A, and f is a nonnegative monotonically increasing function. In general, the demand process {D (t), t >0} is nonregenerative. However, T(z) = inf{t:D(t)>z} = inf{t:f (d(t))>z} = inf {t:d (t)>f -(z)}. Let T(u) = inf {t:d(t)>u} and h = f -'. Then T(z) = T(h(z)). From Theorem 7, we see that both {D(t), t 0O} and {d(t), t 0} share the same

- 19 - equivalent interest rate, namely r* = Aln(l+- ). Although a closed form solution may not exist for such a nonstationary demand process, the planning horizon results developed in [3] may be applicable to such a problem. 5.2. Problem Reformulation The application of the deterministic equivalent approach to stochastic problem solving can be extended by the artful reformulation of problems. For example, consider the traditional buy/keep equipment replacement problem in which maintenance costs increase randomly with the age of the equipment. The common formulation of this problem decides, in each period, if the equipment should be kept or replaced with a new, but otherwise identical, substitute. The optimal solution of this model requires an adaptive solution procedure since the decision in period n is a function of the maintenance costs realized. No deterministic equivalent problem exists for this model. However, we may reformulate the problem so that decisions are made solely on the basis of maintenance costs, rather than at prespecified times. That is, reformulate the problem so that replacements will be made 'when maintenance costs reach ', rather than 'in period n'. This model has a nonadaptive optimal solution and is readily addressed by the techniques developed in this paper. 6. Summary and Conclusion For a large class of stochastic infinite horizon optimization problems, optimal solutions can be found by solving an equivalent deterministic version of the problem. This equivalent problem exists whenever the solution to the stochastic problem is, without loss of generality, a nonadaptive solution. Under certain conditions, there exists an equivalent interest rate which permits the replacement

- 20 -of the stochastic data by their expectations. When the equivalent interest rate exists, the deterministic problem is completely analogous to the original stochastic problem. Thus, the solution of the equivalent deterministic problem can provide valuable insight into the effect of the stochastic data on the optimal solution. By noting how the equivalent interest rate depends on the moments or parameters of the data, one can directly analyze their impact on the optimal solution.

- 21 - APPENDIX Theorem 5 There exists for every set of cost functions, {C (z)}.A, an optimal solution which is nonadaptive if, and only if, the stochastic process {ri (a), i = 1,2,...} has independent increments for all a A. Proof If {7i(a), i = 1,2,...} has independent increments for all a A, the proof is similar to that of Lemma 2 and is therefore omitted. Suppose there exists an action sequence a0 A such that {T,(a0), i =,2,...} has dependent increments. Then there exists i <j such that T (a ~) and AT (a~) are dependent random variables [6]. Without loss of generality, we assume 1) for all k <i, ATk (a~) and AT (a~) are independent random variable, and 2) for all i<k<j, ATk(a~) and ATi(a~) are independent random variables. Let A o= {a A: the first j -1 elements of a and a agree }. Choose a e A -a 0, such that the j h element of a and a0 differ. Such a choice can be made, since Ty (a0) is a decision epoch, and hence, two or more actions must be available at that time. We now choose a set of cost functions so that only a~ and a need be considered. Let Ca,(z)=O for all z >0. Let

- 22 - o z f [0,zj (a0)) =Ca = k z [zJ (a ),zji+(a )) jk 1- 1 e[zj+l(a~),oo) E [e- E r A (a')] For a E A - {a,a1}, Ca (z ) is chosen so that Ca (Z) Ca o(z) for all z, or Ca (z ),> Ca(z) for all z, or both. Thus, only a 0 and a 1 need be considered. Finally, since a ~ A 0, and a l' A, the first j-1 elements of a~ and a1 agree. Hence, the optimal sequence of actions is predetermined until T (a ). As such, we can choose r * on the basis of the expected present value of the costs at Ti (a o). o0 Let Ca- 1 e-rT(Z)dCa(z) 1 C C- ri(a0) Then Ca, = 0, and E[-r ATi (a*) Ca = k 1- Ea J Thus, E [C,, = E [C,] = 0, and it follows that for all choices of k, Min,II^n {E[C,]} =0. Let SL = {a:E[e-' i(a")I iA(a~) =,]<E[c-' Ai(a)]}, SG = {8:E[,e-'ri(a)I,i (a) = a]>E[e- 'A(a)]j, and S5 = {:| E[,-'rT i(a)I ar (a~) = ]-E [c-'e 7,(aI] >P}.

- 23 - By Corollary 4, there exists E >0 such that P{ATi (a ) e S }>E. Thus, P{ATi (a~) e SnSL } >- or P{ATi (a~) SnSG } >- or both. 2 2 If P{ATi (a~) e SnSL } > —, choose k <0. Construct a strategy nr such that a0 if Ti (ao) c S$nSL a1 otherwise. Then E[C] = E [E [C, | Ai (a0)]] E [-e7i(as] < l kI -1+ E[e ---- i()]- e } { ( } <I\\-l+ kE J _ ](=-_ I P{i6'i (aO)e s nSL } [e- rA(T ()]a <0. If P{Ari (a~) e SnfSL} <, then P{Ai (a~) e snSG} >-. In this case, 2 2 choose k >0, and construct a strategy ir such that a if ri (a~)cSf nSG r = a otherwise. The strategies constructed in this manner are strictly better that either of the relevant nonadaptive strategies. Hence, if {T (a~), i=1,2,...} has dependent increments for some a~eA, there there exists a set of cost functions, {Ca (z)} A, for which no optimal solution which is nonadaptive exists. Hence, the result. U

- 24 - REFERENCES [1] Bean, J.C., J.L. Higle, and R.L. Smith, (1984), 'Capacity Expansion Under Stochastic Demands,' Technical Report 84-28, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI 48109. [2] Bean, J.C., C.E. Noon, and G. Salton, (1986), 'Asset Divestiture at Homart Development Company,' Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI 48109. [3] Bean, J.C., and R.L. Smith, (1984), 'Conditions for the Existence of Planning Horizons,' Mathematics of Operations Research, vol. 9, no. 3, pp. 391-401, 1984. [4] Bitran, G.R., and H.H. Yanasee, (1984), 'Deterministic Approximations to Stochastic Production Problems,' Operations Research, vol. 32, no. 5, pp. 999-1008. [5] Boland, P.J., and F. Proschan, (1983), 'Optimum Replacement of a System Subject to Shocks,' Operations Research, vol. 31, no. 4, pp. 697-704. [6] Doob, J.L., (1953), Stochastic Processes, John Wiley and Sons, New York, 1953. [7] Feller, W., (1971), An Introduction to Probability Theory and Its Applications, vol. 2, John Wiley and Sons, New York. [8] Freidenfelds, J., (1980), Capacity Expansion When Demand is a Birth-Death Random Process, Operations Research, vol. 28, no. 3, pp. 712-721. [9] Gaimon, C. (1985), 'The Acquisition of Automation Subject to Diminishing Returns,'IIE Transactions, vol. 17, no. 2, pp. 147-156. [10] Hadley, G., and T. Whitin, Analysis of Inventory Systems, Prentice-Hall, Englewood Cliffs, NJ, 1963. [11] Hopp, W.J., J.C. Bean, and R.L. Smith, (1984), 'Non-Homogeneous Markov Decision Processes,' Technical Report 84-24, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI 48109. [12] Manne, A.S., (1961), 'Capacity Expansion and Probabilistic Growth,' Econometrica, vol. 29, no. 4, pp. 632-649.

- 25 - [13] Myer, R.A., (1971), 'Equipment Replacement Under Management Science, vol. 17, no. 11, pp. 750-758. Uncertainty,' [14] Porteus, E.L., (1984), 'Undiscounted Approximation of Discounted Regenerative Models,' Research Paper No. 749, Graduate School of Business, Stanford University. [15] Smith, R.L., (1979), 'Turnpike Results for Single Location Capacity Expansion,' Management Science, vol. 25, no. 5, pp. 474-483.