Search

We give a detailed analysis of the cost used by the (1+1)-evolutionary algorithm. The problem has been approached in the evolutionary algorithm literature under various views, formulation and degree of rigor. Our asymptotic approximations for the mean and the variance represent the strongest of their kind. The approach we develop is also applicable to characterize the limit laws and is based on asymptotic resolution of the underlying recurrence. While most approximations have their simple formal nature, we elaborate on the delicate error analysis required for rigorous justifications., 53 pages with 8 figures and 4 appendices

We establish the asymptotic normality of the dimension of large-size random Fishburn matrices by a complex-analytic approach. The corresponding dual problem of size distribution under large dimension is also addressed and follows a quadratic type normal limit law. These results represent the first of their kind and solve two open questions raised in the combinatorial literature. They are presented in a general framework where the entries of the Fishburn matrices are not limited to binary or nonnegative integers. The analytic saddle-point approach we apply, based on a powerful transformation for $q$-series due to Andrews and Jel\'inek, is also useful in solving a conjecture of Stoimenow in Vassiliev invariants., Comment: 35 pages, comments are welcome

We study the joint asymptotic behavior of the space requirement and the total path length either summing over all root-key distances or over all root-node distances in random m-ary search trees. The covariance turns out to exhibit a change of asymptotic behavior: it is essentially linear when 3i¾?mi¾?13, but becomes of higher order when mi¾?14. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 3i¾?mi¾?26, but is periodically oscillating for larger m, and we also prove asymptotic independence when 3i¾?mi¾?26. Such a less anticipated phenomenon is not exceptional and our results can be extended in two directions: one for more general shape parameters, and the other for other classes of random log-trees such as fringe-balanced binary search trees and quadtrees. The methods of proof combine asymptotic transfer for the underlying recurrence relations with the contraction method. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 353-379, 2017

We study linear recurrences of Eulerian type of the form P n ( v ) = ( α ( v ) n + γ ( v ) ) P n − 1 ( v ) + β ( v ) ( 1 − v ) P n − 1 ′ ( v ) ( n ⩾ 1 ) , with P 0 ( v ) given, where α ( v ) , β ( v ) and γ ( v ) are in most cases polynomials of low degrees. We characterize the various limit laws of the coefficients of P n ( v ) for large n using the method of moments and analytic combinatorial tools under varying α ( v ) , β ( v ) and γ ( v ) , and apply our results to more than two hundred of concrete examples when β ( v ) ≠ 0 and more than three hundred when β ( v ) = 0 that we gathered from the literature and from Sloane's OEIS database. The limit laws and the convergence rates we worked out are almost all new and include normal, half-normal, Rayleigh, beta, Poisson, negative binomial, Mittag-Leffler, Bernoulli, etc., showing the surprising richness and diversity of such a simple framework, as well as the power of the approaches used.

We give a detailed asymptotic analysis of the profiles of random symmetric digital search trees, which are in close connection with the performance of the search complexity of random queries in such trees. While the expected profiles have been analyzed for several decades, the analysis of the variance turns out to be very difficult and challenging, and requires the combination of several different analytic techniques, including Mellin and Laplace transforms, analytic de-Poissonization, and Laplace convolutions. Our results imply concentration of the profiles in the range where the mean tends to infinity. Moreover, we also obtain a two-point concentration for the distributions of the height and the saturation level., The central limit theorem was removed from this version (and moved to a follow-up paper) since the proof in the previous versions was incomplete. Also, the word "Concentration Properties" was added to the title since this part now entirely focuses on such results

We consider sequences of random variables whose probability generating functions have only roots on the unit circle, which has only been sporadically studied in the literature. We show that the random variables are asymptotically normally distributed if and only if the fourth central and normalized by the standard deviation moment tends to 3, in contrast to the common scenario for polynomials with only real roots for which a central limit theorem holds if and only if the variance is unbounded. We also derive a representation theorem for all possible limit laws and apply our results to many concrete examples in the literature, ranging from combinatorial structures to numerical analysis, and from probability to analysis of algorithms. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,707-738, 2015

An unusual and surprising expansion of the form pn=ρ-n-1(6n+185+3363125n-5+10083125n-6+smaller order terms), as n→∞, is derived for the probability pn that two randomly chosen binary search trees are identical (in shape, hence in labels of all corresponding nodes). A quantity arising in the analysis of phylogenetic trees is also proved to have a similar asymptotic expansion. Our method of proof is new in the literature of discrete probability and the analysis of algorithms, and it is based on the logarithmic psi-series expansions for nonlinear differential equations. Such an approach is very general and applicable to many other problems involving nonlinear differential equations; many examples are discussed in this article and several attractive phenomena are discovered. © 2012 Wiley Periodicals, Inc.

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.

