m-out-of-n Bootstrap | Codeboy's Blog

原始资料有n条，每次重抽不一定也要取n条。少取一些有时能消除普通重抽的结构性偏差，但重抽误差变大了，最后必须换回原任务的尺度。本页用一个能完整证明的端点问题说明这两件事怎样配合。

形式陈述

输入、重抽与目标尺度

沿用Bootstrap的条件重采样接口。观察IID资料D_n=(X_1,…,X_n)，统计量T_n估计θ。给定整数1≤m≤n，从经验分布独立有放回抽取m条，按同一统计规则计算T_m^。星号概率P^(·)=P(·|D_n)只平均这次抽索引的随机性。

若原目标根为a_n(T_n−θ)，一种候选近似是T_m^*在m条资料尺度上的根

R_{m,n}^*=a_m(T_m^*-T_n). \tag{1}

a_m和a_n通常不同。由式(1)取得的分位数若用于原参数区间，最后应除以a_n；不能直接把T_m^*的散布当成T_n的散布。中心和学生化也必须明确，式(1)并非任何统计量都有效的通用定理。

一份完整的有效性定理

设X_i独立服从Uniform(0,θ)，θ>0，令M_n=max_i X_i，M_m^*为m条重抽的最大值。取确定性整数序列m=m_n，满足

m\longrightarrow\infty,\qquad m/n\longrightarrow0. \tag{2}

定义两个无量纲根

U_n=\frac{n(\theta-M_n)}{\theta},\qquad U_{m,n}^*=\frac{m(M_n-M_m^*)}{M_n}. \tag{3}

M_n>0几乎必然。记J(t)=0（t<0）、J(t)=1−e^(−t)（t≥0）。则

U_n\Rightarrow\operatorname{Exp}(1),\qquad \sup_{t\in\mathbb R}|P^*(U_{m,n}^*\le t)-J(t)| \longrightarrow_P0. \tag{4}

第二个结论中的概率收敛针对原资料D_n；不是说固定小样本的重抽CDF已经等于指数CDF。这个定理限定了总体、统计量、归一化和m的选择，不能由m/n小就推到任意分布或任意统计量。

直觉

普通n条重抽很容易再次抽中本次最大值，因此最大值根在零点留下不消失的质量。改成m条后，抽中该点的概率是1−(1−1/n)^m，式(2)使它趋零。

但只去掉原子还不够。如果m一直等于2，重抽根描述的仍是两条观测的极值分布，不能逼近一个大样本极限。m→∞让重抽统计量进入其极限区间，m/n→0让经验分布的端点离散性在该尺度上消失。这两个条件各自承担不同责任。

先计算真实目标

对于0≤t≤n，所有n条观测都低于θ(1−t/n)的概率为

P(U_n>t)=\left(1-\frac tn\right)^n\longrightarrow e^{-t}. \tag{5}

t<0时U_n非负；每个固定非负t最终落在[0,n]内。因此得到式(4)的第一条分布收敛。这里的速度是n，不是样本均值常见的sqrt(n)。

条件于最大值后，数一小段内有几个点

固定t>0且m>t。设r=M_n，令

N_n(t)=\#\{i:X_i\ge r(1-t/m)\}.

Uniform样本没有并列。给定最大值r及它的索引，其余n−1条观测独立服从Uniform(0,r)；这可以从联合密度在立方体(0,r)^(n−1)上为常数直接看出。于是由二项计数，

N_n(t)\ \overset d=\ 1+\operatorname{Bin}(n-1,t/m). \tag{6}

最大值自己贡献前面的1。重抽最大值要低于r(1−t/m)，m次抽取都必须避开这N_n(t)条记录，故

P^*(U_{m,n}^*>t)=\left(1-\frac{N_n(t)}n\right)^m. \tag{7}

阈值恰撞上一条非最大观测的事件概率为零，所以这里严格与非严格计数不改变式(6)；t=0另行处理。

式(6)给出

E\frac{mN_n(t)}n=\frac mn+\frac{n-1}{n}t\longrightarrow t, \qquad \operatorname{Var}\!\left(\frac{mN_n(t)}n\right) \le\frac{tm}{n}\longrightarrow0. \tag{8}

用Chebyshev不等式得到mN_n(t)/n→_P t；又因m→∞，有N_n(t)/n→_P0。在N_n(t)/n≤1/2的高概率事件上，

|\log(1-x)+x|\le x^2\quad(0\le x\le1/2)

可由∫_0^x u/(1−u)du≤x²证明。因此式(7)的对数等于−mN_n(t)/n加上趋零余项：其绝对值至多m(N_n(t)/n)²，而这正是一个趋于t的量乘一个趋零量。条件尾便趋于e^(−t)。

零点与整条CDF

t=0时，U_{m,n}^*=0当且仅当至少一次抽中最大记录，所以

P^*(U_{m,n}^*=0)=1-(1-1/n)^m\le m/n\longrightarrow0. \tag{9}

