Bootstrapping (statistics)
In statistics, bootstrapping can refer to any test or metric that relies on random sampling with replacement. Bootstrapping allows assigning measures of accuracy (defined in terms of bias, variance, confidence intervals, prediction error or some other such measure) to sample estimates.^{[1]}^{[2]} This technique allows estimation of the sampling distribution of almost any statistic using very simple methods.^{[3]}^{[4]} Generally, it falls in the broader class of resampling methods.
Bootstrapping is the practice of estimating properties of an estimator (such as its variance) by measuring those properties when sampling from an approximating distribution. One standard choice for an approximating distribution is the empirical distribution of the observed data. In the case where a set of observations can be assumed to be from an independent and identically distributed population, this can be implemented by constructing a number of resamples with replacement, of the observed dataset (and of equal size to the observed dataset).
It may also be used for constructing hypothesis tests. It is often used as an alternative to inference based on parametric assumptions when those assumptions are in doubt, or where parametric inference is impossible or requires very complicated formulas for the calculation of standard errors.
Contents
 History 1
 Approach 2
 Situations where bootstrapping is useful 3

Discussion 4
 Advantages 4.1
 Disadvantages 4.2
 Recommendations 4.3

Types of bootstrap scheme 5

Case resampling 5.1
 Estimating the distribution of sample mean 5.1.1
 Regression 5.1.2
 Bayesian bootstrap 5.2
 Smooth bootstrap 5.3
 Parametric bootstrap 5.4
 Resampling residuals 5.5
 Gaussian process regression bootstrap 5.6
 Wild bootstrap 5.7

Block bootstrap 5.8
 Time series: Simple block bootstrap 5.8.1
 Time series: Moving block bootstrap 5.8.2
 Cluster data: block bootstrap 5.8.3

Case resampling 5.1
 Choice of statistic 6

Deriving confidence intervals from the bootstrap distribution 7
 Bias, asymmetry, and confidence intervals 7.1
 Methods for bootstrap confidence intervals 7.2

Example applications 8
 Smoothed bootstrap 8.1

Relation to other approaches to inference 9
 Relationship to other resampling methods 9.1
 Ustatistics 9.2
 See also 10
 References 11
 Further reading 12

External links 13
 Software 13.1
History
The bootstrap was published by Bradley Efron in "Bootstrap methods: another look at the jackknife" (1979).^{[5]}^{[6]}^{[7]} It was inspired by earlier work on the jackknife.^{[8]}^{[9]}^{[10]} Improved estimates of the variance were developed later.^{[11]}^{[12]} A Bayesian extension was developed in 1981.^{[13]} The biascorrected and accelerated (BCa) bootstrap was developed by Efron in 1987,^{[14]} and the ABC procedure in 1992.^{[15]}
Approach
The basic idea of bootstrapping is that inference about a population from sample data (sample → population) can be modeled by resampling the sample data and performing inference on (resample → sample). As the population is unknown, the true error in a sample statistic against its population value is unknowable. In bootstrapresamples, the 'population' is in fact the sample, and this is known; hence the quality of inference from resample data → 'true' sample is measurable.
More formally, the bootstrap works by treating inference of the true probability distribution J, given the original data, as being analogous to inference of the empirical distribution of Ĵ, given the resampled data. The accuracy of inferences regarding Ĵ using the resampled data can be assessed because we know Ĵ. If Ĵ is a reasonable approximation to J, then the quality of inference on J can in turn be inferred.
As an example, assume we are interested in the average (or mean) height of people worldwide. We cannot measure all the people in the global population, so instead we sample only a tiny part of it, and measure that. Assume the sample is of size N; that is, we measure the heights of N individuals. From that single sample, only one estimate of the mean can be obtained. In order to reason about the population, we need some sense of the variability of the mean that we have computed.
The simplest bootstrap method involves taking the original data set of N heights, and, using a computer, sampling from it to form a new sample (called a 'resample' or bootstrap sample) that is also of size N. The bootstrap sample is taken from the original using sampling with replacement so, assuming N is sufficiently large, for all practical purposes there is virtually zero probability that it will be identical to the original "real" sample. This process is repeated a large number of times (typically 1,000 or 10,000 times), and for each of these bootstrap samples we compute its mean (each of these are called bootstrap estimates). We now have a histogram of bootstrap means. This provides an estimate of the shape of the distribution of the mean from which we can answer questions about how much the mean varies. (The method here, described for the mean, can be applied to almost any other statistic or estimator.)
Situations where bootstrapping is useful
Adèr et al.^{[16]} recommend the bootstrap procedure for the following situations:

 When the theoretical distribution of a statistic of interest is complicated or unknown. Since the bootstrapping procedure is distributionindependent it provides an indirect method to assess the properties of the distribution underlying the sample and the parameters of interest that are derived from this distribution.

 When the sample size is insufficient for straightforward statistical inference. If the underlying distribution is wellknown, bootstrapping provides a way to account for the distortions caused by the specific sample that may not be fully representative of the population.

 When power calculations have to be performed, and a small pilot sample is available. Most power and sample size calculations are heavily dependent on the standard deviation of the statistic of interest. If the estimate used is incorrect, the required sample size will also be wrong. One method to get an impression of the variation of the statistic is to use a small pilot sample and perform bootstrapping on it to get impression of the variance.
