In this paper, we adapt the very effective Berry-Esseen theorems of Chen and Shao (2004), which apply to sums of locally dependent random variables, for use with randomly indexed sums. Our particular interest is in random variables resulting from integrating a random field with respect to a point process. We illustrate the use of our theorems in three examples: in a rather general model of the insurance collective; in problems in geometrical probability involving stabilizing functionals; and in counting the maximal points in a two-dimensional region.

In 1988 Whittle introduced an important but intractable class of restless bandit problems which generalise the multiarmed bandit problems of Gittins by allowing state evolution for passive projects. Whittle's account deployed a Lagrangian relaxation of the optimisation problem to develop an index heuristic. Despite a developing body of evidence (both theoretical and empirical) which underscores the strong performance of Whittle's index policy, a continuing challenge to implementation is the need to establish that the competing projects all pass an indexability test. In this paper we employ Gittins' index theory to establish the indexability of (inter alia) general families of restless bandits which arise in problems of machine maintenance and stochastic scheduling problems with switching penalties. We also give formulae for the resulting Whittle indices. Numerical investigations testify to the outstandingly strong performance of the index heuristics concerned.

We present recursions for the total number, Sn, of mutations in a sample of n individuals, when the underlying genealogical tree of the sample is modelled by a coalescent process with mutation rate r>0. The coalescent is allowed to have simultaneous multiple collisions of ancestral lineages, which corresponds to the existence of large families in the underlying population model. For the subclass of Λ-coalescent processes allowing for multiple collisions, such that the measure Λ(dx)/x is finite, we prove that Sn/(nr) converges in distribution to a limiting variable, S, characterized via an exponential integral of a certain subordinator. When the measure Λ(dx)/x2 is finite, the distribution of S coincides with the stationary distribution of an autoregressive process of order 1 and is uniquely determined via a stochastic fixed-point equation of the form with specific independent random coefficients A and B. Examples are presented in which explicit representations for (the density of) S are available. We conjecture that Sn/E(Sn)→1 in probability if the measure Λ(dx)/x is infinite.

We propose a simple and efficient scheme for ranking all teams in a tournament where matches can be played simultaneously. We show that the distribution of the number of rounds of the proposed scheme can be derived using lattice path counting techniques used in ballot problems. We also discuss our method from the viewpoint of parallel sorting algorithms.

A stationary partition based on a stationary point process N in ℝd is an ℝd-valued random field π={π(x): x∈ℝd} such that both π(y)∈N for each y∈ℝd and the random partition {{y∈ℝd: π(y)=x}: x∈N} is stationary jointly with N. Stationary partitions may be considered as general versions of the stationary random tessellations studied in stochastic geometry. As in the special case of the Voronoi tessellation, a stationary partition can be used to relate the underlying stationary probability measure to the associated Palm probability measure of N. In doing so, we will develop some basic theory for stationary partitions and extend properties of stationary tessellations to our more general case. One basic idea is that the stationary measure is (up to a shift) a weighted version of the Palm measure, where the weight is the volume of the typical cell. We will make systematic use of a known modified probability measure. Finally, we use our approach to extend some recent results on the shift coupling of the stationary distribution and the Palm distribution.

The estimation of P(Sn>u) by simulation, where Sn is the sum of independent, identically distributed random varibles Y1,…,Yn, is of importance in many applications. We propose two simulation estimators based upon the identity P(Sn>u)=nP(Sn>u, Mn=Yn), where Mn=max(Y1,…,Yn). One estimator uses importance sampling (for Yn only), and the other uses conditional Monte Carlo conditioning upon Y1,…,Yn−1. Properties of the relative error of the estimators are derived and a numerical study given in terms of the M/G/1 queue in which n is replaced by an independent geometric random variable N. The conclusion is that the new estimators compare extremely favorably with previous ones. In particular, the conditional Monte Carlo estimator is the first heavy-tailed example of an estimator with bounded relative error. Further improvements are obtained in the random-N case, by incorporating control variates and stratification techniques into the new estimation procedures.

