LDLuc Devroye

Luc Devroye

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Luc Devroye has a total of 65 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • The Pearson IV distribution: random variate generation and applications

    by Luc Devroye, Joe R. Hill

    1. Undoubtedly, the most enigmatic member of Pearson's family (Pearson, [1]) is the Pearson type IV distribution. It is indexed by two parameters, a shape parameter a>12 and a skewness parameter s∈...

  • Open Access

    Tree Height and the Asymptotic Mean of the Colijn–Plazzotta Rank of Unlabeled Binary Rooted Trees

    by Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, Stephan Wagner

    The Colijn–Plazzotta ranking is a bijective encoding of the unlabeled binary rooted trees with positive integers. We show that the rank f ( t ) of a tree t is closely related to its height h , the maximal path length from a leaf to the root. We consider the rank $$f(\tau _n)$$ f ( τ n ) of a random n -leaf tree $$\tau _n$$ τ n under each of three models: (i) uniformly random unlabeled unordered binary rooted trees, or unlabeled topologies; (ii) uniformly random leaf-labeled binary trees, or labeled topologies under the uniform model; and (iii) random binary search trees, or labeled topologies under the Yule–Harding model. Relying on the close relationship between tree rank and tree height, we obtain results concerning the asymptotic properties of $$\log \log f(\tau _n)$$ log log f ( τ n ) . In particular, we find $${\mathbb {E}}\{\log _2 \log f(\tau _n)\} \sim 2 \sqrt{\pi n}$$ E { log 2 log f ( τ n ) } ∼ 2 π n for uniformly random unlabeled ordered binary rooted trees and uniformly random leaf-labeled binary trees, and for a constant $$\alpha \approx 4.31107$$ α ≈ 4.31107 , $${\mathbb {E}}\{\log _2 \log f(\tau _n)\} \sim \alpha \log n $$ E { log 2 log f ( τ n ) } ∼ α log n for leaf-labeled binary trees under the Yule–Harding model. We show that the mean of $$f(\tau _n)$$ f ( τ n ) itself under the three models is largely determined by the rank $$c_{n-1}$$ c n - 1 of the highest-ranked tree—the caterpillar—obtaining an asymptotic relationship with $$\pi _n c_{n-1}$$ π n c n - 1 , where $$\pi _n$$ π n is a model-specific function of n . The results resolve open problems, providing a new class of results on an encoding useful in mathematical phylogenetics.

  • Open Access

    Simulating random variates from the Pearson IV and betaized Meixner-Morris distributions

    by Luc Devroye, Joe R. Hill

    We develop uniformly fast random variate generators for the Pearson IV distribution that can be used over the entire range of both shape parameters. Additionally, we derive an efficient algorithm for sampling from the betaized Meixner-Morris density, which is proportional to the product of two generalized hyperbolic secant densities.

  • Open Access

    Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees

    by Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, Stephan Wagner

    The Colijn--Plazzotta ranking is a bijective encoding of the unlabeled binary rooted trees with positive integers. We show that the rank $f(t)$ of a tree $t$ is closely related to its height $h$, the length of the longest path from a leaf to the root. We consider the rank $f(τ_n)$ of a random $n$-leaf tree $τ_n$ under each of three models: (i) uniformly random unlabeled unordered binary rooted trees, or unlabeled topologies; (ii) uniformly random leaf-labeled binary trees, or labeled topologies under the uniform model; and (iii) random binary search trees, or labeled topologies under the Yule--Harding model. Relying on the close relationship between tree rank and tree height, we obtain results concerning the asymptotic properties of $\log \log f(τ_n)$. In particular, we find $\mathbb{E} \{\log_2 \log f(τ_n)\} \sim 2 \sqrt{πn}$ for uniformly random unlabeled ordered binary rooted trees and uniformly random leaf-labeled binary trees, and for a constant $α\approx 4.31107$, $\mathbb{E}\{\log_2 \log f(τ_n)\} \sim α\log n $ for leaf-labeled binary trees under the Yule--Harding model. We show that the mean of $f(τ_n)$ itself under the three models is largely determined by the rank $c_{n-1}$ of the highest-ranked tree -- the caterpillar -- obtaining an asymptotic relationship with $π_n c_{n-1}$, where $π_n$ is a model-specific function of $n$. The results resolve open problems, providing a new class of results on an encoding useful in mathematical phylogenetics.

  • Open Access

    An Algorithm to Recover Shredded Random Matrices

    by Caelan Atamanchuk, Luc Devroye, Massimo Vicenzo

    Given some binary matrix $M$, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the unique original orderings and matrix? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that there is a constant $c > 0$ such that the algorithm terminates in $O(n^2)$ time with high probability and in expectation for random $n \times n$ binary matrices with i.i.d.\ Bernoulli $(p)$ entries $(m_{ij})_{ij=1}^n$ such that $\frac{c\log^2(n)}{n(\log\log(n))^2} \leq p \leq \frac{1}{2}$.

  • Open Access

    Random friend trees

    by Louigi Addario Berry, Simon Briend, Luc Devroye, Serte Donderwinkel, Céline Kerriou, Gábor Lugosi

    We study a random recursive tree model featuring complete redirection called the random friend tree and introduced by Saramäki and Kaski. Vertices are attached in a sequential manner one by one by selecting an existing target vertex and connecting to one of its neighbours (or friends), chosen uniformly at random. This model has interesting emergent properties, such as a highly skewed degree sequence. In contrast to the preferential attachment model, these emergent phenomena stem from a local rather than a global attachment mechanism. The structure of the resulting tree is also strikingly different from both the preferential attachment tree and the uniform random recursive tree: every edge is incident to a macro-hub of asymptotically linear degree, and with high probability all but at most $n^{9/10}$ vertices in a tree of size $n$ are leaves. We prove various results on the neighbourhood of fixed vertices and edges, and we study macroscopic properties such as the diameter and the degree distribution, providing insights into the overall structure of the tree. We also present a number of open questions on this model and related models.

  • Open Access

    Random Variate Generation for the First Hit of a Ball for the Symmetric Stable Process in $\mathbb {R}^d$

    by Luc Devroye, John P. Nolan

    We provide uniformly efficient random variate generators for a collection of distributions for the hits of the symmetric stable process in $$\mathbb {R}^d$$ R d .


  • Subtractive random forests

    by Nicolas Broutin, Luc Devroye, Gábor Lugosi, Roberto Imbuzeiro Oliveira


  • Open Access

    Two-Way Linear Probing Revisited

    by Ketan Dalal, Luc Devroye, Ebrahim Malalla

    Linear probing continues to be one of the best practical hashing algorithms due to its good average performance, efficiency, and simplicity of implementation. However, the worst-case performance of linear probing seems to degrade with high load factors due to a primary-clustering tendency of one collision to cause more nearby collisions. It is known that the maximum cluster size produced by linear probing, and hence the length of the longest probe sequence needed to insert or search for a key in a hash table of size n, is Ω(logn), in probability. In this article, we introduce linear probing hashing schemes that employ two linear probe sequences to find empty cells for the keys. Our results show that two-way linear probing is a promising alternative to linear probing for hash tables. We show that two-way linear probing has an asymptotically almost surely O(loglogn) maximum cluster size when the load factor is constant. Matching lower bounds on the maximum cluster size produced by any two-way linear probing algorithm are obtained as well. Our analysis is based on a novel approach that uses the multiple-choice paradigm and witness trees.


  • Open Access

    Two-way Linear Probing Revisited

    by Ketan Dalal, Luc Devroye, Ebrahim Malalla

    We introduce linear probing hashing schemes that construct a hash table of size $n$, with constant load factor $\alpha$, on which the worst-case unsuccessful search time is asymptotically almost surely $O(\log \log n)$. The schemes employ two linear probe sequences to find empty cells for the keys. Matching lower bounds on the maximum cluster size produced by any algorithm that uses two linear probe sequences are obtained as well.