Discussion
Advantages
A great advantage of bootstrap is its simplicity. It is a straightforward way to derive estimates of standard errors and confidence intervals for complex estimators of complex parameters of the distribution, such as percentile points, proportions, odds ratio, and correlation coefficients. Bootstrap is also an appropriate way to control and check the stability of the results. Although for most problems it is impossible to know the true confidence interval, bootstrap is asymptotically more accurate than the standard intervals obtained using sample variance and assumptions of normality.^{[17]}
Disadvantages
Although bootstrapping is (under some conditions) asymptotically consistent, it does not provide general finitesample guarantees. The apparent simplicity may conceal the fact that important assumptions are being made when undertaking the bootstrap analysis (e.g. independence of samples) where these would be more formally stated in other approaches.
Recommendations
The number of bootstrap samples recommended in literature has increased as available computing power has increased. If the results really matter, as many samples as is reasonable, given available computing power and time, should be used. Increasing the number of samples cannot increase the amount of information in the original data, it can only reduce the effects of random sampling errors which can arise from a bootstrap procedure itself.
Types of bootstrap scheme
In univariate problems, it is usually acceptable to resample the individual observations with replacement ("case resampling" below). In small samples, a parametric bootstrap approach might be preferred. For other problems, a smooth bootstrap will likely be preferred.
For regression problems, various other alternatives are available.^{[18]}
Case resampling
Bootstrap is generally useful for estimating the distribution of a statistic (e.g. mean, variance) without using normal theory (e.g. zstatistic, tstatistic). Bootstrap comes in handy when there is no analytical form or normal theory to help estimate the distribution of the statistics of interest, since bootstrap method can apply to most random quantities, e.g., the ratio of variance and mean. There are at least two ways of performing case resampling.
 The Monte Carlo algorithm for case resampling is quite simple. First, we resample the data with replacement, and the size of the resample must be equal to the size of the original data set. Then the statistic of interest is computed from the resample from the first step. We repeat this routine many times to get a more precise estimate of the Bootstrap distribution of the statistic.
 The 'exact' version for case resampling is similar, but we exhaustively enumerate every possible resample of the data set. This can be computationally expensive as there are a total of \binom {2n1}n different resamples, where n is the size of the data set.
