返回学习路线

同一个均值任务，三份不同的保证 ​

你要交付什么 ​

仪器连续产生独立同分布的实值读数，目标始终是总体均值 $\mu =\mathbb{E}X$。你要给出一个估计量及一份可复算的保证：绝对误差不超过 $\epsilon =0.1$，失败概率不超过 $\delta =0.001$。

下面三张条件卡是三种可选的模型保证，不是同一分布的三个互相矛盾描述。每次只使用被给定的那张卡；比较的是“相同精度任务在不同信息下能怎样完成”，不是对三种不同分布的真实误差作排名。

• A：读数几乎处处落在已知区间 $[0,1]$
• B：知道中心化 MGF 满足 $\mathbb{E}{e}^{\lambda (X-\mu )}\le e^{{\lambda }^2/2}$，对每个实 $\lambda$ 成立；读数可以无界
• C：只知道 $\mathrm{Var}(X)\le 1$，不保证有界或存在正指数矩

核心阅读为 Hoeffding理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。、次高斯尺度理路次高斯随机变量Sub-Gaussian random variable · 次高斯尺度 · Subgaussian variance proxy用全实数上的中心化指数矩上界定义次高斯尺度，计算独立加权平均的尾界，并区分方差、尺度代理与条件次高斯假设。、标量 Bernstein理路有界标量 Bernstein 不等式Scalar Bernstein inequality · Bernstein inequality for bounded random variables在已知中心化幅度与方差预算时控制独立标量和，以初等指数矩证明解释两种偏差尺度，并计算罕见事件均值的充分样本量。 与 分组均值中位数理路分组均值中位数估计Median-of-means estimator · MoM 均值估计将独立样本分成不相交的组，先平均再取中位数，以有限方差取得依赖置信度的均值误差保证，并明确组数、余数和尺度条件。。ψ₁ 次指数尾理路次指数尾随机变量（ψ₁）Sub-exponential random variable (Orlicz) · Psi-1 random variable · ψ₁ 次指数尾用绝对值指数矩定义 ψ₁ 尺度，推导局部 MGF 与两尺度和界，并以指数分布和 Pareto 尾辨析同名的重尾卷积类。和 经验 Bernstein理路经验 Bernstein 均值界Empirical Bernstein mean bound · 经验方差均值界对已知有界范围的 IID 观测，以经过校准的样本方差构造固定样本均值区间，解释标准差估计误差、零样本方差与重复查看的边界。 是处理平方读数、未知方差的分支。

主任务 ​

1. 每张条件卡分别选择一个合法估计量，写清所用尺度、概率界及充分整数样本量。C卡同时比较普通平均的 Chebyshev 方案与 MoM 方案
2. 完成 MoM 的证明：组内方差是多少？坏组概率为何至多 $1/4$？中位数失败意味着多少坏组？Hoeffding 此时究竟作用于什么变量？
3. 已有 $23000$ 个观测，使用 C卡 MoM 方案时，确定组数、每组大小、实际用到与丢弃的项数、最终半径。能否在 $50$ 个观测上要求同样的 $\delta$？
4. 用一个方差不超过 $1$ 的分布，直接反驳“只要标准差不超过 $1$，就可以把样本当成 $[0,1]$ 读数套 Hoeffding”
5. 说明把所有原始观测直接取中位数，为何不能普遍代替均值估计。再说明把同一批数据复制成许多组，为什么不会提高置信度

完整解答 ​

A：范围已知，普通平均就够 ​

独立性与已知范围允许使用双侧 Hoeffding：

$$\text{Pr}(|{\overline{X}}_n-\mu |\ge 0.1)\le 2e^{-2n(0.1{)}^2}.$$

因此

$$\ell =\log \left(2/0.001\right)=\log 2000\approx 7.60090246,n_A=\lceil \frac{\ell }{0.02}\rceil =381.$$

我们报告的是样本平均与一个分布无关的充分样本量。无需知道真实方差，也未声称 $381$ 是精确最小值。

B：无硬边界，但有全实参数的尺度 ​

条件卡正好给出次高斯代理 $s^2=1$。独立平均具有尺度 $1/\sqrt{n}$，所以

$$\text{Pr}(|{\overline{X}}_n-\mu |\ge 0.1)\le 2e^{-n(0.1{)}^2/2},n_B=\lceil \frac{2\ell }{0.01}\rceil =1521.$$

A卡也蕴含次高斯，但其代理可以取 $s^2=1/4$；代入就恢复 $381$。两张卡的数字不同是所知尺度不同，不能据此说次高斯方法本身比 Hoeffding 低效。

C：有限方差，需要区分置信度与估计规则 ​

普通平均的方差至多为 $1/n$。Chebyshev 给

$$\text{Pr}(|{\overline{X}}_n-\mu |>0.1)\le \frac{1}{0.01n},n_{C,\mathrm{mean}}=100000.$$

若希望把置信度的代价从 $1/\delta$ 改成对数型，可换成 MoM。先算

$$8\log \left(1000\right)\approx 55.26204,k=57\text{（不小于它的最小正奇数）},$$$$m=\lceil \frac{4\cdot 1}{{0.1}^2}\rceil =400,n_{C,\mathrm{MoM}}=57\cdot 400=22800.$$

按预先固定的原始下标分成 $57$ 个独立组，各算平均，再取排序后的第 $29$ 个组均值。这个估计量不要求知道 $\mu$；数值保证使用了条件卡给出的方差上界 $v=1$。

把保证证明到最后一个事件 ​

每组平均 $Z_j$ 无偏且方差不超过 $1/400$，因此

