This work considers items (e.g. books, files) arranged in an array (e.g. shelf, tape) with N positions and assumes that items are requested according to a Markov chain (possibly, of higher order). After use, the requested item is returned to the leftmost position of the array. Successive applications of the procedure above give rise to a Markov chain on permutations. For equally likely items, the number of requests that makes this Markov chain close to its stationary state is estimated. To achieve that, a coupling argument and the total variation distance are used. Finally, for non-equally likely items and so-called p-correlated requests, the coupling time is presented as a function of the coupling time when requests are independent.

The first-passage problem for the one-dimensional Wiener process with drift in the presence of elastic boundaries is considered. We use the Kolmogorov backward equation with corresponding boundary conditions to derive explicit closed-form expressions for the expected value and the variance of the first-passage time. Special cases with pure absorbing and/or reflecting barriers arise for a certain choice of a parameter constellation.

In this paper, an optimal maintenance model for standby systems is studied. An inspection–repair–replacement policy is employed. Assume that the state of the system can only be determined through an inspection which may incorrectly identify the system state. After each inspection, if the system is identified as in the down state, a repair action will be taken. It will be replaced some time later by a new and identical one. The problem is to determine an optimal policy so that the availability of the system is high enough at any time and the long-run expected cost per unit time is minimized. An explicit expression for the long-run expected cost per unit time is derived. For a geometric model, a simple algorithm for the determination of an optimal solution is suggested.

This paper focuses on the stability of open queueing systems under stationary ergodic assumptions. It defines a set of conditions, the monotone separable framework, ensuring that the stability region is given by the following saturation rule: ‘saturate' the queues which are fed by the external arrival stream; look at the ‘intensity' μ of the departure stream in this saturated system; then stability holds whenever the intensity of the arrival process, say λ satisfies the condition λ < μ, whereas the network is unstable if λ > μ. Whenever the stability condition is satisfied, it is also shown that certain state variables associated with the network admit a finite stationary regime which is constructed pathwise using a Loynes-type backward argument. This framework involves two main pathwise properties, external monotonicity and separability, which are satisfied by several classical queueing networks. The main tool for the proof of this rule is subadditive ergodic theory. It is shown that, for various problems, the proposed method provides an alternative to the methods based on Harris recurrence and regeneration; this is particularly true in the Markov case, where we show that the distributional assumptions commonly made on service or arrival times so as to ensure Harris recurrence can in fact be relaxed.

The Laplace transform of the probability distribution of the end-to-end delay in tandem networks is obtained where the first and/or second queue are G-queues, i.e. they have negative arrivals. For the most general case the method is based on the solution of a boundary value problem on a closed contour in the complex plane, which itself reduces to the solution of a Fredholm integral equation of the second kind. We also consider the dependence or independence of the sojourn times at each queue in the two special cases where only one of the queues is a G-queue, the other having no negative arrivals.

The cumulative distribution of the finite sum of the binary sequence of order k is studied and some of its applications discussed. Certain properties of this sequence are investigated and uniformly superior bounds for the cumulative distribution under minimal information on the ‘success' probabilities are derived.

This paper introduces a new form of local balance and the corresponding product-form results. It is shown that these new product-form results allow capacity constraints at the stations of a queueing network without reversibility assumptions and without special blocking protocols. In particular, exact product-form results for heavily loaded queueing networks are obtained.

Harlow et al. (1983) have given a recursive formula which is fundamental for computing the bundle strength distribution under a general class of load sharing rules called monotone load sharing rules. As the bundle size increases, the formula becomes prohibitively complex and, by itself, does not give much insight into the relationship of the assumed load sharing rule to the overall strength distribution. In this paper, an algorithm is given which gives some additional insight into this relationship. Here it is shown how to explicitly compute the bundle strength survival distribution by using a new type of graph called the loading diagram. The graph is parallel in structure and recursive in nature and so would appear to lend itself to large-scale computation. In addition, the graph has an interesting property (which we refer to as the cancellation property) which is related to the asymptotics of the Weibull as a minimum stable law.

