# Adaptively selecting the number of bootstrap replicates

As with most Monte Carlo methods, the rule for bootstrapping is that the larger the number of replicates, the lower the Monte Carlo error. But there are diminishing returns, so it doesn't make sense to run as many replicates as you possibly can.

Suppose you want to ensure that your estimate $\hat θ$ of a certain quantity $θ$ is within $ε$ of the estimate $\tilde θ$ that you would get with infinitely many replicates. For example, you might want to be reasonably sure that the first two decimal places of $\hat θ$ are not wrong due to Monte Carlo error, in which case $ε = .005$. Is there an adaptive procedure you can use in which you keep generating bootstrap replicates, checking $\hat θ$, and stopping according to a rule such that, say, $|\hat θ - \tilde θ| < ε$ with 95% confidence?

N.B. While the existing answers are helpful, I'd still like to see a scheme to control the probability that $|\hat θ - \tilde θ| < ε$.

• I object to calling the bootstrap a Monte Carlo method. It is not even though often Monte Carlo methods are needed to get good approximations to the bootstrap estimates because enumeration is infeasible. – Michael R. Chernick May 4 '18 at 19:38
• I am not sure exactly what you are asking. But often it is difficult to know in advance how many bootstrap replicates you need to make the Monte Carlo approximation to the bootstrap estimate close to the actual bootstrap estimate. I have suggested doing something like what you are suggesting. That would be to add replications until the change in the estimate is small. This would be an indication of convergence. – Michael R. Chernick May 4 '18 at 19:45
• @MichaelChernick "I am not sure exactly what you are asking." — What can I do to help clarify it? – Kodiologist May 4 '18 at 20:36
• When you talk about adaptive selecting do you mean what I am suggesting? That is to continue to take bootstrap replications until two successive estimate are very close (say the absolute difference is less than a specified $\epsilon$). – Michael R. Chernick May 4 '18 at 21:38
• @MichaelChernick I don't think that looking at differences between successive $\tilde θ$s would suffice to get $|\hat θ - \tilde θ| < ε$. But I'm not sure. – Kodiologist May 4 '18 at 23:13

If the estimation of $\theta$ on the replicates are normally distributed I guess you can estimate the error $\hat{\sigma}$ on $\hat{\theta}$ from the standard deviation $\sigma$:

$$\hat{\sigma} = \frac{\sigma}{\sqrt{n}}$$

then you can just stop when $1.96*\hat{\sigma} < \epsilon$.

Or have I misunderstood the question? Or do you want an answer without assuming normality and in presence of significant autocorrelations?

• It would be nice to not have to assume normality, but we can certainly assume that the bootstrap replicates are selected independently, if that's the sort of dependence you mean by autocorrelation. – Kodiologist May 4 '18 at 23:17
• If we do not assume normality though, we cannot even be sure that the mean is a good estimate for theta. I believe we need more hypotheses to propose a solution... – fabiob May 5 '18 at 10:45
• To be clear, what thing, exactly, are you assuming to be normal? Your answer text says "the replicates are normally distributed", but each replicate is a sample that's the same size as the original sample. I don't know what it would mean for a collection of samples to be normally distributed. – Kodiologist May 5 '18 at 15:52
• I am assuming to be normal the distribution of $\theta_i$ the estimation of the quantity you are interested in, that you perform on the replicate $i$. I will edit my formulation which was unclear. – fabiob May 6 '18 at 11:30
• finally notice how my answer and michael's are the same if you substitute C-> $\sigma^2$ and B ->$n$, which suggests a way to "determine" C. you can take the variance of $\theta_i$, or double of that if you want to be conservative. do you agree (or think I am missing something)? – fabiob May 6 '18 at 12:01

On pages 113-114 of the first edition of my book Bootstrap Methods: A Practitioner's Guide Wiley (1999) I discuss methods for determining how many bootstrap replications to take when using the Monte Carlo approximation.

I go into a detail about a procedure due to Hall that was described in his book The Bootstrap and Edgeworth Expansion, Springer-Verlag (1992). He shows that when the sample size n is large and the number of bootstrap replications B is large the variance of the bootstrap estimate is C/B where C is an unknown constant that does not depend on n or B. So if you can determine C or bound it above you can determine a value for B that that makes the error of the estimate smaller than the $\epsilon$ that you specify in your question.

I describe a situation where C = 1/4. But if You don't have a good idea as to what the value C is you can resort to the approach you describe where you take B=500 say and then double it to 1000 and compare the difference in those bootstrap estimates.This procedure can be repeated until the difference is as small as you want it to be.

Another idea is given by Efron in the article "Better bootstrap confidence intervals (with discussion)", (1987) Journal of the American Statistical Association Vol. 82 pp 171-200.

• Ah, by "two successive estimates" I thought you'd meant something like the estimate of $θ$ from replicate 1,002 versus the estimate of $θ$ from replicate 1,003. Comparing the estimate from all of the first 500 replicates to that of the second 500 or that of the first 1,000 is more intuitive. – Kodiologist May 6 '18 at 15:58
• I've seen Efron (1987) before, but which part addresses the question of choosing the number of bootstrap replicates? – Kodiologist May 6 '18 at 16:19
• In my book I mention that in Efron (1967) and Booth and Sarkar (1998) they point out that after a particular (large) number of iterations the error in the bootstrap estimate is dominated by the error due to the use of the empirical distribution (as an approximation to the population distribution) make the error in the Monte Carlo approximation small. I did not cite the particular page or pages where this is discussed. – Michael R. Chernick May 6 '18 at 17:20
• In the comment above I meant Efron(1987). – Michael R. Chernick May 16 '18 at 0:09