On the expected height of fringe-balanced trees

We study the effect of a well-known balancing heuristic on the expected height of a random binary search tree. After insertion of an element, if any node on the insertion path has a subtree of size precisely 2t+1 for a fixed integert, then the subtree rooted at that node is destroyed and replaced by a new subtree in which the median of the 2t+1 elements is the new root. IfH _n denotes the height of the resulting random tree, we show thatH _n /logn c(t) in probability for some functionc(t). In particular,c(0)=4.31107... (the ordinary binary search tree),c(1)=3.192570 ...,c(3)=2.555539 ...,c(10)=2.049289 ... andc(100)=1.623695 ....Research of the author was sponsored by NSERC Grant A3456 and by FCAR Grant 90-ER-0291     

A probabilistic analysis of the height of tries and of the complexity of triesort

Summary We consider binary tries formed by using the binary fractional expansions of X ₁, ...,X _n, a sequence of independent random variables with common density f on [0,1]. For H _n, the height of the trie, we show that either E(H_n)21og₂ n or E(H_n)= for all n2 according to whether f ²(x)dx is finite or infinite. Thus, the average height is asymptotically twice the average depth (which is log₂ n when f ²(x)dx>). The asymptotic distribution of H _n is derived as well.If f is square integrable, then the average number of bit comparisons in triesort is nlog₂ n+0(n), and the average number of nodes in the trie is 0(n).Research of the author was supported in part by FCAC Grant EQ-1678     

A note on the average depth of tries

LetA _n be the average root-to-leaf distance in a binary trie formed by the binary fractional expansions ofn independent random variablesX ₁,...,X _n with common densityf on [0, 1). We show thateither E(A _n )=∞ for alln≥2or \(\mathop {\lim }\limits_n E(A_n )/\log _2 n = 1\) depending on whether ∫f ² (x)dx = ∞ or ∫f ² (x)dx < ∞.     

The computer generation of poisson random variables

An exact method for the generation of Poisson random variables on a computer is presented. The average time required per random variate decreases as the Poisson parameter tends to infinity.     

On the Probablistic Worst-Case Time of ``Find'

We analyze the worst-case number of comparisons T _n of Hoare's selection algorithm FIND when the input is a random permutation, and worst case is measured with respect to the rank k . We give a new short proof that T _n /n tends to a limit distribution, and provide new bounds for the limiting distribution. Received October 27, 2000; revised November 15, 2000.     

A note on density model size testing

Let (F/sub k/)/sub k/spl ges/1/ be a nested family of parametric classes of densities with finite Vapnik-Chervonenkis dimension. Let f be a probability density belonging to F/sub k//sup */, where k/sup */ is the unknown smallest integer such that f/spl isin/F/sub k/. Given a random sample X/sub 1/,...,X/sub n/ drawn from f, an integer k/sub 0//spl ges/1 and a real number /spl alpha//spl isin/(0,1), we introduce a new, simple, explicit /spl alpha/-level consistent testing procedure of the hypothesis {H/sub 0/:k/sup */=k/sub 0/} versus the alternative {H/sub 1/:k/sup *//spl ne/k/sub 0/}. Our method is inspired by the combinatorial tools developed in Devroye and Lugosi and it includes a wide range of density models, such as mixture models, neural networks, or exponential families.     

On the computer generation of random variables with a given characteristic function

We consider the problem of the computer generation of a random variable X with a given characteristic function when the corresponding density and distribution function are not explicitly known or have complicated explicit formulas. Under mild conditions on the characteristic function, we propose and analyze a rejection/squeeze algorithm which requires the evaluation of one integral at a crucial stage.     

Strongly consistent model selection for densities

Let f be an unknown multivariate density belonging to a set of densities \(\mathcal{F}_{k^{*}}\) of finite associated Vapnik–Chervonenkis dimension, where the complexity k ^* is unknown, and ? _k ?? _k+1 for all k. Given an i.i.d. sample of size n drawn from f, this article presents a density estimate \(\hat{f}_{K_{n}}\) yielding almost sure convergence of the estimated complexity K _n to the true but unknown k ^* and with the property \(\mathbf{E}\{\int|\hat{f}_{K_{n}}-f|\}=\mbox{O}(1/\sqrt{n}\,)\). The methodology is inspired by the combinatorial tools developed in Devroye and Lugosi (Combinatorial methods in density estimation. Springer, New York, 2001) and it includes a wide range of density models, such as mixture models and exponential families.     

A note on the expected time required to construct the outer layer

The expected time E(T) of the standard divide-and-conquer algorithm for finding the outer layer of a set of points in the plane depends upon the distribution of the points. Under the mild assumption that the points are independent random vectors and have a common bounded density with compact support, it is shown that E(T) = O(n).     

Data structures in kernel density estimation

We analyze and compare several data structures and algorithms for evaluating the kernel density estimate. Frequent evaluations of this estimate are for example needed for plotting, error estimation, Monte Carlo estimation of probabilities and functionals, and pattern classification. An experimental comparison is included.