106 citations · 352 across the 51 of their papers we have counts for
6 papers · 1 filter
On the measure of Voronoi cells
Luc Devroye, László Györfi, Gábor Lugosi +1
independent random points drawn from a density in define a random Voronoi partition. We study the measure of a typical cell of the partition. We prove that the asympt…
The expected bit complexity of the von Neumann rejection algorithm
Luc Devroye, Claude Gravel
In 1952, von Neumann introduced the rejection method for random variate generation. We revisit this algorithm when we have a source of perfect bits at our disposal. In this random…
Sub-Gaussian mean estimators
Luc Devroye, Matthieu Lerasle, Gabor Lugosi +1
We discuss the possibilities and limitations of estimating the mean of a real-valued random variable from independent and identically distributed observations from a non-asymptotic…
Exceptional rotations of random graphs: a VC theory
Louigi Addario-Berry, Shankar Bhamidi, Sébastien Bubeck +3
In this paper we explore maximal deviations of large random structures from their typical behavior. We introduce a model for a high-dimensional random graph process and ask analogo…
The graph structure of a deterministic automaton chosen at random: full version
Xing Shi Cai, Luc Devroye
A deterministic finite automaton (DFA) of states over a -letter alphabet can be seen as a digraph with vertices which all have exactly labeled out-arcs (-out digr…
Random variate generation using only finitely many unbiased, independently and identically distributed random bits
Luc Devroye, Claude Gravel
For any discrete probability distributions with bounded entropy, we can generate exactly a random variate using only a finite expected number of perfect coin flips. A perfect coin…