We use Stein’s method to establish the rates of normal approximation in terms of the total variation distance for a large class of sums of score functions of samples arising from random events driven by a marked Poisson point process on $\mathbb{R}^d$. As in the study under the weaker Kolmogorov distance, the score functions are assumed to satisfy stabilisation and moment conditions. At the cost of an additional non-singularity condition, we show that the rates are in line with those under the Kolmogorov distance. We demonstrate the use of the theorems in four applications: Voronoi tessellations, k-nearest-neighbours graphs, timber volume, and maximal layers.

In this paper we study the asymptotic behaviour of a random uniform parking function $\pi_n$ of size n. We show that the first $k_n$ places $\pi_n(1),\ldots,\pi_n(k_n)$ of $\pi_n$ are asymptotically independent and identically distributed (i.i.d.) and uniform on $\{1,2,\ldots,n\}$, for the total variation distance when $k_n = {\rm{o}}(\sqrt{n})$, and for the Kolmogorov distance when $k_n={\rm{o}}(n)$, improving results of Diaconis and Hicks. Moreover, we give bounds for the rate of convergence, as well as limit theorems for certain statistics such as the sum or the maximum of the first $k_n$ parking places. The main tool is a reformulation using conditioned random walks.

We prove some estimates for the variations of transition probabilities of the (1+1)-affine process. From these estimates we deduce the strong Feller and the ergodic properties of the total variation distance of the process. The key strategy is the pathwise construction and analysis of several Markov couplings using strong solutions of stochastic equations.

During the last decades, quite a number of interacting particle systems have been introduced and studied in the crossover area of mathematics and statistical physics. Some of these can be seen as simplistic models for opinion formation processes in groups of interacting people. In the model introduced by Deffuant et al. (2000), agents that are neighbors on a given network graph, randomly meet in pairs and approach a compromise if their current opinions do not differ by more than a given threshold value θ. We consider the two-sided infinite path ℤ as the underlying graph and extend existing models to a setting in which opinions are given by probability distributions. Similar to what has been shown for finite-dimensional opinions, we observe a dichotomy in the long-term behavior of the model, but only if the initial narrow mindedness of the agents is restricted.

The contribution of the theory of scan statistics to the study of many real-life applications has been rapidly expanding during the last decades. The multiple scan statistic, defined on a sequence of n Bernoulli trials, enumerates the number of occurrences of k consecutive trials which contain at least r successes among them (r≤k≤n). In this paper we establish some asymptotic results for the distribution of the multiple scan statistic, as n,k,r→∞ and illustrate their accuracy through a simulation study. Our approach is based on an appropriate combination of compound Poisson approximation and random walk theory.

In this paper we study the mixing time of certain adaptive Markov chain Monte Carlo (MCMC) algorithms. Under some regularity conditions, we show that the convergence rate of importance resampling MCMC algorithms, measured in terms of the total variation distance, is O(n-1). By means of an example, we establish that, in general, this algorithm does not converge at a faster rate. We also study the interacting tempering algorithm, a simplified version of the equi-energy sampler, and establish that its mixing time is of order O(n-1/2).

A random k-out mapping (digraph) on [n] is generated by choosing k random images of each vertex one at a time, subject to a 'preferential attachment' rule: the current vertex selects an image i with probability proportional to a given parameter α = α(n) plus the number of times i has already been selected. Intuitively, the larger α becomes, the closer the resulting k-out mapping is to the uniformly random k-out mapping. We prove that α = Θ(n1/2) is the threshold for α growing 'fast enough' to make the random digraph approach the uniformly random digraph in terms of the total variation distance. We also determine an exact limit for this distance for the α = βn1/2 case.

For a collection of objects such as socks, which can be matched according to a characteristic such as color, we study the innocent phrase ‘the distribution of the color of a matching pair’ by looking at two methods for selecting socks. One method is memoryless and effectively samples socks with replacement, while the other samples socks sequentially, with memory, until the same color has been seen twice. We prove that these two methods yield the same distribution on colors if and only if the initial distribution of colors is a uniform distribution. We conjecture a nontrivial maximum value for the total variation distance of these distributions in all other cases.

A stochastic ordering approach is applied with Stein's method for approximation by the equilibrium distribution of a birth-death process. The usual stochastic order and the more general s-convex orders are discussed. Attention is focused on Poisson and translated Poisson approximations of a sum of dependent Bernoulli random variables, for example, k-runs in independent and identically distributed Bernoulli trials. Other applications include approximation by polynomial birth-death distributions.

Quasi-stationary distributions, as discussed in Darroch and 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 this paper, we give 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 refine a Poisson limit theorem of Gnedenko and Kolmogorov (1954): we determine the error order of a Poisson approximation for sums of asymptotically negligible integer-valued random variables that converge in distribution to the Poisson law. As an application of our results, we investigate the case of the coupon collector's problem when the distribution of the collector's waiting time is asymptotically Poisson.