We first introduce a Lorenz ordering family of distributions which are related to the gamma distribution, and then prove that the weak convergence within this family is equivalent to the convergence of each moment sequence of positive orders to the corresponding moment of the limiting distribution.

We consider the problem of reorganizing a linear list, when the individual queries consist of accesses to a subset of the elements stored, as opposed to the individual elements themselves. In this paper, which to our knowledge represents the first reported result in this model of query processing, we first propose a simple model for a query generator which emits set queries. Subsequently, we present extensions to the classical move-to-front (MTF) and transposition (TR) rules under this generalized query generation mechanism and analyze their performance.

Hunt and Kurtz [9] consider a loss network as the number of circuits and the offered traffics become large. They prove a functional law of large numbers for such a network and illustrate their results with some simple examples. In this paper we apply their results to slightly more complicated examples to illustrate other, and sometimes surprising, behaviour of the loss networks in heavy traffic. The networks we consider operate under somewhat unusual routing rules but this is to enable us to produce the behaviour in networks with only a few links. In larger, real-world networks it is likely that much more ‘natural' and intuitively appealing routing rules could produce similar undesirable behaviour.

A variety of performance measures of a GI/G/1 queue are explicitly related to the idle-period distribution of the queue, suggesting that the system analysis can be accomplished by the analysis of the idle period. However, the ‘stand-alone' relationship for the idle-period distribution of the GI/G/1 queue (i.e. the counterpart of Lindley's equation) has not been found in the literature. In this paper we develop a non-linear integral equation for the idle period distribution of the GI/G/1 queue. We also show that this non-linear system defines a unique solution. This development makes possible the analysis of the GI/G/1 queue in a different perspective.

It is shown that the critical two-level (2, d, 1, 1)-superprocess is persistent in dimensions d greater than 4. This complements the extinction result of Wu (1994) and implies that the critical dimension is 4.

Intersymbol and cochannel interference in a communications channel can often be modelled as the sum of an infinite series of random variables with weights which decay fairly rapidly. Frequently, this yields a random variable which is singular but non-atomic. The Hausdorff dimension of the distribution is estimated and methods for calculating expectations are studied. A connection is observed between the dimension and the complexity of the calculation of an expectation.

Formulas for the asymptotic failure rate, long-term average availability, and the limiting distribution of the number of long ‘outages' are obtained for a general class of two-state reliability models for maintained systems. The results extend known formulas for alternating renewal processes to a wider class of point processes that includes sequences of dependent or non-identically distributed operating and repair times.

In this paper, we derive the MacLaurin series of the mean waiting time in light traffic for a GI/G/1 queue. The light traffic is defined by random thinning of the arrival process. The MacLaurin series is derived with respect to the admission probability, and we prove that it has a positive radius of convergence. In the numerical examples, we use the MacLaurin series to approximate the mean waiting time beyond light traffic by means of Padé approximation.

We give simple sufficient conditions for integrability of continuous-time Markov chains in terms of their infinitesimal parameters. Similar conditions for regularity are stated first, and a simple proof given.

The quadratic mean of the deviation between the probability content and the interior point proportion of a random convex hull in is investigated. We obtain, in particular, an explicit and distribution-independent bound.

A trivariate stochastic process is considered, describing a sequence of random shocks {Xn} at random intervals {Yn} with random system state {Jn}. The triviariate stochastic process satisfies a Markov renewal property in that the magnitude of shocks and the shock intervals are correlated pairwise and the corresponding joint distributions are affected by transitions of the system state which occur after each shock according to a Markov chain. Of interest is a system lifetime terminated whenever a shock magnitude exceeds a prespecified level z. The distribution of system lifetime, its moments and a related exponential limit theorem are derived explicitly. A similar transform analysis is conducted for a second type of system lifetime with system failures caused by the cumulative magnitude of shocks exceeding a fixed level z.

We examine a family of supercritical branching processes and compute the density of the limiting random variable, W, for their normalized population size. In this example the left tail of W decays exponentially and there is no oscillation in this tail as typically observed. The branching process is embedded in the n-adic rational random walk approximation to Brownian motion on [0, 1]. This connection allows the explicit computation of the density of W.