$U{\hbox{-}}\textrm{max}$ statistics were introduced by Lao and Mayer in 2008. Such statistics are natural in stochastic geometry. Examples are the maximal perimeters and areas of polygons and polyhedra formed by random points on a circle, ellipse, etc. The main method to study limit theorems for $U{\hbox{-}}\textrm{max}$ statistics is via a Poisson approximation. In this paper we consider a general class of kernels defined on a circle, and we prove a universal limit theorem with the Weibull distribution as a limit. Its parameters depend on the degree of the kernel, the structure of its points of maximum, and the Hessians of the kernel at these points. Almost all limit theorems known so far may be obtained as simple special cases of our general theorem. We also consider several new examples. Moreover, we consider not only the uniform distribution of points but also almost arbitrary distribution on a circle satisfying mild additional conditions.

We investigate properties of random mappings whose core is composed of derangements as opposed to permutations. Such mappings arise as the natural framework for studying the Screaming Toes game described, for example, by Peter Cameron. This mapping differs from the classical case primarily in the behaviour of the small components, and a number of explicit results are provided to illustrate these differences.

We introduce a class of non-uniform random recursive trees grown with an attachment preference for young age. Via the Chen–Stein method of Poisson approximation, we find that the outdegree of a node is characterized in the limit by ‘perturbed’ Poisson laws, and the perturbation diminishes as the node index increases. As the perturbation is attenuated, a pure Poisson limit ultimately emerges in later phases. Moreover, we derive asymptotics for the proportion of leaves and show that the limiting fraction is less than one half. Finally, we study the insertion depth in a random tree in this class. For the insertion depth, we find the exact probability distribution, involving Stirling numbers, and consequently we find the exact and asymptotic mean and variance. Under appropriate normalization, we derive a concentration law and a limiting normal distribution. Some of these results contrast with their counterparts in the uniform attachment model, and some are similar.

In this paper we first use the distribution of the number of records to demonstrate that the right tail probabilities of counts of rare events are generally better approximated by the right tail probabilities of a Poisson distribution than those of the normal distribution. We then show that the moderate deviations in Poisson approximation generally require an adjustment and, with suitable adjustment, we establish better error estimates of the moderate deviations in Poisson approximation than those in [18]. Our estimates contain no unspecified constants and are easy to apply. We illustrate the use of the theorems via six applications: Poisson-binomial distribution, the matching problem, the occupancy problem, the birthday problem, random graphs, and 2-runs. The paper complements the works [16], [8], and [18].

We consider a friendship model in which each member of a community has a latent value such that the probability that any two individuals are friends is a function of their latent values. We consider such questions as does information that i and j are both friends with k make it more likely that i and j are themselves friends. Among other things, we show that for fixed sets S and T, the more friends that i has in S, then the stochastically more friends i has in T. We consider how a variation of the friendship paradox applies to our model. We also study the distribution of the number of friendless individuals in the community and derive a bound on the total variation distance between it and a Poisson with the same mean.

In this work we deal with extreme value theory in the context of continued fractions using techniques from probability theory, ergodic theory and real analysis. We give an upper bound for the rate of convergence in the Doeblin–Iosifescu asymptotics for the exceedances of digits obtained from the regular continued fraction expansion of a number chosen randomly from $(0,1)$ according to the Gauss measure. As a consequence, we significantly improve the best known upper bound on the rate of convergence of the maxima in this case. We observe that the asymptotics of order statistics and the extremal point process can also be investigated using our methods.

It is well known that assumptions of monotonicity in size-bias couplings may be used to prove simple, yet powerful, Poisson approximation results. Here we show how these assumptions may be relaxed, establishing explicit Poisson approximation bounds (depending on the first two moments only) for random variables which satisfy an approximate version of these monotonicity conditions. These are shown to be effective for models where an underlying random variable of interest is contaminated with noise. We also state explicit Poisson approximation bounds for sums of associated or negatively associated random variables. Applications are given to epidemic models, extremes, and random sampling. Finally, we also show how similar techniques may be used to relax the assumptions needed in a Poincaré inequality and in a normal approximation result.

Poisson-like behavior for event count data is ubiquitous in nature. At the same time, differencing of such counts arises in the course of data processing in a variety of areas of application. As a result, the Skellam distribution – defined as the distribution of the difference of two independent Poisson random variables – is a natural candidate for approximating the difference of Poisson-like event counts. However, in many contexts strict independence, whether between counts or among events within counts, is not a tenable assumption. Here we characterize the accuracy in approximating the difference of Poisson-like counts by a Skellam random variable. Our results fully generalize existing, more limited, results in this direction and, at the same time, our derivations are significantly more concise and elegant. We illustrate the potential impact of these results in the context of problems from network analysis and image processing, where various forms of weak dependence can be expected.

