TADM2E 2.43

Whether we know $ n $ or not we can sample $ k $ values uniformly by assigning a random value to each element, sorting, and taking the top $ k $ values. However, this is not very efficient so instead we can use a priority queue of size $ k $ with random priority.

Alternatively, we can iterate over the elements in $ S $ from $ i = 0 $ until $ S[i] $ is empty. If $ i < k $, $ S'[i] = S[i] $. After that, for each $ i $, replace a random element in $ S' $ with $ S[i] $, with probability $ \frac{k}{i + 1} $ of performing the replacement rather than skipping to the next.

Return to Algo-analysis-TADM2E ...