Stein's (1970) method of proving limit theorems for sums of dependent random variables is used to derive Poisson approximations for a class of statistics, constructed from finitely exchangeable random variables.

Let be exchangeable random elements of a space and, for I a k-subset of , let XI be a 0–1 function. The statistics studied here are of the form where N is some collection of k -subsets of .

An estimate of the total variation distance between the distributions of W and an appropriate Poisson random variable is derived and is used to give conditions sufficient for W to be asymptotically Poisson. Two applications of these results are presented.

Let X1, X2, …, Xn, … be mutually independent with common CDF F and, for each m, n, let Xm:n be the mth largest among the first n. We consider max1≤n<∞ (X1:n – cn) and the ‘optimal stopping rule' N which maximizes where all l and In particular, we consider and All of these are considered for c ϵ (0,∞) as well as asymptotically as c → 0+.

Queueing systems which can be formulated as Markov renewal processes with basic transitions of three types, ‘arrivals', ‘departures' and ‘feedbacks' are examined. The filtering procedure developed for Markov renewal processes by Çinlar (1969) is applied to such queueing models to show that the queue-length processes embedded at any of the ‘arrival', ‘departure', ‘feedback', ‘input', ‘output' or ‘external' transition epochs are also Markov renewal. In this part we focus attention on the derivation of stationary and limiting distributions (when they exist) for each of the embedded discrete-time processes, the embedded Markov chains. These results are applied to birth–death queues with instantaneous state-dependent feedback including the special cases of M/M/1/N and M/M/1 queues with instantaneous Bernoulli feedback.

It is shown that many properties of Markov processes can be extended to the case where the time parameter is multidimensional (a partially ordered set). This includes Kolmogorov's backward and forward equations, and semi-group treatment of homogeneous processes.

The non-parametric discrete-time estimation of the covariance function R(t) of stationary continuous-time processes is considered. The characteristics of the sampling instants necessary for the consistent estimation of R(t) are explored. A class of covariance estimates is introduced and its asymptotic statistics are derived.

Given two optional positive bounded processes Y and Y′, defined on a probability space , and a non-negative real a, the problem is to maximize the average reward E(YT) among all the stopping times T verifying the following constraint: The problem is solved by Lagrangian saddlepoint techniques in the set of randomized stopping times including the set of stopping times.

In this part we extend and particularise results developed by the author in Part I (pp. 349–375) for a class of queueing systems which can be formulated as Markov renewal processes. We examine those models where the basic transition consists of only two types: ‘arrivals' and ‘departures'. The ‘arrival lobby' and ‘departure lobby' queue-length processes are shown, using the results of Part I to be Markov renewal. Whereas the initial study focused attention on the behaviour of the embedded discrete-time Markov chains, in this paper we examine, in detail, the embedded continuous-time semi-Markov processes. The limiting distributions of the queue-length processes in both continuous and discrete time are derived and interrelationships between them are examined in the case of continuous-time birth–death queues including the M/M/1/M and M/M/1 variants. Results for discrete-time birth–death queues are also derived.

A stochastic process , such that P{Z(0) = 0} = 1, is said to be new better than used (NBU) if, for every x, the first-passage time Tx = inf {t: Z(t) > x} satisfies P{TX > s + t} for everys . In this paper it is shown that many useful processes are NBU. Examples of such processes include processes with shocks and recovery, processes with random repair-times, various Gaver–Miller processes and some strong Markov processes. Applications in reliability theory, queueing, dams, inventory and electrical activity of neurons are indicated. It is shown that various waiting times for clusters of events and for short and wide gaps in some renewal processes are NBU random variables. The NBU property of processes and random variables can be used to obtain bounds on various probabilistic quantities of interest; this is illustrated numerically.

