An infinite random stream of ordered pairs arrives sequentially in discrete time. A pair consists of a “candidate” and an “offer,” each of which is either of type I (with probability p) or of type II (with probability q = 1 – p). Offers are to be assigned to candidates, yielding a reward R > 0 if they match in type, or a smaller reward 0 ≤ r ≤ R if not. An arriving candidate resides in the system until it is assigned, whereas an arriving offer is either assigned immediately to one of the waiting candidates or lost forever. We show that the optimal long-term average reward is R, independent of the population proportion p and the “second prize” r, and that the optimal average reward policy is to assign only a match. Optimal policies for discounted and finite horizon models are also derived.

Bivariate Lomax distribution due to Lindley and Singpurwalla has been characterized through the bivariate extension of a univariate characterizing property of the Lomax distribution.

The burn-in problem is reframed in a decision-making context. The role of the predictive life distribution in the burn-in decision problem is highlighted. The case in which the predictive distribution is a mixture of exponentials is discussed extensively.

Items of various types arrive at a bin-packing facility according to random processes and are to be combined with other readily available items of different types and packed into bins using one of a number of possible packings. One might think of a manufacturing context in which randomly arriving subassemblies are to be combined with subassemblies from an existing inventory to assemble a variety of finished products. Packing must be done on-line; that is, as each item arrives, it must be allocated to a bin whose configuration of packing is fixed. Moreover, it is required that the packing be managed in such a way that the readily available items are consumed at predescribed rates, corresponding perhaps to optimal rates for manufacturing these items. At any moment, some number of bins will be partially full. In practice, it is important that the packing be managed so that the expected number of partially full bins remains uniformly bounded in time. We present a necessary and sufficient condition for this goal to be realized and describe an algorithm to achieve it.

In this paper we consider a problem that arises in estimating the heavy traffic limit of a sojourn time distribution in a queueing network during the course of a medium traffic simulation. We need to estimate α = E[f(γ, M)], where γ is an unknown constant and M a random variable. More specifically, we are given an iid sequence of random vectors {(Xi, Mi), 1 ≤ i ≤ n}, with γ = E[Xi] and Mi having the same distribution as M.

For known γ, we have a standard estimation problem, which we describe here. The standard estimate is unbiased and asymptotically (as n → 8 ) consistent. There is also a central limit theorem for this estimator. For unknown γ, we provide two estimation procedures, one that requires two passes through the data (as well as storage of {Mi, 1 ≤ i ≤ n}), and another one, which is recursive, requiring only one pass through and bounded storage. The estimators obtained from these two procedures are shown to be strongly consistent, and central limit theorems are also proven for them.

Consider a queueing model in which arriving customers have to choose between m parallel servers, each with its own queue. We prove for general arrival streams that the policy which assigns to the shortest queue is stochastically optimal for models with finite buffers and batch arrivals.

Aleliunas et al. [3] proved that for a random walk on a connected raph G = (V, E) on N vertices, the expected minimum number of steps to visit all vertices is bounded by 2|E|(N - 1), regardless of the initial state. We give here a simple proof of that result through an equality involving hitting times of vertices that can be extended to an inequality for hitting times of edges, thus obtaining a bound for the expected minimum number of steps to visit all edges exactly once in each direction.

Gauss-Seidel is a general method for solving a system of equations (possibly nonlinear). It makes repeated sweeps through the variables; within a sweep as each new estimate for a variable is computed, the current estimate for that variable is replaced with the new estimate immediately, instead of on completion of the sweep. The idea is to use new data as soon as it is computed. Gauss- Seidel is often efficient for computing the invariant measure of a Markov chain (especially if the transition matrix is sparse), and for computing the value function in optimal control problems. In many applications the computation can be significantly improved by appropriately ordering the variables within each sweep. A simple heuristic is presented here for computing an ordering that quickens convergence. In parallel processing, several variables must be computed simultaneously, which appears to work against Gauss-Seidel. Simple asynchronous parallel Gauss-Seidel methods are presented here. Experiments indicate that the methods retain the benefit of a good ordering, while further speeding up convergence by a factor of P if P processors participate.

In this paper, we focus on the optimal stopping problem. A probabilistic interpretation of the Gauss-Seidel (and the Jacobi) method for computing the value function is given, which motivates our ordering heuristic. However, the ordering heuristic and parallel processing methods apply in a broader context, in particular, to the important problem of computing the invariant measure of a Markov chain.

The classical binomial group-testing problem considers the use of a minimal number of group tests to identify all defectives in a set of items, each of which independently has probability p of being defective. The minimization problem is very difficult, and the only major result is that for p ≥ (3 - □ root;5) /2, Unger proved that one-by-one testing is the best. Recently, to study the complexity of the group-testing problem, researchers have considered the more general case in which the items have already been tested. Interestingly, Unger's result still holds in this case. However, since the items are no longer equivalent (nor independent), the sequencing of items of testing becomes a legitimate problem, one that did not arise in the classical case. In this paper, we give optimal sequencing under general conditions on the test history.

This paper proposes a pocket-calculator approximation to the normal tail that is more convenient and more accurate than Hamaker's [1] and Lew's [2] over a wide range, when measured in terms of the number of keystrokes and absolute relative error, respectively.

An alternative to Koehler's approximation for the percentiles of the t distribution is given. The alternative is not only slightly more accurate than Koehler's, but also the former is more convenient than the latter when measured in terms of the number of keystrokes.