The structure of the probability space associated with a general point process, when regarded as a counting process, is reviewed using the coincidence formalism. The rest of the paper is devoted to the class of regular point processes for which all coincidence probabilities admit densities. It is shown that their distribution is completely specified by the system of coincidence densities. The specification formalism is stressed for ‘completely’ regular point processes. A construction theorem gives a characterization of the system of coincidence densities of such a process. It permits the study of most models of point processes. New results on the photon process, a particular type of conditioned Poisson process, are derived. New examples are exhibited, including the Gauss-Poisson process and the ‘fermion’ process that is suitable whenever the points are repulsive.

Simulated annealing is a randomized algorithm which has been proposed for finding globally optimum least-cost configurations in large NP-complete problems with cost functions which may have many local minima. A theoretical analysis of simulated annealing based on its precise model, a time-inhomogeneous Markov chain, is presented. An annealing schedule is given for which the Markov chain is strongly ergodic and the algorithm converges to a global optimum. The finite-time behavior of simulated annealing is also analyzed and a bound obtained on the departure of the probability distribution of the state at finite time from the optimum. This bound gives an estimate of the rate of convergence and insights into the conditions on the annealing schedule which gives optimum performance.

Some simple models are described which may be used for the modelling or generation of sequences of dependent discrete random variates with negative binomial and geometric univariate marginal distributions. The models are developed as analogues of well-known continuous variate models for gamma and negative exponential variates. The analogy arises naturally from a consideration of self-decomposability for discrete random variables. An alternative derivation is also given wherein both the continuous and the discrete variate processes arise simultaneously as measures on a process of overlapping intervals. The former is the process of interval lengths and the latter is a process of counts on these intervals.

In this paper, distributional questions which arise in certain mathematical finance models are studied: the distribution of the integral over a fixed time interval [0, T] of the exponential of Brownian motion with drift is computed explicitly, with the help of computations previously made by the author for Bessel processes. The moments of this integral are obtained independently and take a particularly simple form. A subordination result involving this integral and previously obtained by Bougerol is recovered and related to an important identity for Bessel functions. When the fixed time T is replaced by an independent exponential time, the distribution of the integral is shown to be related to last-exit-time distributions and the fixed time case is recovered by inverting Laplace transforms.

In this note we deal with the stochastic difference equation of the form Yn+1 = AnYn + Bn, n∊ℤ, where the sequence is assumed to be strictly stationary and ergodic. By means of simple arguments a unique stationary solution of this equation is constructed. The stability of the stationary solution is the second subject of investigation. It is shown that under some additional assumptions

A family of models for discrete-time processes with Poisson marginal distributions is developed and investigated. They have the same correlation structure as the linear ARMA processes. The joint distribution of n consecutive observations in such a process is derived and its properties discussed. In particular, time-reversibility and asymptotic behaviour are considered in detail. A vector autoregressive process is constructed and the behaviour of its components, which are Poisson ARMA processes, is considered. In particular, the two-dimensional case is discussed in detail.

We discuss a single-server queue whose input is the versatile Markovian point process recently introduced by Neuts [22] herein to be called the N-process. Special cases of the N-process discussed earlier in the literature include a number of complex models such as the Markov-modulated Poisson process, the superposition of a Poisson process and a phase-type renewal process, etc. This queueing model has great appeal in its applicability to real world situations especially such as those involving inhibition or stimulation of arrivals by certain renewals. The paper presents formulas in forms which are computationally tractable and provides a unified treatment of many models which were discussed earlier by several authors and which turn out to be special cases. Among the topics discussed are busy-period characteristics, queue-length distributions, moments of the queue length and virtual waiting time. We draw particular attention to our generalization of the Pollaczek–Khinchin formula for the Laplace–Stieltjes transform of the virtual waiting time of the M/G/1 queue to the present model and the resulting Volterra system of integral equations. The analysis presented here serves as an example of the power of Markov renewal theory.

We consider the standard slotted ALOHA system with a finite number of buffered users. Stability analysis of such a system was initiated by Tsybakov and Mikhailov (1979). Since then several bounds on the stability region have been established; however, the exact stability region is known only for the symmetric system and two-user ALOHA. This paper proves necessary and sufficient conditions for stability of the ALOHA system. We accomplish this by means of a novel technique based on three simple observations: applying mathematical induction to a smaller copy of the system, isolating a single queue for which Loynes' stability criteria is adopted, and finally using stochastic dominance to verify the required stationarity assumptions in the Loynes criterion. We also point out that our technique can be used to assess stability regions for other multidimensional systems. We illustrate it by deriving stability regions for buffered systems with conflict resolution algorithms (see also Georgiadis and Szpankowski (1992) for similar approach applied to stability of token-passing rings).

The cμ rule is optimal for arbitrary arrival processes provided that the service times are geometric and the service discipline is preemptive.

