Estimating the probability that a simulated system will be the best

Consider a stochastic simulation experiment consisting of v independent vector replications consisting of an observation from each of k independent systems. Typical system comparisons are based on mean (long‐run) performance. However, the probability that a system will actually be the best is sometimes more relevant, and can provide a very different perspective than the systems' means. Empirically, we select one system as the best performer (i.e., it wins) on each replication. Each system has an unknown constant probability of winning on any replication and the numbers of wins for the individual systems follow a multinomial distribution. Procedures exist for selecting the system with the largest probability of being the best. This paper addresses the companion problem of estimating the probability that each system will be the best. The maximum likelihood estimators (MLEs) of the multinomial cell probabilities for a set of v vector replications across k systems are well known. We use these same v vector replications to form v^k unique vectors (termed pseudo‐replications) that contain one observation from each system and develop estimators based on AVC (All Vector Comparisons). In other words, we compare every observation from each system with every combination of observations from the remaining systems and note the best performer in each pseudo‐replication. AVC provides lower variance estimators of the probability that each system will be the best than the MLEs. We also derive confidence intervals for the AVC point estimators, present a portion of an extensive empirical evaluation and provide a realistic example. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 341–358, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10019     

A diffusion model for the control of a multipurpose reservoir system

This paper develops a methodology for optimizing operation of a multipurpose reservoir with a finite capacity V. The input of water into the reservoir is a Wiener process with positive drift. There are n purposes for which water is demanded. Water may be released from the reservoir at any rate, and the release rate can be increased or decreased instantaneously with zero cost. In addition to the reservoir, a supplementary source of water can supply an unlimited amount of water demanded during any period of time. There is a cost of C_i dollars per unit of demand supplied by the supplementary source to the i^th purpose (i = 1, 2, …, n). At any time, the demand rate R_i associated with the i^th purpose (i = 1, 2, …, n) must be supplied. A controller must continually decide the amount of water to be supplied by the reservoir for each purpose, while the remaining demand will be supplied through the supplementary source with the appropriate costs. We consider the problem of specifying an output policy which minimizes the long run average cost per unit time.     

A search game with a protector

A classic problem in Search Theory is one in which a searcher allocates resources to the points of the integer interval [1, n] in an attempt to find an object which has been hidden in them using a known probability function. In this paper we consider a modification of this problem in which there is a protector who can also allocate resources to the points; allocating these resources makes it more difficult for the searcher to find an object. We model the situation as a two‐person non‐zero‐sum game so that we can take into account the fact that using resources can be costly. It is shown that this game has a unique Nash equilibrium when the searcher's probability of finding an object located at point i is of the form (1 − exp (−λ_ix_i)) exp (−μ_iy_i) when the searcher and protector allocate resources x_i and y_i respectively to point i. An algorithm to find this Nash equilibrium is given. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47:85–96, 2000     

Asymptotic inference about a density function at an end of its range

For each n, X₁(n),…X_n(n) are independent and identically distributed random variables, with common probability density function Where c, θ, α, and r(y) are all unknown. It is shown that we can make asymptotic inferences about c, θ, and α, when r(y) satisfies mild conditions.     

Efficient multinomial selection in simulation

Consider a simulation experiment consisting of v independent vector replications across k systems, where in any given replication one system is selected as the best performer (i.e., it wins). Each system has an unknown constant probability of winning in any replication and the numbers of wins for the individual systems follow a multinomial distribution. The classical multinomial selection procedure of Bechhofer, Elmaghraby, and Morse (Procedure BEM) prescribes a minimum number of replications, denoted as v*, so that the probability of correctly selecting the true best system (PCS) meets or exceeds a prespecified probability. Assuming that larger is better, Procedure BEM selects as best the system having the largest value of the performance measure in more replications than any other system. We use these same v* replications across k systems to form (v*)^k pseudoreplications that contain one observation from each system, and develop Procedure AVC (All Vector Comparisons) to achieve a higher PCS than with Procedure BEM. For specific small-sample cases and via a large-sample approximation we show that the PCS with Procedure AVC exceeds the PCS with Procedure BEM. We also show that with Procedure AVC we achieve a given PCS with a smaller v than the v* required with Procedure BEM. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 459–482, 1998     