$$\text{Pr}(|Z_j-\mu |>0.1)\le \frac{1/400}{{0.1}^2}=1/4.$$

令 $I_j=\mathbf{1}\{|Z_j-\mu |>0.1\}$。这些指示变量独立且在 $[0,1]$ 中，$\mathbb{E}\sum _j{I}_j\le 57/4$。若中位数落在 $[\mu -0.1,\mu +0.1]$ 外，至少 $29$ 组坏，特别地坏组数至少为 $57/2$。故

$$\text{Pr}(|{\hat{\mu }}_{\mathrm{MoM}}-\mu |>0.1)\le \text{Pr}(\sum _j{I}_j-\mathbb{E}\sum _j{I}_j\ge 57/4)\le e^{-57/8}\approx 0.000804733.$$

最后一步合法，是因为 Hoeffding 作用于坏组指示变量。原始读数可以无界；证明并没有悄悄把它们变成有界观测。

固定样本量时不能跳过取整 ​

已有 $23000$ 项时，仍取 $k=57$，组长 $m=\lfloor 23000/57\rfloor =403$。实际使用 $57\cdot 403=22971$ 项，丢掉末尾 $29$ 项。半径为

$$r=2\sqrt{1/403}\approx 0.0996271,$$

失败概率上界仍为 $e^{-57/8}$。这是一个确定的分组规则；按读数大小重新排序分组会改变抽样结构。

若只有 $50$ 项，要求的 $57$ 组放不下，当前 MoM 方案不可执行。不能让组长为零，也不能只留下 $49$ 组却仍引用 $57$ 组的失败概率。这里没有声称“任何算法在 $50$ 项上都不可能工作”，而是明确指出这份充分证书的可行范围。

直接算出错误套界的矛盾 ​

令读数分布为

$$\text{Pr}(X=100)={10}^{-4},\text{Pr}(X=0)=1-{10}^{-4}.$$

它满足

$$\mu =0.01,\mathrm{Var}(X)=10000\cdot {10}^{-4}-{0.01}^2=0.9999\le 1.$$

取 $n=381$。只要出现至少一个 $100$，就有

$$\overline{X}-\mu \ge 100/381-0.01\approx 0.252467>0.1.$$

因此真实失败概率至少为

$$1-(1-{10}^{-4}{)}^{381}\approx 0.037385.$$

错误地把范围写成 $[0,1]$，却会声称失败概率至多 $2e^{-2\cdot 381\cdot 0.01}\approx 0.000981$。同一事件的下界大于所谓上界，矛盾已经是数值上的，而非泛泛提醒“重尾可能有问题”。

这个分布本身其实有界，真实范围是 $[0,100]$。使用该真实范围的 Hoeffding 完全合法，只是不能获得错误套用 $[0,1]$ 时的短半径。反例否定的是拿方差或观察到的普通值代替总体范围，不是否定 Hoeffding 定理。

中位数的目标与独立票数 ​

Bernoulli$(0.1)$ 的均值为 $0.1$，唯一总体中位数为 $0$。直接取原始样本中位数，会随样本增加趋向 $0$；这不是对均值的一致估计。MoM 的组内平均先围绕总体均值集中，组间中位数才有正确的中心可保护。

复制同一批数据形成许多“组”，只会复制同一个组均值。坏组指示变量完全相同，无法调用独立指示变量的 Hoeffding；组内方差可能缩小过一次，但重复副本没有再创造信息。

两个进阶分支 ​

已知范围和小方差，能否进一步节省 ​

故障指标 IID，未知故障率有事前限制 $0\le p\le 0.01$。要求误差 $0.005$、失败概率 $0.01$。使用 $R=1,v=0.0099$，标量 Bernstein 给

$$n\ge \lceil \frac{2(0.0099+0.005/3)\log 200}{{0.005}^2}\rceil =4903.$$

只利用范围则需要 $105967$ 项。若 $p\le 0.01$ 只是看了数据后作出的猜测，不能用该预算；事前固定的 $1000$ 项若实际有 $10$ 次故障，可转向经验 Bernstein，计算 $S_n^2=9.9/999$、$\ell =\log 400$，得到半径约 $0.0268905$。这里方差由数据估计，所付代价也不同。

读数平方以后，尾部条件发生什么 ​

若读数 $G\sim N(0,1)$，$G$ 的中心化次高斯代理是 $1$。平方读数 $G^2$ 的目标均值也是 $1$，但其正指数矩在 $\lambda \ge 1/2$ 发散，不能沿用同一个全实参数界。

对中心化平方 $G^2-1$，局部指数矩可取 ${\nu }^2=2,b=2$。独立平均平方以误差 $0.2$、失败概率 $0.01$ 估计 $1$，本单元 ψ₁ 推导给充分样本量

$$n\ge \lceil 2(2+2\cdot 0.2)\log 200/{0.2}^2\rceil =636.$$

这里使用的是集中意义的 ψ₁ 次指数尾。它与重尾卷积类 $\mathcal{S}$ 的“一大跳”定义无关；指数分布与 Pareto 分布的交叉反例，见相应辨析页。

最后的检查清单 ​

一个可交付的均值保证至少应包含：估计目标、抽样结构、估计规则、尺度来自哪里、$n$ 与 $\delta$ 的范围、整数取整，以及所报的是充分界而非真实误差。若换成随时查看后停止、未知范围、相关样本或任意污染，应明确指出哪条证明需要重做。

本单元的价值不是多记几个尾界名称，而是能为自己的估计逐步交出这份证书。