We investigate the dependence induced among multiple Markov chains when they are simulated in parallel using a shared Poisson stream of potential event occurrences. One expects this dependence to facilitate comparisons among systems; our results support this intuition. We give conditions on the transition structure of the individual chains implying that the coupled process is an associated Markov chain. Association implies that variance is reduced in comparing increasing functions of the chains, relative to independent simulations, through a routine argument. We also give an apparently new application of association to the problem of selecting the better of two systems from limited data. Under conditions, the probability of incorrect selection is asymptotically smaller when the systems compared are associated than when they are independent. This suggests a further advantage to linking multiple systems through parallel simulation.

We consider time-inhomogeneous Markov chains on a finite state-space, whose transition probabilitiespij(t) = cijε(t)Vij are proportional to powers of a vanishing small parameter ε(t). We determine the precise relationship between this chain and the corresponding time-homogeneous chains pij= cijε(t)vij, as ε ↘ 0. Let {} be the steady-state distribution of this time-homogeneous chain. We characterize the orders {ηι} in = θ(εηι). We show that if ε(t) ↘ 0 slowly enough, then the timewise occupation measures βι := sup { q > 0 | Prob(x(t) = i) = + ∞}, called the recurrence orders, satisfy βi — βj = ηj — ηi. Moreover, : = { ηι|ηι = minj} is the set of ground states of the time-homogeneous chain, then x(t) → . in an appropriate sense, whenever η(t) is “cooled” slowly. We also show that there exists a critical ρ* such that x(t) → if and only if = + ∞. We characterize this critical rate as ρ* = max.min min max. Finally, we provide a graph algorithm for determining the orders [ηi] [βi] and the critical rate ρ*.

We analyze a standard algorithm for sampling m items without replacement from a computer file of n records. The algorithm repeatedly selects a record at random from the file, rejecting records that have previously been selected, until m records are obtained. The running time of the algorithm has two components: a rejection component and a search component. We show that the probability distribution of the rejection component undergoes an infinite series of phase transitions, depending on the order of magnitude of m relative to n. We identify an infinite number of ranges of m, each with a different behavior. The rejection component is distributed as a linear combination of Poisson-like random variables. The search component is customarily done using a hash table with separate chaining. The analysis of the hashing scheme in this problem differs from previous hashing analyses, as the number of lookups in the hash table for each insertion has a geometric distribution. We show that the average overall cost of searching is asymptotically linear with only two phase transitions in the coefficient of linearity.

Let X1,…, Xn, be indicator random variables, and set We present a method for estimating the distribution of W in settings where W has an approximately Poisson distribution. Our method is shown to yield estimates significantly better than straight Poisson estimates when applied to Bernoulli convolutions, urn models, the circular k of n: F system, and a matching problem. Error bounds are given.

We consider a closed queueing network with a fixed number of customers, where a single server moves cyclically between N stations, rending service in each station according to some given discipline (Gated, Exhaustive, or the Globally Gated regime). When service of a customer (message) ends in station j, it is routed to station k with probability Pjk. We derive explicit expressions for the probability generating function and the moments of the number of customers at the various queues at polling instants and calculate the mean cycle duration and throughput for each service discipline. We then obtain the first moments of the queues' length at an arbitrary point in time. A few examples are given to illustrate the analysis. Finally, we address the problem of optimal dynamic control of the order of stations to be served.

We consider a controlled queueing system that is a generalization of the M/M/c/W queue. There are m types of customers that arrive according to independent Poisson processes. Service times are exponential and independent and do not depend on the customer type. There is room in the system for a total of N customers; if there are N customers in the system, new arrivals are lost. Type j customers are more profitable than type (j + 1 ) customers, j = 2,…, m —, and type 1 customers are at least as profitable as type 2 customers. The allowed control is to accept or reject customers at arrival. No preemption of customers in service is allowed. The goal is to maximize the average reward per unit of time subject to a constraint that the blocking probability of type 1 customers is no greater than a given level.

For an M/M/c/c system without a constraint, Miller [12] proved that an optimal policy has a simple threshold structure. We show that, for the constrained problem described above, an optimal policy has a similar structure, but one of the thresholds might have to be randomized. We also derive an algorithm that constructs an optimal policy and describe other forms of optimal policies.

In the context of team recruitment, we discuss an optimal multiple stopping problem for an infinite independent and identically distributed sequence, with general reward function and constant observation cost. We establish the existence and nature of an optimal stopping rule. For the particular case where team quality is governed by the fitness of the weakest member, we show that the recruiter should be more discriminating with either a better, or a larger, group of appointees in hand.

