Lecture Notes: Random shuffling and sampling

In this lecture, we will discuss a fundamental problem: given a set S of size n, how to obtain a random sample set R of S in O(n) time? At first glance, this may seem to be trivial: if we want an R of size s, how about generating a random number t from 1 to n, taking the t-th element of S as a sample, and repeating this s times? But another moment’s thought would reveal that this algorithm may not always suit our needs. First, it samples with replacement. In other words, one can imagine that, after taking an element of S as a sample, this element is put back into S (i.e., replaced) so that it can be sampled again. Sampling with replacement may create a bag of samples, i.e., a multi-set, because the same element can have several copies in R. In some scenarios, we want to have distinct samples: for example, if you want to interview s random people to do a survey, it makes no sense to interview the same person twice. Another limitation of the algorithm is that it needs to know the number n in advance (otherwise, what is the range of your random number?). This is not a desired property in data streams: for example, if you want to keep track of a sample set of the creditcard transactions tomorrow continuously as they take place, you have no idea about n, i.e., the total number of transactions. You may easily come up with another simple algorithm: if the sampling rate is p, why not jus