In this work we analyze a class of 2 × 2 Pólya-Eggenberger urn models with ball replacement matrix and c = pa with . We determine limiting distributions by obtaining a precise recursive description of the moments of the considered random variables, which allows us to deduce asymptotic expansions of the moments. In particular, we obtain limiting distributions for the pills problem a = c = d = 1, originally proposed by Knuth and McCarthy. Furthermore, we also obtain limiting distributions for the well-known sampling without replacement urn, a = d = 1 and c = 0, and generalizations of it to arbitrary and c = 0. Moreover, we obtain a recursive description of the moment sequence for a generalized problem.

We consider sequential selection of an alternating subsequence from a sequence of independent, identically distributed, continuous random variables, and we determine the exact asymptotic behavior of an optimal sequentially selected subsequence. Moreover, we find (in a sense we make precise) that a person who is constrained to make sequential selections does only about 12 percent worse than a person who can make selections with full knowledge of the random sequence.

We investigate the Zagreb index, one of the topological indices, of random recursive trees in this paper. Through a recurrence equation, the first two moments of Z n , the Zagreb index of a random recursive tree of size n, are obtained. We also show that the random process {Z n − E[Z n ], n ≥ 1} is a martingale. Then the asymptotic normality of the Zagreb index of a random recursive tree is given by an application of the martingale central limit theorem. Finally, two other topological indices are also discussed in passing.

This paper presents an analysis of a generalized version of the coupon collector problem, in which the collector receives d coupons each run and chooses the least-collected coupon so far. In the asymptotic case when the number of coupons n goes to infinity, we show that, on average, (nlogn) / d + (n / d)(m − 1)log logn + O(mn) runs are needed to collect m sets of coupons. An exact algorithm is also developed for any finite case to compute the exact mean number of runs. Numerical examples are provided to verify our theoretical predictions.

We consider the Λ-coalescent processes with a positive frequency of singleton clusters. The class in focus covers, for instance, the beta(a, b)-coalescents with a > 1. We show that some large-sample properties of these processes can be derived by coupling the coalescent with an increasing Lévy process (subordinator), and by exploiting parallels with the theory of regenerative composition structures. In particular, we discuss the limit distributions of the absorption time and the number of collisions.

In this paper we investigate the relationship between the sampling formula and Laplace transform associated with the two-parameter Poisson-Dirichlet distribution. We conclude that they are equivalent to determining the corresponding infinite-dimensional distribution. With these tools, a central limit theorem is established associated with the infinitely-many-neutral-alleles model at any fixed time. We also obtain the probability generating function of random sampling from a generalized two-parameter diffusion process. At the end of the paper a selection case is considered.

Limit theorems are established for some functionals of the distances between two nodes in weighted random b-ary recursive trees. We consider the depth of the nth node and of a random node, the distance between two random nodes, the internal path length, and the Wiener index. As an application, these limit results imply, by an imbedding argument, corresponding limit theorems for further classes of random trees: plane-oriented recursive trees and random linear recursive trees.

In the so-called lightbulb process, on days r = 1,…,n, out of n lightbulbs, all initially off, exactly r bulbs, selected uniformly and independent of the past, have their status changed from off to on, or vice versa. With X the number of bulbs on at the terminal time n, an even integer, and μ = n/2, σ2 = var(X), we have supz ∈ R | P((X - μ)/σ ≤ z) - P(Z ≤ z) | ≤ nΔ̅0/2σ2 + 1.64n/σ3 + 2/σ, where Z is a standard normal random variable and Δ̅0 = 1/2√n + 1/2n + e−n/2/3 for n ≥ 6, yielding a bound of order O(n−1/2) as n → ∞. A similar, though slightly larger bound, holds for odd n. The results are shown using a version of Stein's method for bounded, monotone size bias couplings. The argument for even n depends on the construction of a variable Xs on the same space as X that has the X-size bias distribution, that is, which satisfies E[Xg(X)] = μE[g(Xs)] for all bounded continuous g, and for which there exists a B ≥ 0, in this case B = 2, such that X ≤ Xs ≤ X + B almost surely. The argument for odd n is similar to that for even n, but one first couples X closely to V, a symmetrized version of X, for which a size bias coupling of V to Vs can proceed as in the even case. In both the even and odd cases, the crucial calculation of the variance of a conditional expectation requires detailed information on the spectral decomposition of the lightbulb chain.