In Bhatt and Roy's minimal directed spanning tree construction for a random, partially ordered set of points in the unit square, all edges must respect the ‘coordinatewise’ partial order and there must be a directed path from each vertex to a minimal element. We study the asymptotic behaviour of the total length of this graph with power-weighted edges. The limiting distribution is given by the sum of a normal component away from the boundary plus a contribution introduced by the boundary effects, which can be characterized by a fixed-point equation, and is reminiscent of limits arising in the probabilistic analysis of certain algorithms. As the exponent of the power weighting increases, the distribution undergoes a phase transition from the normal contribution being dominant to the boundary effects being dominant. In the critical case in which the weight is simple Euclidean length, both effects contribute significantly to the limit law.

Let F be a probability distribution with support on the nonnegative integers. We describe two algorithms for generating a stationary random graph, with vertex set ℤ, in which the degrees of the vertices are independent, identically distributed random variables with distribution F. Focus is on an algorithm generating a graph in which, initially, a random number of ‘stubs’ with distribution F is attached to each vertex. Each stub is then randomly assigned a direction (left or right) and the edge configuration obtained by pairing stubs pointing to each other, first exhausting all possible connections between nearest neighbors, then linking second-nearest neighbors, and so on. Under the assumption that F has finite mean, it is shown that this algorithm leads to a well-defined configuration, but that the expected length of the shortest edge attached to a given vertex is infinite. It is also shown that any stationary algorithm for pairing stubs with random, independent directions causes the total length of the edges attached to a given vertex to have infinite mean. Connections to the problem of constructing finitary isomorphisms between Bernoulli shifts are discussed.

We consider the class of level-independent quasi-birth-and-death (QBD) processes that have countably many phases and generator matrices with tridiagonal blocks that are themselves tridiagonal and phase independent. We derive simple conditions for possible decay rates of the stationary distribution of the ‘level’ process. It may be possible to obtain decay rates satisfying these conditions by varying only the transition structure at level 0. Our results generalize those of Kroese, Scheinhardt, and Taylor, who studied in detail a particular example, the tandem Jackson network, from the class of QBD processes studied here. The conditions derived here are applied to three practical examples.

We study the harmonic moments of Galton-Watson processes that are possibly inhomogeneous and have positive values. Good estimates of these are needed to compute unbiased estimators for noncanonical branching Markov processes, which occur, for instance, in the modelling of the polymerase chain reaction. By convexity, the ratio of the harmonic mean to the mean is at most 1. We prove that, for every square-integrable branching mechanism, this ratio lies between 1-A/k and 1-A/k for every initial population of size k>A. The positive constants A and Aͤ are such that A≥Aͤ, are explicit, and depend only on the generation-by-generation branching mechanisms. In particular, we do not use the distribution of the limit of the classical martingale associated with the Galton-Watson process. Thus, emphasis is put on nonasymptotic bounds and on the dependence of the harmonic mean upon the size of the initial population. In the Bernoulli case, which is relevant for the modelling of the polymerase chain reaction, we prove essentially optimal bounds that are valid for every initial population size k≥1. Finally, in the general case and for sufficiently large initial populations, similar techniques yield sharp estimates of the harmonic moments of higher degree.

Fractional Laplace motion is obtained by subordinating fractional Brownian motion to a gamma process. Used recently to model hydraulic conductivity fields in geophysics, it might also prove useful in modeling financial time series. Its one-dimensional distributions are scale mixtures of normal laws, where the stochastic variance has the generalized gamma distribution. These one-dimensional distributions are more peaked at the mode than is a Gaussian distribution, and their tails are heavier. In this paper we derive the basic properties of the process, including a new property called stochastic self-similarity. We also study the corresponding fractional Laplace noise, which may exhibit long-range dependence. Finally, we discuss practical methods for simulation.