Technical note: Find a hidden “treasure”

This paper deals with a two searchers game and it investigates the problem of how the possibility of finding a hidden object simultaneously by players influences their behavior. Namely, we consider the following two‐sided allocation non‐zero‐sum game on an integer interval [1,n]. Two teams (Player 1 and 2) want to find an immobile object (say, a treasure) hidden at one of n points. Each point i ∈ [1,n] is characterized by a detection parameter λ_i (μ_i) for Player 1 (Player 2) such that p_i(1 ? exp(?λ_ix_i)) (p_i(1 ? exp(?μ_iy_i))) is the probability that Player 1 (Player 2) discovers the hidden object with amount of search effort x_i (y_i) applied at point i where p_i ∈ (0,1) is the probability that the object is hidden at point i. Player 1 (Player 2) undertakes the search by allocating the total amount of effort X(Y). The payoff for Player 1 (Player 2) is 1 if he detects the object but his opponent does not. If both players detect the object they can share it proportionally and even can pay some share to an umpire who takes care that the players do not cheat each other, namely Player 1 gets q₁ and Player 2 gets q₂ where q₁ + q₂ ≤ 1. The Nash equilibrium of this game is found and numerical examples are given. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

The variance of the coverage of a randomly located area target by a salvo of weapons

We derive formulas for the variance of that proportion of the value of a randomly located, circularly symmetric area target that is destroyed by N independently fired weapons of identical type whose damage functions are circularly symmetric about the respective impact points. The probability density functions of the target center location and of the weapon impact points are also circularly symmetric. The general results are specialized to uniform and Gaussian functions. In the latter case a closed-form solution (triple integral) for the variance of the coverage is derived. Similar to some well-known results on expected coverage, this expression for the variance of the coverage can be easily evaluated by numerical quadrature. Numerical results are given which indicate the target coverage variability caused by the combined effects of random target-locating errors and weapon impact point fluctuations.     

A note on a prediction interval for a first-order Gauss Markov process

Let X_t, t = 1,2, ?, be a stationary Gaussian Markov process with E(X_t) = μ and Cov(X_t, X_t+k) = σ²ρ^k. We derive a prediction interval for X_2n+1 based on the preceding 2n observations X₁,X₂, ?,X_2n.     

The asymptotic distribution of order statistics

For each n., X₁(n), X₂(n), …, X_n(n) are IID, with common pdf f_n(x). y₁(n) < … < Y_n (n) are the ordered values of X₁ (n), …, X_n(n). K_n is a positive integer, with lim K_n = ∞. Under certain conditions on K_n and f_n (x), it was shown in an earlier paper that the joint distribution of a special set of K_n + 1 of the variables Y₁ (n), …, Y_n (n) can be assumed to be normal for all asymptotic probability calculations. In another paper, it was shown that if f_n (x) approaches the pdf which is uniform over (0, 1) at a certain rate as n increases, then the conditional distribution of the order statistics not in the special set can be assumed to be uniform for all asymptotic probability calculations. The present paper shows that even if f_n (x) does not approach the uniform distribution as n increases, the distribution of the order statistics contained between order statistics in the special set can be assumed to be the distribution of a quadratic function of uniform random variables, for all asymptotic probability calculations. Applications to statistical inference are given.     

On the first time a separately maintained parallel system has been down for a fixed time

