Search

The Erdős-Turán law gives a normal approximation for the order of a randomly chosen permutation of n objects. In this paper, we provide a sharp error estimate for the approximation, showing that, if the mean of the approximating normal distribution is slightly adjusted, the error is of order log−1/2n

An axiomatic basis for the construction of measures of niche overlap is analysed, and its implications are discussed, with particular reference to the more commonly used measures. A method of establishing that a measure of overlap complies with the axioms is put forward, making possible the construction of families of new measures. Certain extremal measures of overlap are also identified

Empirical point processes of exceedances play an important role in extreme value theory, and their limiting behaviour has been extensively studied. Here, we provide explicit bounds on the accuracy of approximating an exceedance process by a compound Poisson or Poisson cluster process, in terms of a Wasserstein metric that is generally more suitable for the purpose than the total variation metric. The bounds only involve properties of the finite, empirical sequence that is under consideration, and not of any limiting process. The argument uses Bernstein blocks and Lindeberg's method of compositions.

Poisson approximation in total variation can be successfully established in a wide variety of contexts, involving sums of weakly dependent random variables which usually take the value 0, and occasionally the value 1. If the random variables can take other positive integer values, or if there is stronger dependence between them, compound Poisson approximation may be more suitable. Stein's method, which is so effective in the Poisson context, turns out to be much more difficult to apply for compound Poisson approximation, because the solutions of the Stein equation have undesirable properties. In this paper, we prove new bounds on the absolute values of the solutions to the Stein equation and of their first differences, over certain ranges of their arguments. These enable compound Poisson approximation in total variation to be carried out with almost the same efficiency as in the Poisson case. Even for sums of independent random variables, which have been exhaustively studied in the past, new results are obtained, effectively solving a problem discussed by Le Cam (1965, Bernoulli, Bayes, Laplace. Springer, New York, pp. 179–202), in the context of nonnegative integer valued random variables.

Small world models are networks consisting of many local links and fewer long range `shortcuts'. In this paper, we consider some particular instances, and rigorously investigate the distribution of their inter--point network distances. Our results are framed in terms of approximations, whose accuracy increases with the size of the network. We also give some insight into how the reduction in typical inter--point distances occasioned by the presence of shortcuts is related to the dimension of the underlying space., Corrected version; see also the journal ``Random Structures and Algorithms''; 30 pages, 1 figure, 1 style file

The accuracy of compound Poisson approximation can be estimated using Stein's method in terms of quantities similar to those which must be calculated for Poisson approximation. However, the solutions of the relevant Stein equation may, in general, grow exponentially fast with the mean number of ‘clumps’, leading to many applications in which the bounds are of little use. In this paper, we introduce a method for circumventing this difficulty. We establish good bounds for those solutions of the Stein equation which are needed to measure the accuracy of approximation with respect to Kolmogorov distance, but only in a restricted range of the argument. The restriction on the range is then compensated by a truncation argument. Examples are given to show that the method clearly outperforms its competitors, as soon as the mean number of clumps is even moderately large.

A tournament T on a set V of n players is an orientation of the edges of the complete graph Kn on V; T will be called a random tournament if the directions of these edges are determined by a sequence {Yj[ratio ]j = 1, …, (n2)} of independent coin flips. If (y, x) is an edge in a (random) tournament, we say that y beats x. A set A ⊂ V, |A| = k, is said to be beaten if there exists a player y ∉ A such that y beats x for each x ∈ A. If such a y does not exist, we say that A is unbeaten. A (random) tournament on V is said to have property Sk if each k-element subset of V is beaten. In this paper, we use the Stein–Chen method to show that the probability distribution of the number W0 of unbeaten k-subsets of V can be well-approximated by that of a Poisson random variable with the same mean; an improved condition for the existence of tournaments with property Sk is derived as a corollary. A multivariate version of this result is proved next: with Wj representing the number of k-subsets that are beaten by precisely j external vertices, j = 0, 1, …, b, it is shown that the joint distribution of (W0, W1, …, Wb) can be approximated by a multidimensional Poisson vector with independent components, provided that b is not too large.

For d ≥ 1, a d-clique in a graph G is a complete d-vertex subgraph not contained in any larger complete subgraph of G. We investigate the limit distribution of the number of d-cliques in the binomial random graph G(n, p), p = p(n), n→∞.

In contrast to the classical theory of partial sums of independent and identically distributed random variables, the maximum value taken by a component of a Markov population process x N is typically largely determined by the variation in its mean, rather than by stochastic fluctuation. A closer approximation to its distribution is found by considering the supremum of V ( t ) − N 1 2 c ( t ) for a suitable centred Gaussian process V , where c incorporates the effect of the variation in the mean of x N . Under appropriate conditions, it is shown that this has a distribution which is normally distributed, to within an error of order N − 1 2 log N , and expressions for the mean and variance of the approximating distribution are derived.

The Stein-Chen method for Poisson approximation is adapted into a form suitable for obtaining error estimates for the approximation of the whole distribution of a point process on a suitable topological space by that of a Poisson process. The adaptation involves consideration of an immigration-death process on the topological space, whose equilibrium distribution is that of the approximating Poisson process; the Stein equation has a simple interpretation in terms of the generator of the immigration-death process. The error estimates for process approximation in total variation do not have the ‘magic’ Stein-Chein multiplying constants, which for univariate approximation tend to zero as the mean gets larger, but examples, including Bernoulli trials and the hard-core model on the torus, show that this is not possible. By choosing weaker metrics on the space of distributions of point processes, it is possible to reintroduce these constants. The proofs actually yield an improved estimate for one of the constants in the univariate case.

Quasi-stationary distributions, as discussed by Darroch & Seneta (1965), have been used in biology to describe the steady state behaviour of population models which, while eventually certain to become extinct, nevertheless maintain an apparent stochastic equilibrium for long periods. These distributions have some drawbacks: they need not exist, nor be unique, and their calculation can present problems. In an earlier paper, we gave biologically plausible conditions under which the quasi-stationary distribution is unique, and can be closely approximated by distributions that are simple to compute. In this paper, we consider conditions under which the quasi-stationary distribution, if it exists, need not be unique, but an apparent stochastic equilibrium can nonetheless be identified and computed; we call such a distribution a quasi-equilibrium distribution., 22 pages