Memoryless Routing in Convex Subdivisions: Random Walks are Optimal (2009)
Chen, Dan, Devroye, Luc, Dujmovic, Vida, Morin, Pat
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coordinates of v, t,...
Consistency of Random Forests and Other Averaging Classifiers (2009)
Gérard Biau, Luc Devroye, Gábor Lugosi
In the last years of his life, Leo Breiman promoted random forests for use in classification. He suggested using averaging as a means of obtaining good discrimination rules. The base classifiers used...
On combinatorial testing problems (2009)
Addario-Berry, Louigi, Broutin, Nicolas, Devroye, Luc, Lugosi, Gabor
We study a class of hypothesis testing problems in which, upon observing the realization of an n-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal...
On the Expected Maximum Degree of Gabriel and Yao Graphs (2009)
Devroye, Luc, Gudmundsson, Joachim, Morin, Pat
Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximal degree of a random Gabriel graph or Yao graph defined on $n$ points drawn uniformly at...
TWO-WAY CHAINING WITH REASSIGNMENT (2009)
Ketan Dalal, Luc Devroye, Ebrahim Malalla, Erin Mcleish
Abstract. We present an algorithm for hashing ⌊ αn ⌋ elements into a table with n separate chains that requires O(1) deterministic worst-case insert time, and O(1) expected worst-case search...
Proceedings of the 1996 Winter Simulation Conference (2009)
D. J. Morrice, D. T. Brunner, J. J. Swa”n, Luc Devroye
RANDOM VARIATE GENERATION IN ONE LINE OF CODE A random variate with a given non-uniform distribu-tion can often by generated in one assignment state-ment if a uniform source and some simple functions...
Non-uniform random variate generation. Bibliography: p. (2009)
Thls text Is about one small Aeld on the crossroads of statlstlcs, operatlons research and computer sclence. Statlstlclans need random number generators to test and compare estlmators before uslng...
The Kernel Estimate is Relatively Stable 9 Spfinger-Verlag 1988 (2008)
Summary. Consider the Parzen-Rosenblatt kernel estimate f. = (l/n) ~ Kh (x--Xi), where h> 0 is a constant, K is an absolutely integrable i=1 function with integral one, Kh(X)=(1/ha)K(x/h), and...
Bin width selection in multivariate histograms by (2008)
the combinatorial method
On the stabbing number of a random Delaunay triangulation (2008)
We consider a Delaunay triangulation defined on n points distributed independently and uniformly on a planar compact convex set of positive volume. Let the stabbing number be the maximal number of...
Distances between pairs of vertices and vertical profile in conditioned Galton--Watson trees (2008)
We consider a conditioned Galton-Watson tree and prove an estimate of the number of pairs of vertices with a given distance, or, equivalently, the number of paths of a given length. We give two...
Abstract. Let X be an IR d-valued random variable with unknown density f. Let X1,..., Xn be i.i.d. random variables drawn from f. The objective is to estimate f(x), where x = (x1,..., xd). We study...
Luc Devroye, William Evans, David Kirkpatrick
p n) in the worst case. For all fi-skeletons with fi 2 [0; 1], we prove that the spanning ratio is at most O(n fl) where fl = (1 \Gamma log2(1 +
Strongly consistent model selection for densities (2008)
Biau, Gérard, Cadre, Benoît, Devroye, Luc, Gyorfi, Laszlo
Let f be an unknown multivariate density belonging to a set of densities F_k* of finite associated Vapnik-Chervonenkis dimension, where the complexity k* is unknown, and F_k subset of F_{k+1} for all...
Formatting Font Formats (2008)
Font formats are a tug of war between artists (designers and drawers), programmers (computer scientists), the business world, and users. Each of these four groups has had an influence on the...
Consistency of a Recursive Nearest Neighbor Regression Function Estimate (2008)
Luc Devroye, Gary L. Wise, Communicated M. Rosenblatt
Let (X, Y) be an IR ” x H-valued random vector and let (Xi, Y,),..., (X,, YN) be. a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length I,,..., I,,...
Upper and Lower Class Sequences for Minimal Uniform Spacings (2008)
Summary. Let K, be the k-th smallest spacing defined by X~,...,X,, inde-pendent random variables uniformly distributed on [0, 1], where k> 1 is a fixed integer. Let u, be a sequence of positive...
On the Performance of Clustering in Hilbert Spaces (2008)
Gérard Biau, Luc Devroye, Gábor Lugosi
Abstract—Based on � randomly drawn vectors in a separable Hilbert space, one may construct a �-means clustering scheme by minimizing an empirical squared error. We investigate the risk of such...
MINIMALIST APPROXIMATIONS FOR CONVEX FUNCTIONS Prosenjit Bose (2008)
ABSTRACT. We study data structures for approximating convex functions whose slopes are bounded as well as applications of such data structures to problems in clustering and facility location. 1
Succinct Data Structures for Approximating Convex Functions with Applications ⋆ (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ɛ-approximations of convex functions whose slopes are bounded. Since the queries are efficient in these structures requiring only O(log(1/ε)+log log...
Abstract Multiple Choice Tries and Distributed Hash Tables ∗ (2008)
Luc Devroye, Gabor Lugosi, Gahyun Park, Wojciech Szpankowski
Tries were introduced in 1960 by Fredkin as an efficient method for searching and sorting digital data. Recent years have seen a resurgence of interest in tries. In some of these applications, most...
classes of densities with finite Vapnik-Chervonenkis dimension. Let � be a probability density belonging to ¡�£� � , where ��� ¢¡¤£¦¥§£©¨� � be a nested family of...
Oat ON THE VARIANCE OF THE HEIGHT OF RANDOM BINARY SEARCH TREES* (2008)
Abstract. Let Hn be the height of a random binary search tree on n nodes. We show that there exists a constant a = 4.31107... such that P { I Hn- a log n i> f log log n}-+ 0, where> 15a / In 2...
SUCCINCT DATA STRUCTURES FOR APPROXIMATING CONVEX FUNCTIONS, WITH APPLICATIONS † (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ε-approximations of convex functions whose slopes are bounded from above and below by n and −n, respectively. The structures we describe have size...
Luc Devroye, Michael Mcdougall
We presentseveral methods for creating a random printed handwriting font based upon a small sample from a person’s own hand. The first method uses random interpolation and possibly random...
SUCCINCT DATA STRUCTURES FOR APPROXIMATING CONVEX FUNCTIONS, WITH APPLICATIONS † (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ε-approximations of convex functions whose slopes are bounded from above and below by n and −n, respectively. The structures we describe have size...
Succinct Data Structures for Approximating Convex Functions with Applications ⋆ (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ɛ-approximations of convex functions whose slopes are bounded. Since the queries are efficient in these structures requiring only O(log(1/ε)+log log...
Local tail bounds for functions of independent random variables (2008)
It is shown that functions defined on {0, 1, . . . , r − 1} n satisfying certain condi- tions of bounded differences that guarantee subgaussian tail behavior also satisfy a much stronger...
On the performance of clustering in Hilbert spaces (2008)
Biau, Gerard, Devroye, Luc, Lugosi, Gábor
Based on $n$ randomly drawn vectors in a separable Hilbert space, one may construct a $k$-means clustering scheme by minimizing an empirical squared error. We investigate the risk of such a...
Consistency of random forests and other averaging classifiers (2008)
Biau, Gérard, Devroye, Luc, Lugosi, Gábor
In the last years of his life, Leo Breiman promoted random forests for use in classification. He suggested using averaging as a means of obtaining good discrimination rules. The base classifiers...
Local tail bounds for functions of independent random variables (2007)
It is shown that functions defined on $\{0,1,...,r-1\}^n$ satisfying certain conditions of bounded differences that guarantee sub-Gaussian tail behavior also satisfy a much stronger ``local''...
Almost Sure Testability Of Classes Of Densities (2007)
. Let a class F of densities be given. We draw an i.i.d. sample from a density f which may or may not be in F . After every n, one must make a guess whether f 2 F or not. A class is almost surely...
Luc Devroye, Pat Morin, Alfredo Viola
Abstract. We consider open addressing hashing, and implement it by using the Robin Hood strategy, that is, in case of collision, the element that has traveled the furthest can stay in the slot. We...
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing #-approximations of convex functions whose slopes are bounded. Since the queries are e#cient in these structures requiring only O(log(1/#)+log log n)...
We consider algorithms for generating random variates having a density, when only its Fourier coefficients or moments are known. We also study the expected time per random variate. 1.
North-Holland AN EQUIVALENCE THEOREM FOR L, CONVERGENCE OF THE KERNEL REGRESSION ESTIMATE* (2007)
Luc Devroye, Adam Krzyzak, Recommended M. Rosenblatt
Abstract: We show that all modes of convergence in Lt (in probability, almost surely, complete) for the standard kernel regression estimate are equivalent. AMS Subject Classification: Primary 62605....
North-Holland METHODS FOR GENERATING RANDOM VARIATES WITH POLYA CHARACTERISTIC FUNCTIONS (2007)
Abstract: Polya has shown that real even continuous functions that are convex on (0,oo), 1 for t = 0, and decreasing to 0 as t---, ~ are characteristic functions. Dugu6 and Girault (1955) have shown...
Processing Letters A note on the Horton-Strahler number for random trees (2007)
Luc Devroye, Paul Kruszewski *j
Information
North-Holland A UNIVERSAL LOWER BOUND FOR THE KERNEL ESTIMATE (2007)
Abstract: Let f,, be the kernel density estimate with arbitrary smoothing factor h and arbitrary (absolutely integrable) kernel K, based upon an i.i.d. sample of size n drawn from a density f. It is...
DIAMONDS ARE NOT A MINIMUM WEIGHT (2007)
Triangulation's Best Friend, Luc Devroye, William Evans
Two recent methods have increased hopes of finding a polynomial time solution to the problem of computing the minimum weight triangulation of a set S of n points in the plane. Both involve computing...
Luc Devroye, William Evans, David Kirkpatrick
Abstract. The spanning ratio of a graph dened on n points in the Euclidean plane is the maximal ratio over all pairs of data points (u; v), of the minimum graph distance between u and v, over the...
SIMULATING BESSEL RANDOM VARIABLES (2007)
Abstract. In this paper, we discuss e#cient exact random variate generation for the Bessel distribution. The expected time of the algorithm is uniformly bounded over all choices of the parameters,...
ALMOST SURE TESTABILITY OF CLASSES OF DENSITIES (2007)
Abstract. Let a class F of densities be given. We draw an i.i.d. sample from a density f which mayor may not be in F. After every n, one must make a guess whether f 2F or not. A class is almost...
-valued random variable with unknown density f. Let X 1,..., Xn be i.i.d. random variables drawn from f. The objective is to estimate f(x), where x = (x 1,..., x d). We study the pointwise...
Random Search Under Additive Noise (2007)
Luc Devroye School, Luc Devroye
this paper. In noisy optimization in general, it is possible to observe a sample drawn from distribution F x at each x, with F x possibly di#erent for each x. The mean of F x is Q(x). If there are...
A Note on Robust Detection (2007)
Luc Devroye Lszl, Luc Devroye, Lszl Gyr, Gbor Lugosi
We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of k nominal densities is the true density is closest to,...
. After every n, one must make a guess whether f (2007)
Let a class of densities be given. We draw an i.i.d. sample from a density f which may or may not be in . After every n, one must make a guess whether f or not. A class is almost surely discernible...
Bin Width Selection in Multivariate Histograms (2007)
The Combinatorial Method, Luc Devroye, Gabor Lugosi
We present several multivariate histogram density estimates that are universally L 1 -optimal to within a constant factor and an additive term O( log n/n). The bin widths are chosen by the...
EXPECTED WORST-CASE PARTIAL MATCH IN RANDOM QUADTRIES (2007)
Luc Devroye, Carlos Zamora-cura
We consider random multivariate quadtries obtained from n points independently and uniformly distributed on the unit cube of R . Let Nn (y) be the complexity of the standard partial match algorithm...
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing #-approximations of convex functions whose slopes are bounded. Since the queries are e#cient in these structures requiring only O(log(1/#)+log log n)...
Sid's contributions to noisy optimization From the early days in his career, Sid Yakowitz showed interest in noisy function optimization. He realized the universality of random search as an...
Zhi-dong Bai, Jilin Prc, Luc Devroye, Hsien-kuei Hwang, Tsung-hsi Tsai
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...
Campos, Victor, Chvatal, Vasek, Devroye, Luc, Taslakian, Perouz
A transversal in a rooted tree is any set of nodes that meets every path from the root to a leaf. We let c(T,k) denote the number of transversals of size k in a rooted tree T. We define a partial...
Devroye, Luc, Lugosi, Gábor, Park, Gahyun, Szpankowski, Wojchiek
In this paper we consider tries built from n strings such that each string can be chosen from a pool of k strings, each of them generated by a discrete i.i.d. source. Three cases are considered: k =...
Inverse Distributions and Independent Gamma-Distributed Products of Random Variables (2007)
Luc Devroye, Peter Epstein, Jörg-rüdiger Sack, Luc Devroye, Peter Epstein, Jörg-rüdiger Sack, ...
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use...
Note on the structure of Kruskal’s Algorithm (2007)
Nicolas Broutin, Luc Devroye, Erin Mcleish
We study the merging process when Kruskal’s algorithm is run with random graphs as inputs. Our aim is to analyze this process when the underlying graph is the complete graph on n vertices lying in...
Consistency of random forests and other averaging classifiers ∗ (2007)
Gérard Biau, Luc Devroye, Gábor Lugosi
This paper is dedicated to the memory of Leo Breiman. In the last years of his life, Leo Breiman promoted random forests for use in classification. He suggested using averaging as a means
Width and mode of the profile for some random trees of logarithmic height (2006)
Devroye, Luc, Hwang, Hsien-Kuei
We propose a new, direct, correlation-free approach based on central moments of profiles to the asymptotics of width (size of the most abundant level) in some random trees of logarithmic height. The...
Width and mode of the profile for some random trees of logarithmic height (2006)
Devroye, Luc, Hwang, Hsien-Kuei
We propose a new, direct, correlation-free approach based on central moments of profiles to the asymptotics of width (size of the most abundant level) in some random trees of logarithmic height. The...
Local tail bounds for functions of independent random variables (2006)
It is shown that functions defined on $\{0,1,\ldots,r-1\}^n$ satisfying certain conditions of bounded differences that guarantee subgaussian tail behavior also satisfy a much stronger ``local''...
Gérard Biau, Benoît Cadre, Luc Devroye, László Györfi, G. Biau, B. Cadre, ...
Abstract Let f be an unknown multivariate density belonging to a set of densities Fk ∗ of finite associated Vapnik–Chervonenkis dimension, where the complexity k ∗ is unknown, and Fk ⊂ Fk+1...
L'aszl'o Gy"orfi ## (2006)
Abstract Let f be an unknown multivariate density belonging to a set of densitiesF k * of finite associated Vapnik-Chervonenkis dimension, where the complexity k * is unknown, and Fk ae Fk+1 for all...
Large Deviations for the Weighted Height of an Extended Class of Trees (2006)
We use large deviations to prove a general theorem on the asymptotic edge-weighted height H ⋆ n of a large class of random trees for which H ⋆ n ∼ c log n for some positive constant c. A...
Multiple Choice Tries and Distributed Hash Tables (2006)
Luc Devroye, Gábor Lugosi, Gahyun Park, Wojciech Szpankowski
Tries were introduced in 1960 by Fredkin as an efficient method for searching and sorting digital data. Recent years have seen a resurgence of interest in tries that find applications in dynamic...
Multiple Choice Tries and Distributed Hash Tables (2006)
Luc Devroye, Gábor Lugosi, Gahyun Park, Wojciech Szpankowski
Tries were introduced in 1960 by Fredkin as an efficient method for searching and sorting digital data. Recent years have seen a resurgence of interest in tries that find applications in dynamic...
Multiple Choice Tries and Distributed Hash Tables (2006)
Luc Devroye, Gábor Lugosi, Gahyun Park, Wojciech Szpankowski
Tries were introduced in 1960 by Fredkin as an efficient method for searching and sorting digital data. Recent years have seen a resurgence of interest in tries that find applications in dynamic...
Cove, Joshua, Blinder, Pablo, Abi-Jaoude, Elia, Lafrenière-Roula, Myriam, Devroye, Luc, Baranes, Danny
The integrative properties of dendrites are determined by several factors, including their morphology and the spatio-temporal patterning of their synaptic inputs. One of the great challenges is to...
A Limit Law for the Root Value of Minimax Trees (2005)
Khan, Tämur Ali; Johann Wolfgang Goethe Universität, Germany; Alikhan@ismi.math.uni-frankfurt.de, Devroye, Luc; McGill University, Canada; Luc@cs.mcgill.ca, Neininger, Ralph; Wolfgang Goethe Universität, Germany; Neiningr@math.uni-frankfurt.de
We consider minimax trees with independent, identically distributed leaf values that have a continuous distribution function FV being strictly increasing on the range where 0< FV
We propose a new, direct, correlation-free approach based on central moments of profiles to the asymptotics of width (size of the most abundant level) in random trees of logarithmic height. The...
Abstract. Under certain conditions, sums of functions of subtrees of a random binary search tree are asymptotically normal. We show how Stein’s method can be applied to study these random trees,...
Universal asymptotics for random tries and PATRICIA trees (2005)
Abstract. We consider random tries and random patricia trees constructed from n independent strings of symbols drawn from any distribution on any discrete space. We show that many parameters Zn of...
Universal asymptotics for random tries and PATRICIA trees (2005)
Abstract. We consider random tries and random patricia trees constructed from n independent strings of symbols drawn from any distribution on any discrete space. We show that many parameters Zn of...
Cove, Joshua, Blinder, Pablo, Abi-Jaoude, Elia, Lafrenière-Roula, Myriam, Devroye, Luc, Baranes, Danny
The integrative properties of dendrites are determined by several factors, including their morphology and the spatio-temporal patterning of their synaptic inputs. One of the great challenges is to...
Cove, Joshua, Blinder, Pablo, Abi-Jaoude, Elia, Lafrenière-Roula, Myriam, Devroye, Luc, Baranes, Danny
The integrative properties of dendrites are determined by several factors, including their morphology and the spatio-temporal patterning of their synaptic inputs. One of the great challenges is to...
Cove, Joshua, Blinder, Pablo, Abi-Jaoude, Elia, Lafrenière-Roula, Myriam, Devroye, Luc, Baranes, Danny
The integrative properties of dendrites are determined by several factors, including their morphology and the spatio-temporal patterning of their synaptic inputs. One of the great challenges is to...
Cove, Joshua, Blinder, Pablo, Abi-Jaoude, Elia, Lafrenière-Roula, Myriam, Devroye, Luc, Baranes, Danny
The integrative properties of dendrites are determined by several factors, including their morphology and the spatio-temporal patterning of their synaptic inputs. One of the great challenges is to...
Bin Width Selection in Multivariate Histograms by the Combinatorial Method (2004)
We present several multivariate histogram density estimates that are universally $L_1$-optimal to within a constant factor and an additive term $O(\sqrt{\log n / n })$. The bin widths are chosen by...
Bin Width Selection in Multivariate Histograms by the Combinatorial Method (2004)
We present several multivariate histogram density estimates that are universally $L_1$-optimal to within a constant factor and an additive term $O(\sqrt{\log n / n })$. The bin widths are chosen by...
Expected time analysis for delaunay point location (2004)
Luc Devroye, Christophe Lemaire, Jean-michel Moreau
Abstract. We consider point location in Delaunay triangulations with the aid of simple data structures. In particular, we analyze methods in which a simple data structure is used to first locate a...
Distances and Finger Search in Random Binary Search Trees (2004)
For the random binary search tree with n nodes inserted the number of ancestors of the elements with ranks k and l, 1 <= k < l <= n, as well as the path distance between these elements in...
On Worst Case Robin-Hood Hashing (2004)
Luc Devroye, Pat Morin, Alfredo Viola
We consider open addressing hashing and implement it by using the Robin Hood strategy; that is, in case of collision, the element that has traveled the farthest can stay in the slot. We hash ∼ αn...
Zhi-dong Bai, Jilin Prc, Hsien-kuei Hwang, Tsung-hsi Tsai, Luc Devroye
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...
Zhi-dong Bai, Jilin Prc, Hsien-kuei Hwang, Tsung-hsi Tsai, Luc Devroye
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...
Expected Time Analysis for Delaunay Point Location (2004)
Luc Devroye, Christophe Lemaire, Jean-michel Moreau
We consider point location in Delaunay triangulations with the aid of simple data structures. In particular, we analyze methods in which a simple data structure is used to first locate a point close...
Distances and finger search in random binary search trees (2004)
For the random binary search tree with n nodes inserted the number of ancestors of the elements with ranks k and l, 1 <= k < l <= n, as well as the path distance between these elements in...
Cuckoo Hashing: Further Analysis (2003)
Abstract. We consider cuckoo hashing as proposed by Pagh and Rodler in 2001. We show that the expected construction time of the hash table is O(n) as long as the two open addressing tables are each...
On the risk of estimates for block decreasing densities (2003)
Abstract. A density f = f(x1,..., x d) on [0, ∞) d is block decreasing if for each j ∈ {1,..., d}, it is a decreasing function of xj, when all other components are held fixed. Let us consider the...
Luc Devroye, Pat Morin, Alfredo Viola
Abstract. We consider open addressing hashing, and implement it by using the Robin Hood strategy, that is, in case of collision, the element that has traveled the furthest can stay in the slot. We...
Random Suffix Search Trees (2003)
A random suffix search tree is a binary search tree constructed for the suffixes X i = 0:B i B i+1 B i+2 : : : of a sequence B 1 ; B 2 ; B 3 :; : : : of independent identically distributed random...
Cuckoo hashing: Further analysis (2003)
Luc Devroye, Pat Morin, Communicated F. Dehne
We consider cuckoo hashing as proposed by Pagh and Rodler in 2001. We show that the expected construction time of the hash table is O(n) as long as the two open addressing tables are each of size at...
For the random binary search tree with n nodes inserted the number of ancestors of the elements with ranks k and ℓ, 1 ≤ k < ℓ ≤ n, as well as the path distance between these elements in...
Devroye, Luc, Neininger, Ralph
An algorithm is developed for exact simulation from distributions that are defined as fixed points of maps between spaces of probability measures. The fixed points of the class of maps under...
An algorithm is developed for the exact simulation from distributions that are defined as fixed-points of maps between spaces of probability measures. The fixed-points of the class of maps under...
Abstract An algorithm is developed for the exact simulation from distributions that are defined as fixed-points of maps between spaces of probability measures. The fixed-points of the class of maps...
Laws of large numbers and tail inequalities for random tries and Patricia trees (2002)
Abstract. We consider random tries and random patricia trees constructed from n independent strings of symbols drawn from any distribution on any discrete space. If Hn is the height of this tree, we...
On the spanning ratio of gabriel graphs and β-skeletons (2002)
Prosenjit Bose, Luc Devroye, William Evans, David Kirkpatrick
Abstract. The spanning ratio of a graph defined on n points in the Euclidean plane is the maximum ratio, over all pairs of data points (u, v), of the minimum graph distance between u and v divided by...
Giant components for two expanding graph processes (2002)
Luc Devroye, Colin McDiarmid, Bruce Reed
We discuss the emergence of giant components in two random graph models (one directed, one undirected). Our study of these models was motivated by an interest in finding a random model of the...
Random suffix search trees (2002)
A random suffix search tree is a binary search tree constructed for the suffixes Xi = 0.BiBi+1Bi+2... of a sequence B1, B2, B3.,... of independent identically distributed random b-ary digits Bj. Let...
A Note on Density Model Size Testing (2002)
Let (Fk ) k1 be a nested family of parametric classes of densities with finite Vapnik-Chervonenkis dimension. Let f be a probability density belonging to Fk , where k is the unknown smallest integer...
Limit laws for sums of functions of subtrees of random binary search trees (2001)
We consider sums of functions of subtrees of a random binary search tree, and obtain general laws of large numbers and central limit theorems. These sums correspond to L random recurrences of the...
On the probabilistic worst-case time of ”FIND (2001)
Abstract. We analyze the worst-case number of comparisons Tn 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...
Limit laws for sums of functions of subtrees of random binary search trees, preprint (2001)
Abstract. We consider sums of functions of subtrees of a random binary search tree, and obtain general laws of large numbers and central limit theorems. These sums correspond to random recurrences of...
Exact simulation of random variables that are solutions of fixed-point equations (2001)
An algorithm is developed for the exact simulation from distributions that are dened as xed-points of maps between spaces of probability measures. The xed-points of the class of maps under...
Exact simulation of random variables that are solutions of fixed-point equations (2001)
An algorithm is developed for the exact simulation from distributions that are defined as fixed-points of maps between spaces of probability measures. The fixed-points of the class of maps under...
Simulating perpetuities (2001)
Abstract. A perpetuity is a random variable that can be represented as 1 + W 1 + W 1 W 2 + W 1 W 2 W 3 + \Delta \Delta \Delta, where the W i 's are i.i.d. random variables. We study exact random...
On the Spanning Ratio of Gabriel Graphs and beta-Skeletons (2001)
Prosenjit Bose, Luc Devroye, William Evans, David Kirkpatrick
The spanning ratio of a connected graph defined on n points in the Euclidean plane is the maximal ratio over all pairs of data points (u; v), of the minimum graph distance between u and v, over the...
Large Deviations of Divergence Measures on Partitions (2001)
Jan Beirlant, Luc Devroye, László Györfi, Igor Vajda
We discuss Cherno#-type large deviation results for the total variation, the I-divergence errors, and the # 2 -divergence errors on partitions. In contrast to the total variation and the...
Laws of Large Numbers and Tail Inequalities for Random Tries and Patricia Tries (2001)
We consider random tries and random patricia trees constructed from n independent strings of symbols drawn from any distribution on any discrete space. If Hn is the height of this tree, we show that...
Cuckoo Hashing: Further Analysis (2001)
We consider cuckoo hashing as proposed by Pagh and Rodler in 2001. We show that the expected construction time of the hash table is O(n) as long as the two open addressing tables are each of size at...
Analysis of random LC tries (2001)
LC tries were introduced by Andersson and Nilsson in 1993. They are compacted versions of tries or patricia tries in which, from the top down, maximal height complete subtrees are level compressed....
Cuckoo Hashing: Further Analysis (2001)
We consider cuckoo hashing as proposed by Pagh and Rodler in 2001. We show that the expected construction time of the hash table is O(n) as long as the two open addressing tables are each of size at...
SIMULATING BESSEL RANDOM VARIABLES (2001)
Abstract. In this paper, we discuss efficient exact random variate generation for the Bessel distribution. The expected time of the algorithm is uniformly bounded over all choices of the parameters,...
A Note on Robust Detection (2000)
Devroye, Luc, Györfi, László, Lugosi, Gábor
We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of $k$ nominal densities is the true density is closest to,...
Perfect Simulation from the Quicksort Limit Distribution (2000)
Devroye, Luc; McGill University; Luc@cs.mcgill.ca, Fill, James Allen; The Johns Hopkins University; Jimfill@jhu.edu, Neininger, Ralph; Universität Freiburg; Rn@stochastik.uni-freiburg.de
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point...
Perfect simulation from the Quicksort limit distribution (2000)
Devroye, Luc, Fill, James Allen, Neininger, Ralph
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point...
Luc Devroye, Jean Jabbour, Carlos Zamora-cura
Abstract. We modify the k-d tree on [0, 1] d by always cutting the longest edge instead of rotating through the coordinates. This modification makes the expected time behavior of lower-dimensional...
Perfect simulation from the quicksort limit distribution (2000)
Luc Devroye, James Allen Fill, Ralph Neininger
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point...
INEQUALITIES FOR A NEW DATA-BASED METHOD FOR SELECTING NONPARAMETRIC DENSITY ESTIMATES (2000)
Luc Devroye, Gábor Lugosi, Frederic Udina
We develop a general method to select an estimate from any given family of (regular and additive) nonparametric density estimates. We provide explicit non-asymptotic density-free inequalities that...
Variable kernel estimates: On the impossibility of tuning the parameters (2000)
ABSTRACT For the standard kernel density estimate, it is known that one can tune the bandwidth such that the expected L1 error is within a constant factor of the optimal L1 error (obtained when one...
Luc Devroye, Jean Jabbour, Carlos Zamora-cura
Abstract. We modify the k-d tree on [0; 1]
A Note on Robust Detection (2000)
Luc Devroye, Lszl Gyr, Gábor Lugosi
We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of k nominal densities is the true density is closest to,...
Perfect Simulation from the Quicksort Limit Distribution (2000)
Luc Devroye, James Allen Fill, Ralph Neininger
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point...
Luc Devroye, Jean Jabbour, Carlos Zamora-cura
. We modify the k-d tree on [0; 1] d by always cutting the longest edge instead of rotating through the coordinates. This modification makes the expected time behavior of lower-dimensional partial...
Estimating The Number Of Vertices Of A Polyhedron (2000)
Given a polyhedron P by a list of inequalities we develop unbiased estimates of the number of vertices and bases of P . The estimates are based on applying tree estimation methods to the reverse...
Luc Devroye, Jean Jabbour, Carlos Zamora-cura
Abstract. We modify the k-d tree on [0, 1] d by always cutting the longest edge instead of rotating through the coordinates. This modification makes the expected time behavior of lowerdimensional...
Large Deviations of Divergence Measures on Partitions (2000)
Jan Beirlant, Luc Devroye, László Györfi, Igor Vajda
We discuss Chernoff-type large deviation results for the total variation, the I-divergence errors, and the -divergence errors on partitions. In contrast to the total variation and the I-divergence,...
A rawa tree is a binary search tree for an ordinary random walk 0; S_1 , S_2, S_3, ..., where S_n = \sum_{i=1}^n X i and the X i's are i.i.d. distributed as X. We study the height H_n of the...
Almost Sure Testability of Classes of Densities (1999)
Let a class $\F$ of densities be given. We draw an i.i.d.\ sample from a density $f$ which may or may not be in $\F$. After every $n$, one must make a guess whether $f \in \F$ or not. A class is...
Lower bounds for bayes error estimation (1999)
Andraâs Antos, Luc Devroye, Laâszloâ Gyoèrfi
AbstractÐWe give a short proof of the following result. Let …X; Y † be any distribution on N f0; 1g, and let …X1;Y1†;...; …Xn;Yn † be an i.i.d. sample drawn from this distribution. In...
Acta Informatica 37, 355–383 (2001) Analysis of range search for random k-d trees (1999)
Luc Devroye, Carlos Zamora-cura
c ○ Springer-Verlag 2001 Abstract. We analyze the expected time complexity of range searching with k-d trees in all dimensions when the data points are uniformly distributed in the unit hypercube....
Properties of random triangulations and trees (1999)
Luc Devroye, Inria Rocquencourt, Ferran Hurtado, Marc Noy, William Steiger
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural "geometric " features of a triangulation # Tn, for example...
Fast Delaunay point location with search structures, p (1999)
Luc Devroye, Christophe Lemaire, Jean-michel Moreau
We present an improvement over a former technique, Jump & Walk ([7]), to locate points in the Delaunay triangulation of n sites uniformly distributed in a square. The method uses a dynamically...
Random Triangulations and Trees (1999)
Luc Devroye, Philippe Flajolet, Ferran Hurtado, Marc Noy, William Steiger, Politecnica Catalunya, ...
gulation ø of K, let d i denote the degree of vertex v i , the number of (the n \Gamma 3 internal) diagonals of ø that are incident with v i . We study \Delta n (ø) = max(d i ; i = 0; : : : ; n...
Analysis of Range Search for Random K-D Trees (1999)
Philippe Chanzy, Luc Devroye, Carlos Zamora-cura
. We analyze the expected time complexity of range searching with k-d trees in all dimensions when the data points are uniformly distributed in the unit hypercube. The partial match results of...
Properties of random triangulations and trees (1999)
Luc Devroye, Marc Noy, Ferran Hurtado, William Steiger
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural “geometric ” features of a triangulation τ ∈ Tn, for example ∆n(τ)...
The Height and Size of Random Hash Trees and Random Pebbled Hash Trees (1999)
The random hash tree and the N-tree were introduced by Ehrlich in 1981. In the random hash tree, n data points are hashed to values X 1 ,...,X n , independently and identically distributed random...
On the Impossibility of Estimating Densities in the Extreme Tail (1999)
We give a short proof of the following result. Let X 1 ;:::;X n be independent and identically distributed observations drawn from a density f on the real line. Let f n be any estimate of the density...
On the Hilbert kernel density estimate (1999)
Luc Devroye, Adam Krzyzak, Adam Krzy˙zak B
Let X be an R -valued random variable with unknown density f. Let X 1 ;:::;X n be i.i.d. random variables drawn from f. We study the pointwise convergence of a new class of density estimates, of...
Variable Kernel Estimates: On the Impossibility of Tuning the Parameters (1998)
For the standard kernel density estimate, it is known that one can tune the bandwidth such that the expected L1 error is within a constant factor of the optimal L1 error (obtained when one is allowed...
Inequalities for a New Data-Based Method for Selecting Nonparametric Density Estimates (1998)
Devroye, Luc, Lugosi, Gábor, Udina I Abelló, Frederic
We continue the development of a method for the selection of a bandwidth or a number of design parameters in density estimation. We provide explicit non-asymptotic density-free inequalities that...
On the richness of the collection of subtrees in random binary search trees (1998)
Luc Devroye, Communicated F. Dehne
The purpose of this paper is to settle two conjectures by Flajolet, Gourdon and Martinez ( 1996). We confirm that in a random binary tree on n nodes, the expected number of different subtrees grows...
Inequalities for a new data-based method for selecting nonparametric densitys (1998)
on the beach while the manuscript was being typed. Abstract. We continue the development of a method for the selection of a bandwidth or a number of design parameters in density estimation. We...
Inequalities For A New Data-Based Method For Selecting Nonparametric Density Estimates (1998)
Luc Devroye, Gábor Lugosi, Frederic Udina
We continue the development of a method for the selection of a bandwidth or a number of design parameters in density estimation. We provide explicit non-asymptotic density-free inequalities that...
Variable Kernel Estimates: On The Impossibility Of Tuning The Parameters (1998)
For the standard kernel density estimate, it is known that one can tune the bandwidth such that the expected L1 error is within a constant factor of the optimal L1 error (obtained when one is allowed...
A Study Of Random Weyl Trees (1998)
. We study binary search trees constructed from Weyl sequences fn`g; n 1, where ` is an irrational and f:g denotes "mod 1". We explore various properties of the structure of these trees,...
Binary search trees based on Weyl and Lehmer sequences (1998)
This paper is based upon the presentation at the meeting in Salzburg. As a courtesy to those who attended the meeting, I will try to faithfully reproduce---with minor omissions and additions---what I...
Unoriented Theta-Maxima In The Plane: Complexity And Algorithms (1998)
David Avis, Bryan Beresford-smith, Luc Devroye, Hossam Elgindy, Eric Guévremont, Ferran Hurtado, ...
We introduce the unoriented Theta-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented Theta-maximum of a set of...
Journal of Multivariate AnalysisMV1725 (1998)
Journal Of Multivariate, Luc Devroye
INTRODUCTION Let (X 1 , Y 1 ), ..., (X n , Y n ) be independent observations of an R _Rvalued random vector (X, Y ). Denote the probability measure of X by +. The regression function m(x)=E(Y | X=x)...
Universal Limit Laws for Depths in Random Trees (1998)
Random binary search trees, b-ary search trees, median-of-(2k+1) trees, quadtrees, simplex trees, tries, and digital search trees are special cases of random split trees. For these trees, we o#er a...
Inequalities for a new data-based method for selecting nonparametric densitys (1998)
Luc Devroye, G 'abor Lugosi, Frederic Udina
ABSTRACT We develop a general method to select an estimate from any given family of (regular and additive) nonparametric density estimates. We provide explicit non-asymptotic density-free...
Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes (1997)
We introduce a method to select a smoothing factor for kernel density estimation such that, for all densities in all dimensions, the $L_1$ error of the corresponding kernel estimate is not larger...
In earlier work with Gabor Lugosi, we introduced a method to select a smoothing factor for kernel density estimation such that, for all densities in all dimensions, the L1 error of the corresponding...
The Annals of Statistics (1997)
Vol No Nonasymptotic, Luc Devroye, Gábor Lugosi
this paper, a "cleaner" related estimate is proposed, and explicit nonasymptotic performance guarantees are provided that are uniform over all f. Received June 1996; revised June 1997
Universal Smoothing Factor Selection in Density Estimation: Theory and Practice (1997)
In earlier work with Gabor Lugosi, we introduced a method to select a smoothing factor for kernel density estimation such that, for all densities in all dimensions, the L 1 error of the corresponding...
A universally acceptable smoothing factor for kernel density estimates (1996)
We define a minimum distance estimate of the smoothing factor for kernel density estimates, based on a methodology first developed by Yatracos. It is shown that if $f_{nh}$ denotes the kernel density...
The Botanical Beauty of Random Binary Trees (1996)
Devroye, Luc, Kruszewski, Paul
We present a simple mechanism for quickly rendering computer images of botanical trees based on random binary trees commonly found in computer science. That is, we visualize abstract binary trees as...
The Botanical Beauty of Random Binary Trees (1996)
Devroye, Luc, Kruszewski, Paul
We present a simple mechanism for quickly rendering computer images of botanical trees based on random binary trees commonly found in computer science. That is, we visualize abstract binary trees as...
The Botanical Beauty of Random Binary Trees (1996)
Devroye, Luc, Kruszewski, Paul
We present a simple mechanism for quickly rendering computer images of botanical trees based on random binary trees commonly found in computer science. That is, we visualize abstract binary trees as...
Random Triangulations (Extended Abstract) (1996)
Luc Devroye, Philippe Flajolet, Inria Rocquencourt, Ferran Hurtado, Marc Noy, William Steiger
) 3 Luc Devroye McGill University luc@kriek.cs.mcgill.ca Philippe Flajolet INRIA - Rocquencourt Philippe.Flajolet@inria.fr Ferran Hurtado Universitat Politecnica de Catalunya hurtado@ma2.upc.es Marc...
On the strong universal consistency of nearest neighbor regression function estimates (1994)
Luc Devroye, Laszlo Gyorfi, Adam Krzyzak, Gabor Lugosi
Two results are presented concerning the consistency of the k-nearest neighbor regression estimate. We show that all modes of convergence in L 1 (in probability, almost sure, complete) are equivalent...
On random Cartesian trees (1994)
Cartesian trees are binary search trees in which the nodes exhibit the heap property according to a second (priority) key. lithe search key and the priority key are independent, and the tree is...
Records, the maximal layer, and the uniform distributions (1993)
Abatract--Consider a nondecreasing nonnegative integrable function f on [0,1]. Draw an indepen-dent sample (X1,Y1)..... (Xn,Yn) of size n from the uniform distribution under f, and let Nn be the...
On random variate generation for the generalized hyperbolic secant distributions (1993)
We give random variate generators for the generalized hyperbolic secant distribution and related families such as Morris's skewed generalized hyperbolic secant family and a family introduced by...
A triptych of discrete distributions related to the stable law (1993)
We derive useful distributional representations for three discrete laws: the discrete stable distribution of Steutel and Van Harn, the discrete Linnik distribution introduced by Pakes, and a...
On the expected height of fringe-balanced trees (1993)
Abstract. 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...
Convex hulls for random lines (1993)
Luc Devroye, Godfried Toussaint
Consider n i.i.d. random lines in the plane defined by their slope and distance from the origin. The slope is uniformly distributed on (0, 27r] and independent of the distance R from the origin....
On the strong universal consistency of nearest neighbor regression function estimates
Abstract: In data analytic applications of density estimation one is usually interested in estimating the density over its support. However, common estimators such as the basic kernel estimator use a...
Limit laws for local counters in random binary search trees (1991)
Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for...
North-Holland On the oscillation of the expected number of extreme points of a random set (1990)
Absfract: Let EN, be the expected number of extreme points among n i.i.d. points with a common radially symmetric distribution in the plane. We show that for any monotone sequence wn t co and for...
On the height of random m-ary search trees (1990)
A random m-ary leach tree is constructed from a random permutation of 1,..., n. A la of large numbers is obtained for the height Hn of these trees by applying the theory of branching random alks. In...
North-Holland A NOTE ON LINNIK’S DISTRIBUTION (1989)
Abstract: We provide a short proof of the validity and unimodality of Linnik’s characteristic function l/(1 + 1 t I”), 0 < a < 2, by noting that it corresponds to the distribution of...
The double kernel method in density estimation (1989)
Abstract. Let f nh be the Parzen-Rosenblatt kernel estimate of a density f on the real line, based upon a sample of n i.i.d. random variables drawn from f, and with smoothing factor h. Let g nh be...
Random Walks on Highly Symmetric Graphs (1989)
We consider uniform random walks on finite graphs with n nodes. When the hitting times are symmetric, the expected covering time is at least 89 log n-O(n log log n) uniformly over all such graphs. We...
North-Holland ON THE NON-CONSISTENCY OF THE L2-CROSS-VALIDATED KERNEL DENSITY ESTIMATE (1989)
Abstract: Let f, be the L, cross-validated kernel estimate of a univariate density f. We show that 1iminfE If,-fl>,l n-m / when K is a symmetric bounded unimodal density, f is a monotone density...
The Double Kernel Method In Density Estimation (1989)
Let f nh be the Parzen-Rosenblatt kernel estimate of a density f on the real line, based upon a sample of n i.i.d. random variables drawn from f , and with smoothing factor h. Let g nh be another...
variate generators for the Poisson-Poisson and related distributions
The Analysis of Some Algorithms for Generating Random Variates with a Given Hazard Rate (1986)
We analyze the expected time penonnance of two versions of the thinning algorithm of Lewis and Shedler for generating random variates with a given hazard rate on [0,00). For thinning with fixed...
Author: TABLE OF CONTENTS (1986)
J. Bentley, E. Coffman, R. L. Graham, D. Kuck, Luc Devroye, Luc Devroye
Non-Uniform Random Variate Generation (1986)
Abstract. This chapter provides a survey of the main methods in non-uniform random variate generation, and highlights recent research on the subject. Classical paradigms such as inversion, rejection,...
North-Holland THE LIMIT BEHAVIOR OF AN INTERVAL SPLITTING SCHEME (1985)
Luc Devroye, Vanamamalai Seshadri
Abstract: We split [0,1] in a uniform manner, take the largest of the two intervals thus obtained, split this interval again uniformly, and continue in this fashion ad infinitum. We show that the...
The expected length of the longest probe sequence when the distribution is not uniform (1985)
We study the expected value of the maximum number of accesses needed to locate an element in a hashing file constructed by using an order-preserving hashing function and with collision resolution by...
North-Holland A NOTE ON THE EXPECTED TIME REQUIRED TO CONSTRUCT THE OUTER LAYER (1984)
Luc Devroye, Communicated J. Nievergelt
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...
Strong laws for the maximal k-spacing when k _< c log n (1984)
Paul Deheuvels, Luc Devroye, Zeitschrift Far
Summary. We consider the maximal k-spacing M, = max (U,,i+ k- U,i)
Exponential bounds for the running time of a selection algorithm (1984)
Hoare’s selection algorithm for finding the &h-largest element in a set of n elements is shown to use C comparisons where (i) E(P) < A,n ” for some constant A,> 0 and all p> 1; (ii)...
Distribution-free lower bounds in density estimation (1984)
We consider the kernel estimate on the real line, fn(x) _ ( nh)-1 E n 1 K((X;- x)/h), where K is a bounded even density with compact support, and X 1, • • •, X, are independent random variables...
Bounds for the uniform deviation of empirical measures (1982)
Luc Devroye, Communicated M. Rosenblatt
If x,)...) X, are independent identically distributed Rd-valued random vectors with probability measure p and empirical probability measure p,, and if QZ is a subset of the Bore1 sets on Rd, then we...
On the computer generation of random convex hulls (1982)
The convex hull of X1,..., Xn, a sample of independent identically distributed Rd-valued random vectors with density f is called a random convex hull with parameters f and II. In this paper, we give...
Recent results in non-uniform random variate generation (1981)
A selective survey is given of new methods in non-uniform random variate generation.
Communicated by R. L. Graham Abstract-Let X,..,X. be a sequence of independent Rd-valued random vectors with a common density f The following class of convex hull finding algorithms is considered:...
Luc Devroye, Communicated Donald, E. Knuth
Abstract-Frequently the need arises for the computer generation of variates that are exact/y distributed as 2 = max(X,,., X.) where X,,..., X, form a sequence of independent identically distributed...
Bin width selection in multivariate histograms by the combinatorial method
Multivariate density estimation, nonparametric estimation, variable histogram estimate, bandwith selection, 62G05,
Inequalities for a New Data-Based Method for Selecting Nonparametric Density Estimates
Luc Devroye, Gábor Lugosi, Frederic Udina
We continue the development of a method for the selection of a bandwidth or a number of design parameters in density estimation. We provide explicit non-asymptotic density-free inequalities that...
Variable Kernel Estimates: On the Impossibility of Tuning the Parameters
For the standard kernel density estimate, it is known that one can tune the bandwidth such that the expected L1 error is within a constant factor of the optimal L1 error (obtained when one is allowed...
Almost Sure Testability of Classes of Densities
Let a class $\F$ of densities be given. We draw an i.i.d.\ sample from a density $f$ which may or may not be in $\F$. After every $n$, one must make a guess whether $f \in \F$ or not. A class is...
Luc Devroye, László Györfi, Gábor Lugosi
We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of $k$ nominal densities is the true density is closest to,...
The Hilbert Kernel Regression Estimate
Devroye, Luc, Györfi, Laszlo, Krzyzak, Adam
Let (X, Y) be an d--valued regression pair, whereXhas a density andYis bounded. Ifni.i.d. samples are drawn from this distribution, the Nadaraya-Watson kernel regression estimate in dwith Hilbert...
Bounds for the uniform deviation of empirical measures
If X1,...,Xn are independent identically distributed Rd-valued random vectors with probability measure [mu] and empirical probability measure [mu]n, and if is a subset of the Borel sets on Rd, then...
Consistency of a recursive nearest neighbor regression function estimate
Let (X, Y) be an d - -valued random vector and let (X1, Y1),...,(XN, YN) be a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length l1, ..., ln, find the...
Simulating Bessel random variables
In this paper, we discuss efficient exact random variate generation for the Bessel distribution. The expected time of the algorithm is uniformly bounded over all choices of the parameters, and the...
On the Hilbert kernel density estimate
Let X be an -valued random variable with unknown density f. Let X1,...,Xn be i.i.d. random variables drawn from f. We study the pointwise convergence of a new class of density estimates, of which the...
On the impossibility of estimating densities in the extreme tail
We give a short proof of the following result. Let X1,...,Xn be independent and identically distributed observations drawn from a density f on the real line. Let fn be any estimate of the density gn...
Simulating theta random variates
We develop an exact simple random variate generator for the theta distribution, which occurs as the limit distribution of the height of nearly all models of uniform random trees. Even though the...
Another proof of a slow convergence result of Birgé
We give a short proof of the following result. Let fn be any density estimate based upon an i.i.d. sample drawn from a density f. For any monotone decreasing sequence {an} of positive numbers...
On the non-consistency of an estimate of Chiu
We show that for some densities, a bandwidth selection method of Chiu (1991) for kernel density estimates is not consistent. While the method shows promise for some densities, it should be used with...
A triptych of discrete distributions related to the stable law
We derive useful distributional representations for three discrete laws: the discrete stable distribution of Steutel and Van Harn, the discrete Linnik distribution introduced by Pakes, and a...
On the oscillation of the expected number of extreme points of a random set
Let ENn be the expected number of extreme points among n i.i.d. points with a common radially symmetric distribution in the plane. We show that for any monotone sequence [omega]n [short up arrow]...
A note on linnik's distribution
We provide a short proof of the validity and unimodality of Linnik's characteristic function 1/(1 + t [alpha]), 0 < [alpha] [less-than-or-equals, slant] 2, by noting that it corresponds to the...
A universal lower bound for the kernel estimate
Let fn be the kernel density estimate with arbitrary smoothing factor h and arbitrary (absolutely integrable) kernel K, based upon an i.i.d. sample of size n drawn from a density f. It is shown that...
On the non-consistency of the L2-cross-validated kernel density estimate
Let fn be the L2 cross-validated kernel estimate of a univariate density f. We show that when K is a symmetric bounded unimodal density, f is a monotone density on [0, [infinity]) and x3/4f(x) -->...
The limit behavior of an interval splitting scheme
Devroye, Luc, Letac, Gerard, Seshadri, Vanamamalai
We split [0,1] in a uniform manner, take the largest of the two intervals thus obtained, split this interval again uniformly, and continue in this fashion ad infinitum. We show that the extremes of...
Methods for generating random variates with Polya characteristic functions
Polya has shown that real even continuous functions that are convex on (0,[infinity]), for 1 t = 0, and decreasing to 0 as t --> [infinity] are characteristic functions. Dugué and Girault (1955)...
Density estimation by the penalized combinatorial method
Let f be an unknown multivariate density belonging to a prespecified parametric class of densities, , where k is unknown, but for all k and each has finite Vapnik-Chervonenkis dimension. Given an...
On the risk of estimates for block decreasing densities
A density f=f(x1,...,xd) on [0,[infinity])d is block decreasing if for each j[set membership, variant]{1,...,d}, it is a decreasing function of xj, when all other components are held fixed. Let us...
New Multivariate Product Density Estimators
Let X be an d-valued random variable with unknown density f. Let X1, ..., Xn be i.i.d. random variables drawn from f. The objective is to estimate f(x), where x=(x1, ..., xd). We study...
Strongly consistent model selection for densities
Gérard Biau, Benoît Cadre, Luc Devroye, László Györfi
Histogram-based estimate, Mixture densities, Multivariate density estimation, Strong consistency, Vapnik–Chervonenkis dimension, 62G10,
LOCAL TAIL BOUNDS FOR FUNCTIONS OF INDEPENDENT RANDOM VARIABLES
It is shown that functions defined on {0,1,...,r − 1} n satisfying certain conditions of bounded differences that guarantee sub-Gaussian tail behavior also satisfy a much stronger “local ”...