Estimating the distribution of sample mean
Consider a coinflipping experiment. We flip the coin and record whether it lands heads or tails. (Assume for simplicity that there are only two outcomes) Let X = x_{1}, x_{2}, …, x_{10} be 10 observations from the experiment. x_{i} = 1 if the i th flip lands heads, and 0 otherwise. From normal theory, we can use tstatistic to estimate the distribution of the sample mean, \bar{x} = \frac{1}{10} (x_1 + x_2 + \ldots + x_{10}).
Instead, we use bootstrap, specifically case resampling, to derive the distribution of \bar{x}. We first resample the data to obtain a bootstrap resample. An example of the first resample might look like this X_{1}* = x_{2}, x_{1}, x_{10}, x_{10}, x_{3}, x_{4}, x_{6}, x_{7}, x_{1}, x_{9}. Note that there are some duplicates since a bootstrap resample comes from sampling with replacement from the data. Note also that the number of data points in a bootstrap resample is equal to the number of data points in our original observations. Then we compute the mean of this resample and obtain the first bootstrap mean: μ_{1}*. We repeat this process to obtain the second resample X_{2}* and compute the second bootstrap mean μ_{2}*. If we repeat this 100 times, then we have μ_{1}*, μ_{2}*, …, μ_{100}*. This represents an empirical bootstrap distribution of sample mean. From this empirical distribution, one can derive a bootstrap confidence interval for the purpose of hypothesis testing.
Regression
In regression problems, case resampling refers to the simple scheme of resampling individual cases  often rows of a data set. For regression problems, so long as the data set is fairly large, this simple scheme is often acceptable. However, the method is open to criticism.
In regression problems, the explanatory variables are often fixed, or at least observed with more control than the response variable. Also, the range of the explanatory variables defines the information available from them. Therefore, to resample cases means that each bootstrap sample will lose some information. As such, alternative bootstrap procedures should be considered.
Bayesian bootstrap
Bootstrapping can be interpreted in a Bayesian framework using a scheme that creates new datasets through reweighting the initial data. Given a set of N data points, the weighting assigned to data point i in a new dataset \mathcal{D}^J is w^J_i = x^J_i  x^J_{i1}, where \mathbf{x}^J is a lowtohigh ordered list of N1 uniformly distributed random numbers on [0,1], preceded by 0 and succeeded by 1. The distributions of a parameter inferred from considering many such datasets \mathcal{D}^J are then interpretable as posterior distributions on that parameter.^{[19]}
Smooth bootstrap
Under this scheme, a small amount of (usually normally distributed) zerocentered random noise is added onto each resampled observation. This is equivalent to sampling from a kernel density estimate of the data.
Parametric bootstrap
In this case a parametric model is fitted to the data, often by maximum likelihood, and samples of random numbers are drawn from this fitted model. Usually the sample drawn has the same sample size as the original data. Then the quantity, or estimate, of interest is calculated from these data. This sampling process is repeated many times as for other bootstrap methods. The use of a parametric model at the sampling stage of the bootstrap methodology leads to procedures which are different from those obtained by applying basic statistical theory to inference for the same model.
Resampling residuals
Another approach to bootstrapping in regression problems is to resample residuals. The method proceeds as follows.
 Fit the model and retain the fitted values \hat y_i and the residuals \hat{\epsilon}_i = y_i  \hat{y}_i, (i = 1,\dots, n).
 For each pair, (x_{i}, y_{i}), in which x_{i} is the (possibly multivariate) explanatory variable, add a randomly resampled residual, \hat{\epsilon}_j, to the response variable y_{i}. In other words create synthetic response variables y^*_i = \hat{y}_i + \hat{\epsilon}_j where j is selected randomly from the list (1, …, n) for every i.
 Refit the model using the fictitious response variables y^*_i, and retain the quantities of interest (often the parameters, \hat\mu^*_i, estimated from the synthetic y^*_i).
 Repeat steps 2 and 3 a statistically significant number of times.
This scheme has the advantage that it retains the information in the explanatory variables. However, a question arises as to which residuals to resample. Raw residuals are one option; another is studentized residuals (in linear regression). Whilst there are arguments in favour of using studentized residuals; in practice, it often makes little difference and it is easy to run both schemes and compare the results against each other.
Gaussian process regression bootstrap
When data are temporally correlated, straightforward bootstrapping destroys the inherent correlations. This method uses Gaussian process regression to fit a probabilistic model from which replicates may then be drawn. Gaussian processes are methods from Bayesian nonparametric statistics but are here used to construct a parametric bootstrap approach, which implicitly allows the timedependence of the data to be taken into account.
Wild bootstrap
The Wild bootstrap, proposed originally by Wu (1986),^{[20]} is suited when the model exhibits heteroskedasticity. The idea is, like the residual bootstrap, to leave the regressors at their sample value, but to resample the response variable based on the residuals values. That is, for each replicate, one computes a new y based on:
 y^*_i = \hat{y}_i + \hat{\epsilon}_i v_i