Consider a system consisting of n separately maintained independent components where the components alternate between intervals in which they are “up” and in which they are “down”. When the i^th component goes up [down] then, independent of the past, it remains up [down] for a random length of time, having distribution F_i[G_i], and then goes down [up]. We say that component i is failed at time t if it has been “down” at all time points s ?[t-A.t]: otherwise it is said to be working. Thus, a component is failed if it is down and has been down for the previous A time units. Assuming that all components initially start “up,” let T denote the first time they are all failed, at which point we say the system is failed. We obtain the moment-generating function of T when n = l, for general F and G, thus generalizing previous results which assumed that at least one of these distributions be exponential. In addition, we present a condition under which T is an NBU (new better than used) random variable. Finally we assume that all the up and down distributions F_i and G_i i = l,….n, are exponential, and we obtain an exact expression for E(T) for general n; in addition we obtain bounds for all higher moments of T by showing that T is NBU.     

Confidence intervals for ranked means

Suppose that observations from populations π₁, …, π_k (k ≥ 1) are normally distributed with unknown means μ₁., μ_k, respectively, and a common known variance σ². Let μ_[1] μ … ≤ μ_[k] denote the ranked means. We take n independent observations from each population, denote the sample mean of the n observation from π₁ by X _i (i = 1, …, k), and define the ranked sample means X _[1] ≤ … ≤ X _[k]. The problem of confidence interval estimation of μ₍₁₎, …,μ_[k] is stated and related to previous work (Section 1). The following results are obtained (Section 2). For i = 1, …, k and any γ(0 < γ < 1) an upper confidence interval for μ_[i] with minimal probability of coverage γ is (? ∞, X _[i]+ h) with h = (σ/n^1/2) Φ^?1(γ^1/k-i+1), where Φ(·) is the standard normal cdf. A lower confidence interval for μ_[i] with minimal probability of coverage γ is (X _i[i] – g, + ∞) with g = (σ/n^1/2) Φ^?1(γ^1/i). For the upper confidence interval on μ_[i] the maximal probability of coverage is 1– [1 – γ^1/k-i+1]ⁱ, while for the lower confidence interval on μ_[i] the maximal probability of coverage is 1–[1– γ^1/i] ^k-i+¹. Thus the maximal overprotection can always be calculated. The overprotection is tabled for k = 2, 3. These results extend to certain translation parameter families. It is proven that, under a bounded completeness condition, a monotone upper confidence interval h(X ₁, …, X _k) for μ_[i] with probability of coverage γ(0 < γ < 1) for all μ = (μ_[1], …,μ_[k]), does not exist.     

Readiness and the optimal redeployment of resources

This paper considers the problem of the optimal redeployment of a resource among different geographical locations. Initially, it is assumed that at each location i, i = 1,…, n, the level of availability of the resource is given by a₁ ≧ 0. At time t > 0, requirements R_f(t) ≧ 0 are imposed on each location which, in general, will differ from the a₁. The resource can be transported from any one location to any other in magnitudes which will depend on t and the distance between these locations. It is assumed that ΣR_j > Σa_t The objective function consideis, in addition to transportation costs incurred by reallocation, the degree to which the resource availabilities after redeployment differ from the requirements. We shall associate the unavailabilities at the locations with the unreadiness of the system and discuss the optimal redeployment in terms of the minimization of the following functional forms: \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj) + } $\end{document} transportation costs, Max \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {Max}\limits_j \,[kj(Rj - yj)] + $\end{document} transportation costs, and \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj)^2 + } $\end{document} transportation costs. The variables y_j represent the final amount of the resource available at location j. No benefits are assumed to accrue at any location if y_j > R_j. A numerical three location example is given and solved for the linear objective.     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

Estimating value in a uniform auction

