Let 𝓅 be a Poisson process of intensity one in a square Sn of area n. We construct a random geometric graph Gn,k by joining each point of 𝓅 to its k ≡ k(n) nearest neighbours. Recently, Xue and Kumar proved that if k ≤ 0.074 log n then the probability that Gn, k is connected tends to 0 as n → ∞ while, if k ≥ 5.1774 log n, then the probability that Gn, k is connected tends to 1 as n → ∞. They conjectured that the threshold for connectivity is k = (1 + o(1)) log n. In this paper we improve these lower and upper bounds to 0.3043 log n and 0.5139 log n, respectively, disproving this conjecture. We also establish lower and upper bounds of 0.7209 log n and 0.9967 log n for the directed version of this problem. A related question concerns coverage. With Gn, k as above, we surround each vertex by the smallest (closed) disc containing its k nearest neighbours. We prove that if k ≤ 0.7209 log n then the probability that these discs cover Sn tends to 0 as n → ∞ while, if k ≥ 0.9967 log n, then the probability that the discs cover Sn tends to 1 as n → ∞.

In a unified approach, this paper presents distributional properties of a Voronoi tessellation generated by a homogeneous Poisson point process in the Euclidean space of arbitrary dimension. Probability density functions and moments are given for characteristics of the ‘typical’ edge in lower-dimensional section hyperplanes (edge lengths, adjacent angles). We investigate relationships between edges and their neighbours, called Poisson points or centres; namely angular distributions, distances, and positions of neighbours relative to the edge. The approach is analytical, and the results are given partly explicitly and partly as integral expressions, which are suitable for the numerical calculations also presented.

Given a class Γ of curves in [0, 1]2, we ask: in a cloud of n uniform random points, how many points can lie on some curve γ ∈ Γ? Classes studied here include curves of length less than or equal to L, Lipschitz graphs, monotone graphs, twice-differentiable curves, and graphs of smooth functions with m-bounded derivatives. We find, for example, that there are twice-differentiable curves containing as many as OP(n1/3) uniform random points, but not essentially more than this. More generally, we consider point clouds in higher-dimensional cubes [0, 1]d and regular hypersurfaces of specified codimension, finding, for example, that twice-differentiable k-dimensional hypersurfaces in Rd may contain as many as OP(nk/(2d-k)) uniform random points. We also consider other notions of ‘incidence’, such as curves passing through given location/direction pairs, and find, for example, that twice-differentiable curves in R2 may pass through at most OP(n1/4) uniform random location/direction pairs. Idealized applications in image processing and perceptual psychophysics are described and several open mathematical questions are identified for the attention of the probability community.

Our main result is the proof of the existence of random stationary tessellations in d-dimensional Euclidean space with the following stability property: their distribution is invariant with respect to the operation of iteration (or nesting) of tessellations with an appropriate rescaling. This operation means that the cells of a given tessellation are individually and independently subdivided by independent, identically distributed tessellations, resulting in a new tessellation. It is also shown that, for any stationary tessellation, the sequence that is generated by repeated rescaled iteration converges weakly to such a stable tessellation; thus, the class of all stable stationary tessellations is fully characterized.

We construct random dynamics for collections of nonintersecting planar contours, leaving invariant the distributions of length- and area-interacting polygonal Markov fields with V-shaped nodes. The first of these dynamics is based on the dynamic construction of consistent polygonal fields, as presented in the original articles by Arak (1983) and Arak and Surgailis (1989), (1991), and it provides an easy-to-implement Metropolis-type simulation algorithm. The second dynamics leads to a graphical construction in the spirit of Fernández et al. (1998), (2002) and yields a perfect simulation scheme in a finite window in the infinite-volume limit. This algorithm seems difficult to implement, yet its value lies in that it allows for theoretical analysis of the thermodynamic limit behaviour of length-interacting polygonal fields. The results thus obtained include, in the class of infinite-volume Gibbs measures without infinite contours, the uniqueness and exponential α-mixing of the thermodynamic limit of such fields in the low-temperature region. Outside this class, we conjecture the existence of an infinite number of extreme phases breaking both the translational and rotational symmetries.

