2
$\begingroup$

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:

  1. 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.

  2. 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?

  3. 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?

$\endgroup$
  • $\begingroup$ Welcome to our site. Could you elaborate on what you mean by "following the population" and describe the ultimate purpose of your sampling activity? $\endgroup$ – whuber Aug 25 '18 at 17:52
  • $\begingroup$ I want the empirical cumulative distribution functions of $\mathcal D$ and $\mathcal D_s$ to be as similar as possible (e.g. perhaps to sample in a way that minimizes the KL divergence between the two? Or another distribution distance measure if one is more fitting). $\endgroup$ – Nathan Aug 25 '18 at 20:12
3
$\begingroup$

One purpose here is to show how the three methods can be carried out using R statistical software.

Sampling without replacement. Suppose the parent sample is of size $n = 200$ and that we want a sub-sample of size (about or exactly) $n = 100.$ If you are doing an experiment with two treatments A and B and you want to split 200 available subjects at random into two groups of 100 each, without any inadvertent bias.

Let the 200 available subjects come from a population distributed $\mathsf{Norm}(\mu = 100,\, \sigma=15),$ with values rounded to integers.

set.seed (825);  x = round(rnorm(200, 100, 15))
summary(x);  sd(x);  length(x)
  Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 56.00   89.00   99.00   99.38  110.00  147.00 
[1] 15.06187  # SD
[1] 200       # n
hist(x, ylim=c(0,60), col="skyblue2", label=T)

enter image description here

The statement set.seed would allow you to retrieve exactly the same sample; omit it if you want your own sample of 200.

The R function sample selects a random sample of a specified size from an existing 'population'. Here the 'population' is the vector x of length 200. By default (unless we ask otherwise), the sample is chosen without replacement.

y = sample(x, 100);  summary(y);  sd(y); length(y)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  56.00   88.00   97.50   97.87  107.25  135.00 
[1] 15.84818   # SD of subsample
[1] 100        # m

The sample mean of the 200 observations $\bar X = 99.38$ and of the subsample $\bar Y = 97.87$ are nearly equal and so are the two standard deviations $S_X = 15.05$ and $S_Y = 15.85.$

If the population and sample sizes in sample are the same, then sample simply shuffles or 'permutes' the observations in the population. (If no sample size is given, this is what sample does.) If we did this and then picked the first 100 and the second 100 values from the scrambled list, then we would have the two randomly chosen groups for our experiment.

x.perm = sample(x);  y.a = x.perm[1:100];  y.b = x.perm[101:200]
mean(y.a);  sd(y.a);  mean(y.b);  sd(y.b)
[1] 101.61    # mean of subsample A
[1] 14.66935  # SD of A
[1] 97.15     # mean of subsample B
[1] 15.19129  $ SD of B

Although chosen at random, the two samples are not exactly the same:

enter image description here

The answer to your 'bonus question' is Yes. Choosing 10 cards without replacement from a standard deck is usually done in card games by shuffling the deck once (which is usually not nearly enough to put it in random order) and dealing cards from the top of the shuffled deck.

Choosing element-wise with probability p. If it doesn't matter whether the the two experimental groups are exactly of the same size, you might use your first method. Let's look at the same sample of 200 as above, and use this method to split the sample into two sub-samples. This is as if we toss a fair coin to decide whether each subject goes into group A or group B. An 89-to-111 split is an unusually unequal outcome for the sizes of the two samples. Such possibilities are one reason this method is usually not preferred for randomizing subjects into groups.

set.seed (825);  x = round(rnorm(200, 100, 15))
set.seed (818); ht = rbinom(200, 1, p=1/2)
y.A = x[ht==1];  y.B = x[ht==0]     
mean(y.A);  sd(y.A);  length(y.A)
[1] 98.96629
[1] 13.91733
[1] 89
mean(y.B);  sd(y.B);  length(y.B) 
[1] 99.71171
[1] 15.9752
[1] 111

Sampling with replacement: In nonparametric bootstrapping, the assumption is that the sample (of size $n)$ at hand represents what we know about the population from which it was taken. For example, by re-sampling from these observations we hope to gain information about the variability of the sample mean $\bar X$ as an estimate of the population mean $\mu$ in order to make a confidence interval for $\mu.$ For technical reasons, the 're-samples' should be the same size $n$ as the original sample. But if we sampled without replacement, the re-samples would just be permuted versions of the original, so nothing interesting would be gained. By sampling with replacement, we can get different samples. And there is nothing wrong with encountering an observation several times: if the population can produce a particular value once, then ought to be able to produce that same value again.

Let's look at a sample w of size $n = 100$ from the distribution $\mathsf{Exp}(rate = 1/10),$ which has $\mu = 10.$ The mean of our sample is $\bar W = 9.84.$ By statistical theory, a 95% confidence interval for $\mu$ based on a sample of size 100, using the distribution $\mathsf{Gamma}(n,n),$ is $(8.17, 12.10).$

set.seed(2018);  w = rexp(100, .1);  mean(w)
[1] 9.84329
mean(w)/qgamma(c(.975,.025), 100, 100)
[1]  8.166743 12.097846

Means of two re-samples of size $n = 100$ from w, using sampling with replacement, are 8.95 and 9.13, as follows:

mean(sample(w, 100, repl=T));  mean(sample(w, 100, repl=T))
[1] 8.953673
[1] 9.132817

A very crude nonparametric bootstrap 95% confidence interval for $\mu,$ based on $B = 1000$ re-samples from the sample w, and not using the assumption that the data are from $\mathsf{Gamma}(100,100),$ is $(8.14, 11.68).$ (This bootstrap is a simplified version just for easy illustration here, and is not generally recommended.) You can google 'bootstap' and look at other Q&A's on this site for more detailed information on bootstrap confidence intervals.

set.seed(2018);  w = rexp(100, .1) 
summary(w)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
0.1236  3.4578  7.5711  9.8433 13.5535 60.1451 

a = replicate(1000, mean(sample(w, 100, repl=T)))
quantile(a, c(.025,.975))
     2.5%     97.5% 
8.137961 11.677630 

enter image description here

Note: Because the sample w is skewed with sample mean larger than sample median, there would be reason to suspect the population mean $\mu$ may be a scale parameter rather than a location parameter. A more sophisticated bootstrap 95% CI treating $\mu$ as a scale parameter is $(8.30, 11.91).$

$\endgroup$
  • $\begingroup$ I appreciate the answer, though I'm not sure if it directly answer the question. Is the suggestion to just try the three different methods on my data and then see empirically which one leads (on average) to a subset $\mathcal D_s$ with eCDF closest to that of $\mathcal D$? (which doesn't seem an unreasonable suggestion, I'm just unsure if there's a theoretical, rather than empirical, answer) $\endgroup$ – Nathan Aug 26 '18 at 3:39
  • $\begingroup$ Not clear whether your $D$ is a population (finite, countably infinite, continuous?) or a sample? Not clear what measure of 'closest' you're using. Not clear whether this is purely theoretical or whether you have an application in mind. Please revise your question to settle those issues and maybe someone can suggest a path toward a more satisfactory solution. $\endgroup$ – BruceET Aug 26 '18 at 6:33
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.