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.

For n independent, identically distributed uniform points in [0, 1]d, d ≥ 2, let Ln be the total distance from the origin to all the minimal points under the coordinatewise partial order (this is also the total length of the rooted edges of a minimal directed spanning tree on the given random points). For d ≥ 3, we establish the asymptotics of the mean and the variance of Ln, and show that Ln satisfies a central limit theorem, unlike in the case d = 2.

In this paper we discuss the complementary theorem applied to the typical n-tuple of a Poisson point process. The theorem was first presented by Miles in 1970 and discussed by Santaló in 1976 and, within a Palm measure framework, by Møller and Zuyev in 1996. The theorems put forward by these authors are not correct for all the examples that they present, suggesting that further consideration of their work is needed if one wishes to bring all those examples within the ambit of the complementary theorem. We give alternative analyses of the errant examples and, with a modification of the technicalities in the work of the above authors, move toward a more comprehensive complementary theorem. Some open issues still remain.

We study a random field obtained by counting the number of balls containing a given point when overlapping balls are thrown at random according to a Poisson random measure. We describe a microscopic process which exhibits multifractional behavior. We are particularly interested in the local asymptotic self-similarity (LASS) properties of the field, as well as in its X-ray transform. We obtain two different LASS properties when considering the asymptotics either in law or in the sense of second-order moments, and prove a relationship between the LASS behavior of the field and the LASS behavior of its X-ray transform. These results can be used to model and analyze porous media, images, or connection networks.

In this article, we study a particular example of general random tessellation, the dead leaves model. This model, first studied by the mathematical morphology school, is defined as a sequential superimposition of random closed sets, and provides the natural tool to study the occlusion phenomenon, an essential ingredient in the formation of visual images. We generalize certain results of G. Matheron and, in particular, compute the probability of n compact sets being included in visible parts. This result characterizes the distribution of the boundary of the dead leaves tessellation.

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 extend the boson process first to a large class of Cox processes and second to an even larger class of infinitely divisible point processes. Density and moment results are studied in detail. These results are obtained in closed form as weighted permanents, so the extension is called a permanental process. Temporal extensions and a particularly tractable case of the permanental process are also studied. Extensions of the fermion process along similar lines, leading to so-called determinantal processes, are discussed.

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.

We study the problem of dynamically allocating flexible workers to stations in tandem or serial manufacturing systems. Workers are trained to do a subset of consecutive tasks. We show that the optimal policy is often LBFS (last buffer first-served) or FBFS (first buffer first-served). These results generalize earlier results on the optimality of the pick-and-run, expedite, and bucket brigade-type policies. We also show that, for exponential processing times and general manufacturing networks, the optimal policy will tend to have several workers assigned to the same station.

The existence and uniqueness of maximum likelihood estimators for the time and range parameters in random sequential adsorption models are investigated.

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.

In this paper we establish large deviation results on the number of extreme points of a homogeneous Poisson point process in the unit ball of Rd. In particular, we deduce an almost-sure law of large numbers in any dimension. As an auxiliary result we prove strong localization of the extreme points in an annulus near the boundary of the ball.

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.

A bookmaker takes bets on a two-horse race, attempting to minimise expected loss over all possible outcomes of the race. Profits are controlled by manipulation of customers' betting behaviour, which is assumed to be determined uniquely by the price quoted for each horse. We consider different strategies for choosing these prices as bets accumulate, and examine the penalty incurred by the use of a strategy other than the optimal one, in the general case where the distribution of the customers' betting probabilities is unknown.

Random (pseudo)graphs GN with the following structure are studied: first, independent and identically distributed capacities Λi are drawn for vertices i = 1, …, N; then, each pair of vertices (i, j) is connected, independently of the other pairs, with E(i, j) edges, where E(i, j) has distribution Poisson(Λi Λj / ∑k=1N Λk). The main result of the paper is that when P(Λ1 > x) ≥ x−τ+1, where τ ∈ (2, 3), then, asymptotically almost surely, GN has a giant component, and the distance between two randomly selected vertices of the giant component is less than (2 + o(N))(log log N)/(-log (τ − 2)). It is also shown that the cases τ > 3, τ ∈ (2, 3), and τ ∈ (1, 2) present three qualitatively different connectivity architectures.

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.

The maximization of the long-term growth rate of expected utility is considered under drawdown constraints. In a general situation, the value and the optimal strategy of the problem are related to those of another ‘standard’ risk-sensitive-type portfolio optimization problem. Furthermore, an upside-chance maximization problem of a large deviation probability is stated as a ‘dual’ optimization problem. As an example, a ‘linear-quadratic’ model is studied in detail: the conditions to ensure the solvabilities of the problems are discussed and explicit expressions for the solutions are presented.

Conditions are derived for the asymptotic normality of a general class of vector-valued functionals of stationary Boolean models in the d-dimensional Euclidean space, where a Lindeberg-type central limit theorem for m-dependent random fields, m ∈ N, is applied. These functionals can be used to construct joint estimators for the vector of specific intrinsic volumes of the underlying Boolean model. Extensions to functionals of more general germ–grain models satisfying some mixing and integrability conditions are also discussed.

We consider the portfolio optimization problem of maximizing the asymptotic growth rate under a combination of fixed and proportional costs. Expressing the asymptotic growth rate in terms of the risky fraction process, the problem can be transformed to that of controlling a diffusion in one dimension. Then we use the corresponding quasivariational inequalities to obtain the explicit shape together with the existence of an optimal impulse control strategy. This optimal strategy is given by only four parameters: two for the stopping boundaries and two for the new risky fractions the investor chooses at these times.

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.