分组均值中位数估计

为什么少数失常的组不会拖走答案 ​

每组的平均满足

记 $r=2\sqrt{v/m}$，把 $|Z_j-\mu |>r$ 称为“坏组”，并令其指示变量为 $I_j$。Chebyshev 给出

这一步不要求原始观测有界，也不要求它有指数矩。它只承诺每组至少有四分之三的机会落在同一个好区间 $[\mu -r,\mu +r]$。

若超过一半的组均值都在好区间中，中位数一定在其中。反过来，中位数跑出区间，至少有 $(k+1)/2$ 个坏组。因此

原始样本独立、分组不相交，保证各 $I_j$ 相互独立。对这些落在 $[0,1]$ 中的变量使用单侧 Hoeffding，得到

从而证明式 (1)。这里 Hoeffding 用于坏组的指示变量，不是用于无界的原始读数。重尾读数仍可以很大；它们在最终投票中只占所属组的一票。

同一个放大机制已经出现在 AMS 二阶矩 Sketch理路AMS 二阶矩 SketchAMS sketch · Alon–Matias–Szegedy sketch用随机符号线性投影的平方无偏估计频率向量二阶矩，并以均值—中位数组合放大。 中：那里的单副本估计 $F_2$，本页则把它作为任意有限方差总体均值的可复用统计方法。特殊应用中的随机副本和这里的观测样本，是不同的随机来源。

给定置信度，怎样实际选整数 ​

给定 $0<\delta <1$，令 $k_{\delta }$ 是不小于 $8\log \left(1/\delta \right)$ 的最小正奇数，所有对数取自然对数。执行时先算上取整，再在偶数时加一。只要 $n\ge k_{\delta }$，就可以采用

如果 $k_{\delta }>n$，这个分组方案不能达到所请求的置信度；不能创建零长度的组。对固定 $n$，可用的最小 $\delta$ 由“$k_{\delta }\le n$”决定。特别地，不能把式 (3) 宣称为对任意小 $\delta$ 都成立的同一个估计量：组数会随 $\delta$ 改变。

反过来，若先要求误差至多 $\epsilon >0$，一个直接可执行的充分样本量是

当 $n\ge n_{\ast }$ 时，用 $k_{\delta }$ 组及 $\lfloor n/k_{\delta }\rfloor$ 的组长即可。公式明确保留两个整数取整，不把 $k_{\delta }$ 偷换成实数 $8\log \left(1/\delta \right)$。

若只关心量级，且 $n\ge 2k_{\delta }$，则 $\lfloor n/k_{\delta }\rfloor \ge n/(2k_{\delta })$，所以半径不超过 $\sqrt{8v{k}_{\delta }/n}$。当置信度提高，付出的主要代价是 $\sqrt{\log \left(1/\delta \right)}$，而样本平均的 Chebyshev 半径是 $\sqrt{v/(n\delta )}$。常数与可行的置信度范围仍由前面的精确公式负责。

一次从要求到样本量的计算 ​

要求估计某项读数的均值，绝对误差至多 $0.1$，失败概率至多 $0.001$；已知方差不超过 $1$，没有幅度或指数矩保证。计算

因此 $n_{\ast }=57\cdot 400=22800$。每个组均值的方差至多 $1/400$，超过 $0.1$ 的概率至多 $(1/400)/0.01=1/4$。最终失败概率至多

如果已拿到 $23000$ 项，组长应为 $\lfloor 23000/57\rfloor =403$，实际使用 $22971$ 项，丢余 $29$ 项；半径为 $2/\sqrt{403}\approx 0.0996271$。把 $23000/57$ 当作实际组长虽然差别小，却不是所实施的算法。

作为比较，直接用全部样本平均配合 Chebyshev，需要 $n\ge 1/(0.001\cdot {0.1}^2)=100000$。这只是两个充分界的比较，并非声称 MoM 的常数对所有置信度都更好。例如置信度没有那么高时，简单 Chebyshev 可能给出更小的数。

名字中的“中位数”没有改变估计目标 ​

令 $X\sim \mathrm{Bernoulli}(0.1)$。总体均值是 $0.1$，唯一总体中位数是 $0$。大量原始观测直接取中位数，会趋向 $0$，而不是所要估计的 $0.1$。

