2021/04/11 by Daniel Ting, Ting, Daniel
Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2104.05091
openalex publication_date 2021/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 construct algorithms that are even simpler, easier to implement, and have optimal space and time complexity.