29
$\begingroup$

Having recently studied bootstrap, I came up with a conceptual question that still puzzles me:

You have a population, and you want to know a population attribute, i.e. $\theta=g(P)$, where I use $P$ to represent population. This $\theta$ could be population mean for example. Usually you can't get all the data from the population. So you draw a sample $X$ of size $N$ from the population. Let's assume you have i.i.d. sample for simplicity. Then you obtain your estimator $\hat{\theta}=g(X)$. You want to use $\hat{\theta}$ to make inferences about $\theta$, so you would like to know the variability of $\hat{\theta}$.

First, there is a true sampling distribution of $\hat{\theta}$. Conceptually, you could draw many samples (each of them has size $N$) from the population. Each time you will have a realization of $\hat{\theta}=g(X)$ since each time you will have a different sample. Then in the end, you will be able to recover the true distribution of $\hat{\theta}$. Ok, this at least is the conceptual benchmark for estimation of the distribution of $\hat{\theta}$. Let me restate it: the ultimate goal is to use various method to estimate or approximate the true distribution of $\hat{\theta}$.

Now, here comes the question. Usually, you only have one sample $X$ that contains $N$ data points. Then you resample from this sample many times, and you will come up with a bootstrap distribution of $\hat{\theta}$. My question is: how close is this bootstrap distribution to the true sampling distribution of $\hat{\theta}$? Is there a way to quantify it?

$\endgroup$
  • 1
    $\begingroup$ This highly related question contains a wealth of additional information, to the point of making this question possibly a duplicate. $\endgroup$ – Xi'an Jan 13 '15 at 10:40
  • $\begingroup$ First, thank you all for answer my questions so promptly. This is the first time I use this website. I never expected my question will draw anyone's attention honestly. I have a small question here, what is 'OP'?@Silverfish $\endgroup$ – KevinKim Jan 13 '15 at 14:40
  • $\begingroup$ @Chen Jin: "OP" = original poster (i.e. you!). Apologies for the use of an abbreviation, which I accept is potentially confusing. $\endgroup$ – Silverfish Jan 13 '15 at 14:48
  • 1
    $\begingroup$ I have edited the title so that it more closely matches your statement that "My question is: how close is this to the true distribution of $\hat\theta$? Is there a way to quantify it?" Feel free to revert it if you do not think my edit reflects your intention. $\endgroup$ – Silverfish Jan 13 '15 at 15:04
  • $\begingroup$ @Silverfish Thank you so much. When I start this poster, I am not quite sure about my question actually. This new title is good. $\endgroup$ – KevinKim Jan 13 '15 at 15:46
20
$\begingroup$

In Information Theory the typical way to quantify how "close" one distribution to another is to use KL-divergence

Let's try to illustrate it with a highly skewed long-tail dataset - delays of plane arrivals in the Houston airport (from hflights package). Let $\hat \theta$ be the mean estimator. First, we find the sampling distribution of $\hat \theta$, and then the bootstrap distribution of $\hat \theta$

Here's the dataset:

enter image description here

The true mean is 7.09 min.

First, we do a certain number of samples to get the sampling distribution of $\hat \theta$, then we take one sample and take many bootstrap samples from it.

For example, let's take a look at two distributions with the sample size 100 and 5000 repetitions. We see visually that these distributions are quite apart, and the KL divergence is 0.48.

enter image description here

But when we increase the sample size to 1000, they start to converge (KL divergence is 0.11)

enter image description here

And when the sample size is 5000, they are very close (KL divergence is 0.01)

enter image description here

This, of course, depends on which bootstrap sample you get, but I believe you can see that the KL divergence goes down as we increase the sample size, and thus bootstrap distribution of $\hat \theta$ approaches sample distribution $\hat \theta$ in terms of KL Divergence. To be sure, you can try to do several bootstraps and take the average of the KL divergence.

Here's the R code of this experiment: https://gist.github.com/alexeygrigorev/0b97794aea78eee9d794

