Thomas L. Draper

collaborators

4 papers

cs.CC2026

Space-Entropy Lower Bounds for Random Sampling

Thomas L. Draper, Feras A. Saad

We prove fundamental space lower bounds for exact random sampling using an entropy source of i.i.d. uniform bits. A classic result from information theory shows that generating $n$ …

cs.DS2026

Online Random Sampling with Real Probabilities

Thomas L. Draper, David G. Harris, Feras A. Saad

We develop an efficient online algorithm to sample a sequence of discrete random variables using an entropy source of i.i.d. fair coin flips, in a standard model of real computatio…

cs.DS2025

Efficient Online Random Sampling via Randomness Recycling

Thomas L. Draper, Feras A. Saad

This article studies the fundamental problem of using i.i.d. coin tosses from an entropy source to efficiently generate random variables $X_{i} \sim P_{i}$ $(i \geq 1)$ , where $(P_1, P_…

cs.DS2025

Efficient Rejection Sampling in the Entropy-Optimal Range

Thomas L. Draper, Feras A. Saad

We study the problem of generating a random variate $X$ from a finite discrete probability distribution $P$ using an entropy source of independent fair coin flips. A classic result…