The convex hull of n independent random points in ℝd, chosen according to the normal distribution, is called a Gaussian polytope. Estimates for the variance of the number of i-faces and for the variance of the ith intrinsic volume of a Gaussian polytope in ℝd, d∈ℕ, are established by means of the Efron-Stein jackknife inequality and a new formula of Blaschke-Petkantschin type. These estimates imply laws of large numbers for the number of i-faces and for the ith intrinsic volume of a Gaussian polytope as n→∞.

We consider a hard-sphere model in ℝd generated by a stationary point process N and the lilypond growth protocol: at time 0, every point of N starts growing with unit speed in all directions to form a system of balls in which any particular ball ceases its growth at the instant that it collides with another ball. Some quite general conditions are given, under which it is shown that the model is well defined and exhibits no percolation. The absence of percolation is attributable to the fact that, under our assumptions, there can be no descending chains in N. The proof of this fact forms a significant part of the paper. It is also shown that, in the absence of descending chains, mutual-nearest-neighbour matching can be used to construct a bijective point map as defined by Thorisson.

We consider stationary and ergodic tessellations X = Ξnn≥1 in Rd, where X is observed in a bounded and convex sampling window Wp ⊂ Rd. It is assumed that the cells Ξn of X possess random inner structures, examples of which include point patterns, fibre systems, and tessellations. These inner cell structures are generated, both independently of each other and independently of the tessellation X, by generic stationary random sets that are related to a stationary random vector measure J0 acting on Rd. In particular, we study the asymptotic behaviour of a multivariate random functional, which is determined both by X and by the individual cell structures contained in Wp, as Wp ↑ Rd. It turns out that this functional provides an unbiased estimator for the intensity vector associated with J0. Furthermore, under natural restrictions, strong laws of large numbers and a multivariate central limit theorem of the normalized functional are proven. Finally, we discuss in detail some numerical examples and applications, for which the inner structures of the cells of X are induced by iterated Poisson-type tessellations.

Our objective is to construct a perfect simulation algorithm for unmarked and marked Hawkes processes. The usual straightforward simulation algorithm suffers from edge effects, whereas our perfect simulation algorithm does not. By viewing Hawkes processes as Poisson cluster processes and using their branching and conditional independence structures, useful approximations of the distribution function for the length of a cluster are derived. This is used to construct upper and lower processes for the perfect simulation algorithm. A tail-lightness condition turns out to be of importance for the applicability of the perfect simulation algorithm. Examples of applications and empirical results are presented.

We introduce a class of Cox cluster processes called generalised shot noise Cox processes (GSNCPs), which extends the definition of shot noise Cox processes (SNCPs) in two directions: the point process that drives the shot noise is not necessarily Poisson, and the kernel of the shot noise can be random. Thereby, a very large class of models for aggregated or clustered point patterns is obtained. Due to the structure of GSNCPs, a number of useful results can be established. We focus first on deriving summary statistics for GSNCPs and, second, on how to simulate such processes. In particular, results on first- and second-order moment measures, reduced Palm distributions, the J-function, simulation with or without edge effects, and conditional simulation of the intensity function driving a GSNCP are given. Our results are exemplified in important special cases of GSNCPs, and we discuss their relation to the corresponding results for SNCPs.

In a tree, a level consists of all those nodes that are the same distance from the root. We derive asymptotic approximations to the correlation coefficients of two level sizes in random recursive trees and binary search trees. These coefficients undergo sharp sign-changes when one level is fixed and the other is varying. We also propose a new means of deriving an asymptotic estimate for the expected width, which is the number of nodes at the most abundant level. Crucial to our methods of proof is the uniformity achieved by singularity analysis.

