It is not in the paper but it is a simple extension of that paper. I explained the algorithm briefly in the last paragraph of the javadoc. Basically, for each output position, we do a random sort and select the smallest one. Let s be the sample size and n be the population size. For any q > 0, the probability of all random keys being greater than q is (1-q)^n. Thus, if we throw away items with associated keys greater than q, with probability at least 1 - s (1-q)^n, we still have at least one candidate for each position. Let the failure rate delta = s (1-q)^n and solve for q, we get q = 1 - exp(log(delta/s)/n).