Daniel Ting

Simple, Optimal Algorithms for Random Sampling Without Replacement

2021 · arXiv (Cornell University)

Consider the fundamental problem of drawing a simple random sample of size k without replacement from [n] := {1, . . . , n}. Although a number of classical algorithms exist for this problem, we …