After preliminaries on Markov chains, supermartingales and potential theory (Section 1), the energy of a potential supermartingale generated by an increasing process is defined. The paper examines some properties of the energy of potentials of the form Ut = p(Xt) where p is a purely excessive function (which is also a potential of a charge) for a Markov chain (Xt). Also, the mutual energy of two potentials associated with the same Markov chain is discussed. Finally, several applications and examples are worked out in detail (Section 3).

Let t ≥ 0 be a Markov transition probability semigroup on a general space satisfying a suitable φ-irreducibility condition. We show the existence of (i) a decay parameter λ ≥ 0 which is a common abscissa of convergence of the integrals ƒ estPt (x, A) dt for almost all x and all suitable A, (ii) a natural classification into λ-positive, λ-null and λ-transient cases. Moreover this classification is completely determined by any one of the h-skeleton chains of (Pt). We study the convergence of eλtPt(x, A) in the λ-positive case, and show that the limit f(X)π(A) (where f and π are the unique λ-invariant function and measure, normalized so that π(f) = 1) is reached at a uniform exponential rate of convergence, i.e. ||eλtPt(x, ·)-f(x)π(·)||f = O (e−αt) for some α > 0 and almost all x if there is a π-positive set such that the convergence is exponentially fast on this set. These results are used to deduce conditions for (Pt) to have quasi-stationary distributions.

Suppose two alternative designs for a stochastic system are to be compared. These two systems can be simulated independently or dependently. This paper presents a method for comparing two regenerative stochastic processes in a dependent fashion using common random numbers. A set of sufficient conditions is given that guarantees that the dependent simulations will produce a variance reduction over independent simulations. Numerical examples for a variety of simple stochastic models are included which illustrate the variance reduction achieved.

The concept of ‘coefficient of ergodicity’, τ(P), for a finite stochastic matrix P, is developed from a standpoint more general and less standard than hitherto, albeit synthesized from ideas in existing literature. Several versions of such a coefficient are studied theoretically and by numerical examples, and usefulness in applications compared from viewpoints which include the degree to which extension to more general matrices is possible. Attention is given to the less familiar spectrum localization property: where λ is any non-unit eigenvalue of P. The essential purpose is exposition and unification, with the aid of simple informal proofs.

Let denote the empirical distribution obtained from a sequence of i.i.d. -valued random vectors with common distribution P. If is a class of Borel subsets of then we say that it forms a Glivenko–Cantelli class for P if In this paper we describe a simple technique for identifying such classes, based on the idea of uniformity classes for setwise convergence. Classes for which the method proves successful include the closed half-spaces, closed balls, and the class of all convex subsets of .

We showed in [2] that if an object of initial size x (x large) is subjected to a succession of random partitions, then the object is decomposed into a large number of terminal cells, each of relatively small size, where if Z(x, B) denotes the number of such cells whose sizes are points in the set B, then there exists c, (0 < ≦ 1), such that Z(x, B)x−c converges in probability, as x → ∞, to a random variable W. We show here that if a parent object of size x produces k offspring of sizes y1, y2, ···, yk and if for each k x - y1 - y2 - ··· - yk (the ‘waste’ or the ‘cover’, depending on the point of view) is relatively small, then for each n the nth cumulant, Ψn (x, B), of Z(x, B) satisfies Ψn (x, B)x-c → κn (B), as x → ∞, for some κn(B). Thus, writing N = xc, Z(x, B) has approximately the same distribution as the sum of N independent and identically distributed random variables (The determination of the distribution of the individual appears to be a difficult problem.) The theory also applies when an object of moderate size is broken down into very fine particles or granules.

In an earlier paper (Bartholomew (1977)) the problem of maintaining a grade (or age) structure by controlling the recruitment flows was discussed. Here we carry out a parallel analysis for the case where control is by promotion. We show how to calculate the probability that a structure can be maintained and investigate the performance of several strategies for keeping a structure as near as possible to that desired. As before, the results demonstrate the limitations of a deterministic analysis of the problem.

Random closed sets (in Matheron's sense) which are a.s. compact convex and contain the origin are considered. The totality of such random closed sets are closed under the Minkowski addition and we can define the concept of infinite divisibility with respect to Minkowski addition of random compact convex sets. Using a generalized notion of Laplace transformations we get Lévy-type canonical representations of infinitely divisible random compact convex sets. Isotropic and stable cases are also considered. Finally we get several mean formulas of Minkowski functionals of infinitely divisible random compact convex sets in terms of their Lévy spectral measures.

Let Un be the time between the nth and (n + 1)th arrivals to a single-server queuing system, and Vn the nth arrival's service time. There are quite a few models in which {Un, Vn, n ≥ 1} is a regenerative sequence. In this paper, some light and heavy traffic limit theorems are proved solely under this assumption; some of the light traffic results, and all the heavy traffic results, are new for two such models treated earlier by the author; and all the results are new for the semi-Markov queuing model.

In the last three sections, the results are applied to a single-server queue whose input is the output of a G/G/1 queue functioning in light traffic.

This paper considers a queueing system consisting of two single-server queues in series, in which the service times of an arbitrary customer at both queues are identical. Customers arrive at the first queue according to a Poisson process.

Of this model, which is of importance in modern network design, a rather complete analysis will be given. The results include necessary and sufficient conditions for stationarity of the tandem system, expressions for the joint stationary distributions of the actual waiting times at both queues and of the virtual waiting times at both queues, and explicit expressions (i.e., not in transform form) for the stationary distributions of the sojourn times and of the actual and virtual waiting times at the second queue.

In Part II (pp. 644–659) these results will be used to obtain asymptotic and numerical results, which will provide more insight into the general phenomenon of tandem queueing with correlated service times at the consecutive queues.