Difference between revisions of "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.