Radix Sort is a sorting algorithm based on analyzing digital data. We study the number of swaps made by Radix Select (a one-sided version of Radix Sort) to find an element with a randomly selected rank. This kind of grand average provides a smoothing over all individual distributions for specific fixed-order statistics. We give an exact analysis for the grand mean and an asymptotic analysis for the grand variance, obtained by poissonization, the Mellin transform, and depoissonization. The digital data model considered is the Bernoulli(p). The distributions involved in the swaps experience a phase change between the biased cases (p ≠ ½) and the unbiased case (p = ½). In the biased cases, the grand distribution for the number of swaps (when suitably scaled) converges to that of a perpetuity built from a two-point distribution. The tool for this proof is contraction in the Wasserstein metric space, and identifying the limit as the fixed-point solution of a distributional equation. In the unbiased case the same scaling for the number of swaps gives a limiting constant in probability.

We consider a serialized coin-tossing leader election algorithm that proceeds in rounds until a winner is chosen, or all contestants are eliminated. The analysis allows for either biased or fair coins. We find the exact distribution for the duration of any fixed contestant; asymptotically, it turns out to be a geometric distribution. Rice's method (an analytic technique) shows that the moments of the duration contain oscillations, which we give explicitly for the mean and variance. We also use convergence in the Wasserstein metric space to show that the distribution of the total number of coin flips (among all participants), suitably normalized, approaches a normal limiting random variable.

In this paper we study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in Holmgren (2010), which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quad trees, medians of (2k + 1)-trees, simplex trees, tries, and digital search trees.

We consider a generalized form of the coupon collection problem in which a random number, S, of balls is drawn at each stage from an urn initially containing n white balls (coupons). Each white ball drawn is colored red and returned to the urn; red balls drawn are simply returned to the urn. The question considered is then: how many white balls (uncollected coupons) remain in the urn after the kn draws? Our analysis is asymptotic as n → ∞. We concentrate on the case when kn draws are made, where kn / n → ∞ (the superlinear case), although we sketch known results for other ranges of kn. A Gaussian limit is obtained via a martingale representation for the lower superlinear range, and a Poisson limit is derived for the upper boundary of this range via the Chen-Stein approximation.

In this paper we study the size of the largest clique ω(G(n, α)) in a random graph G(n, α) on n vertices which has power-law degree distribution with exponent α. We show that, for ‘flat’ degree sequences with α > 2, with high probability, the largest clique in G(n, α) is of a constant size, while, for the heavy tail distribution, when 0 < α < 2, ω(G(n, α)) grows as a power of n. Moreover, we show that a natural simple algorithm with high probability finds in G(n, α) a large clique of size (1 − o(1))ω(G(n, α)) in polynomial time.

We investigate the final size distribution of the SIR (susceptible-infected-recovered) epidemic model in the critical regime. Using the integral representation of Martin-Löf (1998) for the hitting time of a Brownian motion with parabolic drift, we derive asymptotic expressions for the final size distribution that capture the effect of the initial number of infectives and the closeness of the reproduction number to zero. These asymptotics shed light on the bimodularity of the limiting density of the final size observed in Martin-Löf (1998). We also discuss the connection to the largest component in the Erdős-Rényi random graph, and, using this connection, find an integral expression of the Laplace transform of the normalized Brownian excursion area in terms of Airy functions.

In this paper we consider a generalized coupon collection problem in which a customer repeatedly buys a random number of distinct coupons in order to gather a large number n of available coupons. We address the following question: How many different coupons are collected after k = kn draws, as n → ∞? We identify three phases of kn: the sublinear, the linear, and the superlinear. In the growing sublinear phase we see o(n) different coupons, and, with true randomness in the number of purchases, under the appropriate centering and scaling, a Gaussian distribution is obtained across the entire phase. However, if the number of purchases is fixed, a degeneracy arises and normality holds only at the higher end of this phase. If the number of purchases have a fixed range, the small number of different coupons collected in the sublinear phase is upgraded to a number in need of centering and scaling to become normally distributed in the linear phase with a different normal distribution of the type that appears in the usual central limit theorems. The Gaussian results are obtained via martingale theory. We say a few words in passing about the high probability of collecting nearly all the coupons in the superlinear phase. It is our aim to present the results in a way that explores the critical transition at the ‘seam line’ between different Gaussian phases, and between these phases and other nonnormal phases.

