We approach sphere of influence graphs (SIGs) from a probabilistic perspective. Ordinary SIGs were first introduced by Toussaint as a type of proximity graph for use in pattern recognition, computer vision and other low-level vision tasks. A random sphere of influence graph (RSIG) is constructed as follows. Consider n points uniformly and independently distributed within the unit square in d dimensions. Around each point, Xi, draw an open ball (‘sphere of influence’) with radius equal to the distance to Xi's nearest neighbour. Finally, draw an edge between two points if their spheres of influence intersect. Asymptotically exact values for the expected number of edges in a RSIG are determined for all values of d; previously, just upper and lower bounds were known for this quantity. A modification of the Azuma-Hoeffding exponential inequality is employed to exhibit the sharp concentration of the number of edges around its expected value.

When fractal dimensions are estimated from an observed point pattern, there is some ambiguity as to the interpretation of the quantity being estimated. (The point pattern itself has dimension zero.) Two possible interpretations are described. In the first of these, the observation region is regarded as being held fixed, while observations accumulate with time. In this case, provided the process is stationary and ergodic in time, and the cumulants satisfy certain regularity constraints, the dimension estimates consistently estimate the Rényi moment dimensions of the marginal distribution in space. If the regularity constraints are not satisfied, then different limits can be obtained according to the manner in which the limits are taken.

In the second case, the process is regarded as being stationary and ergodic in its spatial component, time being held fixed. In this case the estimates provide consistent estimates of the initial power-law rates of growth of the moment measures of the Palm distribution, the estimates for successively higher Rényi dimensions estimating the growth rates for successively higher-order moment measures of the Palm distribution.

Several examples are given, to illustrate the different types of behaviour which may occur, including the case where the points are generated by a dynamical system.

Consider the basic location problem in which k locations from among n given points X1,…,Xn are to be chosen so as to minimize the sum M(k; X1,…,Xn) of the distances of each point to the nearest location. It is assumed that no location can serve more than a fixed finite number D of points. When the Xi, i ≥ 1, are i.i.d. random variables with values in [0,1]d and when k = ⌈n/(D+1)⌉ we show that

where α := α(D,d) is a positive constant, f is the density of the absolutely continuous part of the law of X1, and c.c. denotes complete convergence.

Management of a bufferless resource is considered under non-homogeneous demand consisting of one-unit and two-unit requests. Two-unit requests can be served only by a given partition of the resource. Three simple admission policies are evaluated with regard to revenue generation. One policy involves no admission control and two policies involve trunk reservation. A limiting regime in which demand and capacity increase in proportion is considered. It is shown that each policy is asymptotically optimal for a certain range of parameters. Limiting dynamical behavior is obtained via a theory developed by Hunt and Kurtz. The results also point out the remarkable effect of partition constraints.

This paper considers a germ-grain model for a random system of non-overlapping spheres in ℝd for d = 1, 2 and 3. The centres of the spheres (i.e. the ‘germs’ for the ‘grains’) form a stationary Poisson process; the spheres result from a uniform growth process which starts at the same instant in all points in the radial direction and stops for any sphere when it touches any other sphere. Upper and lower bounds are derived for the volume fraction of space occupied by the spheres; simulation yields the values 0.632, 0.349 and 0.186 for d = 1, 2 and 3. The simulations also provide an estimate of the tail of the distribution function of the volume of a randomly chosen sphere; these tails are compared with those of two exponential distributions, of which one is a lower bound and is an asymptote at the origin, and the other has the same mean as the simulated distribution. An upper bound on the tail of the distribution is also an asymptote at the origin but has a heavier tail than either of these exponential distributions. More detailed information for the one-dimensional case has been found by Daley, Mallows and Shepp; relevant information is summarized, including the volume fraction 1 - e-1 = 0.63212 and the tail of the grain volume distribution e-yexp(e-y - 1), which is closer to the simulated tails for d = 2 and 3 than the exponential bounds.

A popular procedure in spatial data analysis is to fit a line segment of the form c(x) = 1 - α ||x||, ||x|| < 1, to observed correlations at (appropriately scaled) spatial lag x in d-dimensional space. We show that such an approach is permissible if and only if

the upper bound depending on the spatial dimension d. The proof relies on Matheron's turning bands operator and an extension theorem for positive definite functions due to Rudin. Side results and examples include a general discussion of isotropic correlation functions defined on d-dimensional balls.

We consider a singularly perturbed (finite state) Markov chain and provide a complete characterization of the fundamental matrix. In particular, we obtain a formula for the regular part simpler than a previous formula obtained by Schweitzer, and the singular part is obtained via a reduction process similar to Delebecque's reduction for the stationary distribution. In contrast to previous approaches, one works with aggregate Markov chains of much smaller dimension than the original chain, an essential feature for practical computation. An application to mean first-passage times is also presented.

In this paper we consider the continuous-time filtering problem and we estimate the order of convergence of an interacting particle system scheme presented by the authors in previous works. We will discuss how the discrete time approximating model of the Kushner-Stratonovitch equation and the genetic type interacting particle system approximation combine. We present quenched error bounds as well as mean order convergence results.

