text:
ABCs of the Bomber Problem and its Relatives
- Edmund Phelps
- 2 years ago
- Views:
1 ABCs of the Bomber Problem and its Relatives Richard Weber Abstract In a classic Markov decision problem of Derman, Lieberman, and Ross (1975) an investor has an initial capital x from which to make investments, the opportunities for which occur randomly over time. An investment of size y results in profit P(y), and the aim is maximize the sum of the profits obtained within a given time t. The problem is similar to a groundwater management problem of Burt (1964), the notorious bomber problem of Klinger and Brown (1968), and types of fighter problems addressed by Weber (1985), Shepp et al (1991) and Bartroff et al (2010a). In all these problems, one is allocating successive portions of a limited resource, optimally allocating y(x, t), as a function of remaining resource x and remaining time t. For their investment problem, Derman et al (1975) proved that an optimal policy has three monotonicity properties: (A) y(x, t) is nonincreasing in t, (B) y(x,t) is nondecreasing in x, and (C) x y(x,t) is nondecreasing in x. Theirs is the only problem of its type for which all three properties are known to be true. In the bomber problem the status of (B) is unresolved. For the general fighter problem the status of (A) is unresolved. We survey what is known about these exceedingly difficult problems. We show that (A) and (C) remain true in the bomber problem, but that (B) is false if we very slightly relax the assumptions of the usual model. We give other new results, counterexamples and conjectures for these problems. Keywords Bomber problem fighter problem groundwater management problem investment problem Markov decision problem 1 Stochastic sequential allocation problems 1.1 An investment problem In a classic Markov decision problem posed by Derman, Lieberman, and Ross (1975) an investor has initial capital of x dollars, from which he can make withdrawals to fund investments. The opportunities for investment occur randomly as time proceeds. An investment of size y results in profit P(y), and the aim is maximize the sum of the profits obtained within a given time t. Without more ado let us set out this problem s dynamic programming equation. With an eye to variations of this problem to come, we make some notational changes. We take the remaining number of uninvested dollars to be discrete (a nonnegative integer) and denote it by n (= 0,1,...) rather than x. The remaining time is also discrete and denoted by t = 0,1,... We suppose that an investment opportunity occurs with probability p (= 1 q), independently at each remaining time step. We replace P(y) with a(k). Let F(n,t) denote the expected total payoff from investments made over t Richard Weber Statistical Laboratory, University of Cambridge, Cambridge CB2 0WB, UK
2 2 Richard Weber further time steps, given initial capital n, and following an optimal policy. The dynamic programming equations is then F(n,t) = qf(n,t 1)+p max a(k)+f(n k,t 1), (1) k {0,1,...,n} with F(n,0) = 0. Let k(n,t) denote a k which is maximizing on the right hand side of (1). We might have chosen to write k (n,t), but it is less cluttering if we drop the star. Usually this k is unique, but if it is not then we may define k(n,t) to be the least maximizer. This is a mathematical nuisance, but it cannot affect our conclusions in any crucial way. Since time is discrete it is not hard to show that, given any positive integers N and T, and assuming that a(k) is strictly increasing, an infinitesimal perturbation of p is sufficient to create a new problem in which the maximizer is unique for all n N and t T. Derman et al proved that k(n, t) has three monotonicity properties, traditionally called (A), (B) and (C). They can be proved to hold under the assumption that a(k) is increasing and concave in k. The properties are (A) k(n, t) is nonincreasing t. (B) k(n, t) is nondecreasing in n. (C) n k(n,t) is nondecreasing in n. A reader who is new to this problem should pause for a moment to reflect how highly reasonable and intuitive are the properties (A), (B) and (C). Consider, for example, the case p = 1. Then F(n,t) = a(k1 )+ +a(k t ), max k 1,...,k t k 1+ +k t n where k i dollars are allocated to the ith investment. Assuming that a(k) is a concave function, then it is clear that we should take all the k i as nearly equal as possible, so that k 1 = n/t and so trivially (A), (B), and (C) are all true. So far, so unsurprising. What becomes surprising, is that there exist similar problems, with dynamic programming equations that are nearly the same as (1), for which the status of (A) and (B) remains a difficult open question. In the remainder of this section we describe these similar problems. In Section 2 we discuss the discrete-time bomber problem. We present some counterexamples to show that (B) does not hold for some near neighbours of the bomber problem, and we discuss some ways that one might try to prove (B). Section 3 discusses some continuous-time problems. The paper wraps up with some discussion in Section 4. In Appendices A C we place proofs of some new results (which are marked by superscripts in Table 1.) One purpose of this paper is to bring these problems to the attention of younger researchers who may not have met them before. So in Appendix A we include proofs of (A), (B), (C) for the investment problem in a streamlined style. The proofs of (A) and (B) are quite different from those given by Derman et al, and are somewhat easier because we take the resource to be composed of discrete units. The sense in which we prove (A) is much stronger. Our proof of (C) is new and establishes this property under more generous assumptions than in any previous work. 1.2 A groundwater management problem The investment problem posed by Derman et al is very similar to a problem of groundwater management that dates back to Burt (1964). Interestingly, research in these two problem areas seems never to have intersected, or has their similarity been noticed previously. In the groundwater management problem the quantity of remaining resource equates to the level of water in an aquifer. Again, let us cut to the chase with a statement of the dynamic programming equation. Since the resource that we are now allocating is water, we denote its quantity by x, a continuous variable. We include a
3 ABCs of the Bomber Problem and its Relatives 3 random variable, R t, having some given distribution. This random variable models rainfall (runoff, or replenishment). Our dynamic programing equation is now F(x,t) = qβf(x,t 1)+p max a(y) c(x,y)+βef(x y +R t,t 1), (2) y 0,x with F(x,0) = 0. We have also introduced a factor β ( (0,1) to discount future rewards, and included a cost c(x,y) for the effort of extracting water quantity of y, when the aquifer is at level x. It is usual to take p = 1, but that is not necessary, so we have left it general. Knapp and Olson (1995) were the first to formulate conjectures (B) and (C) for this problem, but they were unable to prove them. Recently, Huh and Khrisnamurthy have discovered that this is because Knapp and Olsen adopted Burt s model of c(x,y) = c(x)y. They have shown that (B) and (C) may not hold under Burt s model, but that they do hold if one supposes instead that c(x,y) = Γ(x) Γ(x y), where Γ(y) is increasing and concave in y and Γ(y +δ) Γ(y) is convex in y for all positive δ. For example, we might take Γ(y)= 1 e y, so then Γ(y+δ) Γ(y)=(1 e δ )e y. Or we could take x c(x,y) = γ(z)dz, x y where γ(z) is nonnegative, decreasing and convex. Although F(x,t) need not be concave in x, the truth of (B) follows from showing that F(x, t) + Γ(x) is concave in x. Collaborating further on this problem, (in Huh, Krishnamurthy, and Weber (2011)) we also have proved (A), (B) and (C), with arguments similar to those in Appendix A. We take x to be a reference level, which may be be negative. But if we wish to constrain the stock of remaining ammunition or groundwater to be nonnegative then we can make this happen by letting Γ(y) tend rapidly to as y decreases from 0 towards ; this ensures that under an optimal policy the quantity of remaining resource (such as ammunition) will be maintained nonnegative. 1.3 Fighter problems The profit function a(y) may be given other interpretations.let us look again at (1), but now narrate a story that a fighter aircraft is in flight for a remaining time t. During that time it will encounter enemy aircraft and try to shoot them down. An encounter with an enemy occurs with probability p at each time step. If at such an encounter k of n remaining missiles are expended, that enemy plane will be shot down with probability a(k). Now F(n,t) is the expected number of enemy that will he shot down when following an optimal policy, starting with n missiles and time t to go. Equation (1) assumes enemy aircraft are not dangerous. But perhaps they might be, in which case we might change the dynamic programming equation to F(n,t) = q t F(n,t 1)+p t max a(k)+c(k)f(n k,t 1), (3) k {0,1,...,n} where now c(k) is some nondecreasing function of k. Noticethatwehavealsoaddedthewrinklethatq t = 1 p t isnonstationary,sothattheprobability of meetingan enemy at each discrete timestep is known,but mayvary withtime.this generalization does not invalidate any known result for this, or for Derman et al s investment problem. Of course it makes more sense for t to be continuous, but that is a limit of our discrete time model and is essentially the same. In this generality, we must understand (A) correctly. Let us denote the least maximizer on the right hand side of (3) by k(n,p t 1,...,p 1 ). Then (A) is to be understood as claiming that k(n,p t 1,p t 2,...,,p 1 ) k(n,0,p t 2,...,p 1 ). This has been proved for the special cases c( ) = a( ) and c( ) = 1. It is also very plausible that k(n,p t 1,p t 2,...,p 1 ) k(n,0,p t 2,...,p 1 ). This says that it is a property of an optimal policy that as the fighter continues flying forward in time, without
4 4 Richard Weber yet meeting an enemy, the number of missiles that it should be ready to expend at the next meeting with the enemy is nondecreasing. Generalizing this intuition even further, we may define a stronger version of property (A): (A) k(n,p t 1,...,p 1 ) is nonincreasing in each of the variables p t 1,...,p 1. In Appendix A we prove that (A) holds in the special case of (3) with c( ) = 1. We do not yet know whether or not it true for the special case c( ) = a( ). One very plausible model for a(k) is that each missile fails to hit the enemy with probability θ. If the enemy is not hit then it succeeds in destroying the fighter with some probability v = 1 u. So with θ,v 0,1, a(k) = 1 θ k c(k) = a(k)+(1 a(k))u= u+(1 u)a(k) = 1 vθ k. A convenient name for the above is the Bernoulli model. Let us emphasise that the decision to fire k(n,t) units of ammunition must be made at the moment the enemy is met, and then the missiles are fired as a volley. This is in contrast to the so-called shoot-look-shoot manner, in which one can fire one missile, and then wait to see if that hits the enemy before deciding whether to fire another missile. Such problems are discussed by Sato (1997). Bartroff, Goldstein, Rinott, and Samuel-Cahn (2010a), and Bartroff and Samuel-Cahn (2011) have coined the name frail fighter for the case u = 0, c( ) = a( ), and the name invincible fighter for the case u = 1 and c( ) = 1. The Invincible Fighter Problem corresponds to the investment problem of Derman et al and so (A), (B) and (C) all hold. Bartroff et al (2010a) have reproved these facts, using different styles of proof and in a continuous time setting. A version of the Frail Fighter Problem, with t =, was first considered by Weber (1985), who was motivated to pose the problem in an attempt to find an easier bomber problem for which (B) might be proved true. However, (B) turned out to be false. E.g. for θ = 1/2, we found k(4, ) = 3, but k(5, ) = 2. An intuitive explanation for the failure of (B) is that as the stock of ammunition increases from 4 to 5, we may anticipate being able to shoot down a greater number of the enemy, but to do this we must be more conservative in use of ammunition at the first meeting with the enemy. Shepp, Simons, and Yao (1991) showed that this failure of (B) is not simply an artifact of the ammunition being discrete. They give a counterexample to (B) in which ammunition is continuous, (taking a(y) = c(y) = 1 e y ). Both (A) and (C) are true for the frail fighter. (C) is very easy to prove. As observed above, (B) is not true. Bartroff and Samuel-Cahn (2011) have reported that the same counterexample that we gave to disprove (B) for t = is also a counterexample for t > They have also proved (A). That proof is not obvious, but essentially involves showing that log(1 + F(n, t)) is supermodular in (n,t) (or to put it another way that (1 + F(n,t))/(1 + F(n 1,t)) is nondecreasing in t). The arguments are very similar to those that were used by Samuel (1970) to prove (A) for the bomber problem. However, this is rather different to the (easier) proof of (A) for the invincible fighter which involves showing supermodularity of F(n, t). In Appendix A we prove two new results. The first of these is that (A) holds for the invincible fighter. The second is that (C) holds for the general fighter under the simple conditions that a(k) is increasing and concave, and c(k) is increasing and log-concave. It is not necessary to assume the special form c(k) = u+(1 u)a(k). Open Problem for the Fighter It is not known whether (A) holds for the general fighter and the Bernoulli model with 0 < u < 1. We know that (A) holds for u = 0 and u = 1. However, as mentioned above, the proofs of (A) are quite different for these two cases and there is no obvious way to interpolate between them. If (A) is true for arbitrary u then it should be true in the very special case that p t = 1 for all t. This means that starting in state (n,t) we know that the enemy will surely be met exactly t times.
5 ABCs of the Bomber Problem and its Relatives 5 The proof for this case is not as easy as one might think! A proof is in Appendix B. We would be interested to see a simpler proof. 1.4 Bomber Problem Finally, we come to the notorious bomber problem, which was posed long ago by Klinger and Brown (1968). This is the problem that we obtain from (3) on putting a(k) = 0 and changing the boundary condition to F(n,0) = 1. This makes F(n,t) the probability of successfully defending a bomber against attacking enemy planes that it meets on the way to its target, starting in state (n, t) and using an optimal ammunition rationing policy. Klinger and Brown proved (C) and showed that the truth of (B) would imply (A). A new proof of (C) is in Appendix A. The proof of (A) (not assuming (B)) is difficult and is due to Samuel (1970). Her proof was recast in discrete time by Simons and Yao (1990), who proved (A) by showing that k(n,p t 1,...,p 1 ) is nondecreasing in p t 1. They made the conjecture that (A) holds for the bomber problem, but could not prove it. As mentioned above, we have proved (A) for the invincible fighter. Open Problem for the Bomber Despite 40 years of research, it is still not known if (B) is true for the bomber problem. So far as I know, the best we can say about (B) is that k(n+1,t) k(n,t) if either n 3 or t 3, and also that k(n,t) = 1 = k(n 1,t) = 1 for all t. These results are recorded in Appendix C. 1.5 A table of results and open problems We summarise in Table 1 the status of (A), (B) and (C) for the set of problems discussed above, all of which are defined by cases of dynamic programming equation (3). The proofs of various results marked with a yes can be established using properties of functions that are supermodular, concave, and/or totally positive. The important result of Topkis (1978) about the monotonicity of the maximizer of a supermodular functions is often useful, and this is essentially what is being done in the proof of (A) in Appendix A. It is easy to prove (C) for the bomber problem or invincible fighter. This needs just a few (though slightly different) lines of algebra in each case, and it holds under very weak conditions. Proofs for (A) and (B) are substantially more difficult. Results which we believe to be new in this paper are given a superscript. The reader should appreciate that it is of no practical value to military planners to resolve the open problems marked by? in Table 1. If (B) is not true for the bomber problem, but we were to restrict ourselves to the class of policies for which (B) holds, then we would see only a miniscule reduction in the probability of successfully surviving until time t. The operations research literature is fullof papers in whichitis provedthatan optimalpolicy(insome givenproblem)has the character of changing monotonically in some manner as some state or parameter of the problem varies, e.g. that the optimalrate at which to serve a queue is nondecreasing in the number of customers waiting. By and large, such results are both obvious and easy to prove. What makes the bomber problem so intriguing is that (B) is obvious, but it is very far from being easy to prove or disprove. Apart from the sheer intellectual challenge that it poses, one imagines that a resolution of (B) for the bomber problem might lead to interesting new theoretical ideas, and new techniques with wider applicability. 2 So what do we make of (B) for the bomber problem? The doubly discrete time bomber problem arises from (3) upon setting a = 0 and F(n,0) = 1. For this problem, in which both ammunition and time are discrete, Simons and Yao (1990) have shown that (A) and (C) hold under the assumption that c(k) = 1 vθ k. Their proofs remain valid for any c(k) that is nondecreasing and log-concave in k (i.e. such that log c(k) is concave), and with
6 6 Richard Weber Table 1 Known results and open problems for fighter and bomber problems that are doubly discrete (in both ammunition and time) as defined by dynamic programming equation (3). Question marks indicate the two exceedingly difficult open problems. Results which we believe are new in this paper have a superscript and are located within the text as follows: 1 Appendix B; 2 Appendix A.2 (the strengthened version of (A)); 3 Counterexample 1; 4 Counterexample 2; 5 Counterexamples 3 and 4; 6 Appendix A.3. Other results have superscripts amongst the set {b,d,g,s,s,y,w}, shown here and after dates of papers listed amongst the references. These are attached with some license, as the referenced paper may have addressed a model with continuous ammunition or time, or it may have proved something weaker, but one can see that the stronger result could have been proved by the same method. Superscript are omitted if something stronger exists in another row of the table. F(n,0) a(k) c(k) p t (A) (B) (C) 0 Bernoulli u+(1 u)a(k) p? no w,s,b,g yes b,g general fighter 0 concave u+(1 u)a(k) 1 yes 1 no yes general fighter 0 concave δ yes 2,d,b yes d,b,g yes d,b,g invincible fighter 0 concave a(k) yes b,g no yes frail fighter 1 0 Bernoulli p yes? yes bomber 1 0 log-concave 1 yes yes yes bomber 1 0 log-concave yes S,y,g no 3 yes S,g bomber 1 0 log-concave p yes no 3 yes bomber 1 0 concave p yes no 4 yes bomber concave 0 Bernoulli p yes no 5 yes bomber 0 concave log-concave yes 6 bomber/fighter nonstationary meeting probabilities, p t as written in (3). It is intuitive that this result implies that log-concavity of c(k) is sufficient for (A) and (C) to hold in other versions of the problem, in which either ammunition is discrete and time is continuous (as previously shown by Samuel (1970)), or in the doubly continuous version (as shown directly in Bartroff, Goldstein, Rinott, and Samuel-Cahn (2010a)). However, we say intuitive because the arguments that are needed to pass from discrete to continuous models are not trivial. Indeed, a proper discussion of this issue could probably fill an entire paper. The observation that (A) and (C) hold if c(k) is log-concave, and p t nonstationary, raises the following obvious question. Might (B) hold under assumptions just as weak as those for which (A) and (C) hold? The answer is no, as the following counterexamples demonstrate. Notice that if c(k) is an increasing and concave function of k then it is also log-concave in k. For this reason Counterexample 1 shows nothing stronger that does Counterexample 2. However, we include it because it is a much simpler example to construct. For both counterexamples we assume p t is stationary, i.e. p t = p, for some p. Counterexample 1 There exists a nondecreasing and log-concave c(k) for which (B) does not hold. Let p t = 10/11 for all t, and {c(0),c(1),c(2),c(3),c(4),...} = {0, 3 16, 1 2,1,1,...}. Note that c(i)2 c(i+1)c(i 1) for all i 1, so c( ) is log-concave. Then {k(n,4)} n=1,2,... = {1,1,1,2,2,3,2,...}, i.e. 3 = k(6,4) > k(7,4) = 2. Counterexample 1 was easily found by trial and error. However, it is not as easy to find a failure of (B) for a concave c(k). The next counterexample explains how that may be done. Counterexample 2 There exists a nondecreasing and concave c(k) for which (B) does not hold.
7 ABCs of the Bomber Problem and its Relatives 7 The construction of this counterexample is based on the idea that if ammunition is continuous then (B) can hold only if F(x,t) is log-concave in x. So let x denote a continuous quanitityof ammunition, and observe that F(x,1) = q+pc(x) F(x,2) = max q 2 +pqc(y)+qpc(x)+p 2 c(y)c(x y). y 0,x Our counterexample is constructed by cooking up a nondecreasing and concave function c( ) for which F(x,2) is not log-concave at a particular value of x. Let us do this at x = 3. We design c( ) so that (i) c( ) is nondecreasing and concave; (ii) F(x,2) is not log-concave at x = 3; (iii) y(x,2) = argmax y 0,x c(y)f(x y,1) = 1 2 (1+x) in the neighbourhood of x = 3. Condition (iii) is arbitrary, but is imposed so that we have an easy way to figure out the value of F(x,2) in the neighbourhood of x = 3, i.e. F(x,2) = qf(x,1)+pc ( ) ( x+1 2 F x 1 2,1). Note that y(3,2) = 2 and 3 y(3,2) = 1. This means that conditions equivalent to (i) (iii) can be expressed in terms of just nine variables: {c(x),c (x),c (x)}, at x = 1,2,3. (To save space, we omit writing down these conditions; it is straightforward.) By using Mathematica s FindInstance function and then doing some judicious hand-tweaking, it turns out that we can achieve (i) (iii) by taking p = 2/3, and {c(1),c(2),c(3)} = {1/4,7/16,1/2}, {c (1),c (2),c (3)} = {1/4,7/48,1/64}, {c (1),c (2),c (3)}= {0,0,0}, and making c linear in intervals. It is now convenient to rescale by a factor of 6, so that 1,2,3 become 6,12,18. By this means we arrive at { 1 c(x) = min 24 x, x, x, } 384 x,1. (4) c(x) Fig. 1 A concave c( ) for which (B) does not hold in the bomber problem, when p = 2/3, ammunition is either continuous or discrete, and time is discrete. x Clearly c(x) is a concave function of x (as it is the minimum of linear functions of x). We find, in contradiction to (B), y(32,3) = arg max c(y)f(31.4 y,2) = y 0,5.24 y(33,3) = arg max c(y)f(31.5 y,2) = y 0,5.25 Note that 32 y(32,3) = = and 33 y(33,3) = = lie in the neighbourhood of x = 3 6 = 18, where we have ensured that F(x,2) is not log-concave. This is what leads to (B) failing to be true.
8 8 Richard Weber This same example also shows that (B) fails when ammunition is discrete. It is easy to calculate that {k(n,2)} 40 n=1 = {1,2,3,4,5,6,7,8,9,9,9,9,10,10,11,11,12,12,13,13, 13,14,14,14,14,14,14,15,15,15,16,17,18,19,20,21,22,23,24,25} {k(n,3)} 40 n=1 = {1,2,3,4,5,6,6,7,7,8,8,8,8,9,9,9,9,10,11,12, 13,13,13,13,14,14,14,14,14,14,15,14,15,14,14,15,15,15,15,15}. So k(31,3) = 15 > 14 = k(32,3), in contradiction to (B). It is interesting that within the definition of c(k) in (4) the term for which the minimum is achieved in (4) is the i(k)th, where {i(k)} 20 k=1 = {1,1,1,1,1,1,1,1,2,2,2,2,2,3,{3,4},4,4,4,4,4}. So the third term within the minimum on the right hand side of (4) is active in defining c(k) only for k = 14 (and third and fourth terms are equal at k = 15). However, this is crucial, for if we alter c( ) by omitting this term then k(n,3) is monotone in n. 2.1 How might we prove (B) in the Bernoulli case? Counterexample 2 shows us that (B) is not true unless we make some strong assumption about c(k). In particular, the status of (B) for the Bernoulli case of c(k) = 1 θ k remains open. Researchers have tried many things in pursuit of a proof of (B) for this case, or of finding a counterexample. It is worth recording some dead ends, if only to save others their rediscovery. Might we vary the last missile s effectiveness? Take the Bernoulli model and suppose that the last unit of ammunition has a miss probability ψ θ,1, so that c(k) = 1 ψθ k 1 when the last missile is fired amongst a set of k. We might conjecture that k(n,t,ψ) is nonincreasing as ψ increases from θ to 1. If this is true, then (B) would follow from k(n,t) = k(n,t,θ) k(n,t,1) = k(n 1,t). No counterexample to this conjecture has been found. A somewhatsimilartrickwouldbe to changethe boundary conditionto F(0,0) = 1 and F(n,0) = 1+λ, n 1. As λ increases this would impose a constraint that a last missile be kept unused. Now letting k(n,t,λ) denote the optimalunits of ammunitionto fire we would have k(n,t,0) k(n,t, ) = k(n 1,t). But for this we have Counterexample 3, in which k(n,t,λ) increases, and then decreases, as λ increases. Counterexample 3 Suppose that p = θ = 3/5, F(0,0) = 1 and F(n,0) = 1+λ, n 1. Let k(n,t,λ) denotetheoptimalnumberofmissilestofire.then k(8,3,0.4) = 3,k(8,3,0.6) = 4andk(8,3,0.8) = 3. This even gives a counterexampleto (B) when the terminal rewards are those given by a constant λ, λ = 0.6. We find k(8,3,0.6) = 4, and k(9,3,0.6) = 3. One could vary F(n,0) in other ways. Interestingly, (B) appears to be true when F(n,0) = n, i.e. when the aim is to maximize the expected number of missiles that are delivered to the destination. Might we prove (B) by value iteratation with the dynamic programming equation? An iterative argument with the dynamic programming equation lies at the heart of the proof of almost every one of the positive results in Table 1. One might have hoped that the same approach would work for (B) if only an appropriate inductive hypothesis could be formulated. Suppose that one takes the dynamic programming equation of F(n,t) = q t + t s=1 q s 1 pmax c(k)f(n k,t s) k and tries to inductively show some property of F(n,t), from which then (B) might follow, by using iterates of the form t F j+1 (n,t) = q t + q s 1 pmax c(k)fj (n k,t s), j = 0,1,..., (5) k s=1
9 ABCs of the Bomber Problem and its Relatives 9 startingwithf 0 = 1,say.Then(5)isthedynamicprogrammingequationforaproblemofmaximizing the probability of surviving until either time t has elapsed or there have been j meetings with the enemy. Let k j (n,t) denote the maximizer on the right hand side of (5). Counterexample 4 shows that (B) does not hold in respect of k j (n,t). Counterexample 4 Consider the Bernoulli model with p t = 1/2 and c(k) = 1 (3/5) k. We find k 8 (7,18) = 2, but k 8 (8,18) = 1, so k j (n,t) is not nondecreasing in n. Note also, the somewhat surprising fact that k 7 (7,17) = 1 and k 8 (7,17) = 2, so k j (n,t) can be increasing in j. (More usually it is nonincreasing.) Might we prove that F(n, t) is log-concave in n? Almost the first thing that any researcher appreciates when he or she begins to consider the question of whether (B) does or does not hold for the bomber problem is this: that a sufficient (but not necessary) conditionfor (B) is that logf(n,t) is concave in n. This is because the condition of log-concavityis equivalent to saying that F(n,t)/F(n 1,t) is nonincreasingin n. This would imply that the inequality c(k+1)f(n k 1,t) c(k)f(n k,t) would remain true as n increases beyond the least value for which it is true, and this fact would imply (B). However, F(n, t) is not log-concave (at least not in the discrete-time discrete-ammunition bomber problem). A failure of log-concavity means that for some n and t, (n,t) := F(n+1,t) F(n,t) F(n,t) F(n 1,t) > 0. Weber (1985) gave the example (p,θ) = (0.64,0.65) with (14,3) > 0. Simons and Yao (1990) gavethe example(p,θ) = (0.58,0.6), (8,3) = For (p,θ) = (0.7015, )we can obtain an even greater value of (8,3) = This is the largest positive value of (n,t) that I have found for any choice of the parameters (n,t,p,θ). Lest one think that a failure of log-concavity arises only when t or n is small, or when p is large, let us note that there are examples of non-log-concavity even in the following cases. For (p,θ) = (0.1, ), (8,3) = (a number that really is positive, since we can also express it as an exact fraction). One can also find (n,t) > 0 for arbitrarily large t, by taking n large, and p and θ both tending to 1. It can even happen that log-concavity fails infinitely often. For (p,θ) = (0.99,0.99), we find (n,3) > 0 for all n = 16,22,28,34,40,..., i.e. for an infinite number of n. The valuesof k(n,t), n 9 and t 3, are the samein manyof the examplesmentionedabove.but these examples are also very sensitive to the parameters. A slight change in p or θ makes (8,3) 0. Figure 2 shows a plot of F(8,3) (8,3) for all values of p and θ in the interval 0,1. Log-concavity fails when this quantity is negative, which occurs, within a small trench where p is a bit less than θ. We have not found any non-log-concavity for p approaching 0 while θ is bounded away from 0. This is the appropriate approximation of a continuous-time model, for which no instances of nonlog-concavity have been found. Of course (B) is has never been found to be false in the discrete-time setting, despite very numerous calculations and intelligently-directed searches for a counterexample. In concluding this section, we remark that in Table 1 we have not considered the possibility that the functions a(k) and c(k) might depend on time. Indeed, (C) remains true under such a relaxation in assumptions. However, because of a failure of log-concavity(b) is definitely not true in the bomber problem if c(k) is allowed to depend on time. It can be proved that F(n,t) is log-concave for t = 1,2 (see Appendix C). In the doubly-continuous problem bomber problem, (B) can only be true if logp(x,t) is concave in x (see Weber (1985) and Simons and Yao (1990)). 3 Continuous-time bomber and fighter problems It is also interesting to look at versions of these problem in which either one or both of remaining time or remaining ammunition is taken to be a continuous variable. By making a variable continuous
10 10 Richard Weber 1 1 p θ 0 Fig. 2 F(8,3) 2 F(7,3)F(9,3) as a function of p and θ. The region of non-log-concavity, where this quantity is negative, lies in the central trench, where p is a bit less than θ. a proof of (A) or (B) should be easier (since, as we have remarked above, intutitively a result for a discrete variable implies the same result in its continuous analogue). For example, making time continuous, the bomber problem has a defining equation, for n 1, of t F(n,t) = e t + 0 max k {1,...,n} c(k)f(n k,s) e (t s) ds. (6) with F(0,t) = e t and F(n,0) = 1. It is attractive to rewrite this, by defining G(n,t) = e t F(n,t). Then we have the apparently very simple recursion, for n 1, t G(n,t) = 1+ 0 max k {1,...,n} c(k)g(n k,s) ds. (7) with G(0,t) = G(n,0) = 1. No example has been found in which F(n,t) is not log-concave in n. However, proving it from (6) or (7) seems difficult, since the behaviour of a measure of log-concavity is not at all well-behaved. We see this in Figures 3 and 4. We can show that (B) is true in any problem in which we are contrained (or it is optimal) never to fire more than 2 missiles. An example is when c(k) = 1 θ min(2,k). Note first that k(n,t) k(n k(n,t),t). If this were not true, then by (A), we would have k(n,t) < j(s) := k(n k(n,t),s), for all s t, and so c(k(n,t))g(n k(n,t),t) = c(k(n,t)) 1+ t c(j)g(n k(n,t) j(s),s)ds 0 The right hand side can be made greater simply by increasing k(n,t) by 1 and decreasing j(s) by 1. From this fact we can deduce (B), because k(n,t) = 1 implies k(n k(n,t),t) = k(n 1,t) 1. Suppose that we take c(1) = 1/2, c(k) = 1, k 2. This is a concave (but not Bernoulli) choice of c( ). The above argument establishes that (B) is true, but it turns out that F(n,t) is not log-concave. Thus log-concavity is not necessary for (B). Similarly, suppose c(k) = 1 (7/8) min(3,k). It is clear.
11 ABCs of the Bomber Problem and its Relatives Fig. 3 F (n, t)/f (n 1, t) F (n+1, t)/f (n, t), for the continuous-time bomber problem with θ = 1/2, for 0 t 20 and n = 2,..., 8 (reading left to right across the asymptotes). Although we see that F (n, t) is log-concave in n, the fact that these functions are not monotone increasing, in either n or t, means that it is probably difficult to prove that F (n, t) is log-concave in n by some sort of induction on n, or using differential equations in t Fig. 4 This is a plot of (n, t) = F (n, t)/f (n 1, t) F (n + 1, t)/f (n, t), for the discrete-time bomber problem, with (p, θ) = (1/10, 1/2), for 1 t 2400 and n = 60,..., 99 (reading left to right across the asymptotes). Notice that the behavior differs depending on whether n is even or odd. One continues to see essentially the same sort of thing when making p even smaller, approaching even more closely the continuous time model. In this example (n, t) becomes very close to zero around t = 2000 but never actually goes negative. that an optimal policy need never fire more than 3 missiles. For this model it turns out that F (n, t) is not log-concave, but calculations indicate that (B) is true. One can also imagine making the quantity of ammunition a continuous variable, as indeed is appropriate in the groundwater management problem. As remarked above, if (B) is true with continuous ammunition then F (x, t) must be log-concave in x. A spend-it-all region for the bomber problem in the case of continuous ammunition and continuous time is addressed by Bartroff, Goldstein, and Samuel-Cahn (2010b), and Bartroff (2011). In Appendix C we describe the spend-it-all region in the doubly discrete setting. So far as I know, there is no problem for which a re-framing in continuous variables changes the known truth status of any of (A), (B) or (C).
12 12 Richard Weber 4 Where next? Over the course of the past 40 years the increasing power of computers and computational software has provided a motivation for returning to the bomber problem in the hope of making new discoveries. To some extent that has paid off, since we have now discovered the fact that (B) relies crucially on the Bernoulli model for c(k). In this paper we have focused upon the doubly-discrete bomber problem, in which both remaining ammunition and time are nonnegative integers. It makes sense to look at this setting of the problem because if (B) is true in this setting then it is also true if either time or ammunition is taken to be continuous, and if (B) is false it may be easiest to find a counterexample in this setting. Arguments can still be made for (B) being true or false. In favourof (B) beingtrue is thefact thatdespite a truelyenormousamountof computationalexperimentationno counterexample has been found when the model is c(k) = 1 θ k. Such computation has not been conducted simply by trying random parameter values, but has been intelligently-focused in areas of the parameter space (θ,p) 0,1 0,1 where P(n,t) fails most dramatically to be logconcave in n, as indeed must be the case if (B) is false. Today s computing power means that one can compute k(n,t) for values of n and t numbering in thousands, and that for smaller n,t we can even optimize carefully by varying θ and p. None of this exploration has produced a counterexample to (B). Notice that Counterxamples 3, 4, 5 have been found for quite small values of n and t. There has been no need to take these particuarly large. In favour of (B) being false is the fact that (B) is false for some very near-neighbours of the bomber problem, such as problems that are obtained by varying c(k) away from the Bernoulli model, or by modestly changing the boundary condition of F(n,0) = 1. If one thinks that (B) is intuitively true, why does this intuition fail for those near-neighbours for which (B) is false? Recall that (B) does not hold in the frail fighter problem. In Section 1.3 we gave an intuitive argument why this should be so. But this begs the opposite question: why does not the same intuitive argument convince us that (B) is false for the invincible fighter, for which (B) is provably true? Here are some research tasks that readers might like to pursue. (i) Construct a nice proof that in the case c(k) = 1 θ k, P(n,2) = q 2 +qpc(n)+pmax k qc(k)+pc(k)c(n k) is a log-concave function of n. I can prove this result, but not in a manner that is sufficiently attractive to reproduce here. This result implies that k(n, 3) is nondecreasing in n. (ii) Let c(k) = 1 θ k. Pick some particular value for θ, say θ = 1/2. Show that despite the fact that P(n,3) is not necessarily log-concave n, we do have (B), i.e. that k(n,4) is nondecreasing in n. (iii) For t = 3,4, showthatthere exists p t such that P(n,t)is log-concavein n for all p p t. Evaluate the extent to which p 4 must be taken smaller than p 3. (iv) Examine more carefully Counterexample 2. Explore the boundaries of this counterexample. How small is it possible to make p? Can one find P(n,t) failing to be log-concave, when c(k) is an arbitrary concave function and we set the problem in continuous time? (v) We know (B) is true for the special model c(k) = 1 θ min(2,k). What if c(k) = 1 θ min(3,k)? Acknowledgements I thank Sheldon Ross for introducing me to the bomber problem (in ). I am grateful to Tim Huh and Chandra Krishnamurty for alerting me to the similar strand of work on groundwater management problems. This paper was assembled while preparing a talk for the Third International Workshop on Sequential Methods (Stanford, June 14 16, 2011). At this workshop I very much enjoyed meeting others who have also been fascinated by, and contributed to, the study of ABCs of the bomber problem and its relatives: Jay Bartroff, Larry Goldstein (who organised our session), Ester Samuel-Cahn, Larry Shepp and Yi-Ching Yao. Their comments on drafts of this paper have been helpful.
13 ABCs of the Bomber Problem and its Relatives 13 References Bartroff J (2011) A proof of the bomber problem s spend-it-all conjecture. Sequential Analysis 30:52 57 Bartroff J, Samuel-Cahn E (2011) b The fighter problem: optimal allocation of a discrete commodity. Adv Appl Probab 43: Bartroff J, Goldstein L, Rinott R, Samuel-Cahn E (2010a) g On optimal allocation of a continuous resource using an iterative approach and total positivity. Adv Appl Probab 42(3): Bartroff J, Goldstein L, Samuel-Cahn E (2010b) The spend-it-all region and small time results for the continuous bomber problem. Sequential Analysis 29: Burt OR (1964) Optimal resource use over time with an application to ground water. Manage Sci 11(1):80 93 Derman C, Lieberman GJ, Ross SM (1975) d A stochastic sequential allocation model. Oper Res 23(6): Huh WT, Krishnamurthy CK, Weber RR (2011) Concavity and monotonicity properties in a groundwater management model, to appear in Naval Res. Logist. Klinger A, Brown TA (1968) Allocating unreliable units to random demands. In: Karreman H (ed) Stochastic Optimization and Control, Wiley, pp Knapp KC, Olson LJ (1995) The economics of conjunctive groundwater management with stochastic surface supplies. Journal of Environmental Economics and Management 28(3): Marshall AW, Olkin I (1979) Inequalities: Theory of Majorization and Its Applications. Academic Press, New York Samuel E (1970) S On some problems in operations research. J Appl Probab 7: Sato M (1997) A stochastic sequential allocation problem where the resources can be replenished. J Oper Res Soc Japan 40(2): Shepp LA, Simons G, Yao YC (1991) s On a problem of ammunition rationing. Adv Appl Prob 23: Simons G, Yao YC (1990) y Some results on the bomber problem. Adv Appl Prob 22: Topkis DM (1978) Minimizing a submodular function on a lattice. Oper Res 26(2): Weber RR (1985) w A problem of ammunition rationing. In: Radermacher FJ, Ritter G, Ross SM (eds) Conference report: Stochastic Dynamic Optimization and Applications in Scheduling and Related Fields, held at University of Passau, Facultät für Mathematik und Informatik, p 148 A Proofs of (A), (B) and (C) for Derman, Lieberman, and Ross s investment problem We sketch (for discrete time and discrete resource) proofs of (A), (B) and (C) for the investment problem of Derman, Lieberman, and Ross (1975) and also, where it is simple to do so, some stronger results. The ordering below is pedagogical, rather than alphabetical. Throughout we assume that a(k) and c(k) are nondecreasing in k and, respectively, concave and log-concave. A.1 Proof of (B) This is for the problem dynamic programming equation of the investment problem/invincible fighter. It is the special case of (3) in which we take c( ) = 1. As we shortly explain below, (B) is true if F(n,t) can be shown to be concave in n. That is, for all n,t, F(n+2,t) 2F(n+1,t)+F(n,t) 0. (8) Suppose that (8) is true. Recall that k(n,t) is the least k for which a(k)+f(n k,t 1) is maximal. Suppose that k 1 = k(n,t) and k 2 = k(n + 1,t), and that in contradiction to (B) we have k 2 < k 1. By interchanging the usages of k 1 and k 2, so that k 2 is used in states (n,t) and k 1 is used in state (n+1,t), the sum of profits increases by p t times ( ) ( ) F(n+1 k 1,t 1)+F(n k 2,t 1) F(n+1 k 2,t 1)+F(n k 1,t 1). This is nonnegative by (8). So the profit obtained when starting from at least one of (n,t) and (n + 1,t) has not decreased. By definition of k(n, t) the profit starting from (n, t) must have strictly decreased. So the profit starting from (n + 1,t) must have strictly increased, which contradicts k 2 = k(n + 1,t). We must therefore conclude that we cannot have k 2 < k 1. We now prove (8) by induction on t. This is clearly true when t = 0 since then F = 0. Suppose that k 0 = k(n,t) and k 2 = k(n+2,t). Property (C) can be proved independently of (B) (see below). So we may use (C) to observe
14 14 Richard Weber that k 2 k Then for all j 1 {0,...,n+1}, F(n+2,t) 2F(n+1,t)+F(n,t) q tf(n+2,t 1) 2F(n+1,t 1)+F(n,t 1) (9) +p t a(k 2 ) 2a(j 1 )+a(k 0 ) (10) +F(n+2 k 2,t 1) 2F(n+1 j 1,t 1)+F(n k 0,t 1). (11) An application of the inductive hypothesis shows that (9) is nonpositive. Ifk 2 = k 0 +2then wecan putj 1 = k 0 +1,sothat(11) vanishes,andin(10)we have a(k 0 +2) 2a(k 0 +1)+a(k 0 ) 0. If k 2 k 0 +1 then in each of the middle terms in (10) and (11) that involve j 1 and have a coefficient of 2 we can once put j 1 = k 0 and once put j 1 = k 2. This causes (10) to vanish and (11) is nonpositive by the inductive hypothesis (since n+2 k 2 n+1 k 0 ). This style of proof also works to prove (B) for the groundwater management problem of (2), if we modify (8) to the statement that F(x,t)+Γ(x) concave in x. A.2 Proof of (A) This is for the same setup as (B) above. As remarked above, we can prove a very strong form of (A), denoted (A). This result is not difficult, but does go beyond what has been shown by Derman, Lieberman, and Ross (1975) or Bartroff and Samuel-Cahn (2011) (who were concerned only with a continuous time model). Let F(n,p t 1,...,p 1 ) denote the same thing as F(n,t), but let us now explicitly show the dependence on the probabilities p t 1,...,p 1. Similarly, let k(n,p t 1,...,p 1 ) denote the maximizer on the right hand side of (3). We show a strong form of (A), namely that (A) k(n,p t 1,...,p 1 ) is nonincreasing in each of p t 1,...,p 1. (12) Just as (B) is proved using (8) (concavity), so (A) is proved by simultaneously showing that F(n+1,p t 1,...,p 1 ) F(n,p t 1,...,p 1 ) is nondecreasing in each of p t 1,...,p 1. (13) This is also the statement that F(n,t) is supermodular in (n,p j ) for each j = 1,...,t 1. The proof is by induction on t. Note that (12) (13) are both trivially true for t = 2. We begin by showing an inductive step for (12). Suppose that (p t 1,...,p 1 ) (p t 1,...,p 1 ), componentwise. Let optimal decisions be denoted k = k(n,p t 1,...,p 1 ) and k = k(n,p t 1,...,p 1 ). Suppose that in contradiction to (12) we have k > k. Just as with the proof of (B) we consider an interchange of the usages of k and k. The sum of payoffs would increase by F(n k,p t 2,...,p 1 )+F(n k,p t 2,...,p 1) F(n k,p t 2,...,p 1 ) F(n k,p t 2,...,p 1) which is nonnegative assuming (13) holds with t replaced by t 1. But use of k in state (n,p t 1,...,p 1 ) must cause a strict decrease, since k is supposedly the least maximizer. This means that use of k in state (n,p t 1,...,p 1 ) must cause a strict increase, which is impossible by definition of k. The proof is completed by showing an inductive step for (13). It is easy to see that the interval 0,1 can be divided into subintervals such that as p j varies within such a subinterval the optimal policy does not change. Where such subintervals join, there is some change of policy, but at that point the value of the objective function is the same under either policy. So we may consider what happens as p j varies within such a subinterval. Let us begin by taking a derivative with respect to p j, where j {1,...,t 2}. Take k 1 = k(n,t) and k 2 = k(n+1,t). Then d F(n+1,p t 1,...,p 1 ) F(n,p t 1,...,p 1 ) dp j d = q t 1 F(n+1,p t 2,...,p 1 ) F(n,p t 2,...,p 1 ) dp j +p t 1 d dp j a(k 2 )+F(n+1 k 2,p t 2,...,p 1 ) a(k 1 ) F(n k 1,p t 2,...,p 1 ) We may deduce that the right hand side is nonnegative by appealing to an inductive hypothesis that (13) is true for a smaller time horizon, and the fact that (C) implies n+1 k 2 n k 1..
15 ABCs of the Bomber Problem and its Relatives 15 Now, let us consider taking the derivative with respect to p t 1. d F(n+1,p t 1,...,p 1 ) F(n,p t 1,...,p 1 ) dp t 1 = a(k 2 )+F(n+1 k 2,p t 2,...,p 1 ) a(k 1 ) F(n k 1,p t 2,...,p 1 ) F(n+1,p t 2,...,p 1 ) F(n,p t 2,...,p 1 ) { } max a(k 1 +1) a(k 1 ),F(n+1 k 1,p t 2,...,p 1 ) F(n k 1,p t 2,...,p 1 ) (14) F(n+1,p t 2,...,p 1 ) F(n,p t 2,...,p 1 ). (15) Consider the term in (15). We now evaluate this, conditional the event that the next meeting with the enemy occurs at time s ( t 1), (after which there subsequently remain at most s 1 further meetings). Letting j 2 = k(n + 1,p s 1,...,p 1 ) and j 1 = k(n,p s 1,...,p 1 ) and assuming this conditioning (which for convenience we do not try to show in any notation), we may write (15) as F(n+1,p t 2,...,p 1 ) F(n,p t 2,...,p 1 ) = a(j 2 ) F(n+1 j 2,p s 1,...,p 1 )+a(j 1 )+F(n j 1,p s 1,...,p 1 ). Now by the inductive hypothesis for (12), j 1 k 1, and j 2 k 2. Also, by (B) and (C), we have j 1 +1 j 2 j 1. In the case j 2 = j 1 +1, we deduce that (14) (15) sum to at least a(k 1 +1) a(k 1 ) a(j 1 +1) a(j 1 ). This is nonnegative by concavity of a( ) and j 1 k 1. In the case j 2 = j 1, we deduce that (14) (15) sum to at least F(n+1 k 1,p t 2,...,p 1 ) F(n k 1,p t 2,...,p 1 ) F(n+1 j 1,p s 1,...,p 1 ) F(n j 1,p s 1,...,p 1 ) F(n+1 j 1,p t 2,...,p 1 ) F(n j 1,p t 2,...,p 1 ) F(n+1 j 1,p s 1,...,p 1 ) F(n j 1,p s 1,...,p 1 ) 0, where since j 1 k 1 the first inequality follows from concavity of F(n, ) in n, and the second inequality follows from the inductive hypothesis for (12) (i.e. by putting p t 1 = = p s = 0). A.3 Proof of (C) The following proof is new. It is for all our models: both fighter and bomber problems. It is for the general model (3) when a(k) is nondecreasing and concave in k, and c(k) is nondecreasing and log-concave in k. These are more generous assumptions than those made by Bartroff and Samuel-Cahn (2011), where they give a proof of (C) for the general fighter but which only works for the particular form c(k) = u+(1 u)a(k). Suppose that k 2 = k(n+1,t), k 1 = k(n,t), but in contradiction to (C), the resources that then remain satisfy n k 1 > (n + 1) k 2. This implies k 2 > k 2 1 k > k 1. The payoffs from these states, given that an investment opportunity or a meeting with the enemy occurs, are from the right hand side of (3) P n+1 = a(k 2 )+c(k 2 )F(n+1 k 2,t 1) P n = a(k 1 )+c(k 1 )F(n k 1,t 1). To prove (C) we think about what happens if we increase k 1 to k 2 1 and decrease k 2 to k The profits are now, P n+1 = a(k 1 +1)+c(k 1 +1)F(n k 1,t 1) P n = a(k 2 1)+c(k 2 1)F(n+1 k 2,t 1) Neither of these provides an improvement only if P n+1 P n+1 and Pn P n. This begs the question of whether it is possible to satisfy these two inequalities. In the special case of c = 1 it is easy to see that this is impossible because P n+1 +P n > P n+1 +P n. In the special case of c = a it is easy to see that this is impossible because P n+1 P n > P n+1 P n.
16 16 Richard Weber So it is easy to prove (C) for the invincible or frail fighter. It is more difficult to see what happens for more general choices of a and c. Let x = F(n+1 k 2,t 1) and y = F(n k 1,t 1). Now By concavity of a( ), (16) implies that we must have P n+1 P n+1 a(k 2 )+c(k 2 )x a(k 1 +1)+c(k 1 +1)y (16) P n P n a(k 1 )+c(k 1 )y a(k 2 1)+c(k 2 1)x. (17) a(k 2 1)+a(k 1 +1) a(k 1 )+c(k 2 )x a(k 1 +1)+c(k 1 +1)y. So putting d = a(k 2 1) a(k 1 ) 0 we have that (16) (17) imply d+c(k 2 )x c(k 1 +1)y 0 (18) d+c(k 1 )y c(k 2 1)x 0. (19) Using log-concavity of c, so that c(k 1 ) c(k 2 1)c(k 1+1)/c(k 2 ), we find that (19) requires c(k 2 )d +c(k 2 1) c(k 1 +1)y c(k 2 )x 0. The term in square brackets must be nonnegative, and so since c(k 2 ) c(k 2 1), this implies that we must have d+c(k 1 +1)y c(k 2 )x 0. (20) The inequalities above become strict if the functions a and c are not constant functions. When inequalities are strict (20) is in contradiction to (18). Therefore we may conclude that at least one of the changes k 1 k 2 1 and k 2 k 1 +1 makes a strict improvement, and that so the posited counterexample to (C) cannot occur. B Proof of (A) for a special case of general fighter Consider the a special case of the fighter problem defined by (3), but with p t = 1. So the dynamic programming equation is F(n,t) = max a(k)+c(k)f(n k,t 1), k {1,...,n} with F(n,0) = 0. In other words, we wish to maximize a(k 1 )+c(k 1 )a(k 2 )+c(k 1 )c(k 2 )a(k 3 )+ +c(k 1 )c(k 2 ) c(k t 1 )a(k t), subject to k 1 + +k t = n. Here k i is the units of ammunition to be used at the ith meeting with the enemy. For the optimal values of these variables we might write ki, but for convenience we omit the stars in what follows. Our aim is to show (A), namely that for any fixed n, the optimal k 1 is a nonincreasing function of t. In the case that 0 < u < 1 and c(k) = u+(1 u)a(k), we can write a(k) = (c(k) u)/(1 u), substitute, and write our objective function as u 1 u +c(k 1)+c(k 1 )c(k 2 )+ +c(k 1 ) c(k t 1 )+ 1 1 u c(k 1) c(k t). But this is of no obvious assistance in showing that k 1 should be nondecreasing in t. Let us remark that it is trivial to establish (B) for the bomber problem when p = 1 and c(k) is log-concave (the objective being to maximize c(k 1 ) c(k t)). We should take k 1 = n/t (or k 1 = n/t ), which is trivially nondecreasing in n. Can we prove that (A) holds for the general fighter problem when p = 1 and a(k) is concave, and c(k) = u + (1 u)a(k)? It is only for the invincible fighter (u = 1) that (A) is obvious, since then the objective is a(k 1 )+ +a(k t) and we should take k 1 = n/t. For the general fighter there is no optimal solution that we can simply write down, such as k 1 = n/t. We must argue in a more cunning way. In cases of the invincible and frail fighters, the proof of (A) is via showing supermodularity (also sometimes called increasing differences ), in (n, t), of either F(n,t) or logf(n,t), respectively. The following proof is of a non-traditional form, because it does not involve this sort of inductive proof of some property of the optimal value function. Let us consider the problem of maximizing a(k 1 )+c(k 1 )a(k 2 )+c(k 1 )c(k 2 )a(k 3 )+ +c(k 1 )c(k 2 ) c(k t 1 )a(k t)x, subject to k 1 + +k t = n, where X is a nonnegative quantity that we allow to vary. Denote the maximized value as F X (n,t).
17 ABCs of the Bomber Problem and its Relatives 17 We will show that k 1 is a nonincreasing function of t by showing that k 1 is a nonincreasing function of X. We then apply this result as X increases from 0 to 1, i.e. as we increase the number of enemy encounters from t 1 to t. First, notice that it is easy to show that k 1 k 2 k t (by a simple interchange argument). Imagine increasing X continuously from 0. The optimal k i will change at various points. Consider any value of X, say X = x, at which it becomes optimal to change some of the k i values. Call the new values, k 1,...,k t (these being optimal at X = x and at values of X just greater than x). Suppose that k 1 > k 1 (in contradiction to (A)). Then by property (C) (which one can show for this problem in the usual way) we must have k 1 > k 1 k 1 +k 2 k 1 +k 2 k 1 +k 2 +k 3 k 1 +k 2 +k 3. k 1 +k 2 + +k t = k 1 +k 2 + +k t.. Now F X (n,t) is a convex function of X (being the maximum of linear functions of X). So as the k i change to k i we must see that the coefficient of X is nondecreasing. This coefficient is c(k 1 )c(k 2 ) c(k t 1 )a(k t) = c(k 1 )c(k 2 ) c(k t 1 )c(k t) a(kt) c(k t). Notice that k t kt. Taking the canonical specification of a(k) being concave and c(k) = u + (1 u)a(k), it is easy to check that a(k t )/c(k t ) a(kt)/c(kt). However, the product c(k 1)c(k 2 ) c(k t 1 )c(k t) also decreases as we change k i to k i. This follows from the Karamata Majorization Inequality, which says as follows. Karamata Majorization Inequality Suppose x and y are vectors with x 1 x t and y 1 y t and x majorizes y (written x y), in the sense that j i=1 x i j i=1 y i for all j = 1,...,t 1, and t i=1 x i = t i=1 y i. Suppose f is a concave function. Then t t f(x i ) f(y i ). See Marshall and Olkin (1979) for a proof. i=1 We apply this inequality with f(k) = logc(k) (which is a strictly concave function of m), to deduce that if k 1 > k 1 then m m (as argued above) and hence and we conclude i=1 c(k 1) c(k t) < c(k 1 ) c(k t) c(k 1) c(k t 1)a(k t) < c(k 1 ) c(k t 1 )a(k t). This is inconsistent with the fact that F X (n,t) is convex in X. We must therefore conclude that k 1 is nonincreasing in X. The above proof seems rather a heavy-handed for a result that is so obvious. I would be interested if a reader could prove this result in a simpler way. C Small results about (B) in the bomber problem Consider the discrete-time discrete-ammunition bomber problem. It is as good to spend all units of the remaining resource as it is to spend all but 1 unit if where F(0,t) and F(1,t) are solutions to c(n)f(0,t 1) c(n 1)F(1,t 1), (21) F(0,t) = qf(0,t 1)+pc(0)F(0,t 1), F(1,t) = qf(1,t 1)+pc(1)F(0,t 1), with F(0,0) = F(1,0) = 1. Upon solving these recurrences, we find that (21) is equivalent to c(n) c(n 1) 1 ( ) ( ) q t 1 c(1) c(1) c(0). (22) c(0) q +pc(0)
18 18 Richard Weber In the limit c(0) 0 this becomes c(n) 1+(p/q)(t 1)c(1). (23) c(n 1) Notice that if (22) (or (23)) is satisfied, then it remains satisfied if either n or t decreases. Thus, we may deduce the following lemma directly from the dynamic programming equation. Lemma 1 If (22) holds then k(n,t) = n, and F(n,t) = q t + c(n) ( (q +pc(0)) t q t). c(0) In the case c(0) = 0, similarly (23) implies k(n,t) = n and F(n,t) = q t +tpq t 1 c(n). By taking p = T/t, n = xn and c(n) = 1 ue n/n, then letting both N and t tend to infinity one can recover some of the same results that have been obtained by Bartroff (2011) for the case of both continuous ammunition and time. Lemma 2 (i) k(n+1,t) k(n,t) for all n and t = 1,2,3. (ii) If c(k) is concave in k then F(n,1) = 1 p+pc(n) is concave in n. (iii) If c(k) = 1 θ k, then, with q i = 1 p i, then F(n,2) = q 1 q 2 + max k {1,...,n} { q1 p 2 c(n)+p 1 q 2 c(k)+p 1 p 2 c(k)c(n k) } is log-concave in n. Statement (i) follows from (ii) and (iii). It is only (iii) that is difficult to prove. I know only a rather long and tedious proof, making use of Mathematica to assist with the algebra, and which requires one to assume the special form of c(k) = 1 θ k. I omit a proof from this paper and leave it as a challenge to some interested reader to prove (iii) in a better way. Counterexample 2 tells us that (iii) is not true if c( ) is simply assumed to be concave. Lemma 3 k(n,t) = 1 = k(n 1,t) = 1. Proof This follows from a fact that we have already mentioned in Section 3. This is that k(n k(n,t),t 1) k(n,t). To see this, notice that if k(n k(n,t),t 1) > k(n,t) then by (A) we must have k(n k(n,t),s) > k(n,t) for all s t 1. One can check that a better policy is obtained by increasing k(n,t) by 1 and decreasing every k(n k(n,t),s) by 1. A corollary of Lemma 3 is the following. Theorem 1 If we are constrained to firing only 1 or 2 units of ammunition at each meeting with the enemy then (B) is true. By using Lemmas 2 and 3 one can fairly easily establish the fact that (B) is true when either t or n is small. Theorem 2 If n 3 or t 3 then k(n+1,t) k(n,t).
Stochastic Inventory Control
Chapter 3 Stochastic Inventory Control 1 In this chapter, we consider in much greater details certain dynamic inventory control problems of the type already encountered in section 1.3. In addition to theMore information
arxiv:1112.0829v1 [math.pr] 5 Dec 2011
How Not to Win a Million Dollars: A Counterexample to a Conjecture of L. Breiman Thomas P. Hayes arxiv:1112.0829v1 [math.pr] 5 Dec 2011 Abstract Consider a gambling game in which we are allowed to repeatedlyMore information
WHAT ARE MATHEMATICAL PROOFS AND WHY THEY ARE IMPORTANT? introduction Many students seem to have trouble with the notion of a mathematical proof. People that come to a course like Math 216, who certainlyMore information
3. Mathematical Induction
3. MATHEMATICAL INDUCTION 83 3. Mathematical Induction 3.1. First Principle of Mathematical Induction. Let P (n) be a predicate with domain of discourse (over) the natural numbers N = {0, 1,,...}. If (1)More information
Adaptive Online Gradient Descent
Adaptive Online Gradient Descent Peter L Bartlett Division of Computer Science Department of Statistics UC Berkeley Berkeley, CA 94709 bartlett@csberkeleyedu Elad Hazan IBM Almaden Research Center 650More information
Large induced subgraphs with all degrees odd
Large induced subgraphs with all degrees odd A.D. Scott Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, England Abstract: We prove that every connected graph of orderMore information
x if x 0, x if x < 0.
Chapter 3 Sequences In this chapter, we discuss sequences. We say what it means for a sequence to converge, and define the limit of a convergent sequence. We begin with some preliminary results about theMore information
Partitioning edge-coloured complete graphs into monochromatic cycles and paths
arxiv:1205.5492v1 [math.co] 24 May 2012 Partitioning edge-coloured complete graphs into monochromatic cycles and paths Alexey Pokrovskiy Departement of Mathematics, London School of Economics and PoliticalMore information
ON INDUCED SUBGRAPHS WITH ALL DEGREES ODD. 1. Introduction
ON INDUCED SUBGRAPHS WITH ALL DEGREES ODD A.D. SCOTT Abstract. Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We proveMore information
An example of a computable
An example of a computable absolutely normal number Verónica Becher Santiago Figueira Abstract The first example of an absolutely normal number was given by Sierpinski in 96, twenty years before the conceptMore information
2. Methods of Proof Types of Proofs. Suppose we wish to prove an implication p q. Here are some strategies we have available to try.
2. METHODS OF PROOF 69 2. Methods of Proof 2.1. Types of Proofs. Suppose we wish to prove an implication p q. Here are some strategies we have available to try. Trivial Proof: If we know q is true thenMore information
CHAPTER II THE LIMIT OF A SEQUENCE OF NUMBERS DEFINITION OF THE NUMBER e.
CHAPTER II THE LIMIT OF A SEQUENCE OF NUMBERS DEFINITION OF THE NUMBER e. This chapter contains the beginnings of the most important, and probably the most subtle, notion in mathematical analysis, i.e.,More information
BX in ( u, v) basis in two ways. On the one hand, AN = u+
1. Let f(x) = 1 x +1. Find f (6) () (the value of the sixth derivative of the function f(x) at zero). Answer: 7. We expand the given function into a Taylor series at the point x = : f(x) = 1 x + x 4 xMore information
Using Generalized Forecasts for Online Currency Conversion
Using Generalized Forecasts for Online Currency Conversion Kazuo Iwama and Kouki Yonezawa School of Informatics Kyoto University Kyoto 606-8501, Japan {iwama,email@example.com Abstract. El-YanivMore information
Some Polynomial Theorems. John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 firstname.lastname@example.com.
Some Polynomial Theorems by John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 firstname.lastname@example.com This paper contains a collection of 31 theorems, lemmas,More information
Probability Generating Functions
page 39 Chapter 3 Probability Generating Functions 3 Preamble: Generating Functions Generating functions are widely used in mathematics, and play an important role in probability theory Consider a sequenceMore information
The Exponential Distribution
21 The Exponential Distribution From Discrete-Time to Continuous-Time: In Chapter 6 of the text we will be considering Markov processes in continuous time. In a sense, we already have a very good understandingMore information
31 Kragujevac J. Math. 25 (2003) 31 49. SHARP BOUNDS FOR THE SUM OF THE SQUARES OF THE DEGREES OF A GRAPH Kinkar Ch. Das Department of Mathematics, Indian Institute of Technology, Kharagpur 721302, W.B.,More information
LECTURE 15: AMERICAN OPTIONS 1. Introduction All of the options that we have considered thus far have been of the European variety: exercise is permitted only at the termination of the contract. TheseMore information
MOP 2007 Black Group Integer Polynomials Yufei Zhao. Integer Polynomials. June 29, 2007 Yufei Zhao email@example.com
Integer Polynomials June 9, 007 Yufei Zhao email@example.com We will use Z[x] to denote the ring of polynomials with integer coefficients. We begin by summarizing some of the common approaches used in dealingMore information
CHAPTER 3 Numbers and Numeral Systems
CHAPTER 3 Numbers and Numeral Systems Numbers play an important role in almost all areas of mathematics, not least in calculus. Virtually all calculus books contain a thorough description of the natural,More information
PUTNAM TRAINING POLYNOMIALS. Exercises 1. Find a polynomial with integral coefficients whose zeros include 2 + 5.
PUTNAM TRAINING POLYNOMIALS (Last updated: November 17, 2015) Remark. This is a list of exercises on polynomials. Miguel A. Lerma Exercises 1. Find a polynomial with integral coefficients whose zeros includeMore information
The Relation between Two Present Value Formulae
James Ciecka, Gary Skoog, and Gerald Martin. 009. The Relation between Two Present Value Formulae. Journal of Legal Economics 15(): pp. 61-74. The Relation between Two Present Value Formulae James E. Ciecka,More information
Notes on Factoring. MA 206 Kurt Bryan
The General Approach Notes on Factoring MA 26 Kurt Bryan Suppose I hand you n, a 2 digit integer and tell you that n is composite, with smallest prime factor around 5 digits. Finding a nontrivial factorMore information
A Comparison of the Optimal Costs of Two Canonical Inventory Systems
A Comparison of the Optimal Costs of Two Canonical Inventory Systems Ganesh Janakiraman 1, Sridhar Seshadri 2, J. George Shanthikumar 3 First Version: December 2005 First Revision: July 2006 Subject Classification:More information
1 Introduction. Linear Programming. Questions. A general optimization problem is of the form: choose x to. max f(x) subject to x S. where.
Introduction Linear Programming Neil Laws TT 00 A general optimization problem is of the form: choose x to maximise f(x) subject to x S where x = (x,..., x n ) T, f : R n R is the objective function, SMore information
3(vi) B. Answer: False. 3(vii) B. Answer: True
Mathematics 0N1 Solutions 1 1. Write the following sets in list form. 1(i) The set of letters in the word banana. {a, b, n}. 1(ii) {x : x 2 + 3x 10 = 0}. 3(iv) C A. True 3(v) B = {e, e, f, c}. True 3(vi)More information
Chapter 21: The Discounted Utility Model
Chapter 21: The Discounted Utility Model 21.1: Introduction This is an important chapter in that it introduces, and explores the implications of, an empirically relevant utility function representing intertemporalMore information
U.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009. Notes on Algebra
U.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009 Notes on Algebra These notes contain as little theory as possible, and most results are stated without proof. Any introductoryMore information
Notes from Week 1: Algorithms for sequential prediction
CS 683 Learning, Games, and Electronic Markets Spring 2007 Notes from Week 1: Algorithms for sequential prediction Instructor: Robert Kleinberg 22-26 Jan 2007 1 Introduction In this course we will be lookingMore information
Solutions for Practice problems on proofs
Solutions for Practice problems on proofs Definition: (even) An integer n Z is even if and only if n = 2m for some number m Z. Definition: (odd) An integer n Z is odd if and only if n = 2m + 1 for someMore information
Sensitivity Analysis 3.1 AN EXAMPLE FOR ANALYSIS
Sensitivity Analysis 3 We have already been introduced to sensitivity analysis in Chapter via the geometry of a simple example. We saw that the values of the decision variables and those of the slack andMore information
Induction. Margaret M. Fleck. 10 October These notes cover mathematical induction and recursive definition
Induction Margaret M. Fleck 10 October 011 These notes cover mathematical induction and recursive definition 1 Introduction to induction At the start of the term, we saw the following formula for computingMore information
Optimal shift scheduling with a global service level constraint
Optimal shift scheduling with a global service level constraint Ger Koole & Erik van der Sluis Vrije Universiteit Division of Mathematics and Computer Science De Boelelaan 1081a, 1081 HV Amsterdam TheMore information
MATH10212 Linear Algebra. Systems of Linear Equations. Definition. An n-dimensional vector is a row or a column of n numbers (or letters): a 1.
MATH10212 Linear Algebra Textbook: D. Poole, Linear Algebra: A Modern Introduction. Thompson, 2006. ISBN 0-534-40596-7. Systems of Linear Equations Definition. An n-dimensional vector is a row or a columnMore information
Chapter 7. BANDIT PROBLEMS.
Chapter 7. BANDIT PROBLEMS. Bandit problems are problems in the area of sequential selection of experiments, and they are related to stopping rule problems through the theorem of Gittins and Jones (974).More information
Graphs without proper subgraphs of minimum degree 3 and short cycles
Graphs without proper subgraphs of minimum degree 3 and short cycles Lothar Narins, Alexey Pokrovskiy, Tibor Szabó Department of Mathematics, Freie Universität, Berlin, Germany. August 22, 2014 AbstractMore information
4: SINGLE-PERIOD MARKET MODELS Ben Goldys and Marek Rutkowski School of Mathematics and Statistics University of Sydney Semester 2, 2015 B. Goldys and M. Rutkowski (USydney) Slides 4: Single-Period MarketMore information
Pricing of Limit Orders in the Electronic Security Trading System Xetra
Pricing of Limit Orders in the Electronic Security Trading System Xetra Li Xihao Bielefeld Graduate School of Economics and Management Bielefeld University, P.O. Box 100 131 D-33501 Bielefeld, GermanyMore information
All trees contain a large induced subgraph having all degrees 1 (mod k)
All trees contain a large induced subgraph having all degrees 1 (mod k) David M. Berman, A.J. Radcliffe, A.D. Scott, Hong Wang, and Larry Wargo *Department of Mathematics University of New Orleans NewMore information
This chapter is all about cardinality of sets. At first this looks like a
CHAPTER Cardinality of Sets This chapter is all about cardinality of sets At first this looks like a very simple concept To find the cardinality of a set, just count its elements If A = { a, b, c, d },More information
Mechanisms for Fair Attribution
Mechanisms for Fair Attribution Eric Balkanski Yaron Singer Abstract We propose a new framework for optimization under fairness constraints. The problems we consider model procurement where the goal isMore information
9.2 Summation Notation
9. Summation Notation 66 9. Summation Notation In the previous section, we introduced sequences and now we shall present notation and theorems concerning the sum of terms of a sequence. We begin with aMore information
Wald s Identity. by Jeffery Hein. Dartmouth College, Math 100
Wald s Identity by Jeffery Hein Dartmouth College, Math 100 1. Introduction Given random variables X 1, X 2, X 3,... with common finite mean and a stopping rule τ which may depend upon the given sequence,More information
2.3 Convex Constrained Optimization Problems
42 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION Theorem 15 Let f : R n R and h : R R. Consider g(x) = h(f(x)) for all x R n. The function g is convex if either of the following two conditionsMore information
Information Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay
Information Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay Lecture - 17 Shannon-Fano-Elias Coding and Introduction to Arithmetic CodingMore information
Computational Finance Options
1 Options 1 1 Options Computational Finance Options An option gives the holder of the option the right, but not the obligation to do something. Conversely, if you sell an option, you may be obliged toMore information
SUBGROUPS OF CYCLIC GROUPS. 1. Introduction In a group G, we denote the (cyclic) group of powers of some g G by
SUBGROUPS OF CYCLIC GROUPS KEITH CONRAD 1. Introduction In a group G, we denote the (cyclic) group of powers of some g G by g = {g k : k Z}. If G = g, then G itself is cyclic, with g as a generator. ExamplesMore information
THE FUNDAMENTAL THEOREM OF ARBITRAGE PRICING 1. Introduction The Black-Scholes theory, which is the main subject of this course and its sequel, is based on the Efficient Market Hypothesis, that arbitragesMore information
Moral Hazard. Itay Goldstein. Wharton School, University of Pennsylvania
Moral Hazard Itay Goldstein Wharton School, University of Pennsylvania 1 Principal-Agent Problem Basic problem in corporate finance: separation of ownership and control: o The owners of the firm are typicallyMore information
3.3. Solving Polynomial Equations. Introduction. Prerequisites. Learning Outcomes
Solving Polynomial Equations 3.3 Introduction Linear and quadratic equations, dealt within Sections 3.1 and 3.2, are members of a class of equations, called polynomial equations. These have the generalMore information
Probability in the Engineering and Informational Sciences, 22, 2008, 107 131. Printed in the U.S.A. DOI: 10.1017/S0269964808000077 OPTIMAL CONTROL OF FLEXILE SERVERS IN TWO TANDEM QUEUES WITH OPERATINGMore information
OPRE 6201 : 2. Simplex Method
OPRE 6201 : 2. Simplex Method 1 The Graphical Method: An Example Consider the following linear program: Max 4x 1 +3x 2 Subject to: 2x 1 +3x 2 6 (1) 3x 1 +2x 2 3 (2) 2x 2 5 (3) 2x 1 +x 2 4 (4) x 1, x 2More information
Cycles in a Graph Whose Lengths Differ by One or Two
Cycles in a Graph Whose Lengths Differ by One or Two J. A. Bondy 1 and A. Vince 2 1 LABORATOIRE DE MATHÉMATIQUES DISCRÉTES UNIVERSITÉ CLAUDE-BERNARD LYON 1 69622 VILLEURBANNE, FRANCE 2 DEPARTMENT OF MATHEMATICSMore information
The Heat Equation. Lectures INF2320 p. 1/88
The Heat Equation Lectures INF232 p. 1/88 Lectures INF232 p. 2/88 The Heat Equation We study the heat equation: u t = u xx for x (,1), t >, (1) u(,t) = u(1,t) = for t >, (2) u(x,) = f(x) for x (,1), (3)More information
Stocks paying discrete dividends: modelling and option pricing
Stocks paying discrete dividends: modelling and option pricing Ralf Korn 1 and L. C. G. Rogers 2 Abstract In the Black-Scholes model, any dividends on stocks are paid continuously, but in reality dividendsMore information
a 11 x 1 + a 12 x 2 + + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + + a 2n x n = b 2.
Chapter 1 LINEAR EQUATIONS 1.1 Introduction to linear equations A linear equation in n unknowns x 1, x,, x n is an equation of the form a 1 x 1 + a x + + a n x n = b, where a 1, a,..., a n, b are givenMore information
Gambling Systems and Multiplication-Invariant Measures
Gambling Systems and Multiplication-Invariant Measures by Jeffrey S. Rosenthal* and Peter O. Schwartz** (May 28, 997.. Introduction. This short paper describes a surprising connection between two previouslyMore information
Elementary Number Theory and Methods of Proof. CSE 215, Foundations of Computer Science Stony Brook University http://www.cs.stonybrook.
Elementary Number Theory and Methods of Proof CSE 215, Foundations of Computer Science Stony Brook University http://www.cs.stonybrook.edu/~cse215 1 Number theory Properties: 2 Properties of integers (wholeMore information
CPC/CPA Hybrid Bidding in a Second Price Auction
CPC/CPA Hybrid Bidding in a Second Price Auction Benjamin Edelman Hoan Soo Lee Working Paper 09-074 Copyright 2008 by Benjamin Edelman and Hoan Soo Lee Working papers are in draft form. This working paperMore information
Discrete Mathematics Lecture 3 Elementary Number Theory and Methods of Proof. Harper Langston New York University
Discrete Mathematics Lecture 3 Elementary Number Theory and Methods of Proof Harper Langston New York University Proof and Counterexample Discovery and proof Even and odd numbers number n from Z is calledMore information
24. The Branch and Bound Method
24. The Branch and Bound Method It has serious practical consequences if it is known that a combinatorial problem is NP-complete. Then one can conclude according to the present state of science that noMore information
Surface bundles over S 1, the Thurston norm, and the Whitehead link
Surface bundles over S 1, the Thurston norm, and the Whitehead link Michael Landry August 16, 2014 The Thurston norm is a powerful tool for studying the ways a 3-manifold can fiber over the circle. InMore information
1. (First passage/hitting times/gambler s ruin problem:) Suppose that X has a discrete state space and let i be a fixed state. Let
Copyright c 2009 by Karl Sigman 1 Stopping Times 1.1 Stopping Times: Definition Given a stochastic process X = {X n : n 0}, a random time τ is a discrete random variable on the same probability space asMore information
Scheduling a sequence of tasks with general completion costs
Scheduling a sequence of tasks with general completion costs Francis Sourd CNRS-LIP6 4, place Jussieu 75252 Paris Cedex 05, France firstname.lastname@example.com Abstract Scheduling a sequence of tasks in the acceptationMore information
1. Prove that the empty set is a subset of every set.
1. Prove that the empty set is a subset of every set. Basic Topology Written by Men-Gen Tsai email: email@example.com Proof: For any element x of the empty set, x is also an element of every set sinceMore information
P (A) = lim P (A) = N(A)/N,
1.1 Probability, Relative Frequency and Classical Definition. Probability is the study of random or non-deterministic experiments. Suppose an experiment can be repeated any number of times, so that weMore information
A Portfolio Model of Insurance Demand. April 2005. Kalamazoo, MI 49008 East Lansing, MI 48824
A Portfolio Model of Insurance Demand April 2005 Donald J. Meyer Jack Meyer Department of Economics Department of Economics Western Michigan University Michigan State University Kalamazoo, MI 49008 EastMore information
Prime Numbers and Irreducible Polynomials
Prime Numbers and Irreducible Polynomials M. Ram Murty The similarity between prime numbers and irreducible polynomials has been a dominant theme in the development of number theory and algebraic geometry.More information
CONTRIBUTIONS TO ZERO SUM PROBLEMS S. D. ADHIKARI, Y. G. CHEN, J. B. FRIEDLANDER, S. V. KONYAGIN AND F. PAPPALARDI Abstract. A prototype of zero sum theorems, the well known theorem of Erdős, GinzburgMore information
FIRST YEAR CALCULUS. Chapter 7 CONTINUITY. It is a parabola, and we can draw this parabola without lifting our pencil from the paper.
FIRST YEAR CALCULUS WWLCHENW L c WWWL W L Chen, 1982, 2008. 2006. This chapter originates from material used by the author at Imperial College, University of London, between 1981 and 1990. It It is isMore information
TAKE-AWAY GAMES. ALLEN J. SCHWENK California Institute of Technology, Pasadena, California INTRODUCTION
TAKE-AWAY GAMES ALLEN J. SCHWENK California Institute of Technology, Pasadena, California L INTRODUCTION Several games of Tf take-away?f have become popular. The purpose of this paper is to determine theMore information
Elementary Number Theory We begin with a bit of elementary number theory, which is concerned
CONSTRUCTION OF THE FINITE FIELDS Z p S. R. DOTY Elementary Number Theory We begin with a bit of elementary number theory, which is concerned solely with questions about the set of integers Z = {0, ±1,More information
SOME ASPECTS OF GAMBLING WITH THE KELLY CRITERION. School of Mathematical Sciences. Monash University, Clayton, Victoria, Australia 3168
SOME ASPECTS OF GAMBLING WITH THE KELLY CRITERION Ravi PHATARFOD School of Mathematical Sciences Monash University, Clayton, Victoria, Australia 3168 In this paper we consider the problem of gambling withMore information
An Innocent Investigation
An Innocent Investigation D. Joyce, Clark University January 2006 The beginning. Have you ever wondered why every number is either even or odd? I don t mean to ask if you ever wondered whether every numberMore information
COMPLETE MARKETS DO NOT ALLOW FREE CASH FLOW STREAMS NICOLE BÄUERLE AND STEFANIE GRETHER Abstract. In this short note we prove a conjecture posed in Cui et al. 2012): Dynamic mean-variance problems inMore information
Chapter 7. Sealed-bid Auctions
Chapter 7 Sealed-bid Auctions An auction is a procedure used for selling and buying items by offering them up for bid. Auctions are often used to sell objects that have a variable price (for example oil)More information
princeton univ. F 13 cos 521: Advanced Algorithm Design Lecture 6: Provable Approximation via Linear Programming Lecturer: Sanjeev Arora
princeton univ. F 13 cos 521: Advanced Algorithm Design Lecture 6: Provable Approximation via Linear Programming Lecturer: Sanjeev Arora Scribe: One of the running themes in this course is the notion ofMore information
Section 6-2 Mathematical Induction
6- Mathematical Induction 457 In calculus, it can be shown that e x k0 x k k! x x x3!! 3!... xn n! where the larger n is, the better the approximation. Problems 6 and 6 refer to this series. Note thatMore information
Sequences and Series
Sequences and Series Consider the following sum: 2 + 4 + 8 + 6 + + 2 i + The dots at the end indicate that the sum goes on forever. Does this make sense? Can we assign a numerical value to an infiniteMore information
A PRIORI ESTIMATES FOR SEMISTABLE SOLUTIONS OF SEMILINEAR ELLIPTIC EQUATIONS. In memory of Rou-Huai Wang
A PRIORI ESTIMATES FOR SEMISTABLE SOLUTIONS OF SEMILINEAR ELLIPTIC EQUATIONS XAVIER CABRÉ, MANEL SANCHÓN, AND JOEL SPRUCK In memory of Rou-Huai Wang 1. Introduction In this note we consider semistableMore information
The Classes P and NP
The Classes P and NP We now shift gears slightly and restrict our attention to the examination of two families of problems which are very important to computer scientists. These families constitute theMore information
1 Sets and Set Notation.
LINEAR ALGEBRA MATH 27.6 SPRING 23 (COHEN) LECTURE NOTES Sets and Set Notation. Definition (Naive Definition of a Set). A set is any collection of objects, called the elements of that set. We will mostMore information
OSTROWSKI FOR NUMBER FIELDS KEITH CONRAD Ostrowski classified the nontrivial absolute values on Q: up to equivalence, they are the usual (archimedean) absolute value and the p-adic absolute values forMore information
No: 10 04. Bilkent University. Monotonic Extension. Farhad Husseinov. Discussion Papers. Department of Economics
No: 10 04 Bilkent University Monotonic Extension Farhad Husseinov Discussion Papers Department of Economics The Discussion Papers of the Department of Economics are intended to make the initial resultsMore information
Further Study on Strong Lagrangian Duality Property for Invex Programs via Penalty Functions 1
Further Study on Strong Lagrangian Duality Property for Invex Programs via Penalty Functions 1 J. Zhang Institute of Applied Mathematics, Chongqing University of Posts and Telecommunications, ChongqingMore information
LOOKING FOR A GOOD TIME TO BET LAURENT SERLET Abstract. Suppose that the cards of a well shuffled deck of cards are turned up one after another. At any time-but once only- you may bet that the next cardMore information
M.Sc. program in mathematics INTRODUCTORY SET THEORY Katalin Károlyi Department of Applied Analysis, Eötvös Loránd University H-1088 Budapest, Múzeum krt. 6-8. CONTENTS 1. SETS Set, equal sets, subset,More information
Chapter 8 THREE DIMENSIONAL GEOMETRY 8.1 Introduction In this chapter we present a vector algebra approach to three dimensional geometry. The aim is to present standard properties of lines and planes,More information
The Open University s repository of research publications and other research outputs
Open Research Online The Open University s repository of research publications and other research outputs The degree-diameter problem for circulant graphs of degree 8 and 9 Journal Article How to cite:More information
Unraveling versus Unraveling: A Memo on Competitive Equilibriums and Trade in Insurance Markets
Unraveling versus Unraveling: A Memo on Competitive Equilibriums and Trade in Insurance Markets Nathaniel Hendren January, 2014 Abstract Both Akerlof (1970) and Rothschild and Stiglitz (1976) show thatMore information
11 Ideals. 11.1 Revisiting Z
11 Ideals The presentation here is somewhat different than the text. In particular, the sections do not match up. We have seen issues with the failure of unique factorization already, e.g., Z[ 5] = O Q(More information
1 Short Introduction to Time Series
ECONOMICS 7344, Spring 202 Bent E. Sørensen January 24, 202 Short Introduction to Time Series A time series is a collection of stochastic variables x,.., x t,.., x T indexed by an integer value t. TheMore information
You know from calculus that functions play a fundamental role in mathematics.
CHPTER 12 Functions You know from calculus that functions play a fundamental role in mathematics. You likely view a function as a kind of formula that describes a relationship between two (or more) quantities.More information
Taylor Polynomials and Taylor Series Math 126
Taylor Polynomials and Taylor Series Math 26 In many problems in science and engineering we have a function f(x) which is too complicated to answer the questions we d like to ask. In this chapter, we willMore information
PROOFS BY DESCENT KEITH CONRAD As ordinary methods, such as are found in the books, are inadequate to proving such difficult propositions, I discovered at last a most singular method... that I called theMore information
Homework until Test #2
MATH31: Number Theory Homework until Test # Philipp BRAUN Section 3.1 page 43, 1. It has been conjectured that there are infinitely many primes of the form n. Exhibit five such primes. Solution. Five suchMore information
ECON 312: Oligopolisitic Competition 1. Industrial Organization Oligopolistic Competition
ECON 312: Oligopolisitic Competition 1 Industrial Organization Oligopolistic Competition Both the monopoly and the perfectly competitive market structure has in common is that neither has to concern itselfMore information
SECTION 10-2 Mathematical Induction
73 0 Sequences and Series 6. Approximate e 0. using the first five terms of the series. Compare this approximation with your calculator evaluation of e 0.. 6. Approximate e 0.5 using the first five termsMore information
CHAPTER 3. Methods of Proofs. 1. Logical Arguments and Formal Proofs
CHAPTER 3 Methods of Proofs 1. Logical Arguments and Formal Proofs 1.1. Basic Terminology. An axiom is a statement that is given to be true. A rule of inference is a logical rule that is used to deduceMore information


text:
Who died on the Cross?
Hi all,
At our mid week bible study the Pastor said that God (as in the second person of the Trinity) died on the Cross. Instinctively I believed that to be wrong, and so I checked it out, first from the Word and then from trusted sources, I ended up with R.C.Sproul saying that it was impossible for God (the second person of the Trinity) to die, and John Macarthur said that God did die on the cross.I'm hoping that someone could shed some light on the subject.
Thank you
Who Died
The flesh body of Jesus was the Earth Clothes of God, aka; sacrificial lamb, simply the vehicle He rode in on earth. Collosians says that all of the fullness of the Godhead lived bodily in Christ Jesus. That body died and was resurrected. God is a Spirit (John 4) and therefore not subject to death. Spirit is eternal and cannot die because it was not cursed by the original sin (a work of the flesh). God is omnipotent and therefore was still on the throne when Jesus (The Flesh Clothes of God) was allowed to die [by God] as a representative of sinful flesh. This is what proves that Jesus was entirely God because if He were completely dead, body, soul and spirit, He could do nothing.

subset: commoncrawl


text:
American National College (ANC) Education, Sri Lanka's largest education conglomerate, has partnered with EDEX Expo, the country's biggest education exhibition and job fair as a Platinum sponsor. ANC, being a long-term supporter of EDEX Expo, has partnered with the EDEX initiative for thirteen consecutive years, proving our commitment to education.
Left to Right
Nishan Jayalath – Director Sponsorships - EDEX, Sudheera Senaratne – Secretary –EDEX, Athula Munasinghe – Secretary – Royal College Union, Mahinda Galagedara – Chairman – EDEX, Dr Punarjeeva Karunanayake - CEO/Executive Director - ANC, P. Saravanan - Director/ Group Chief Financial Officer - ANC, Aruni Mahipala - Director/ Chief Operating Officer - ANC, Ramesh Ramkumar - Senior Manager, US University Programs - ANC, Chandima Garumanna - Senior Manager, Marketing - ANC
American Education Centre Limited (AECL), which operates under the brand name ANC Education, was established in 2002 envisioning to be the most preferred choice for tertiary education in Sri Lanka. Moving forward with that vision, over the years, ANC has established affiliations and partnerships with reputed higher education institutions around the world, including the University of West London (UWL) for postgraduate programs, Northwood University (NU) of USA for the American Degree Completion Program in Sri Lanka and for the US Transfer Program. Apart from that, the ANC Foundation and Diploma programs provide students access to study their degree in major Australian Universities.
Dr Punarjeeva Karunanayake, Chief Executive Officer/ Executive Director of ANC Education said, "Since the beginning of our operation in Sri Lanka with the goal of providing quality international tertiary education options for local students, ANC Education has now grown to be the country's largest provider of trans-national education for Sri Lankan students. With the best interest of students in mind, we are indeed delighted to continue our long-standing partnership with EDEX Expo and showcase all the opportunities available to students who are in pursuit of quality international higher education."
At present, ANC Education offers world-class, quality education to local and foreign students through its various local subsidiaries and associates such as Wycherley International School, Regent International School, Net Assist International, Modern Montessori International (MMI) and PATHE Study Medicine. Through these subsidiaries, ANC provides students access to world recognized universities in America, United Kingdom, Canada, Australia, Germany, Eastern Europe and Malaysia.
Further expanding the horizons of Sri Lankan students, ANC recently partnered with Eurasia Institute to give local students the opportunity to gain access to government funded German universities with a 100% tuition fee-waiver. The universities included in the program are The Technical University of Applied Sciences Wildau, Johannes Gutenberg University of Mainz, University of Applied Sciences Jena, Brandenburg University of Applied Sciences and Martin Luther University of Halle – Wittenberg.
"We are pleased that ANC Education has pledged its support once again for EDEX Expo 2017. ANC has been a reliable education provider for Sri Lankan students for over a decade, and we are proud to be associated with them," said EDEX Chairman, Mr. Athula Munasinghe.
EDEX Expo 2017 is scheduled to be held at the BMICH from 20-22 January 2017 and at the Kandy City Centre (KCC) from 27-28 January 2017. For further details regarding EDEX Expo 2017 please contact the EDEX Secretariat. Tel: 0768 204978/ 01155 21 497. E-mail [email protected] Web site www.edex.lk.


text:
- Home >
- Bathing & Bathroom Aids >
- Benches, Seats & Stools >
- Shower Chairs (Stationary) >
- Economy Shower Chair - Adjustable Height Economy Shower Chair - Adjustable Height+-
This excellent value Shower Chair is ideal for those who struggle to stand in the shower, elderly or disabled people. It features a comfortable white plastic seat with drainage holes and a supportive back rest. The integral arms enable easier rising and support whilst seated. Non slip rubber ferrule feet. Easy height adjustment.
The simple design is easy to clean after use with normal bathroom cleaning products.
- Seat height: 410-537mm (16-21")
- Width between handles: 485mm (19")
- Footprint: 545 x 450mm (21½ x 17¾")
VAT Exemption
Q. What is VAT relief and who is eligible to claim it?
A. Click here for more information ...
Related Categories
- Menu


text:
People are living longer, which means you may be spending more time in retirement than did members of previous generations. To ensure your retirement is a secure one, you will need to plan your finances. This will require you to consider such things as your life expectancy and your Social Security and pension benefits. Equally important is that you identify what being retired means to you in terms of lifestyle and the things you want to do, as well as the risks you want to avoid, such as outliving your financial resources.
Provide Retirement Income
Gayle Turim writes in "Everyday Health" that the odds are good that some people will live into their 80s or 90s. To ensure you aren't forced to make an abrupt change to your lifestyle at some point during your retirement years, review your future sources of income. Your retirement plan should include your Social Security benefits, retirement accounts and other assets that will provide you a secure monthly income in lieu of the salary you earn while working. Some of your assets, such as your Social Security benefit, might pay you a certain amount each month for life. Other assets, such as mutual fund shares, may pay investment income in the form of dividends, interest payments or capital gains that you will collect when you sell the asset.
Minimize Longevity Risk
According to the U.S. News and World Report article, "How to Calculate Your Retirement Number," you may be able to eliminate the risk you will outlive your assets if your retirement plan ensures you can replace 80 percent or more of your income during your retirement years. Robert Powell writes in a MarketWatch article, that you can counter longevity risk by accumulating assets that will pay a specified amount of income for life. Such assets include Social Security benefits, a pension and annuities, as well as a reverse mortgage, longevity insurance and a managed payout plan.
Maintain Standard of Living
Retirement planning prepares a retiree for the life he'll live after his for-pay work ends. A critical part of retirement planning is determining the standard of living you would like to maintain when you no longer work, which is determined in part by how you will want to spend your time. You may support a part of your desired standard of living with a pension or government benefits. You also may need to be disciplined in your saving and investment in financial markets to build an investment portfolio that will yield the annual investment income you'll need to pay for your desired standard of living.
Determine Retirement Age
With careful planning, your retirement age can be a rational decision you make after considering various factors and taking the steps necessary to accumulate the assets that will support your decision. Robert Powell writes in "What's the Best Age to Retire," that you should consider not only the financial feasibility of retiring at a particular age, but also your ability to continue working and other personal issues. For example, think about at what point in time your retirement income will be sufficient to give you the lifestyle you desire and if you need additional paychecks to build your nest egg. This will be determined in part by such factors as your life expectancy, inflation, investment return or other risks, as well as the costs of health care and insurance.
Related Searches
- Photo Credit Digital Vision./Digital Vision/Getty Images
You May Also Like
The Importance of Investment Companies
Investing for the future has never been more important than it is today. The recent financial storm has left many people shaken,...
What Are the Different Types of Retirement Plans?
The American dream is to one day retire and live on an income stream generated from a retirement savings account. Many corporations...
What Is the Importance of Financial Planning?
Financial Planning is a process of setting realistic goals and then achieving them through investment planning, insurance planning and tax planning. To...
The Importance of Personal Finance Planning
Personal finance planning is the key to becoming more stable in almost every facet of your life. From considering career options to...
- The Importance of a Work Plan
List of Retirement Plans
A multitude of different retirement plan types exist, offering consumers, business owners, and employees an opportunity to save money in a plan...


text:
by Staff Writers
Beijing (AFP) Jan 27, 2013
China has carried out a test flight of its biggest-ever army transport aeroplane, state media said Sunday, as the country strengthens its military capabilities.
A successful test flight of the Y-20, a long-range heavy transport jet, took place on Saturday in the northwest of the country, the People's Daily newspaper reported on its website.
The plane was developed in China to transport military combat and support vehicles and can carry up to 66 tons, the report said, making it China's biggest home-grown military transport plane to date.
The Y-20 would be a "huge boost to the intercontinental strategic projection abilities of China's air force", the Beijing News cited an army expert as saying.
China has invested heavily in upgrading its military in recent years, rattling its neighbours in Asia. It insists its army spending is relatively low as a proportion of GDP and is not aimed at any other country.
Related Links
Aerospace News at SpaceMart.com
|The content herein, unless otherwise known to be public domain, are Copyright 1995-2014 - Space Media Network. AFP, UPI and IANS news wire stories are copyright Agence France-Presse, United Press International and Indo-Asia News Service. ESA Portal Reports are copyright European Space Agency. All NASA sourced material is public domain. Additional copyrights may apply in whole or part to other bona fide parties. Advertising does not imply endorsement,agreement or approval of any opinions, statements or information provided by Space Media Network on any Web page published or hosted by Space Media Network. Privacy Statement


text:
Art Of Minimalism In Logo Design
Minimalism has been a movement in art which involves creating a logo design with rudimentary features only. Some expert hail minimalism as a creative logo design trend and this form of designing has been a trend these days. Today's designers believe that simple is better but the designers should be careful in creating a logo … Continue reading


text:
Added to Cart
Fendi L'Acquarossa Eau De Parfum Spray (50ml/1.7oz)
Add to Wishlist
Fendi L'Acquarossa Eau De Parfum Spray (50ml/1.7oz)
- An oriental floral fragrance for modern women
- Strong, crisp, elegant, feminine & bewitching
- Top notes of Sicilian mandarin, Calabrian bergamot & a prune accord
- Heart notes of red-and-gold lantana flowers, rose, orange blossoms & magnolia
- Base notes of red cedar, musk & Indonesian patchouli
- Launched in 2013
- Perfect for all occasions
Due to the nature of this product, we are unable to accept a return under the terms of our Returns Policy for 'change of mind' purposes or sizing errors.
Returns for these products will only be accepted where the goods are deemed faulty under the terms of our Warranty Terms & Conditions .
This Product is offered and supplied by Kogan HK Limited pursuant to the Terms and Conditions.