We present new results based on novel techniques for the problem of characterizing the waiting-time distribution in a class of queueing networks. We give effective methods for computing, for each of possibly several job-classes, the second moment of the equilibrium waiting time for closed systems as well as for open systems. Both open and closed systems have a CPU operating under the processor-sharing (‘time-slicing') discipline in which service-time requirements may depend on job-class. The closed system also includes a bank of terminals grouped according to job-classes, with the class structure allowing distinctions in the user's behavior in the terminal. In the contrasting open system, the job streams submitted to the CPU are Poisson with rate parameters dependent on job-classes.

Our results are exact for the open system and, for the closed system, in the form of an asymptotic series in inverse powers of a parameter N. In fact, the result for open networks is simply the first term in the asymptotic series. For larger closed systems, the parameter N is larger and thus fewer terms of the series need be computed to achieve a desired degree of accuracy. The complexity of the calculations for the asymptotic expansions is polynomial in number of classes and, importantly, independent of the class populations. Only the results on the single-class systems, closed and open, were previously known.

We consider two types of particles performing simple random walks on the integers. When two particles of different types collide they are immediately annihilated. All particles of one type are started off to the left of the origin, and all particles of the other type are started off to the right of the origin. We determine the asymptotic rate of annihilations and the fluctuations, around this rate, of the numbers annihilated at large times.

We study the queue GI/M/s with customers of m different types. An arriving customer is of type i with probability pi and the types of different customers are independent. A customer of type i requires a service time which is exponentially distributed with parameter bi. This model is equivalent to the queue GI/Hm/s, where Hm denotes a mixture of m different exponential distributions. We are primarily interested in the distributions of waiting times and queue lengths. Using a probabilistic argument we reduce the problem to the solution of a system of Wiener-Hopf-type equations. This system is solved by a factorization method. Thus we obtain explicit results for the stationary distributions of waiting times and queue lengths.

A new approach to the optimal control of the service rate in M/G/1 queues is introduced using the method of phases. Each customer's work requirement is approximated by a random number of exponential phases with (possibly) different parameters (a generalized hyper-Erlang distribution). Using a semi-Markov decision-process formulation, we establish monotonicity properties of optimal policies for the finite-horizon problem, by induction on the horizon length. The analysis is then extended to the discounted infinite-horizon and the long-run average-return problems. In contrast to the models in previous papers, our model is appropriate for situations where the system controller has partial information about the work requirement of a customer, specifically the number of phases (tasks) to be performed. Because it requires a multidimensional state description, the analysis of the phase-type control model may be viewed as a first step toward the solution of control models for networks of queues.

This paper obtains the stationary joint distribution of a customer's sojourn times along an overtake-free path in a closed multiclass Jackson network. The distribution has a simple representation in terms of the product form distribution for the state of the network at an arrival instant.

A Poisson stream of arrival rate λI and service-time distribution AI(x) has preempt/resume priority over a second stream of rate λII and distribution AII(x). Abundant theoretical results exist for this system, but severe numerical difficulties have made many descriptive distributions unavailable. Moreover, the distribution of total time in system of low-priority customers has not been discussed theoretically. It is shown that the waiting-time sequences of such customers before first entry into service is a Lindley process modified by replacement. This leads to the total time distribution needed. A variety of descriptive distributions, transient and stationary, is obtained numerically via the Laguerre transform method.

We present some general results related to first-passage percolation. These results involve families of random variables arranged in independent subfamilies. Applications are given to the study of random networks and to first-passage percolation.

Waiting-time distributions for M/G/1 systems with priority dependent on class, order of arrival, service length, etc., are difficult to obtain. For single-server multipurpose processors the difficulties are compounded. A certain ergodic post-arrival depletion time is shown to be a true maximum for all delay times of interest. Explicit numerical evaluation of the distribution of this time is available. A heavy-traffic distribution for this time is shown to provide a simple and useful engineering tool with good results and insensitivity to service-time distribution even at modest traffic intensity levels. The relationship to the diffusion approximation for heavy traffic is described.

This paper considers the two-stage cyclic queueing model consisting of one general (G) and one exponential (M) server. The strong connection between the present model and the M/G/1 model (with finite waiting room) is exploited to yield the joint distribution of the successive response times of a customer at the G queue and the M queue. This result reveals a surprising phenomenon: in general there is a difference between the joint distribution of the two successive response times at (first) the G queue and (then) the M queue, and the joint distribution of the two successive response times at (first) the M queue and (then) the G queue.

Another associated result is an expression for the cycle-time distribution. Special consideration is given to the case that the number of customers in the system tends to ∞, while the mean service times tend to 0 at an inversely proportional rate.

A particular queue, the general arrival, general service-time, infinite-server queue (GA/G/∞), is introduced and certain of its properties studied. Motivated by a life situation in which the interarrival times for service converge to 0, a different sort of regularity condition (involving a tail property of random measures) is imposed on the arrival process to prove various limit theorems. There are similarities to heavy-traffic theory.

It is proved that, for a large class of stable stationary queueing systems with renewal arrival processes and without losses, a necessary condition for the departure process also to be a renewal process is that its interval distribution be the same as that of the arrival process. This result is then applied to the classical GI/G/s queueing systems. In particular, alternative proofs of known characterizations of the M/G/1 and GI/M/1 systems are given, as well as a characterization of the GI/G/∞ system. In the course of the proofs, sufficient conditions for the existence of all the moments of the stationary queue-size distributions of both the GI/G/1 and GI/G/∞ systems are derived.

Queues with delayed feedback have been little studied in queueing theory. Presented here is a rather complete discussion of such problems including queue length processes, busy period processes and several customer flow processes (e.g., departure processes). The case in which the delay mechanism is an M-server queue is studied in detail but it is shown later that many of the results carry over to a more general delay mechanism.