Theory Lunch Seminar / Doctoral Speaking Skills Talk
— 1:00pm
Location:
In Person
-
Gates Hillman 8102
Speaker:
THOMAS DRAPER
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~tdraper/
We study the fundamental problem of using i.i.d.~coin tosses from an entropy source to efficiently generate random variables Xi ~ Pi (i ≥1) where (P1, P2,…) is a random sequence of rational discrete probability distributions subject to an arbitrary stochastic process. Our method achieves an amortized expected entropy cost within ϵ ≥ 0 bits of the information-theoretically optimal Shannon lower bound using O(log(1/ϵ)) space. This result holds both pointwise in terms of the Shannon information content conditioned on Xi and Pi, and in expectation to obtain a rate of 𝔼[H(P1) +… + H(Pn)]/n + ϵ bits per sample as n → ∞ (where H is the Shannon entropy). The combination of space, time, and entropy properties of our method improves upon the Knuth and Yao (1976) entropy-optimal algorithm and Han and Hoshi (1997) interval algorithm for online sampling, which require unbounded space. It also uses exponentially less space than the more specialized methods of Kozen and Soloviev (2022) and Shao and Wang (2025) that generate i.i.d.~samples from a fixed distribution. Our online sampling algorithm rests on a powerful algorithmic technique called randomness recycling, which reuses a fraction of the random information consumed by a probabilistic algorithm to reduce its amortized entropy cost.
On the practical side, we develop randomness recycling techniques to accelerate a variety of prominent sampling algorithms, which include uniform sampling, inverse transform sampling, lookup table sampling, alias sampling, and discrete distribution generating (DDG) tree sampling. We show that randomness recycling enables state-of-the-art runtime performance on the Fisher-Yates shuffle when using a cryptographically secure pseudorandom number generator, and that it reduces the entropy cost of discrete Gaussian sampling.
Presented as part of the Theory Lunch Seminar
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement
For More Information:
matthewstewart@cmu.edu