Consider an auction in which increasing bids are made in sequence on an object whose value θ is known to each bidder. Suppose n bids are received, and the distribution of each bid is conditionally uniform. More specifically, suppose the first bid X₁ is uniformly distributed on [0, θ], and the i^th bid is uniformly distributed on [X_i?1, θ] for i = 2, …?, n. A scenario in which this auction model is appropriate is described. We assume that the value θ is un known to the statistician and must be esimated from the sample X₁, X₂, …?, X_n. The best linear unbiased estimate of θ is derived. The invariance of the estimation problem under scale transformations in noted, and the best invariant estimation problem under scale transformations is noted, and the best invariant estimate of θ under loss L(θ, a) = [(a/θ) ? 1]² is derived. It is shown that this best invariant estimate has uniformly smaller mean-squared error than the best linear unbiased estimate, and the ratio of the mean-squared errors is estimated from simulation experiments. A Bayesian formulation of the estimation problem is also considered, and a class of Bayes estimates is explicitly derived.     

Distribution of number of point targets killed and higher moments of coverage of area targets

The coverage C of area targets by salvos of weapons generally varies randomly, because of random target location and weapon impact point fluctuations. A third source of variation appears when, instead of an area target, a multiple-element target is considered, consisting of m point targets distributed randomly and independently of one another around the target center. A multiple-integral expression is derived for the probability p_k of killing exactly k target elements. It is shown that p_k is a linear function of the higher moments, of the order k to m, of the area coverage C. More explicit expressions are derived for the case of two weapons and for circular-symmetric functions. Similar to well-known results for the expectation and variance of coverage of area targets, these expressions can be evaluated by numerical quadrature. Furthermore, the coverage problem in which all underlying functions are Gaussian can be completely solved in closed form. For such a problem, with two weapons, numerical results are presented. They show that the distribution of k can be approximated by a binomial distribution only if the target center and weapon impact point fluctuations are small.     

Openshop scheduling under linear resources constraints

Consider n jobs (J₁, …, J_n), m working stations (M₁, …, M_m) and λ linear resources (R₁, …, R_λ). Job J_i consists of m operations (O_i1, …, O_im). Operation O_ij requires P_k(i, j) units of resource R_k to be realized in an M_j. The availability of resource R_k and the ability of the working station M_h to consume resource R_k, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP-hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998     

On optimal aiming to hit a linear target

Typically weapon systems have an inherent systematic error and a random error for each round, centered around its mean point of impact. The systematic error is common to all aimings. Assume such a system for which there is a preassigned amount of ammunition of n rounds to engage a given target simultaneously, and which is capable of administering their fire with individual aiming points (allowing “offsets”). The objective is to determine the best aiming points for the system so as to maximize the probability of hitting the target by at least one of the n rounds. In this paper we focus on the special case where the target is linear (one‐dimensional) and there are no random errors. We prove that as long as the aiming error is symmetrically distributed and possesses one mode at zero, the optimal aiming is independent of the particular error distribution, and we specify the optimal aiming points. Possible extensions are further discussed, as well as civilian applications in manufacturing, radio‐electronics, and detection. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 323–333, 1999     

Total optimality of incrementally optimal allocations

This paper considers the problem of finding optimal solutions to a class of separable constrained extremal problems involving nonlinear functionals. The results are proved for rather general situations, but they may be easily stated for the case of search for a stationary object whose a priori location distribution is given by a density function on R, a subset of Euclidean n-space. The functional to be optimized in this case is the probability of detection and the constraint is on the amount of effort to be used Suppose that a search of the above type is conducted in such a manner as to produce the maximum increase in probability of detection for each increment of effort added to the search. Then under very weak assumptions, it is proven that this search will produce an optimal allocation of the total effort involved. Under some additional assumptions, it is shown that any amount of search effort may be allocated in an optimal fashion.     

Scheduling with earliest start and due date constraints on multiple machines

We consider the scheduling of n jobs on m identical machines when the jobs become available for processing at ready times a_i, a_i, ? 0, require d_i time units for processing and must be completed by times b_i for i = 1, 2, … n. The objective chosen is that of minimizing the total elapsed time to complete all jobs subject to the ready time and due date constraints, preemption is not allowed. We present a multi-stage solution algorithm for this problem that is based on an implicit enumeration procedure and also uses the labelling type algorithm which solves the problem when preemption is allowed.