We consider stopping times associated with sequences of non-negative random variables and Poisson processes. With sufficient conditions on the dependence property between the sequences of non-negative random variables (or the Poisson processes) and the stopping times, we develop easily computable stochastic bounds for the stopping times. We use these bounds to develop approximations within the class of generalized phase-type distribution functions for arbitrary distribution functions. The computational tractability of generalized phase-type distribution functions facilitate the computational analysis of complex stochastic systems using these approximate distribution functions. Applications of these approximations to renewal processes are illustrated.

Construction of a certain class of component tests for verification of series system reliability requires the use of some properties of the Poisson distribution that are not commonly known or used. This paper states and proves these results.

We consider preemptive scheduling on parallel machines where processing times of jobs are i.i.d. but jobs may already have received distinct amounts of service. We show that when processing times are increasing in likelihood ratio, SEPT (shortest expected [remaining] processing time first) stochastically minimizes any increasing and Schur-concave function of the job completion times. The same result holds when processing times are exponential with possibly different means.

Consider the problem in which impatient customers have to be routed to or scheduled from a set of parallel homogeneous service stations with finite buffer capacities. When the service times and the deadlines of customers are exponentially distributed, we identify the control policies that stochastically minimize the total number of losses by any time t. We study systems with deadlines to the beginning or to the end of service. The results regarding the individual types of losses, i.e., losses due to deadline misses and losses due to buffer overflow, vary across different systems. In all cases we state explicitly the properties and the limitations of the optimal control policies.

Tasks belonging to N classes arrive for processing in a multi-server facility. Each arriving task has a due date (deterministic or random) associated with the completion of its service. If the service of a task is completed at a time other than the task's due date, an earliness or tardiness penalty is incurred. We determine properties of dynamic nonidling nonpreemptive and dynamic nonidling preemptive scheduling strategies that minimize an infinite horizon expected discounted cost due to the earliness and tardiness penalties. We provide examples that illustrate the properties of the optimal strategies.

Recently, the well-studied consecutive-2 (out-of-n) system has been extended to the consecutive-2 link system, in which links are also part of the system and can be failed. Furthermore, links of the two types i → i + 1 and i → i + 2 are recognized to be different entities. We study the optimal assembly problem for the link system and obtain results that generalize previous results on the consecutive-2 system.

Most of the previous work on (s, S) inventory systems assumes that lead times for orders are such that orders never cross in time; i.e., the arrival of orders follows the same sequence as the placement of the orders. In this paper we consider more general mechanisms for random lead times. Because the introduction of a general random lead time mechanism makes the system essentially intractable for most performance measures of interest, simulation is a. natural candidate for estimating performance and/or optimizing the system. Two important issues in simulation are the stability and ergodicity of the system. Therefore, we first study some theoretical implications of the mechanism by providing conditions for which the system is stable and Harris ergodic, with the accompanying wide-sense regenerative properties. We then consider the problem of gradient estimation during simulation. Using the technique of perturbation analysis, we derive sample path-based gradient estimates for the finite-horizon average cost per period with respect to the parameters s and S and give a sample path proof of unbiasedness. We then show how stability and ergodicity can be used to simplify the estimators in the limiting infinite-horizon case and to establish strong consistency of the resulting estimators.

A consecutive-k-out-of-n: F system is represented by a digraph in which the nodes and certain of the links may fail. System reliability is studied.

This article considers separation for a birth-death process on a finite state space S = [1,2,…, N]. Separation is defined by si(t) = 1 – minj∈sPij(t)/πj, as in Fill [5,6], where Pij(t) denotes the transition probabilities of the birth-death process and πj the stationary probabilities. Separation is a measure of nonstationarity of Markov chains and provides an upper bound of the variation distance. Easily computable upper bounds for si-(t) are given, which consist of simple exponential functions whose parameters are the eigenvalues of the infinitesimal generator or its submatrices of the birth-death process.

Using the Laplace transform, we characterize, by means of necessary and sufficient conditions, the property that two life distributions are ordered in the sense of stochastic ordering, hazard rate ordering, backward hazard rate ordering, and likelihood ratio ordering.

The zero capacity M/M/1 queue with returning customers is examined. Performance measures are calculated and an imposed optimal return rate is determined for customers who return until served. The optimal rate is then calculated for an arbitrary customer as a function of the return rate of the other customers, and limiting cases are analyzed. The other customers may then adjust their return rate each time the arbitrary customer adjusts his/hers until a fixed point solution is obtained. A comparison between systems is made.

Necessary and sufficient conditions for the regularity and recurrence of right-skip-free Markov chains are established. These generalize classical results for the case of birth-and-death processes. Expressions for the general right eigenvectors of such chains are also given.

Neutron scatter in a homogeneous solid is modelled as a one-dimensional i.i.d. random walk with killing. Importance sampling is used to estimate the extremely small probability that the random walk crosses a large level before killing occurs. The theory of large deviations provides insight into the selection of the probability measure used in the simulations. A sample problem demonstrates the variance reduction possible when this technique is used.