We study first passage percolation (FPP) on the configuration model (CM) having power-law degrees with exponent τ ∈ [1, 2) and exponential edge weights. We derive the distributional limit of the minimal weight of a path between typical vertices in the network and the number of edges on the minimal-weight path, both of which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via construction of infinite limiting objects describing the FPP problem in the densely connected core of the network. We consider two separate cases, the original CM, in which each edge, regardless of its multiplicity, receives an independent exponential weight, and the erased CM, for which there is an independent exponential weight between any pair of direct neighbors. While the results are qualitatively similar, surprisingly, the limiting random variables are quite different. Our results imply that the flow carrying properties of the network are markedly different from either the mean-field setting or the locally tree-like setting, which occurs as τ > 2, and for which the hopcount between typical vertices scales as log n. In our setting the hopcount is tight and has an explicit limiting distribution, showing that information can be transferred remarkably quickly between different vertices in the network. This efficiency has a down side in that such networks are remarkably fragile to directed attacks. These results continue a general program by the authors to obtain a complete picture of how random disorder changes the inherent geometry of various random network models; see Aldous and Bhamidi (2010), Bhamidi (2008), and Bhamidi, van der Hofstad and Hooghiemstra (2009).

The Ehrenfest urn is a model for the diffusion of gases between two chambers. Classic research deals with this system as a Markovian model with a fixed number of balls, and derives the steady-state behavior as a binomial distribution (which can be approximated by a normal distribution). We study the gradual change for an urn containing n (a very large number) balls from the initial condition to the steady state. We look at the status of the urn after kn draws. We identify three phases of kn: the growing sublinear, the linear, and the superlinear. In the growing sublinear phase the amount of gas in each chamber is normally distributed, with parameters that are influenced by the initial conditions. In the linear phase a different normal distribution applies, in which the influence of the initial conditions is attenuated. The steady state is not a good approximation until a certain superlinear amount of time has elapsed. At the superlinear stage the mix is nearly perfect, with a nearly perfect symmetrical normal distribution in which the effect of the initial conditions is completely washed away. We give interpretations for how the results in different phases conjoin at the ‘seam lines’. In fact, these Gaussian phases are all manifestations of one master theorem. The results are obtained via martingale theory.

Recurrence equations for the number of types and the frequency of each type in a random sample drawn from a finite population undergoing discrete, nonoverlapping generations and reproducing according to the Cannings exchangeable model are deduced under the assumption of a mutation scheme with infinitely many types. The case of overlapping generations in discrete time is also considered. The equations are developed for the Wright-Fisher model and the Moran model, and extended to the case of the limit coalescent with nonrecurrent mutation as the population size goes to ∞ and the mutation rate to 0. Computations of the total variation distance for the distribution of the number of types in the sample suggest that the exact Moran model provides a better approximation for the sampling formula under the exact Wright-Fisher model than the Ewens sampling formula in the limit of the Kingman coalescent with nonrecurrent mutation. On the other hand, this model seems to provide a good approximation for a Λ-coalescent with nonrecurrent mutation as long as the probability of multiple mergers and the mutation rate are small enough.

We introduce and motivate the study of (n + 1) × r arrays X with Bernoulli entries Xk,j and independently distributed rows. We study the distribution of which denotes the number of consecutive pairs of successes (or runs of length 2) when reading the array down the columns and across the rows. With the case r = 1 having been studied by several authors, and permitting some initial inferences for the general case r > 1, we examine various distributional properties and representations of Sn for the case r = 2, and, using a more explicit analysis, the case of multinomial and identically distributed rows. Applications are also given in cases where the array X arises from a Pólya sampling scheme.

We consider a variety of subtrees of various shapes lying on the fringe of a recursive tree. We prove that (under suitable normalization) the number of isomorphic images of a given fixed tree shape on the fringe of the recursive tree is asymptotically Gaussian. The parameters of the asymptotic normal distribution involve the shape functional of the given tree. The proof uses the contraction method.