Suppose that we are given a set of n elements which are to be arranged in some order. At each unit of time a request is made to retrieve one of these elements — the ith being requested with probability Pi. We show that the rule which always moves the requested element one closer to the front of the line minimizes the average position of the element requested among a wide class of rules for all probability vectors of the form P1 = p, P2= · ·· = Pn = (1 – p)/(n − 1). We also consider the above problem when the decision-maker is allowed to utilize such rules as ‘only make a change if the same element has been requested k times in a row', and show that as k approaches infinity we can do as well as if we knew the values of the Pi.

One probability measure is less than or equal to another in the sense of UCSO (uniform conditional stochastic order) if a standard form of stochastic order holds for each pair of conditional probability measures obtained by conditioning on appropriate subsets. UCSO can be applied to the comparison of lifetime distributions or the comparison of decisions under uncertainty when there may be reductions in the set of possible outcomes. When densities or probability mass functions exist on the real line, then the main version of UCSO is shown to be equivalent to the MLR (monotone likelihood ratio) property. UCSO is shown to be preserved by some standard probability operations and not by others.

It is shown that the limiting random variable W(si) of an irregular branching process with infinite mean, defined in [5], has a continuous and positive distribution on {0 < W(si) < ∞}. This implies that for all branching processes (Zn) with infinite mean there exists a function U such that the distribution of V = limnU(Zn)e–n a.s. is continuous, positive and finite on the set of non-extinction. A kind of law of large numbers for sequences of independent copies of W(si) is derived.

In recent publications of Hadwiger, Bokowski, and Wills it has been shown that it is possible to evaluate the average distance between a fixed and a randomly distributed convex set in terms of the mean projection measures of these sets. In the present note it is pointed out that these and more general results can be obtained from a theorem concerning the relationship between integrals over arbitrary measure spaces and corresponding Lebesgue–Stieltjes integrals.

Sufficient conditions are derived for ergodicity of the two-dimensional process of binary variables discussed by Galbraith and Walley (1976).

The cumulative amount of time that a regenerative or semi-stationary process exceeds a high level and other measures of these exceedances are considered as special cases of a non-decreasing stochastic process of partial sums. We present necessary and sufficient conditions for these exceedance processes to converge in distribution to Poisson processes or processes with stationary independent non-negative increments as the level goes to infinity. We apply our results to random walks, M/M/s queues, and thinnings of point processes.

A collection of jobs is to be processed by a single machine. The amount of processing required by each job is a random variable with a known probability distribution. The jobs must be processed in a manner which is consistent with a precedence relation but the machine is free to switch from one job to another at any time; such switches are costly, however. This paper discusses conditions under which there is an optimal strategy for allocating the machine to the jobs which is given by a fixed permutation of the jobs indicating in which order they should be processed. When this is so, existing algorithms may be helpful in giving the best job ordering.

A variant of the Trotter–Kato theorem due to Kurtz (1969) is used to give new and simpler proofs of functional central limit theorems for Markov processes. Applications include theorems of Bellman and Harris (1951), Stone (1961), Karlin and McGregor (1965), Gihman and Skorokhod (1972) and Rosenkrantz (1975). In addition our methods yield a novel counterexample to the so-called ‘diffusion approximation'.

Let L(t) be the random variable which represents the minimum of length of gaps generated by random packing of unit intervals into [0, t]. We have with Using this equation the asymptotic behaviour of P(L(x)≧h) is discussed.

For a Markov chain with optional transitions, except for those to an arbitrary fixed state accessible from all others, Kesten and Spitzer proved the existence of a control policy which minimized the expected time to reach the fixed state and for constructing an optimal policy, proposed an algorithm which works in certain cases. For the algorithm to work they gave a sufficient condition which breaks down if there are countably many states and the minimal hitting time is bounded. We propose a modified algorithm which is shown to work under a weaker sufficient condition. In the bounded case with countably many states, the proposed sufficient condition is not necessary but a similar condition is. In the unbounded case as well as when the state space is finite, the proposed condition is shown to be both necessary and sufficient for the original Kesten–Spitzer algorithm to work. A new iterative algorithm which can be used in all cases is given.

