Thomas L. Draper

collaborators

Showing cs.DSShow all

3 papers · 1 filter

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…