We describe a class of self-similar random measure that generalizes the class of stable, completely random measure, or, in one dimension, the class of processes with stable independent increments. As with the stable processes, the realizations are purely atomic, but the masses of the atoms are not necessarily independent, but rather characterized by self-similar dependence relations. Indeed, the class can be described most effectively in terms of the point process on the product space for the locations and sizes (‘marksȉ) of the atoms. Then self-similarity reduces to an invariance relation (‘biscale invariance’) on the distribution of this marked point process. The condition can be satisfied when the marked point process is compound Poisson, corresponding to the nonnegative stable processes, but is by no means restricted to this case. An example is given which modifies and extends Ogata's epidemic-type aftershock sequence model for earthquake occurrence.

Given a sample of genes taken from a large population, we consider the neutral coalescent genealogy and study the theoretical and empirical distributions of the size of the smallest clade containing a fixed gene. We show that the theoretical distribution is strongly related to a Yule distribution of parameter 2, and that the empirical count statistics are asymptotically Gaussian as the number of genes grows to infinity. Then we consider external branches of the coalescent tree, and describe their lengths. Using the infinitely many sites model of mutation, we also describe the conditional distribution of the external branch lengths, given the number of pairwise differences between a reference DNA sequence and the sequence of one closest relative in the sample.

We consider the problem of dynamic admission control in a Markovian loss system with two classes. Jobs arrive at the system in batches; each admitted job requires different service rates and brings different revenues depending on its class. We introduce the definition of a ‘preferred class’ for systems receiving mixed and single-class batches separately, and derive sufficient conditions for each system to have a preferred class. We also establish a monotonicity property of the optimal value functions, which reduces the number of possibly optimal actions.

We present two variations of a two-person, noncooperative stochastic game, inspired by the famous red-and-black gambling problem presented by Dubins and Savage. Two players each hold an integer amount of money and they each aim to win the other player's fortune. At every stage of the game they simultaneously bid an integer portion of their current fortune, and their probabilities of winning depend on these bids. We describe two different laws of motion specifying this dependency. In one version of the game, the players' probabilities of winning are proportional to their bets. In the other version, the probabilities of winning depend on the size of their bets and a weight parameter w. For each version we give a Nash equilibrium, in which the player for which the game is subfair (w ≤ ½) plays boldly and the player for which the game is superfair (w ≥ ½) plays timidly.

Stochastic processes with Student marginals and various types of dependence structure, allowing for both short- and long-range dependence, are discussed in this paper. A particular motivation is the modelling of risky asset time series.

Consider a random walk S=(Sn: n≥0) that is ‘perturbed’ by a stationary sequence (ξn: n≥0) to produce the process S=(Sn+ξn: n≥0). In this paper, we are concerned with developing limit theorems and approximations for the distribution of Mn=max{Sk+ξk: 0≤k≤n} when the random walk has a drift close to 0. Such maxima are of interest in several modeling contexts, including operations management and insurance risk theory. The associated limits combine features of both conventional diffusion approximations for random walks and extreme-value limit theory.

In this paper, we consider a certain type of space- and time-fractional kinetic equation with Gaussian or infinitely divisible noise input. The solutions to the equation are provided in the cases of both bounded and unbounded domains, in conjunction with bounds for the variances of the increments. The role of each of the parameters in the equation is investigated with respect to second- and higher-order properties. In particular, it is shown that long-range dependence may arise in the temporal solution under certain conditions on the spatial operators.

We formulate a localization property of wavelet coefficients for processes with stationary increments, in the estimation problem associated with the processes. A general setting for the estimation is adopted and examples that fit this setting are given. An evaluation of wavelet coefficient decay with respect to shift k∈ℕ is explicitly derived (only the asymptotic behavior, for large k, was previously known). It is this evaluation that makes it possible to establish the localization property of the wavelet coefficients. In doing so, it turns out that the theory of positive-definite functions plays an important role. As applications, we show that, in the wavelet coefficient domain, estimators that use a simple moment method are nearly as good as maximum likelihood estimators. Moreover, even though the underlying process is long-range dependent and process domain estimates imply the validity of a noncentral limit theorem, for the wavelet coefficient domain estimates we always obtain a central limit theorem with a small prescribed error.

A simplified proof of Thorp and Walden's fundamental theorem of card counting is presented, and a corresponding central limit theorem is established. Results are applied to the casino game of trente et quarante, which was studied by Poisson and De Morgan.