I appreciate the usefulness of the bootstrap in obtaining uncertainty estimates, but one thing that's always bothered me about it is that the distribution corresponding to those estimates is the distribution defined by the sample. In general, it seems like a bad idea to believe that our sample frequencies look exactly like the underlying distribution, so why is it sound/acceptable to derive uncertainty estimates based on a distribution where the sample frequencies define the underlying distribution?

On the other hand, this may be no worse (possibly better) than other distributional assumptions we typically make, but I'd still like to understand the justification a bit better.

There are several ways that one can conceivably apply the bootstrap. The two most basic approaches are what are deemed the "nonparametric" and "parametric" bootstrap. The second one assumes that the model you're using is (essentially) correct.

Let's focus on the first one. We'll assume that you have a random sample $X_1, X_2, \ldots, X_n$ distributed according the the distribution function $F$. (Assuming otherwise requires modified approaches.) Let $\hat{F}_n(x) = n^{-1} \sum_{i=1}^n \mathbf{1}(X_i \leq x)$ be the empirical cumulative distribution function. Much of the motivation for the bootstrap comes from a couple of facts.

Dvoretzky–Kiefer–Wolfowitz inequality

$$
\renewcommand{\Pr}{\mathbb{P}}
\Pr\big( \textstyle\sup_{x \in \mathbb{R}} \,|\hat{F}_n(x) - F(x)| > \varepsilon \big) \leq 2 e^{-2n \varepsilon^2} \> .
$$

What this shows is that the empirical distribution function converges uniformly to the true distribution function exponentially fast in probability. Indeed, this inequality coupled with the Borel–Cantelli lemma shows immediately that $\sup_{x \in \mathbb{R}} \,|\hat{F}_n(x) - F(x)| \to 0$ almost surely.

There are no additional conditions on the form of $F$ in order to guarantee this convergence.

Heuristically, then, if we are interested in some functional $T(F)$ of the distribution function that is smooth, then we expect $T(\hat{F}_n)$ to be close to $T(F)$.

(Pointwise) Unbiasedness of $\hat{F}_n(x)$

By simple linearity of expectation and the definition of $\hat{F}_n(x)$, for each $x \in \mathbb{R}$,

$$
\newcommand{\e}{\mathbb{E}}
\e_F \hat{F}_n(x) = F(x) \>.
$$

Suppose we are interested in the mean $\mu = T(F)$. Then the unbiasedness of the empirical measure extends to the unbiasedness of linear functionals of the empirical measure. So,
$$
\e_F T(\hat{F}_n) = \e_F \bar{X}_n = \mu = T(F) \> .
$$

So $T(\hat{F}_n)$ is correct on average and since $\hat{F_n}$ is rapidly approaching $F$, then (heuristically), $T(\hat{F}_n)$ rapidly approaches $T(F)$.

To construct a confidence interval (which is, essentially, what the bootstrap is all about), we can use the central limit theorem, the consistency of empirical quantiles and the delta method as tools to move from simple linear functionals to more complicated statistics of interest.

Good references are


B. Efron, Bootstrap methods: Another look at the jackknife, Ann. Stat., vol. 7, no. 1, 1–26.
B. Efron and R. Tibshirani, An Introduction to the Bootstrap, Chapman–Hall, 1994.
G. A. Young and R. L. Smith, Essentials of Statistical Inference, Cambridge University Press, 2005, Chapter 11.
A. W. van der Vaart, Asymptotic Statistics, Cambridge University Press, 1998, Chapter 23.
P. Bickel and D. Freedman, Some asymptotic theory for the bootstrap. Ann. Stat., vol. 9, no. 6 (1981), 1196–1217.