This paper presents proofs of the strong law of large numbers and the central limit theorem for estimators of the parameters in quite general finite-parameter linear models for vector time series. The estimators are derived from a Gaussian likelihood (although Gaussianity is not assumed) and certain spectral approximations to this. An important example of finite-parameter models for multiple time series is the class of autoregressive moving-average (ARMA) models and a general treatment is given for this case. This includes a discussion of the problems associated with identification in such models.

We consider probability metrics of the following type: for a class of functions and probability measures P, Q we define A unified study of such integral probability metrics is given. We characterize the maximal class of functions that generates such a metric. Further, we show how some interesting properties of these probability metrics arise directly from conditions on the generating class of functions. The results are illustrated by several examples, including the Kolmogorov metric, the Dudley metric and the stop-loss metric.

An efficient computational approach to the analysis of finite birth-and-death models in a Markovian environment is given. The emphasis is upon obtaining numerical methods for evaluating stationary distributions and moments of first-passage times.

How should calls be routed or capacity allocated in a circuit-switched communication network so as to optimize the performance of the network? This paper considers the question, using a simplified analytical model of a circuit-switched network. We show that there exist implicit shadow prices associated with each route and with each link of the network, and that the equations defining these prices have a local or decentralized character. We illustrate how these results can be used as the basis for a decentralized adaptive routing scheme, responsive to changes in the demands placed on the network.

The aim of this paper is to present a few techniques which may be useful in the analysis of time series when a failure is suspected. We present two categories of tests and investigate their asymptotic properties: one, of nonparametric type, is intended to detect a general failure in spectrum; the other investigates the properties of likelihood ratio tests in parametric models which have a non-standard behaviour in this situation. Finally, we obtain the asymptotic distribution of the likelihood estimators of the change parameters.

The set of rooted trees, generated by random bifurcation at the terminal nodes, is considered with the aims of enumerating it and of determining its probability distribution. The account of enumeration collates much previous work and attempts a complete perspective of the problems and their solutions. Asymptotic and numerical results are given, and some unsolved problems are pointed out. The problem of ascertaining the probability distribution is solved by obtaining its governing recurrence equation, and numerical results are given. The difficult problem of determining the most probable tree-shape of given size is considered, and for labelled trees a conjecture at its solution is offered. For unlabelled shapes the problem remains open. These mathematical problems arise in attempting to reconstruct evolutionary trees by the statistical approach of Cavalli-Sforza and Edwards.

The behaviour in equilibrium of networks of queues is studied. Equilibrium distributions are obtained and in certain cases it is shown that the state of an individual queue is independent of the state of the rest of the network. The processes considered in this paper are irreversible; however, the method used to establish equilibrium distributions is one which has previously only been used when dealing with reversible processes. Results are obtained for models of communication networks, machine interference and birth-illness-death processes.

Haploid models of genetic drift in populations of constant size are considered. Generalizations of the models of Moran and Wright have been developed by Karlin and McGregor (for multiple alleles and non-overlapping generations), by Chia and Watterson (for two alleles and overlapping or non-overlapping generations) and by Chia (for multiple alleles and overlapping or non-overlapping generations), using conditioned branching processes. A new approach is developed which contains the models mentioned above and provides simpler expressions for the latent roots. A greater dependence between the birth events and death events can be permitted, and non-independent mutations treated.

We prove a monotonicity result for the problem of optimal service rate control in certain queueing networks. Consider, as an illustrative example, a number of ·/M/1 queues which are arranged in a cycle with some number of customers moving around the cycle. A holding cost hi(xi) is charged for each unit of time that queue i contains xi customers, with hi being convex. As a function of the queue lengths the service rate at each queue i is to be chosen in the interval , where cost ci(μ) is charged for each unit of time that the service rate μis in effect at queue i. It is shown that the policy which minimizes the expected total discounted cost has a monotone structure: namely, that by moving one customer from queue i to the following queue, the optimal service rate in queue i is not increased and the optimal service rates elsewhere are not decreased. We prove a similar result for problems of optimal arrival rate and service rate control in general queueing networks. The results are extended to an average-cost measure, and an example is included to show that in general the assumption of convex holding costs may not be relaxed. A further example shows that the optimal policy may not be monotone unless the choice of possible service rates at each queue includes 0.

In this paper we connect various topological and probabilistic forms of stability for discrete-time Markov chains. These include tightness on the one hand and Harris recurrence and ergodicity on the other. We show that these concepts of stability are largely equivalent for a major class of chains (chains with continuous components), or if the state space has a sufficiently rich class of appropriate sets (‘petite sets').

We use a discrete formulation of Dynkin's formula to establish unified criteria for these stability concepts, through bounding of moments of first entrance times to petite sets. This gives a generalization of Lyapunov–Foster criteria for the various stability conditions to hold. Under these criteria, ergodic theorems are shown to be valid even in the non-irreducible case. These results allow a more general test function approach for determining rates of convergence of the underlying distributions of a Markov chain, and provide strong mixing results and new versions of the central limit theorem and the law of the iterated logarithm.

This paper presents a general theory of random tessellations (i.e. stochastic aggregates of disjoint and space-filling cells) in d-dimensional Euclidean space. Some particular models of random tessellations are discussed in detail.