Consider a graph on randomly scattered points in an arbitrary space, with any two points x, y connected with probability ϕ(x, y). Suppose the number of points is large but the mean number of isolated points is O(1). We give general criteria for the latter to be approximately Poisson distributed. More generally, we consider the number of vertices of fixed degree, the number of components of fixed order, and the number of edges. We use a general result on Poisson approximation by Stein's method for a set of points selected from a Poisson point process. This method also gives a good Poisson approximation for U-statistics of a Poisson process.

We take a fresh look at the classical problem of runs in a sequence of independent and identically distributed coin tosses and derive a general identity/recursion which can be used to compute (joint) distributions of functionals of run types. This generalizes and unifies already existing approaches. We give several examples, derive asymptotics, and pose some further questions.

In this article we study a number of collisions concerning a simple occupancy problem with unequal probabilities. Using combinatorial arguments and negative associations of random variables, we have several limit theorems, namely, a weak law of large numbers and a Poisson law of small numbers including the Chen-Stein estimate.

We consider spatial stochastic models, which can be applied to, e.g. telecommunication networks with two hierarchy levels. In particular, we consider Cox processes XL and XH concentrated on the edge set T(1) of a random tessellation T, where the points XL,n and XH,n of XL and XH can describe the locations of low-level and high-level network components, respectively, and T(1) the underlying infrastructure of the network, such as road systems, railways, etc. Furthermore, each point XL,n of XL is marked with the shortest path along the edges of T to the nearest (in the Euclidean sense) point of XH. We investigate the typical shortest path length C* of the resulting marked point process, which is an important characteristic in, e.g. performance analysis and planning of telecommunication networks. In particular, we show that the distribution of C* converges to simple parametric limit distributions if a scaling factor κ converges to 0 or ∞. This can be used to approximate the density of C* by analytical formulae for a wide range of κ.

A random intersection graph G(n, m, p) is defined on a set V of n vertices. There is an auxiliary set W consisting of m objects, and each vertex v ∈ V is assigned a random subset of objects Wv ⊆ W such that w ∈ Wv with probability p, independently for all v ∈ V and all w ∈ W. Given two vertices v1, v2 ∈ V, we set v1 ∼ v2 if and only if Wv1 ∩ Wv2 ≠ ∅. We use Stein's method to obtain an upper bound on the total variation distance between the distribution of the number of h-cliques in G(n, m, p) and a related Poisson distribution for any fixed integer h.

Expectations of unbounded functions of dependent nonnegative integer-valued random variables are approximated by the expectations of the functions of independent copies of these random variables. The Lindeberg method is used.

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.

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.

We study collision probabilities concerning the simple balls-and-bins problem developed by Wendl (2003). In this article we give the factorial moment of the number of collisions. Moreover, we obtain a Poisson approximation for the number of collisions using the Chen-Stein method.

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.

Detection of repeated sequences within complete genomes is a powerful tool to help understanding genome dynamics and species evolutionary history. To distinguish significant repeats from those that can be obtained just by chance, statistical methods have to be developed. In this paper we show that the distribution of the number of long repeats in long sequences generated by stationary Markov chains can be approximated by a Poisson distribution with explicit parameter. Thanks to the Chen-Stein method we provide a bound for the approximation error; this bound converges to 0 as soon as the length n of the sequence tends to ∞ and the length t of the repeats satisfies n2ρt = O(1) for some 0 < ρ < 1. Using this Poisson approximation, p-values can then be easily calculated to determine if a given genome is significantly enriched in repeats of length t.

A stack is a structural unit in an RNA structure that is formed by pairs of hydrogen bonded nucleotides. Paired nucleotides are scored according to their ability to hydrogen bond. We consider stack/hairpin-loop structures for a sequence of independent and identically distributed random variables with values in a finite alphabet, and we show how to obtain an asymptotic Poisson distribution of the number of stack/hairpin-loop structures with a score exceeding a high threshold, given that we count in a proper, declumped way. From this result we obtain an asymptotic Gumbel distribution of the maximal stack score. We also provide examples focusing on the computation of constants that enter in the asymptotic distributions. Finally, we discuss the close relation to existing results for local alignment.