Tldr of the algorithm from the paper:

Instead of choosing random numbers to include in the list, they're choosing the gap between numbers. They derive the distribution of this gap then approximate it so it can be calculated quickly.