TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

m-out-of-n bootstrap and subsampling recover the uniform endpoint root

Statement

For each $n \geq 1$ , let $X_{1}, \dots, X_{n}$ be IID uniform on $[0, 1]$ , $M_{n} = \max_{i \leq n} X_{i}$ , and $R_{n} = n (M_{n} - 1)$ . Let $m = m_{n}$ be integers with $1 \leq m_{n} < n$ for all sufficiently large $n$ , $m_{n} \to \infty$ , and $m_{n} / n \to 0$ . Form the conditional m-out-of-n bootstrap and subsampling roots $R_{m, n}^{*} = m (M_{m, n}^{*} - M_{n}), R_{m, n}^{s u b} = m (M_{I} - M_{n}),$ where $M_{m, n}^{*}$ is the maximum of $m$ draws with replacement from $P_{n}$ , and $M_{I}$ is the maximum over a uniformly selected m-subset. For each method, its conditional CDF converges uniformly in probability to $F (x) = {\begin{cases} e^{x}, & x < 0, \\ 1, & x \geq 0. \end{cases}$ This is also the limiting CDF of the actual m-root $m (M_{m} - 1)$ . Here first-order validity means that the conditional CDF converges in probability to this actual-root limit; the theorem asserts no uniform validity over other distribution classes.

Facts & Assumptions

Given: The IID uniform sample, its empirical law $P_{n}$ , the maximum $M_{n}$ , and an integer sequence $m \to \infty$ with $m / n \to 0$ .

[F1]

m-out-of-n bootstrap and subsampling: The with-replacement root uses conditionally IID draws from $P_{n}$ and scale $a_{m}$ ; the without-replacement root uses a uniform m-subset and also scale $a_{m}$ .

[F2]

Identical distribution and IID families: The observations have a common law and are mutually independent.

[F3]

Cumulative distribution function of a real random variable: $F_{Y} (x) = P (Y \leq x)$ .

[F4]

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials: A binomial $(n, p)$ count is the sum of $n$ independent Bernoulli $(p)$ indicators.

[F5]

A Bernoulli $(p)$ variable has mean $p$ and variance $p (1 - p)$ ; a binomial $(n, p)$ variable has mean $n p$ and variance $n p (1 - p)$ : If $N \sim Binomial (n, p)$ , then $E [N] = n p$ and $Var (N) = n p (1 - p)$ .

[F6]

Chebyshev's inequality for random variables: For square-integrable $Y$ and $t > 0$ , $P (∣ Y - E Y ∣ \geq t) \leq Var (Y) / t^{2}$ .

[F7]

Pointwise CDF convergence to a continuous law is uniform: Pointwise convergence in probability of random CDFs to a continuous CDF implies uniform CDF convergence in probability.

[F10]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: For $x > 0$ , $\log^{'} (x) = 1 / x$ and $\log x = \int_{1}^{x} d t / t$ .

Proof

Given: The objects and hypotheses in the statement.

1.1givenF2F3F10algebra

For a size- $k$ IID uniform sample, $P {k (M_{k} - 1) \leq x} = 0$ for $x < - k$ , equals $(1 + x / k)^{k}$ for $- k \leq x < 0$ , and is $1$ for $x \geq 0$ . For fixed $x < 0$ , [F10] gives $k \log (1 + x / k) \to x$ , so these CDFs converge to $F (x) = e^{x}$ ; for $x \geq 0$ they equal $1$ . The limiting CDF is continuous, including at zero.

1.2givenF2F4F5F6F10algebra

Fix $x < 0$ and put $c = - x > 0$ , $D_{n} = 1 - M_{n}$ , and $K_{n} (c) = # {i : X_{i} > M_{n} - c / m}$ . For fixed $t > 0$ and all sufficiently large $m$ , each indicator $1 {X_{i} > 1 - t / m}$ is Bernoulli $(t / m)$ , and the indicators are independent by [F2]; hence $N_{n} (t) : = # {i : X_{i} > 1 - t / m}$ is binomial by [F4]. By [F5]–[F6], $m N_{n} (t) / n \to t$ in probability, since its mean is $t$ and its variance is $t (m / n) (1 - t / m) \to 0$ . Also $m D_{n} \to 0$ in probability, since for each $η > 0$ and large $m$ , $P (m D_{n} > η) = (1 - η / m)^{n}$ . By [F10], $\log (1 - u) = - \int_{1 - u}^{1} d t / t \leq - u$ for $0 < u < 1$ , so this probability is at most $e^{- η n / m} \to 0$ .

2.1step 1.2F1F10algebra

For any $0 < η < c$ , on $m D_{n} \leq η$ the interval from $1$ down to $M_{n} - c / m$ has width between $c / m$ and $(c + η) / m$ , so $N_{n} (c) \leq K_{n} (c) \leq N_{n} (c + η)$ . Fix $ρ > 0$ and choose $0 < η < \min (c, ρ / 3)$ . Step 1.2 gives $m N_{n} (c) / n \to c$ and $m N_{n} (c + η) / n \to c + η$ , while $P (m D_{n} > η) \to 0$ ; the sandwich therefore gives $m K_{n} (c) / n \to c$ and $K_{n} (c) / n \to 0$ in probability. For $u_{n} = K_{n} (c) / n$ , the integral identity in [F10] gives $∣ \log (1 - u_{n}) + u_{n} ∣ \leq u_{n}^{2} / (1 - u_{n})$ when $u_{n} < 1$ . Since $m u_{n} \to c$ and $u_{n} \to 0$ , $m u_{n}^{2} / (1 - u_{n}) \to 0$ , hence $(1 - u_{n})^{m} \to e^{- c}$ . By [F1], the conditional with-replacement CDF is $P^{*} (R_{m, n}^{*} \leq x) = (1 - K_{n} (c) / n)^{m} \to e^{- c} = e^{x}$ .

3.1givenF1step 2.1algebra

For subsampling, the conditional probability that every selected observation is at most $M_{n} - c / m$ is $P^{*} (R_{m, n}^{s u b} \leq x) = (\binom{n - K_{n} (c)}{m}) / (\binom{n}{m}) = \prod_{j = 0}^{m - 1} (1 - u_{n, j})$ , where $u_{n, j} = K_{n} (c) / (n - j)$ ; this formula holds on $n - K_{n} (c) \geq m$ , an event whose probability tends to one by step 2.1 and $m / n \to 0$ .

3.2givenstep 2.1algebra

We have $\max_{j < m} u_{n, j} \leq (K_{n} (c) / n) / (1 - m / n) \to 0$ in probability, and $\sum_{j = 0}^{m - 1} u_{n, j} = (m K_{n} (c) / n) \cdot m^{- 1} \sum_{j = 0}^{m - 1} n / (n - j) \to c$ , because the average factor lies between $1$ and $(1 - m / n)^{- 1} \to 1$ . Therefore $\sum_{j} u_{n, j}^{2} \leq (\max_{j} u_{n, j}) \sum_{j} u_{n, j} \to 0$ .

4.1F10step 3.1step 3.2algebra

With probability tending to one, all $u_{n, j} < 1$ ; [F10] and $∣ \log (1 - u) + u ∣ \leq u^{2} / (1 - u)$ then show $\sum_{j} \log (1 - u_{n, j}) \to - c$ , so the product in step 3.1 tends to $e^{- c} = e^{x}$ .

5.1F1F7step 1.1step 2.1step 3.1step 3.2step 4.1∎

For $x \geq 0$ , both resampled maxima are at most $M_{n}$ , so both conditional CDFs equal $1$ . Step 1.1 gives the continuous sampling-root limit $F$ , while steps 2.1 and 4.1 prove pointwise convergence for negative $x$ ; [F7] upgrades each method's conditional CDF convergence to uniform convergence in probability. Step 1.1 also identifies $F$ as the limiting CDF of the actual size- $m$ sampling root, which is the first-order target specified in the statement. The use of the actual size- $m$ scale is essential in steps 2.1–4.1.

The m-regime alone is insufficient. Take the singleton class $P = {P}$ with $P = δ_{0}$ , target $θ (P) = 0$ , statistic $T_{k} (z_{1}, \dots, z_{k}) = 1 / k$ , and normalization $a_{k} = k$ . Let $m_{n} = ⌊ \sqrt{n} ⌋$ . For all $n \geq 4$ , $1 \leq m_{n} < n$ , and $m_{n} \to \infty$ , $m_{n} / n \to 0$ , and $a_{m_{n}} / a_{n} = m_{n} / n \to 0$ . The actual size- $n$ and size- $m_{n}$ roots are both identically $1$ , so their CDFs $J_{n, P}$ and $H_{m_{n}, P}$ coincide exactly. For either resampling method, every resampled statistic is $1 / m_{n}$ , so ${\hat{H}}_{m, n}$ is the point-mass CDF at $1 - m_{n} / n$ . With $α_{1} = α_{2} = 1 / 4$ , both quantiles equal $1 - m_{n} / n$ and $I_{n} = {m_{n} / n^{2}}$ . Since $m_{n} / n^{2} > 0$ , the coverage of $θ (P) = 0$ is zero for every $n \geq 4$ . Thus uniform CDF approximation of the actual m-root by the feasible resampling root, and the associated quantile coverage guarantee, do not follow from the m-regime even when the actual n-root and m-root laws coincide.

Depends on

Used by

Uniform endpoint: ordinary bootstrap failure and the m-out-of-n remedy Example

Dependency tree · two levels

33 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

P. J. Bickel, F. Götze, and W. R. van Zwet, Resampling Fewer Than n Observations: Gains, Losses, and Remedies for Losses, §3 and Appendix, Example 3 (standard reference, not scraped)
J. P. Romano and A. M. Shaikh, On the Uniform Asymptotic Validity of Subsampling and the Bootstrap, §2.1, Theorems 2.1–2.2, Appendix A.1 (standard reference, not scraped)
Ryan Martin, Stat 451 Lecture Notes 0812: Bootstrap, pp. 28–30 (standard reference, not scraped)