Luc Devroye
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:
- Gábor Lugosi
Department of Economics and Business Pompeu Fabra University Barcelona Spain
7 shared publications - Louigi Addario-Berry
Department of Mathematics and Statistics McGill University Montréal Québec Canada
5 shared publications - Tommy Reddad
School of Computer Science McGill University 3480 University Street H3A 2A7 Montréal Québec Canada
4 shared publications - Xing Shi Cai
Department of Mathematics Uppsala University Sweden
4 shared publications - Adam Krzyżak
Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada
3 shared publications - Ebrahim Malalla
School of Computer Science, McGill University, Montreal, QC H3A 2K6, Canada
3 shared publications
Latest Publications
- 23 September 2026
- Published by Taylor & Francis in Journal of Statistical Computation and Simulation
- p. 1-20
The Pearson IV distribution: random variate generation and applications
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∈...
- 23 September 2026
- Published by Taylor & Francis in Journal of Statistical Computation and Simulation
- p. 1-20
The Pearson IV distribution: random variate generation and applications
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
- 3 November 2025
- Published by Springer Nature in Bulletin of Mathematical Biology
- Vol. 87 (12) , 1-22
Tree Height and the Asymptotic Mean of the Colijn–Plazzotta Rank of Unlabeled Binary Rooted Trees
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)$$ of a random n -leaf tree $$\tau _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)$$ . In particular, we find $${\mathbb {E}}\{\log _2 \log f(\tau _n)\} \sim 2 \sqrt{\pi n}$$ for uniformly random unlabeled ordered binary rooted trees and uniformly random leaf-labeled binary trees, and for a constant $$\alpha \approx 4.31107$$ , $${\mathbb {E}}\{\log _2 \log f(\tau _n)\} \sim \alpha \log n $$ for leaf-labeled binary trees under the Yule–Harding model. We show that the mean of $$f(\tau _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 $$\pi _n c_{n-1}$$ , where $$\pi _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.- 3 November 2025
- Published by Springer Nature in Bulletin of Mathematical Biology
- Vol. 87 (12) , 1-22
Open AccessTree Height and the Asymptotic Mean of the Colijn–Plazzotta Rank of Unlabeled Binary Rooted Trees
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)$$ of a random n -leaf tree $$\tau _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)$$ . In particular, we find $${\mathbb {E}}\{\log _2 \log f(\tau _n)\} \sim 2 \sqrt{\pi n}$$ for uniformly random unlabeled ordered binary rooted trees and uniformly random leaf-labeled binary trees, and for a constant $$\alpha \approx 4.31107$$ , $${\mathbb {E}}\{\log _2 \log f(\tau _n)\} \sim \alpha \log n $$ for leaf-labeled binary trees under the Yule–Harding model. We show that the mean of $$f(\tau _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 $$\pi _n c_{n-1}$$ , where $$\pi _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
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 AccessSimulating random variates from the Pearson IV and betaized Meixner-Morris distributions
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
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 AccessTree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees
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
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 AccessAn Algorithm to Recover Shredded Random Matrices
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
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 AccessRandom friend trees
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
- 1 February 2024
- Published by Springer Nature in Journal of Statistical Theory and Practice
- Vol. 18 (1) , 1-19
Random Variate Generation for the First Hit of a Ball for the Symmetric Stable Process in $\mathbb {R}^d$We provide uniformly efficient random variate generators for a collection of distributions for the hits of the symmetric stable process in $$\mathbb {R}^d$$ .- 1 February 2024
- Published by Springer Nature in Journal of Statistical Theory and Practice
- Vol. 18 (1) , 1-19
Open AccessRandom Variate Generation for the First Hit of a Ball for the Symmetric Stable Process in $\mathbb {R}^d$We provide uniformly efficient random variate generators for a collection of distributions for the hits of the symmetric stable process in $$\mathbb {R}^d$$ . - 1 January 2024
- Published by Institute for Applied and Pure Mathematics (IMPA) in Latin American Journal of Probability and Mathematical Statistics
- Vol. 21 (1) , 575-591
Subtractive random forests
- 1 January 2024
- Published by Institute for Applied and Pure Mathematics (IMPA) in Latin American Journal of Probability and Mathematical Statistics
- Vol. 21 (1) , 575-591
Subtractive random forests
- Open Access
- 28 October 2023
- Published by MDPI AG in Algorithms
- Vol. 16 (11) , 500
Two-Way Linear Probing Revisited
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 , 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 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.- 28 October 2023
- Published by MDPI AG in Algorithms
- Vol. 16 (11) , 500
Open AccessTwo-Way Linear Probing Revisited
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 , 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 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
- 7 October 2023
- Published by MDPI AG in Preprints.org
Two-way Linear Probing Revisited
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.- 7 October 2023
- Published by MDPI AG in Preprints.org
Open AccessTwo-way Linear Probing Revisited
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.