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.

Observations may be taken from one of the two populations. A randomized selection rule is one that chooses the populations according to some determined odds. The odds for choosing a population the next time may be dependent on all the observations taken so far from both populations. In this paper, the odds are made for the randomized selection rule in such a way that the number of observations from the better population relative to the number of observations from the other population grows at prescribed rates, typically of exponential order or faster. The rules include randomized play-the-winner rules and randomized analogues of Robbins' rules. Some Monte Carlo investigations are conducted to study these randomized selection rules for moderate sample sizes.

An important problem in reliability theory is to determine the reliability of a system from the reliability of its components. If E is a finite set of components, then certain subsets of E are prescribed to be the operating states of the system. A formation is any collection F of minimal operating states whose union is E. Reliability domination is defined as the total number of odd cardinality formations minus the total number of even cardinality formations. The purpose of this paper is to establish some new results concerning reliability domination. In the special case where the system can be identified with a graph or digraph, these new results lead to some new graph-theoretic properties and to simple proofs of certain known theorems. The pertinent graph-theoretic properties include spanning trees, acyclic orientations, Whitney's broken cycles, and Tutte's internal activity associated with the chromatic polynomial.

A novel algorithm is developed which computes the ergodic probability vector for large Markov chains. Decomposing the state space into lumps, the algorithm generates a replacement process on each lump, where any exit from a lump is instantaneously replaced at some state in that lump. The replacement distributions are constructed recursively in such a way that, in the limit, the ergodic probability vector for a replacement process on one lump will be proportional to the ergodic probability vector of the original Markov chain restricted to that lump. Inverse matrices computed in the algorithm are of size (M – 1), where M is the number of lumps, thereby providing a substantial rank reduction. When a special structure is present, the procedure for generating the replacement distributions can be simplified. The relevance of the new algorithm to the aggregation-disaggregation algorithm of Takahashi [29] is also discussed.

In this paper, we are concerned with the simulation of Gaussian random fields by means of iterative stochastic algorithms, which are compared in terms of rate of convergence. A parametrized class of algorithms, which includes stochastic relaxation (Gibbs sampler), is proposed and its convergence properties are established. A suitable choice for the parameter improves the rate of convergence with respect to stochastic relaxation for special classes of covariance matrices. Some examples and numerical experiments are given.

By using the martingale method, we show that thinning of an arbitrary point process produces independent thinned processes if and only if the original point process is (nonhomogeneous) Poisson. Thinning is a classical problem for point processes. It is well-known that independent homogeneous Poisson processes result from constant Bernoulli thinnings of homogeneous Poisson processes. In fact, the conclusion remains true for nonconstant Bernoulli thinnings of nonhomogeneous Poisson processes. processes. In fact, the conclusion remains true for nonconstant Bernoulli thinnings of nonhomogeneous Poisson processes. It is easy to see that the converse is also true, i.e., if the thinned processes are independent nonhomogeneous Poisson processes, so are the original processes. But if we only suppose the thinned processes are independent, nothing is concerned with their distribution law, the problem of whether or not the original processes are (nonhomogeneous) Poisson becomes interesting and challenging, which is the objective of this paper. It is considerably surprising for us to arrive at the affirmative answer. So far as this problem is concerned, the most work was done under the renewal assumption. For example, Bremaud [1] showed that for arbitrary delayed renewal processes, the existence of a pair of uncorrelated thinned processes is sufficient to guarantee that the original process is Poisson. It is natural that the mathematical tools to solve the problem in this case be typical ones for renewal theory, such as renewal equations and Laplace-Stieltjes transformations. Obviously, they are not available for nonrenewal processes. We find out that the martingale method is the most efficient one to solve this problem in the general case. More precisely, we use mainly the dual predictable projections of point processes. In fact, the distribution law of a point process is determined uniquely by its dual predictable projection (see [5]), and Ma [6] offered us a very useful criterion of independence of jump processes having no common jump time through their dual predictable projections. Based on these results, it is not a long way to arrive at the destination.

A second-order continuous-state-space model for two-dimensional queueing systems is developed in this article. A particular problem is treated but the results can apply to some other two-dimensional queueing problems directly. The generating function for the model is obtained by applying a Riemann boundary value problem and leads to a computationally feasible solution.

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.

A consecutive k−out−of-n: F system is a coherent system of n-ordered components that functions if and only if there is no consecutive run of k failures among the components. Examples of such systems exist in telecommunications, oil pipelines, and integrated circuitry. Most of the research in reliability of consecutive k−out-of-n: F systems assumes that the components function independently of one another. In this paper, we develop a model incorporating positive dependence between adjacent components and show that for k ≥ (n + l)/2, the reliability of the system is a decreasing function of this dependence.

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.

This paper is concerned with the problem of optimally scheduling a multiclass open queueing network with four single-server stations in which dynamic control policies are permitted. Under the assumption that the system is heavily loaded, the original scheduling problem can be approximated by a dynamic control problem involving Brownian motion. We reformulate and solve this problem and, from the interpretation of the solution, we obtain two dynamic scheduling policies for our queueing network. We compare the performance of these policies with two static scheduling policies and a lower bound via simulation. Our results suggest that under either dynamic policy the system, at least when heavily loaded, exhibits the form of resource pooling given by the solution to the approximating control problem. Furthermore, even when lightly loaded the system performs better under the dynamic policies than under either static policy.

The same applies when a success occurs in large fields; in this case, p1 = 0. If at least one success occurs in each oilfield after a certain number of wells are drilled, then we reach a position where the number of undiscovered fields is represented by simple Euler distributions, and the results of Section 4.1 showed that the optimal rule is a one-step look-ahead rule.

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.