MoM 在组长增长时先让每个组均值靠近 $0.1$，然后取这些均值的中位数。组内平均不可删掉；若固定组长为 $1$、只增加组数，它就退化为原始样本中位数，本页的半径也不会随组数收缩。对固定 $\delta$，$k_{\delta }$ 固定而 $m\to \mathrm{\infty }$，式 (3) 的误差半径才趋零。

一次手算可以显示两层聚合。按事先固定的组标记，十四个原始读数分为七对：$(1,1.02)$、$(0.96,1)$、$(1,1.06)$、$(1,39)$、$(0.98,1.02)$、$(1,-31)$、$(0.98,1)$。逐对相加除以二，得到 $1.01,0.98,1.03,20,1.00,-15,0.99$；排序后是 $-15,0.98,0.99,1.00,1.01,1.03,20$，MoM 返回 $1.00$。全部十四点的普通平均则为 $10.01/7=1.43$。

保持同一批十四个数不变，只把第三组的 $1.06$ 与第四组的 $39$ 对换，新的第三、四组均值为 $20$ 与 $1.03$，组均值多重集和中位数都不变。若把第四组的 $39$ 与第六组的 $1$ 对换，两个极端读数进入同一组，第四组均值变为 $1$、第六组变为 $4$，其余不变；中位数仍为 $1.00$，但异常组数由二变一。这是在固定小数据上考察污染落点的确定性变化，不能据此在真实抽样后挑最有利的分组，也不证明随机覆盖率。

三条不能越过的边界 ​

重尾与任意污染不同。本页允许干净 IID 分布产生稀有极值。若对手能改写观测，坏组概率的独立性或上界可能失效。一次改写可以破坏一个组；若对手击中足够多的不同组，中位数也会失败。污染下的保证需要另算被破坏组数与剩余随机坏组，不能从式 (1) 自动读出。影响函数理路稳健统计与影响函数Robust statistics · Influence function以污染邻域和统计泛函导数量化少量异常分布对估计的局部影响。研究的局部污染响应，也不是本页的有限样本置信保证。

重叠的组不提供独立票数。把同一批数据复制七遍，再算七个相同组均值，不会获得七次独立机会。证明中失去的是对 $I_j$ 应用 Hoeffding 的资格，组内 Chebyshev 本身可能仍然正确。

数据尺度与估计量尾界不同。有限方差的重尾 $X$ 不会因为使用 MoM 而变成次高斯变量。较强的是估计误差在已声明 $n,\delta$ 范围内的保证。若连二阶矩都无穷，式 (2) 的方差预算也不存在，本页方法及这个半径不能原样照用。

迁移练习 ​

把方差上界改为 $v=9$，要求 $\epsilon =0.3,\delta =0.01$。说明为什么这里每组样本量与 $v=1,\epsilon =0.1$ 时相同，再计算总样本量。

再做一道边界题：固定 $n=50$，请求 $\delta =0.001$，按本页规则需要多少组，能否执行？如果改为 $n=23000$，请算实际使用与丢余项数。

核对：第一题 $4v/{\epsilon }^2=36/0.09=400$；$8\log 100\approx 36.84136$，所以 $k=37$，$n_{\ast }=14800$。这来自标准差与误差阈值同时放大三倍，信噪尺度不变，而不是忽略了方差。第二题需要 $57$ 组，超过 $50$，本方案不可执行；$n=23000$ 时使用 $57\cdot 403=22971$ 项、丢余 $29$ 项。

实现只需顺序累加每组：读入所用观测的算术工作为 $O(n)$，保存 $k$ 个组均值占 $O(k)$ 空间；把它们排序取中位数需 $O(k\log k)$ 比较。也可用线性时间选择算法，但它只改变取中位数的计算代价，不改变抽样保证。

不分组的有限方差求根路线 ​

Catoni 均值估计理路Catoni 有限方差均值估计Catoni mean estimator · Catoni 软截断均值估计用随样本量与置信度校准的单调软截断方程估计重尾均值，证明有限方差误差界，并把括根数值容差加入最终证书。使用同样的干净 IID、有限方差上界接口，但对全部观测求一个单调软截断方程的根，不按组投票。它把方差预算、置信度与样本量一起用于调节得分尺度，再用两个确定端点的指数界括住根。其具体常数和本页不同，重复求根也有额外计算成本。两个方法都是以总体均值为目标的高置信程序；名字里有中位数或软截断，并不自动赋予任意污染下的相同保证。