# How to choose resample size when drawing without replacement?

Say I have some second-order statistic $m(x)$ where $x$ is a data vector of length $n$. Let's also assume that the limiting distribution of $x$ is gaussian-ish, but generally unknown, so that the assumptions that enable one to derive the usual error analysis expressions do not hold. In this case, if I want to get an estimate in the uncertainty in the measure of $m$, I will have to simulate it, using a bootstrap or something. So, I generate 1,000 unique realizations of $x$, $x_i$ (1 $\leq$ $i$ $\leq$ 1000), and use the distribution of all $m(x_i)$ to get an idea of the error in $m$

Now, since $m$ is second-order, it is preferable to draw without replacement when generating the 1,000 resamples of $x$. This is all fine, and the bootstrapping routines I've implemented work well. Here is my problem:

• I have to choose a size of the resample
• If I choose that size to be $n$, then all $x_i$ will be identical since I'm sampling without replacement
• So, the resample size must obviously be smaller than the size of $x$

Problem is, if I choose the size of each $x_i$ to be high, say $0.9n$, then my error is going to be very small. If I choose the size to be small, $0.1n$, then the error can blow up. So, I can effectively make the error in $m$ whatever I'd like, which obviously isn't right...

What do I do at this point, while maintaining integrity?!

• How about a sample size of $n$/2 so you can maximise the total number of unique draws? Not an answer, just a thought. – Moss Murderer Oct 27 '17 at 17:50
• @MossMurderer How does this maximize the number of unique draws? – Anonymous Oct 27 '17 at 17:55
• Because of this? math.stackexchange.com/questions/722952/… – Moss Murderer Oct 27 '17 at 18:07
• @MossMurderer Hmm, interesting. At least that provides some motivation. Thanks a lot! Though I do await more answers – Anonymous Oct 27 '17 at 18:35
• @MossMurderer I thought about this a bit, and I came to some satisfying conclusions - see my answer. Thanks again! – Anonymous Oct 27 '17 at 19:03

I'm posting my own answer here because I think it is probably correct, but feel free to please input ideas.

@MossMurderer brought my attention, in the comments to the original question, an interesting proof. That is, ${n \choose k}$ is maximum at $k=n/2$. This means that if I choose my resample size $k$ to be $n/2$, I will be maximizing the number of unique draws $x_i$.

This is desirable for a very simple reason: to preform the bootstrap, I compute the statistic $m$ for each realization $x_i$. Let's call the results of that calculation a vector $M = [m(x_1),... m(x_{1000})]$. The estimated error in the statistic $m$ is then something like $\sigma(M)$. Of course, you only ever use the standard deviation $\sigma$ as a statistic if you can safely assume your limiting distribution to be gaussian.

If we ensure that we maximize the number of unique $x_i$ by setting $k = n/2$, then we have sampled the $M$ space as well as we possibly can, and therefore $M$ will be as close to gaussian as is possible. In this way, the measure $\sigma(M)$ will be most reliable when the length $k$ of each $x_i$ is $n/2$.

I apologize if this is difficult to read - please edit if you feel you are more eloquent than I.

• I think you should also keep in mind that setting $k=n/2$ might not be enough to guarantee that you sample the distribution over $m$ sufficiently well. You also need enough samples. So if $n$ is very large, say 1 billion but you only generate 1000 realizations, then the value of $k$ might not matter much. – Moss Murderer Oct 27 '17 at 21:55
• @MossMurderer Hmm, I suppose that that is another question in itself; how to optimally choose the number of resamples. – Anonymous Oct 28 '17 at 2:51
• I don't think this is the right approach. There are two types of error here. Suppose instead of putting 1000 samples in M, you hire all the supercomputers in the universe and use every possible subset. Call the result $P$. Your reasoning is that $P$ is big, so $\sigma(M)$ should be close to $\sigma(P)$. This is flat wrong, but more important, it ignores the desired target of inference! If $Q$ is the "true" distribution of data, i.e. an infinite vector of data-that-might-have-been, then you want something close to $\sigma(Q)$. $Q$ is not $P$! – eric_kernfeld Feb 17 '18 at 23:20
• @eric_kernfeld So I am not actually optimizing sampling in any space at all? I sort of see what you're saying... do you see an obvious way to get as close to $\sigma(Q)$ as I can, other than what I've outlined? No doubt that drawing a sample size of $k=n/2$ is better than $k=1$. It is also certainly better than $k=n$, since that would result in $\sigma(M) = 0$... it therefore seems optimal (necessary) to have $1 < k < n$. Would you say that some value satisfying this condition, other than the one I have suggested ($k=n/2$), is more sensibly motivated? – Anonymous Feb 19 '18 at 19:58
• I agree that it's somewhere in between: $1<k_{opt}<n$. I think there is some better way than taking half the dataset -- but I haven't tried to compute an actual value; hence the bounty. – eric_kernfeld Feb 20 '18 at 16:38