Random increasing k-trees represent an interesting and useful class of strongly dependent graphs that have been studied widely, including being used recently as models for complex networks. In this paper we study an informative notion called BFS-profile and derive, by several analytic means, asymptotic estimates for its expected value, together with the limiting distribution in certain cases; some interesting consequences predicting more precisely the shapes of random k-trees are also given. Our methods of proof rely essentially on a bijection between k-trees and ordinary trees, the resolution of linear systems, and a specially framed notion called Flajolet–Odlyzko admissibility.

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 solve the open problem of characterizing the leading constant in the asymptotic approximation to the expected cost used for random partial match queries in random k-d trees. Our approach is new and of some generality; in particular, it is applicable to many problems involving differential equations (or difference equations) with polynomial coefficients.

In a tree, a level consists of all those nodes that are the same distance from the root. We derive asymptotic approximations to the correlation coefficients of two level sizes in random recursive trees and binary search trees. These coefficients undergo sharp sign-changes when one level is fixed and the other is varying. We also propose a new means of deriving an asymptotic estimate for the expected width, which is the number of nodes at the most abundant level. Crucial to our methods of proof is the uniformity achieved by singularity analysis.

We derive a Berry-Esseen bound, essentially of the order of the square of the standard deviation, for the number of maxima in random samples from (0, 1)d. The bound is, although not optimal, the first of its kind for the number of maxima in dimensions higher than two. The proof uses Poisson processes and Stein's method. We also propose a new method for computing the variance and derive an asymptotic expansion. The methods of proof we propose are of some generality and applicable to other regions such as d-dimensional simplex.

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.

Cauchy-Euler differential equations surfaced naturally in a number of sorting and searching problems, notably in quicksort and binary search trees and their variations. Asymptotics of coefficients of functions satisfying such equations has been studied for several special cases in the literature. We study in this paper a very general framework for Cauchy-Euler equations and propose an asymptotic theory that covers almost all applications where Cauchy-Euler equations appear. Our approach is very general and requires almost no background on differential equations. Indeed the whole theory can be stated in terms of recurrences instead of functions. Old and new applications of the theory are given. New phase changes of limit laws of new variations of quicksort are systematically derived. We apply our theory to about a dozen of diverse examples in quicksort, binary search trees, urn models, increasing trees, etc.

We show that the limiting distribution of the number of comparisons used by Hoare's quickselect algorithm when given a random permutation of n elements for finding the mth-smallest element, where m = o(n), is the Dickman function. The limiting distribution of the number of exchanges is also derived.

We derive uniform asymptotic expressions of some Abel sums appearing in some problems in coding theory and indicate the usefulness of these sums in other fields, like empirical processes, machine maintenance, analysis of algorithms, probabilistic number theory, queuing models, etc.

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 propose a uniform approach to describe the phase change of the limiting distribution of space measures in random m-ary search trees: the space requirement, when properly normalized, is asymptotically normally distributed for m≤26 and does not have a fixed limiting distribution for m>26. Our tools are based on the method of moments and asymptotic solutions of differential equations, and are applicable to secondary cost measures of quicksort with median-of-(2t+1) for which the same phase change occurs at t=58. Both problems are essentially special cases of the generalized quicksort of Hennequin in which a sample of m(t+1)−1 elements are used to select m−1 equi-spaced ranks that are used in turn to partition the input into m subfiles. A complete description of the numbers at which the phase change occurs is given. For example, when m is fixed and t varies, the phase change occurs at (m, t)={(2, 58), (3, 19), (4, 10), (5, 6), (6, 4), …}. We also indicate some applications of our approach to other problems including bucket recursive trees. A general framework on “asymptotic transfers” of the underlying recurrence is also given. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 316–358, 2001

We study the distribution of the number n;r of r consecutive records in a sequence of n independent and identically distributed random variables from a common continuous distribution, or equivalently, in a random permutation ofn elements. We show that the asymptotic distribution of n;r is Poisson for r = 1; 2 and non-Poisson for r 3. Precise asymptotic results are derived for four probability distances of the associated approximations: Fortet-Mourier, total variation, Kolmogorov, and point metric. In particular, the distributions of n;r have the specic property that the last three distances are asymptotically of the same behaviors for r 2. We also provide interesting combinatorial bijections for n;2 and compute explicitly the limiting law for n;3 in terms of Kummer’s conuent hypergeometric functions.

A general analytic scheme for Poisson approximation to discrete distributions is studied in which the asymptotic behaviours of the generalized total variation, Fortet-Mourier (or Wasserstein), Kolmogorov and Matusita (or Hellinger) distances are explicitly characterized. Applications of this result include many number-theoretic functions and combinatorial structures. Our approach differs from most of the existing ones in the literature and is easily amended for other discrete approximations; arithmetic and combinatorial examples for Bessel approximation are also presented. A unified approach is developed for deriving uniform estimates for probability generating functions of the number of components in general decomposable combinatorial structures, with or without analytic continuation outside their circles of convergence.

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.