负半轴CDF恒为零。至此在每个实t都有条件CDF依概率趋于J(t)。要得到一致结论，先选两端使J的尾质量小，再用有限网格把相邻J值的增量压小。CDF单调性把网格间误差夹在端点误差加一个小增量内；有限多个端点同时趋好，便给式(4)的上确界结论。

例子与边界

四条资料可以不做模拟而直接求CDF

给定互异正数排序x_(1)<…<x_(n)，每次独立抽m条，则

P^*(M_m^*\le x_{(k)})=(k/n)^m, \qquad P^*(M_m^*=x_{(k)})=\frac{k^m-(k-1)^m}{n^m}. \tag{10}

对资料(1,2,4,7)、m=2，最大值1、2、4、7的质量分别为1/16、3/16、5/16、7/16。对应式(3)的根值依次为12/7、10/7、6/7、0。把根按从小到大排列，其3/4分位数为6/7，因为P^(U^≤6/7)=12/16。

这张小表用于核实抽样协议、次序和分母，不能把m=2当成已经满足m→∞的证据。资料有并列时按每个值的累计频数计算式(10)，不要把并列值强行各分一份不同质量。

左图的无放回CDF由不同索引的组合计数得到，零点质量是1/2，与有放回的7/16不同。右图只看有放回方案：m=n时原子不会消失，而m=floor(sqrt(n))同时满足式(2)的两个条件。

两个缺一不可的规模条件

若m/n→c>0，零点质量趋于1−e^(−c)>0。式(4)的目标CDF在零处连续且等于零，所以近似失败。普通m=n正是c=1的情形；增加Monte Carlo重复次数只能更精确地算出这份错误的条件律。

若m固定，在0≤t≤m上，经验分布一致性和M_n→θ给

P^*(U_{m,n}^*>t)\longrightarrow(1-t/m)^m.

t>m时尾为零。它是固定m极值根的分布，并非指数尾；式(2)中的发散条件也不能删除。

选择m不是选择模拟重复数

m控制每份重抽里有几条记录，B控制重复生成几份重抽结果。它们影响不同误差。把B从一千增到一百万不会改变条件CDF本身；把m从n换成更小值则改变目标近似和有限样本偏差。数据驱动选择m需要把选择规则纳入有效性论证，本页定理先限定确定性m序列。

推论与应用

将分位数换回原始n条资料

令0<α<1，c_n^为U_{m,n}^的1−α分位数，采用inf{t:CDF(t)≥1−α}。指数CDF在该分位数严格穿越水平线，式(4)给c_n^*→_P c=−logα。于是定义

C_n=\begin{cases} [M_n,M_n/(1-c_n^*/n)],&c_n^*<n,\\ [M_n,\infty),&c_n^*\ge n. \end{cases} \tag{11}

其覆盖率趋于1−α。理由是θ≥M_n恒成立，而有限上端覆盖θ恰等价于U_n≤c_n^；用c±ε夹住随机临界值，再由式(5)和极限连续性取ε→0。由于c_n^趋于有限常数，无穷上端分支的概率趋零。

上面四条资料的c_n^*=6/7给区间[7,98/11]。分母使用n=4；若误用m=2，则把更大的重抽波动直接当成原估计误差，得到了另一份没有本页覆盖论证的规则。这个有限数值区间本身不承诺恰好75%覆盖。

旧Bootstrap页已经给出Uniform模型下的参数重抽及精确端点区间。若该模型可信，精确方法当然可以使用；本页的贡献是说明经验重抽改变规模后为什么也能恢复所需极限，以及这种保证只是渐近的。

计算成本与下一步

一般统计规则若计算m条资料的成本为C(m)，B次显式重抽需O(B(m+C(m)))工作；重用一份m条缓冲及保存B个根，额外空间O(m+B)，输入另计。排序根取分位数可用O(B log B)比较，选择算法可另行优化。位精度和拟合失败处理也须单独报告。

最大值例可用式(10)避免枚举n^m条索引序列：先排序资料需O(n log n)比较，再算n个质量；幂的算术/位成本取决于m和所需精度。无放回地选m个不同索引则产生子样本推断，其CDF是组合计数而非(k/n)^m，且有另一条适用于连续极限的证明。

参考资料

P. J. Bickel、F. Götze、W. R. van Zwet，“Resampling Fewer Than n Observations: Gains, Losses, and Remedies for Losses”，Statistica Sinica7，1997，1–31，§§2–3，特别§3对有放回与无放回规则的区分和Theorem2的附加条件。本页Uniform端点结论按计数独立推导，没有声称只要m=o(n)就对所有统计量有效。
Charles J. Geyer，STAT5601: Subsampling，University of Minnesota，2007，Overview和Extreme Values：不同样本量的尺度换算；其中无放回算法由相邻页单独处理。

形式陈述 ​

输入、重抽与目标尺度 ​

一份完整的有效性定理 ​

先计算真实目标 ​

条件于最大值后，数一小段内有几个点 ​

零点与整条CDF ​

四条资料可以不做模拟而直接求CDF ​

两个缺一不可的规模条件 ​

选择m不是选择模拟重复数 ​

将分位数换回原始n条资料 ​

计算成本与下一步 ​

反向链接