Sample size is $10^7$, what happens if we bootstrap with replacement using subsample of size $5000$?

Question

Let $\{X_1,X_2,\dots,X_n\}$ be a sample of $n$ iid observations of a random variable $X$, and let $\overline X_n = \frac{1}{n} \sum_{i=1}^n X_i$ be the sample mean.

Now suppose we want to use bootstrapping to estimate, for example, the variance of the sample mean. Let $\{X_1^{*(i)},X_2^{*(i)},\dots,X_n^{*(i)}\}$ be a sample with replacement from the original sample and let $\overline X_n^{*(i)} = \frac{1}{n} \sum_{j=1}^n X_j^{*(i)}$ be the sample mean for the $i$-th bootstrap sample.

Let $B$ be the number of bootstrap rounds. Then we have a bootstrap estimate of the variance. $$ \text{Var}_{B,n} = \frac{1}{B-1} \sum_{i=1}^B (\overline X_n^{*(i)} - \overline X_B^*)^2, \quad \quad \text{where} \ \overline X_B^* = \frac{1}{B} \sum_{i=1}^B \overline X_n^{*(i)}. $$

Suppose $n$ is very large and computing the bootstrap variance estimate will be computationally intensive. For example suppose we were using a slow computer and take $n=10^7$

To speed things up, we decide that instead of repeatedly drawing samples of size $n$ we will instead draw samples of size $m \ll n$ with replacement. For example, for $n=10^7$, we could take $m=5000$.

Let $\{Y_1^{*(i)},Y_2^{*(i)},\dots,Y_m^{*(i)}\}$ be a sample with replacement from the original sample $\{X_1,X_2,\dots,X_n\}$ and let $\overline Y_m^{*(i)} = \frac{1}{m} \sum_{j=1}^m Y_j^{*(i)}$ be the sample mean for the $i$-th bootstrap sample.

Now, this time we have the variance estimate: $$ \text{Var}_{B,m} = \frac{1}{B-1} \sum_{i=1}^B (\overline Y_m^{*(i)} - \overline Y_B^*)^2, \quad \quad \text{where} \ \overline Y_B^* = \frac{1}{B} \sum_{i=1}^B \overline Y_m^{*(i)}. $$

Is $\text{Var}_{B,m}$ a valid estimate of the variance of the sample mean? One issue that I have noticed is that since $m$ is such so much smaller than $n$ that we have effectively sampled without replacement when we computed $\text{Var}_{B,m}$. Is this a problem?

Answer 1

I'm no expert in the bootstrap, but I anticipate that using fewer samples in your bootstrap means that the uncertainty in mean will be inflated.

The standard error of the sampling distribution is inversely proportional to the square root of the sample size. A smaller sample size thus means larger uncertainty in your estimates. Its easy to see evidence of this. Shown below are bootstrap samples of a dataset I've simulated. Blue histogram is resamples using the full size of the dataset. Red histogram is using 1% of the dataset.

Bootstrapping is embarrassingly parallelized. I'm willing to bet there is a good solution to this problem which does not require sub sampling of the data.