$\endgroup$
  • 5
    $\begingroup$ +1 and this also shows that for any given sample size (like e.g. 100), bootstap bias can be large and unavoidable. $\endgroup$ – amoeba Jan 13 '15 at 14:40
  • $\begingroup$ This one is awesome! So in order to let the distribution of $\hat{\theta}$ from the bootstrap be close to the TRUE distribution of $\hat{\theta}$, we need large sample size $N$ right? For any fixed sample size, distribution generated from the bootstrap can be very different from the TRUE distribution as mentioned by @amoeba. $\endgroup$ – KevinKim Jan 13 '15 at 14:52
  • $\begingroup$ My next question is: If I fixed $N$ large enough, then I did 2 bootstraps, one just resample $B=10$ times, and the other resample $B=10000$. What's the difference between the distribution of $\hat{\theta}$ coming out of these 2 bootstraps? This question is essentially asking when we fix $N$, what's the role played by $B$ in generating distribution of $\hat{\theta}$. @Grigorev $\endgroup$ – KevinKim Jan 13 '15 at 14:52
  • 1
    $\begingroup$ @Chen, but the distribution of $\hat \theta$ is something that you obtain by doing resamples, right? So the difference between $B=10$ and $B=10000$ is that in one case you get $10$ numbers to build your distribution (not much information $\Rightarrow$ not very reliable estimate of its standard deviation), and in other case you get $10000$ numbers (much more reliable). $\endgroup$ – amoeba Jan 13 '15 at 14:54
  • 1
    $\begingroup$ @Chen, I think you are either a bit confused or not being very clear about what $F_5$ in your comment is supposed to be. If you resample $5$ times, you get a set of $5$ numbers. How is that a distribution? It is a set of numbers! These numbers come from what you called $F_B$ distribution. The more numbers you get, the better you can estimate $F_B$. $\endgroup$ – amoeba Jan 13 '15 at 15:07
23
$\begingroup$

Bootstrap is based on the convergence of the empirical cdf to the true cdf, that is, $$\hat{F}_n(x) = \frac{1}{n}\sum_{i=1}^n\mathbb{I}_{X_i\le x}\qquad X_i\stackrel{\text{iid}}{\sim}F(x)$$ converges (as $n$ goes to infinity) to $F(x)$ for every $x$. Hence convergence of the bootstrap distribution of $\hat{\theta}(X_1,\ldots,X_n)=g(\hat{F}_n)$ is driven by this convergence which occurs at a rate $\sqrt{n}$ for each $x$, since $$\sqrt{n}\{\hat{F}_n(x)-F(x)\}\stackrel{\text{dist}}{\longrightarrow}\mathsf{N}(0,F(x)[1-F(x)])$$ even though this rate and limiting distribution does not automatically transfer to $g(\hat{F}_n)$. In practice, to assess the variability of the approximation, you can produce a bootstrap evaluation of the distribution of $g(\hat{F}_n)$ by double-bootstrap, i.e., by bootstrapping bootstrap evaluations.

As an update, here is an illustration I use in class: enter image description here where the lhs compares the true cdf $F$ with the empirical cdf $\hat{F}_n$ for $n=100$ observations and the rhs plots $250$ replicas of the lhs, for 250 different samples, in order to measure the variability of the cdf approximation. In the example I know the truth and hence I can simulate from the truth to evaluate the variability. In a realistic situation, I do not know $F$ and hence I have to start from $\hat{F}_n$ instead to produce a similar graph.

Further update: Here is what the tube picture looks like when starting from the empirical cdf: enter image description here

$\endgroup$
  • 5
    $\begingroup$ The crux of this answer is that the bootstrap works because it is a large-sample approximation. I don't think this point is emphasized enough $\endgroup$ – shadowtalker Jan 13 '15 at 14:52
  • 2
    $\begingroup$ I mean, "emphasized often enough in general" $\endgroup$ – shadowtalker Jan 13 '15 at 15:52
  • $\begingroup$ @Xi'an Thanks a lot. I like the last 2 panels, so in this example, let's pretend we don't know the true cdf, i.e. the red curve on the lhs, I just have the empirical cdf $\hat{F}$ from one sample of $n=100$. Then I do resampling from this sample. Then I produce a similar graph as the rhs. Will this new graph has a wider tube than the current tube on your current rhs figure? And will the new tube still centered around the true cdf, i.e. the red curve as the tube on you current rhs figure? $\endgroup$ – KevinKim Jan 13 '15 at 15:52
  • 3
    $\begingroup$ The tube produced by creating empirical cdfs based on samples created from one empirical cdf is eventually less wide than the one produced from the true $F$ as we are always using the same $n$ datapoints. And the new tube is centred around the empirical cdf, not the true $F$. There is thus bias in scale and location for that tube. $\endgroup$ – Xi'an Jan 13 '15 at 16:01
  • $\begingroup$ @Xi'an Very nice! it would be even nicer if the 2nd and 3rd figure can be combined together in one figure $\endgroup$ – KevinKim Jan 13 '15 at 16:10

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.