How to sample a population Suppose I have a set $\mathcal D$ of $n$ data points and want to generate a subset $\mathcal D_s$ with (potentially approximately) $m$ data points. What is the best way to do this in terms of following the distribution of $\mathcal D$? These are the three approaches that I've thought of:


*

*For each point, sample a Bernoulli with $p = m / n$; include that point in $D_s$ if the sample is 1. This gives $\mathbb E[|\mathcal D_s|] = m$, but the actual size of the subset will vary.

*Sequentially sample a point from $\mathcal D$ uniformly at random and add it to $\mathcal D_s$ until $|\mathcal D_s| = m$ (this is sampling with replacement, as nothing is removed from $\mathcal D$). I'm aware that this is how bootstrap subsampling is done. The accepted answer to this question indicates that it's because one starts with a sample from some larger population; the potentially repeated elements represent elements from the original population that weren't included in the sample. However, since I want the distribution of $\mathcal D_s$ to follow that of $\mathcal D$, I think this could be construed as sampling from a population instead of subsampling a sample from a population? Does sampling with replacement make any sense then?

*As in 2. except sample without replacement (i.e. remove each point from $\mathcal D$ if it's added to $\mathcal D_s$).
Both 2. and 3. guarantee $|\mathcal D_s| = m$ while 1. will have a distribution for $|\mathcal D_s|$.
Is there some theoretical result about which sampling method will give $\mathcal D_s$ that best approximates $\mathcal D$? (and if $\mathcal D$ was a sample from a larger population, would 2. then be the right method to generate $\mathcal D_s$?)
Related question, for bonus points: Is the sequential sampling without replacement in 3. equivalent to shuffling $\mathcal D$ and selecting the first $m$ points?
 A: 
Related question, for bonus points: Is the sequential sampling without replacement ... equivalent to shuffling $\mathcal D$ and selecting the first $m$ points?

Yes, so long as the "shuffling" is done properly. Consider an population of values $x_1,...,x_n$ and suppose we create a random permutation $\boldsymbol{I} = (i_1,...,i_n)$ that we use to reorder the values into the "shuffled" vector $x_{i_1},...,x_{i_n}$.  If each possible permutation is equally likely then the latter vector of values is exchangeable and the "shuffle" has been done correctly.  The key requirement is that the latter vector of shuffled values must be exchangeable.  If this holds then the first $m$ values from the shuffled vector give a simple-random-sample without replacement from the full vector.
A well-known shuffling algorithm that produces an exchangeable sequence of values is the Fisher-Yates shuffle.  In this algorithm (forward version) you go through the units in the original population sequentially and swap each one with a uniformly randomised unit that is no earlier in the sequence than the one under consideration.  Once you get all the way through the sequence the original vector of values is properly shuffled (so long as your random number generator has a sufficient number of seeds and avoids modulo bias).
