Search

We propose a new approach to Poisson approximation. The basic idea is very simple and based on properties of the Charlier polynomials and the Parseval identity. Such an approach quickly leads to new effective bounds for several Poisson approximation problems. We also give a selected survey on diverse Poisson approximation results.

We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio α of the level and the logarithm of tree size lies in [0,e). Convergence of all moments is shown to hold only for α ∈ [0,1] (with only convergence of finite moments when α ∈ (1,e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for α = 0 and a "quicksort type" limit law for α = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees; we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.

We propose means for computing the Fourier expansions of periodic functions appearing in higher moments of the sum-of-digits function and in the solutions of some divide-and-conquer recurrences. The expansions are shown to be absolutely convergent. We also give a new approach to efficiently compute numerically the coefficients involved to high precision.

A fine analysis is given of the transitional behavior of the average cost of quicksort with median-of-three. Asymptotic formulae are derived for the stepwise improvement of the average cost of quicksort when iterating median-of-threek rounds for all possible values ofk. The methods used are general enough to apply to quicksort with median-of-(2t + 1) and to explain in a precise manner the transitional behaviors of the average cost from insertion sort to quicksort proper. Our results also imply nontrivial bounds on the expected height, "saturation level," and width in a random locally balanced binary search tree.

We examine in detail the asymptotic behaviors of the number of comparisons used in Batcher's sorting algorithm and a quantity arising in analyzing the rectangle heuristic for finding minimum Euclidean matching due to Supowit and Reingold. We put forth methods (elementary and analytic) for computing the Fourier coefficients of periodic functions appearing in the asymptotic expansions of these quantities. The methods consist of the approach by Flajolet and Golin for divide-and-conquer recurrences and van der Corput's method from analytic number theory for exponential sums.

This note provides exact formulae for the mean and variance of the cost of top-down recursive mergesort. These formulae improve upon earlier results of Flajolet and Golin.