We consider the stability of the longest-queue-first scheduling policy (LQF), a natural and low-complexity scheduling policy, for a generalized switch model. Unlike that of common scheduling policies, the stability of LQF depends on the variance of the arrival processes in addition to their average intensities. We identify new sufficient conditions for LQF to be throughput optimal for independent, identically distributed arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize the stability of LQF. We combine properties of diffusion-scaled sample path functionals and local fluid limits into a sharper characterization of stability.

Gaussian wave models have been successfully used since the early 1950s to describe the development of random sea waves, particularly as input to dynamic simulation of the safety of ships and offshore structures. A drawback of the Gaussian model is that it produces stochastically symmetric waves, which is an unrealistic feature and can lead to unconservative safety estimates. The Gaussian model describes the height of the sea surface at each point as a function of time and space. The Lagrange wave model describes the horizontal and vertical movements of individual water particles as functions of time and original location. This model is physically based, and a stochastic version has recently been advocated as a realistic model for asymmetric water waves. Since the stochastic Lagrange model treats both the vertical and the horizontal movements as Gaussian processes, it can be analysed using methods from the Gaussian theory. In this paper we present an analysis of the stochastic properties of the first-order stochastic Lagrange waves model, both as functions of time and as functions of space. A Slepian model for the description of the random shape of individual waves is also presented and analysed.

In this paper, we analyze a queueing system characterized by a space-time arrival process of customers served by a countable set of servers. Customers arrive at points in space and the server stations have space-dependent processing rates. The workload is seen as a Radon measure and the server stations can adapt their power allocation to the current workload. We derive the stability region of the queueing system in the usual stationary ergodic framework. The analysis of this stability region gives some counter-intuitive results. Some specific subclasses of policy are also studied. Wireless communications networks is a natural field of application for the model.

In 1977 D. G. Kendall considered diffusions of shape induced by independent Brownian motions in Euclidean space. In this paper, we consider a different class of diffusions of shape, induced by the projections of a randomly rotating, labelled ensemble. In particular, we study diffusions of shapes induced by projections of planar triangular configurations of labelled points onto a fixed straight line. That is, we consider the process in Σ13 (the shape space of triads in ℝ) that results from extracting the ‘shape information’ from the projection of a given labelled planar triangle as this evolves under the action of Brownian motion in SO(2). We term the thus-defined diffusions Radon diffusions and derive explicit stochastic differential equations and stationary distributions. The latter belong to the family of angular central Gaussian distributions. In addition, we discuss how these Radon diffusions and their limiting distributions are related to the shape of the initial triangle, and explore whether the relationship is bijective. The triangular case is then used as a basis for the study of processes in Σ1k arising from projections of an arbitrary number, k, of labelled points on the plane. Finally, we discuss the problem of Radon diffusions in the general shape space Σnk.

Classical principal component analysis on manifolds, for example on Kendall's shape spaces, is carried out in the tangent space of a Euclidean mean equipped with a Euclidean metric. We propose a method of principal component analysis for Riemannian manifolds based on geodesics of the intrinsic metric, and provide a numerical implementation in the case of spheres. This method allows us, for example, to compare principal component geodesics of different data samples. In order to determine principal component geodesics, we show that in general, owing to curvature, the principal component geodesics do not pass through the intrinsic mean. As a consequence, means other than the intrinsic mean are considered, allowing for several choices of definition of geodesic variance. In conclusion we apply our method to the space of planar triangular shapes and compare our findings with those of standard Euclidean principal component analysis.

We review characteristics of data traffic which we term stylized facts: burstiness, long-range dependence, heavy tails, bursty behavior determined by high-bandwidth users, and dependence determined by users without high transmission rates. We propose an infinite-source Poisson input model which supplies traffic in adjacent time slots. We study properties of the model as slot width decreases and traffic intensity increases. This model has the ability to account for many of the stylized facts.