A general formula is obtained for the variance of the maximum of partial sums of n-exchangeable random variables, derived from a result of Spitzer's. The formula is applied in particular to obtain the variance of the maximum of adjusted rescaled partial sums of normal summands. This is of direct relevance to the Hurst effect.

Consider a two-component parallel system. There is a stockpile of n spares, spare i having lifetime Xi, exponentially distributed with rate µi. The system breaks down when neither component functions. Every time a spare expires it has to be replaced, to avoid system breakdown. We investigate the policies which maximize the expected lifetime of the system using these n spares.

A diffusion model is used to find heavy traffic approximate autocorrelation functions for several variables in queueing systems (i.e. for waiting time, system time, number in system and unfinished work). A table is given by which correlations can easily be found for each variable in any GI/G/1 queue. Further, the infinite sum or integral of the autocorrelations is also found, and the spectral density function. The sum has applications in statistical analysis of queues.

Extensive comparisons of approximate and exact correlations and their sums are reported, particularly for waiting times and system times, but also including number in system in M/M/1 queues. In general the correlations have similar accuracy to the probability distributions found by diffusion approximations. The percentage error is less for number in system than for waiting time.

Many random variables arising in problems of geometric probability have intractable densities, and it is very difficult to find probabilities or percentage points based on these densities. A simple approximation, a generalization of the chi-square distribution, is suggested, to approximate such densities; the approximation uses the first three moments. These may be theoretically derived, or may be obtained from Monte Carlo sampling.

The approximation is illustrated on random variables (the area, the perimeter, and the number of sides) associated with random polygons arising from two processes in the plane. Where it can be checked theoretically, the approximation gives good results. It is compared also with Pearson curve fits to the densities.

The ‘snake' theorem, i.e., the weak convergence of the complex quantogram, is studied. The moment assumption is weakened by a strong approximation result of the author.

A controlled Markov chain with finite state space has transition probabilities which depend on an unknown parameter α lying in a known finite set A. For each α, a stationary control law ϕ α is given. This paper develops a control scheme whereby at each stage t a parameter α t is chosen at random from among those parameters which nearly maximize the log likelihood function, and the control ut is chosen according to the control law ϕ αt. It is proved that this algorithm leads to identification of the true α under conditions weaker than any previously considered.

In this paper an axiomatic development of multistate systems is presented. Three types of coherence based on the strength of the relevancy axiom are studied. The strongest of these has been investigated previously by El-Neweihi, Proschan, and Sethuraman [3]. One of the weaker types of coherence permits wider applicability to real life situations without sacrificing any of the mathematical results obtained by El-Neweihi, Proschan, and Sethuraman. The concept of system performance is formalized through expected utility and the effect of component improvement on system performance is studied using a generalization of Birnbaum's reliability importance.

Starting from the theory of point processes the concept of a process with an embedded marked point process is defined. It is shown that the known formula expressing the relation between the stationary and synchronous version of a regenerative process remains valid without the assumption of independence of cycles. General formulae for stationary availability and interval reliability of complex systems with repair are also obtained. In this way generalizations of Keilson's results for Markovian systems and Ross's results for systems with separately maintained elements are presented. The formulae are applied to a two-unit parallel system with a single repair facility.

We consider closed networks of interconnected service centers with multiple types of customers and multiple classes, whose stationary state probabilities at arbitrary times have a product form. A customer can change its class but not its type as it traverses the network. We show that the stationary state probabilities at instants at which customers of a particular type arrive at a particular service center and enter a particular class are equal to the stationary state probabilities at arbitrary times for the network with one less customer of that type. Applications of this result are given.

Let X(t) be a continuous, homogeneous stochastic process with independent increments characterized by a, σ, M, N in the Lévy representation formula. In this note we obtain the Lévy canonical representation of the characteristic function of a stochastic integral (in the sense of convergence in probability) of the form (where υ(t) is a non-decreasing, non-negative and left-continuous function) in terms of υ(t), a, σ, M, N.