We establish the asymptotic normality of the number of upper records in a sequence of iid geometric random variables. Large deviations and local limit theorems as well as approximation theorems for the number of lower records are also derived.

Let Fq[X] denote a polynomial ring over a finite field Fq with q elements. Let n be the set of monic polynomials over Fq of degree n. Assuming that each of the qn possible monic polynomials in n is equally likely, we give a complete characterization of the limiting behavior of P(Ωn=m) as n∞ by a uniform asymptotic formula valid for m≥1 and n−m∞, where Ωn represents the number (multiplicities counted) of irreducible factors in the factorization of a random polynomial in n. The distribution of Ωn is essentially the convolution of a Poisson distribution with mean log n and a negative binomial distribution with parameters q and q−1. Such a convolution law exhibits three modes of asymptotic behaviors: when m is small, it behaves like a Poisson distribution; when m becomes large, its behavior is dominated by a negative binomial distribution, the transitional behavior being essentially a parabolic cylinder function (or some linear combinations of the standard normal law and its iterated integrals). As applications of this uniform asymptotic formula, we derive most known results concerning P(Ωn=m) and present many new ones like the unimodality of the distribution. The methods used are widely applicable to other problems on multiset constructions. An extension to Renyi's problem, concerning the distribution of the difference of the (total) number of irreducibles and the number of distinct irreducibles, is also presented. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 17–47, 1998

Given a class of combinatorial structures [Cscr ], we consider the quantity N(n, m), the number of multiset constructions [Pscr ] (of [Cscr ]) of size n having exactly m [Cscr ]-components. Under general analytic conditions on the generating function of [Cscr ], we derive precise asymptotic estimates for N(n, m), as n→∞ and m varies through all possible values (in general 1[les ]m[les ]n). In particular, we show that the number of [Cscr ]-components in a random (assuming a uniform probability measure) [Pscr ]-structure of size n obeys asymptotically a convolution law of the Poisson and the geometric distributions. Applications of the results include random mapping patterns, polynomials in finite fields, parameters in additive arithmetical semigroups, etc. This work develops the ‘additive’ counterpart of our previous work on the distribution of the number of prime factors of an integer [20].

A detailed study is made of the number of occupied seats in an unfriendly seating scheme with two rows of seats. An unusual identity is derived for the probability generating function, which is itself an asymptotic expansion. The identity implies particularly a local limit theorem with optimal convergence rate. Our approach relies on the resolution of Riccati equations., Comment: 23 pages with 12 figures in Advances in Applied Mathematics, 2015

Several new asymptotic estimates (with precise error bounds) are derived for Poisson and binomial distributions as the parameters tend to innity. The analytic methods used are also applicable to other discrete distribution functions.

Partitions and compositions of integers are, besides their intrinsic interests, usually used as theoretical models for evolutionary processes in different contexts: statistical mechanics, theory of quantum strings, populaw x tion biology, nonparametric statistics, etc.; cf. 1, 4, 8, 10, 12, 30, 49, 54 . Also parameters in partitions often have natural interpretations in terms w x Ž of characters in symmetric groups; cf. 15, 47 . Thus properties statistical, . algebraic, analytic, . . . of these objects received constant attention in the literature. In many situations, the notion of ‘‘degree of distinctness’’ naturally arises. The classical birthday paradox states that one needs on the average ) 23 people to discover two that have the same birthday with probability w x ) 1r2, assuming all birth dates to be equally likely; cf. 16 . The coupon collector problem is similar: what is the expected number of coupons one needs to gather before a full collection, under suitable probability assumptions on the issuing of the coupons? In applications in which only the first Ž . product element, particle, . . . is ‘‘expensive’’ and the ‘‘cost’’ of the remaining reproductions is negligible, the study of the measures of distinctness becomes meaningful and important. The number of distinct outcomes Ž . in a sequence of multinomial trials the classical occupancy problem has w x w x wide applications; see, for example, Knuth 34 , Johnson and Kotz 28 , w x w x w x Kolchin et al. 35 , Arato and Benczur 5 , and Vitter and Chen 50 . The number of distinct sites visited by a random walk plays an important role

Let Lk denote the Lebesgue constants of the Walsh system. The following exact result is established by means of Mellin transforms: ∑1≤k

We give a closed-form expression for a complicated constant in the average-case analysis of maximum-finding algorithms for a random walk. The following constant arose from the average case analysis of some algorithms for determining the maximum of a random walk in Odlyzko [3]: c0 = 2 π ∫ ∞