so the residuals are randomly multiplied by a random variable v_i with mean 0 and variance 1. This method assumes that the 'true' residual distribution is symmetric and can offer advantages over simple residual sampling for smaller sample sizes. Different forms are used for the random variable v_i, such as:

 A distribution suggested by Mammen (1993).^{[21]}

 v_i = \left\{\begin{matrix} (\sqrt{5} 1)/2 & \mbox {with prob. } (\sqrt{5} +1)/(2\sqrt{5}) \\ (\sqrt{5} +1)/2 & \mbox {with prob. } (\sqrt{5} 1)/(2\sqrt{5}) \end{matrix}\right.

 Or the simpler distribution, linked to the Rademacher distribution:

 v_i = \left\{\begin{matrix} 1 & \mbox {with prob. } 1/2 \\ 1 & \mbox {with prob. } 1/2 \end{matrix}\right.
Block bootstrap
The block bootstrap is used when the data, or the errors in a model, are correlated. In this case, a simple case or residual resampling will fail, as it is not able to replicate the correlation in the data. The block bootstrap tries to replicate the correlation by resampling instead blocks of data. The block bootstrap has been used mainly with data correlated in time (i.e. time series) but can also be used with data correlated in space, or among groups (socalled cluster data).
Time series: Simple block bootstrap
In the (simple) block bootstrap, the variable of interest is split into nonoverlapping blocks.
Time series: Moving block bootstrap
In the moving block bootstrap, introduced by Künsch (1989),^{[22]} data is split into nb+1 overlapping blocks of length b: Observation 1 to b will be block 1, observation 2 to b+1 will be block 2 etc. Then from these nb+1 blocks, n/b blocks will be drawn at random with replacement. Then aligning these n/b blocks in the order they were picked, will give the bootstrap observations.
This bootstrap works with dependent data, however, the bootstrapped observations will not be stationary anymore by construction. But, it was shown that varying randomly the block length can avoid this problem.^{[23]}
Cluster data: block bootstrap
Cluster data describes data where many observations per unit are observed. This could be observing many firms in many states, or observing students in many classes. In such cases, the correlation structure is simplified, and one does usually make the assumption that data is correlated with a group/cluster, but independent between groups/clusters. The structure of the block bootstrap is easily obtained (where the block just corresponds to the group), and usually only the groups are resampled, while the observations within the groups are left unchanged. Cameron et al. (2008) ^{[24]} discusses this for clustered errors in linear regression.
Choice of statistic
The bootstrap distribution of a point estimator of a population parameter has been used to produce a bootstrapped confidence interval for the parameter's true value, if the parameter can be written as a function of the population's distribution.
Population parameters are estimated with many point estimators. Popular families of pointestimators include meanunbiased minimumvariance estimators, medianunbiased estimators, Bayesian estimators (for example, the posterior distribution's mode, median, mean), and maximumlikelihood estimators.
A Bayesian point estimator and a maximumlikelihood estimator have good performance when the sample size is infinite, according to asymptotic theory. For practical problems with finite samples, other estimators may be preferable. Asymptotic theory suggests techniques that often improve the performance of bootstrapped estimators; the bootstrapping of a maximumlikelihood estimator may often be improved using transformations related to pivotal quantities.^{[25]}
Deriving confidence intervals from the bootstrap distribution
The bootstrap distribution of a parameterestimator has been used to calculate confidence intervals for its populationparameter.
Bias, asymmetry, and confidence intervals

Bias: The bootstrap distribution and the sample may disagree systematically, in which case bias may occur.
 If the bootstrap distribution of an estimator is symmetric, then percentile confidenceinterval are often used; such intervals are appropriate especially for medianunbiased estimators of minimum risk (with respect to an absolute loss function). Bias in the bootstrap distribution will lead to bias in the confidenceinterval.
 Otherwise, if the bootstrap distribution is nonsymmetric, then percentile confidenceintervals are often inappropriate.
Methods for bootstrap confidence intervals
There are several methods for constructing confidence intervals from the bootstrap distribution of a real parameter:
 Basic Bootstrap. The basic bootstrap is the simplest scheme to construct the confidence interval: one simply takes the empirical quantiles from the bootstrap distribution of the parameter (see Davison and Hinkley 1997, equ. 5.6 p. 194):
 (2\theta \theta^{*}_{(1\alpha/2)};2\theta \theta^{*}_{(\alpha/2)}) where \theta^{*}_{(1\alpha/2)} denotes the 1\alpha/2 percentile of the bootstrapped coefficients \theta^{*} .
 Percentile Bootstrap. The percentile bootstrap proceeds in a similar way to the basic bootstrap, using percentiles of the bootstrap distribution, but with a different formula (note the inversion of the left and right quantiles!):
 (\theta^{*}_{(\alpha/2)};\theta^{*}_{(1\alpha/2)}) where \theta^{*}_{(1\alpha/2)} denotes the 1\alpha/2 percentile of the bootstrapped coefficients \theta^{*} .
See Davison and Hinkley (1997, equ. 5.18 p. 203) and Efron and Tibshirani (1993, equ 13.5 p. 171). This method can be applied to any statistic. It will work well in cases where the bootstrap distribution is symmetrical and centered on the observed statistic^{[26]} and where the sample statistic is medianunbiased and has maximum concentration (or minimum risk with respect to an absolute value loss function). In other cases, the percentile bootstrap can be too narrow. When working with small sample sizes (i.e., less than 50), the percentile confidence intervals for (for example) the variance statistic will be too narrow. So that with a sample of 20 points, 90% confidence interval will include the true variance only 78% of the time^{[27]}
 Studentized Bootstrap. The studentized bootstrap, also called bootstrapt, works similarly as the usual confidence interval, but replaces the quantiles from the normal or student approximation by the quantiles from the bootstrap distribution of the Student's ttest (see Davison and Hinkley 1997, equ. 5.7 p. 194 and Efron and Tibshirani 1993 equ 12.22, p. 160):
 (\theta  t^{*}_{(1\alpha/2)}\cdot \hat{se}_{\theta};\thetat^{*}_{(\alpha/2)}\cdot \hat{se}_{\theta}) where t^{*}_{(1\alpha/2)} denotes the 1\alpha/2 percentile of the bootstrapped Student's ttest t^{*}=(\hat{\theta}^{*}\hat{\theta})/\hat{se}_{\hat{\theta}^*} , while \hat{se}_{\theta} is the estimated standard error of the coefficient in the original model.
The studentized test enjoys optimal properties as the statistic that is bootstrapped is pivotal (i.e. it does not depend on nuisance parameters as the ttest follows asymptotically a N(0,1) distribution), unlike the percentile bootstrap.
 BiasCorrected Bootstrap  adjusts for bias in the bootstrap distribution.
 Accelerated Bootstrap  The biascorrected and accelerated (BCa) bootstrap, by Efron (1987),^{[14]} adjusts for both bias and skewness in the bootstrap distribution. This approach is accurate in a wide variety of settings, has reasonable computation requirements, and produces reasonably narrow intervals.
Example applications
Smoothed bootstrap
In 1878, Simon Newcomb took observations on the speed of light.^{[28]} The data set contains two outliers, which greatly influence the sample mean. (Note that the sample mean need not be a consistent estimator for any population mean, because no mean need exist for a heavytailed distribution.) A welldefined and robust statistic for central tendency is the sample median, which is consistent and medianunbiased for the population median.
The bootstrap distribution for Newcomb's data appears below. A convolutionmethod of regularization reduces the discreteness of the bootstrap distribution, by adding a small amount of N(0, σ^{2}) random noise to each bootstrap sample. A conventional choice is \sigma = 1/\sqrt n for sample size n.
Histograms of the bootstrap distribution and the smooth bootstrap distribution appear below . The bootstrap distribution of the samplemedian has only a small number of values. The smoothed bootstrap distribution has a richer support.In this example, the bootstrapped 95% (percentile) confidenceinterval for the population median is (26, 28.5), which is close to the interval for (25.98, 28.46) for the smoothed bootstrap.
Relation to other approaches to inference
Relationship to other resampling methods
The bootstrap is distinguished from :
 the jackknife procedure, used to estimate biases of sample statistics and to estimate variances, and
 crossvalidation, in which the parameters (e.g., regression weights, factor loadings) that are estimated in one subsample are applied to another subsample.
For more details see bootstrap resampling.
Bootstrap aggregating (bagging) is a metaalgorithm based on averaging the results of multiple bootstrap samples.
Ustatistics
In situations where an obvious statistic can be devised to measure a required characteristic using only a small number, r, of data items, a corresponding statistic based on the entire sample can be formulated. Given an rsample statistic, one can create an nsample statistic by something similar to bootstrapping (taking the average of the statistic over all subsamples of size r). This procedure is known to have certain good properties and the result is a Ustatistic. The sample mean and sample variance are of this form, for r=1 and r=2.
See also
 Accuracy and precision
 Bootstrap aggregating
 Empirical likelihood
 Imputation (statistics)
 Reliability (statistics)
 Reproducibility
 Engelbart's Law
References
 ^ software
 ^ Second Thoughts on the Bootstrap  Bradley Efron, 2003
 ^ Varian, H.(2005). "Bootstrap Tutorial". Mathematica Journal, 9, 768775.
 ^ Weisstein, Eric W. "Bootstrap Methods." From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/BootstrapMethods.html
 ^ Notes for Earliest Known Uses of Some of the Words of Mathematics: Bootstrap (John Aldrich)
 ^ Earliest Known Uses of Some of the Words of Mathematics (B) (Jeff Miller)
 ^
 ^ Quenouille M (1949) Approximate tests of correlation in timeseries. J Roy Statist Soc Ser B 11 68–84
 ^ Tukey J (1958) Bias and confidence in notquite large samples (abstract). Ann Math Statist 29 614
 ^ Jaeckel L (1972) The infinitesimal jackknife. Memorandum MM72121511, Bell Lab
 ^ Bickel P, Freeman D (1981) Some asymptotic theory for the bootstrap. Ann Statist 9 1196–1217
 ^ Singh K (1981) On the asymptotic accuracy of Efron’s bootstrap. Ann Statist 9 1187–1195
 ^ Rubin D (1981). The Bayesian bootstrap. Ann Statist 9 130–134
 ^ ^{a} ^{b}
 ^ Diciccio T, Efron B (1992) More accurate confidence intervals in exponential families. Biometrika 79 231–245
 ^ Adèr, H. J., Mellenbergh G. J., & Hand, D. J. (2008). Advising on research methods: A consultant's companion. Huizen, The Netherlands: Johannes van Kessel Publishing. ISBN 9789079418015
 ^ DiCiccio TJ, Efron B (1996) Bootstrap confidence intervals (with Discussion). Statistical Science 11: 189228
 ^ Efron B., R. J. Tibshirani, An introduction to the bootstrap, Chapman & Hall/CRC 1998
 ^ Rubin, D. B. (1981). "The Bayesian bootstrap". Annals of Statistics, 9, 130.
 ^ Wu, C.F.J. (1986). "Jackknife, bootstrap and other resampling methods in regression analysis (with discussions)". Annals of Statistics 14: 1261–1350.
 ^ Mammen, E. (Mar 1993). "Bootstrap and wild bootstrap for high dimensional linear models". Annals of Statistics 21 (1): 255–285.
 ^ Künsch, H. R. (1989). “The jackknife and the bootstrap for general stationary observations,” Annals of Statistics, 17, 1217–1241.
 ^ Politis, D.N. and Romano, J.P. (1994). The stationary bootstrap. Journal of American Statistical Association, 89, 13031313.
 ^ Cameron, A. C., J. B. Gelbach, and D. L. Miller (2008): “Bootstrapbased im provements for inference with clustered errors,” Review of Economics and Statistics, 90, 414–427
 ^
 ^
 ^
 ^ Bayesian Data AnalysisData from examples in
Further reading
External links
 Bootstrap sampling tutorial using MS Excel
 Bootstrap example to simulate stock prices using MS Excel
 bootstrapping tutorial
 package animation
Software
 Statistics101: Resampling, Bootstrap, Monte Carlo Simulation program. Free program written in Java to run on any operating system.

 Articles lacking intext citations from June 2012
 All articles lacking intext citations
 All articles with unsourced statements
 Articles with unsourced statements from April 2009
 Articles with unsourced statements from June 2012
 Articles with unsourced statements from January 2010
 Articles with unsourced statements from March 2012
 Accuracy disputes from April 2012
 All accuracy disputes
 Computational statistics
 Data analysis
 Statistical inference
 Resampling (statistics)