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.

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 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.

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.

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.

There is a growing interest in networks of queues with customers and signals. The signals in these models carry commands to the service nodes and trigger customers to move instantaneously within the network. In this note we consider networks of queues with signals and random triggering times; that is, when a signal arrives at a node, it takes a random amount of time to trigger a customer to move with distribution depending on the source of the signal. By appropriately choosing the triggering times, we can obtain network models such that a signal changes a customer's service time distribution – for example, the signal increases or decreases the service time of a customer. We show that the stationary distribution of this model has a product form solution.

This note extends a recently proposed approximation for the loss probability to the batch-arrival Finite-buffer queues with complete rejection. Also, a condition is stated under which the approximation is exact.

Parallel processing systems with jobs structured as random graphs, where the nodes correspond to executable tasks and the directed edges to precedence constraints, are studied from a queueing theoretic point of view under general stationarity assumptions on the job flows. Jobs need to have their tasks processed non-preemptively by a set of uniform processors. Simple, natural greedy schemes of allocating processors to tasks are shown to asymptotically minimize the long-term average execution time per job. The stability condition for this queueing system is specified, and greedy allocation schemes are shown to stabilize the system under the maximum possible job arrival rate. Some recurrence properties of the system state are also established.

The paper considers representations of network reliability measures as the mean value of a random variable defined on the trajectories of a certain Markov process and investigates utility of such formulae for Monte Carlo (MC) estimating. Such an MC estimator is called (ε,δ)-polynomial if its relative error is less than ε with probability >1 – δ, for any sample size equal to or greater than a polynomial of ε-1, δ-1, and the size of the network. One of the main results: The suggested MC estimator for the disconnectedness probability of a multiterminal network is (ε,δ)-polynomial, under a certain natural condition on the edge failure probabilities. The method applies also to estimating the percolation critical point and certain equilibrium characteristics of renewal networks.

Frequency measurements by means of zero-crossing-counting device can be disturbed by noise in many different ways, such as fluctuating zero level or extra zero crossings. This paper presents a mathematical theory for analysis of the effect of noise on a zero-crossing counter. Comparisons are made with experiments made on the production of clicks in a zero-crossing-detecting FM receiver.

A multi-period model of interruptible electric power service that includes early notification may be described as a stochastic control problem: whom to notify when. When customer interruption losses are multiplicative or submodular, an optimal priority ordering exists, allowing for a simple notification policy.

This paper gives fast and reliable algorithms for the numerical evaluation of the incomplete gamma functions and for auxiliary functions, such as functions related with the gamma function and error function. All these functions are of basic importance in applied probability problems.