How to sample randomly from a population? What do you think about the following method to perform a random sampling:


*

*Generate as many floats (between 0 and 1) as individuals using a quantum random generator (each value appears only one time).

*Assign floats to individuals.

*Sort individuals according to the order of the floats.

*Select individuals as needed.


Since the generator has good quality, is it risky to use this method?
 A: It's a fine method in theory.  To see why, we need to check two things.


*

*Are all individuals selected with equal chances?  Yes, because the distributions of floats assigned to each individual are identical (they are uniform in $[0,1)$).

*Are the selections independent?  Yes, because the floats assigned to the individuals are independent (presumably: that's part of what it means to be a "high quality" random number generator).
However, this method tends to be inefficient both in terms of computation time and memory resources.  It takes $O(n\log(n))$ time and $O(n)$ memory for selecting from a population of $n$.  Both can often be improved, sometimes greatly.
A general-purpose algorithm starts by considering how much of the population you need to sample.  If it's more than half the population, then identify the individuals not in the sample and select the rest (at a cost of $O(n)$ time).  This leaves us to identify no more than half the population, say $k$ out of $n$ individuals (with $2k \le n$).  Let their identifiers be in an array population[0..n-1]:
i = 0
selection = new set
while (i < k) {
    x = random float in [0,1)
    j = int(x * (n-i))
    adjoin population[j] to selection
    population[j] = population[n-1-i]
    i++
}
return selection

The key step--copying the last individual at population[n-i-i] into the space vacated by the recently selected individual, population[j]--doesn't actually require the entire population[] array to be in RAM: you can do it with a dictionary of $k$ pointers instead.  This makes the computation time $O(k \log(k))$ rather than $O(k)$ but reduces the storage requirements from $O(n)$ to $O(k)$, which can be substantial for small selections from huge populations stored offline.
The proof that this algorithm works is inductive.  Obviously it works for $n=1$.  For general $n\gt 1$, and assuming the random float procedure is a good one, then at the first step (a) each individual is chosen with equal probability and (b) that choice is independent of the next step, which selects $k-1$ individuals from a population of $n-1$.  Because this (inductively) is assumed to be correct, we are done.