Let X1, X2,… and Y1, Y2,… be two sequences of absolutely continuous, independent and identically distributed (i.i.d.) random variables with equal means E(Xi)=E(Yi), i=1,2,… In this work we provide upper bounds for the total variation and Kolmogorov distances between the distributions of the partial sums ∑i=1nXi and ∑i=1nYi. In the case where the distributions of the Xis and the Yis are compared with respect to the convex order, the proposed upper bounds are further refined. Finally, in order to illustrate the applicability of the results presented, we consider specific examples concerning gamma and normal approximations.

We present a method to obtain both exact values and sharp estimates for the total variation distance between binomial and Poisson distributions with the same mean λ. We give a simple efficient algorithm, whose complexity order is to compute exact values. Such an algorithm can be further simplified for moderate sample sizes n, provided that λ is neither close to from the left nor close to from the right. Sharp estimates, better than other known estimates in the literature, are also provided. The 0s of the second Krawtchouk and Charlier polynomials play a fundamental role.

The distributions of the run occurrences for a sequence of independent and identically distributed (i.i.d.) experiments are usually obtained by combinatorial methods (see Balakrishnan and Koutras (2002, Chapter 5)) and the resulting formulae are often very tedious, while the distributions for non i.i.d. experiments are generally intractable. It is therefore of practical interest to find a suitable approximate model with reasonable approximation accuracy. In this paper we demonstrate that the negative binomial distribution is the most suitable approximate model for the number of k-runs: it outperforms the Poisson approximation, the general compound Poisson approximation as observed in Eichelsbacher and Roos (1999), and the translated Poisson approximation in Rollin (2005). In particular, its accuracy of approximation in terms of the total variation distance improves when the number of experiments increases, in the same way as the normal approximation improves in the Berry-Esseen theorem.

In designing a network to link n points in a square of area n, we might be guided by the following two desiderata. First, the total network length should not be much greater than the length of the shortest network connecting all points. Second, the average route length (taken over source-destination pairs) should not be much greater than the average straight-line distance. How small can we make these two excesses? Speaking loosely, for a nondegenerate configuration, the total network length must be at least of order n and the average straight-line distance must be at least of order n1/2, so it seems implausible that a single network might exist in which the excess over the first minimum is o(n) and the excess over the second minimum is o(n1/2). But in fact we can do better: for an arbitrary configuration, we can construct a network where the first excess is o(n) and the second excess is almost as small as O(log n). The construction is conceptually simple and uses stochastic methods: over the minimum-length connected network (Steiner tree) superimpose a sparse stationary and isotropic Poisson line process. Together with a few additions (required for technical reasons), the mean values of the excess for the resulting random network satisfy the above asymptotics; hence, a standard application of the probabilistic method guarantees the existence of deterministic networks as required (speaking constructively, such networks can be constructed using simple rejection sampling). The key ingredient is a new result about the Poisson line process. Consider two points a distance r apart, and delete from the line process all lines which separate these two points. The resulting pattern of lines partitions the plane into cells; the cell containing the two points has mean boundary length approximately equal to 2r + constant(log r). Turning to lower bounds, consider a sequence of networks in satisfying a weak equidistribution assumption. We show that if the first excess is O(n) then the second excess cannot be

We show how good multivariate Poisson mixtures can be approximated by multivariate Poisson distributions and related finite signed measures. Upper bounds for the total variation distance with applications to risk theory and generalized negative multinomial distributions are given. Furthermore, it turns out that the ideas used in this paper also lead to improvements in the Poisson approximation of generalized multinomial distributions.

In this paper, we consider the total variation distance between the distributions of two random sums SM and SN with different random summation indices M and N. We derive upper bounds, some of which are sharp. Further, bounds with so-called magic factors are possible. Better results are possible when M and N are stochastically or stop-loss ordered. It turns out that the solution of this approximation problem strongly depends on how many of the first moments of M and N coincide. As approximations, we therefore choose suitable finite signed measures, which coincide with the distribution of the approximating random sum SN if M and N have the same first moments.

The random variables X1, X2, …, Xn are said to be totally negatively dependent (TND) if and only if the random variables Xi and ∑j≠iXj are negatively quadrant dependent for all i. Our main result provides, for TND 0-1 indicators X1, x2, …, Xn with P[Xi = 1] = pi = 1 - P[Xi = 0], an upper bound for the total variation distance between ∑ni=1Xi and a Poisson random variable with mean λ ≥ ∑ni=1pi. An application to a generalized birthday problem is considered and, moreover, some related results concerning the existence of monotone couplings are discussed.

We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.