The distribution of the size of one connected component and the largest connected component of the excursion set is derived for stationary χ2, t and F fields, in the limit of high or low thresholds. This extends previous results for stationary Gaussian fields (Nosko 1969, Adler 1981) and for χ2 fields in one and two dimensions (Aronowich and Adler 1986, 1988). An application of this is to detect regional changes in positron emission tomography (PET) images of blood flow in human brain, using the size of the largest connected component of the excursion set as a test statistic.

For random planar stationary tessellations a parameter system of three mean values and two directional distributions of the edges is considered. To investigate the interdependences between these parameters their joint range is described, i.e. the set of values which can be realized by tessellations. The constructive proof is based on mixtures of stationary regular tessellations. To explore the range for the class of stationary ergodic tessellations a procedure is used which we refer to as iteration.

By using Chibisov-O'Reilly type theorems for uniform empirical and quantile processes based on stationary observations, we establish a weak approximation theory for empirical Lorenz curves and their inverses used in economics. In particular, we obtain weak approximations for empirical Lorenz curves and their inverses also under the assumptions of mixing dependence, often used structures of dependence for observations.

Two species (designated by 0's and 1's) compete for territory on a lattice according to the rules of a voter model, except that the 0's jump d0 spaces and the 1's jump d1 spaces. When d0 = d1 = 1 the model is the usual voter model. It is shown that in one dimension, if d1 > d0 and d0 = 1,2 and initially there are infinitely many blocks of 1's of length ≥ d1, then the 1's eliminate the 0's. It is believed this may be true whenever d1 > d0. In the biased annihilating branching process particles place offspring on empty neighbouring sites at rate λ and neighbouring pairs of particles coalesce at rate 1. In one dimension it is known to converge to the product measure density λ/(1+λ) when λ ≥ 1/3, and the initial configuration is non-zero and finite. This result is extended to λ ≥ 0.0347. Bounds on the edge-speed are given.

This paper examines a problem of importance to the telecommunications industry. In the design of modern ATM switches, it is necessary to use simulation to estimate the probability that a queue within the switch exceeds a given large value. Since these are extremely small probabilities, importance sampling methods must be used. Here we obtain a change of measure for a broad class of models with direct applicability to ATM switches.

We consider a model with A independent sources of cells where each source is modeled by a Markov renewal point process with batch arrivals. We do not assume the sources are necessarily identically distributed, nor that batch sizes are independent of the state of the Markov process. These arrivals join a queue served by multiple independent servers, each with service times also modeled as a Markov renewal process. We only discuss a time-slotted system. The queue is viewed as the additive component of a Markov additive chain subject to the constraint that the additive component remains non-negative. We apply the theory in McDonald (1999) to obtain the asymptotics of the tail of the distribution of the queue size in steady state plus the asymptotics of the mean time between large deviations of the queue size.

This paper is concerned with the standard bivariate death process as well as with some Markovian modifications and extensions of the process that are of interest especially in epidemic modeling. A new and powerful approach is developed that allows us to obtain the exact distribution of the population state at any point in time, and to highlight the actual nature of the solution. Firstly, using a martingale technique, a central system of relations with two indices for the temporal state distribution will be derived. A remarkable property is that for all the models under consideration, these relations exhibit a similar algebraic structure. Then, this structure will be exploited by having recourse to a theory of Abel-Gontcharoff pseudopolynomials with two indices. This theory generalizes the univariate case examined in a preceding paper and is briefly introduced in the Appendix.

Sufficient conditions are given ensuring tightness of a suitably normalized stationary waiting time in the FIFO G/G/1 queue under heavy traffic.

Recently in the paper by Møller and Zuyev (1996), the following Gamma-type result was established. Given n points of a homogeneous Poisson process defining a random figure, its volume is Γ(n,λ) distributed, where λ is the intensity of the process. In this paper we give an alternative description of the class of random sets for which the Gamma-type results hold. We show that it corresponds to the class of stopping sets with respect to the natural filtration of the point process with certain scaling properties. The proof uses the martingale technique for directed processes, in particular, an analogue of Doob's optional sampling theorem proved in Kurtz (1980). As well as being compact, this approach provides a new insight into the nature of geometrical objects constructed with respect to a Poisson point process. We show, in particular, that in this framework the probability that a point is covered by a stopping set does not depend on whether it is a point of the process or not.

Kohonen self-organizing interval maps are considered. In this model a linear graph is embedded randomly into the unit interval. At each time a point is chosen randomly according to a fixed distribution. The nearest vertex and some of its nearby neighbors are moved closer to the point. These models have been proposed as models of learning in the audio-cortex. The models possess not only the structure of a Markov chain, but also the added structure of a random dynamical system. This structure is used to show that for a large class of these models, in a strong way, the initial conditions are unimportant and only the dynamics govern the future. A contractive condition is proven in spite of the fact that the maps are not continuous. This, in turn, shows that the Markov chain is uniformly ergodic.

The paper is concerned with the final state and severity of a number of SIR epidemic models in finite populations. Two different classes of models are considered, namely the classical SIR Markovian models and the collective models introduced recently by the authors. First, by applying a simple martingale argument, it is shown that in both cases, there exists a common algebraic structure underlying the exact law of the final state and severity. Then, a unified approach to these statistics is developed by exploiting the theory of Abel-Gontcharoff pseudopolynomials (presented in a preceding paper).