Dvoretzky–Kiefer–Wolfowitz 不等式

形式陈述

一个阈值处的样本比例容易控制；若阈值看完数据后再挑，怎样仍有共同保证？设 $n\ge1$ ， $X_1,\ldots,X_n$ 为实值独立同分布样本，总体分布函数为 $F$ ，经验分布函数为

F_n(x)=\frac1n\sum_{i=1}^n\mathbf1_{\{X_i\le x\}}.

Dvoretzky–Kiefer–Wolfowitz 不等式的 Massart 常数版本为

P\left(\sup_{x\in\mathbb R}|F_n(x)-F(x)|>\varepsilon\right) \le2e^{-2n\varepsilon^2},\qquad\varepsilon>0.

它对每个有限样本量成立，允许 $F$ 离散或有原子。右端超过一时当然可再取与一的较小值。对给定 $\alpha\in(0,1)$ ，令

\varepsilon_{n,\alpha}=\sqrt{\frac{\log(2/\alpha)}{2n}},

便有概率至少 $1-\alpha$ ，同时对全部 $x$ 成立

\max\{0,F_n(x)-\varepsilon_{n,\alpha}\} \le F(x)\le \min\{1,F_n(x)+\varepsilon_{n,\alpha}\}.

这是整条 CDF 的同时置信带，不是一串分别有 $1-\alpha$ 覆盖率的点态区间。

直觉

所有半直线 $(-\infty,x]$ 都按包含关系排成一条链。一个观测随阈值增大只会被纳入一次，所以各阈值上的误差高度相关，不是无穷多个互不相干的估计问题。

对固定 $x$ ，Hoeffding 不等式已经给出同样的指数尺度。但不能对不可数多个 $x$ 直接取并集界，也不能对所有样本阶跃分别取界后还保留前因子二。尖锐结果利用这条嵌套链的鞅结构，一次控制所有可能越界的位置。

例子与边界

二百个样本的一条共同带

若 $n=200,\alpha=0.05$ ，则

\varepsilon_{200,0.05}=\sqrt{\frac{\log40}{400}}\approx0.0960.

例如某阈值处 $F_n(x)=0.70$ ，带给 $F(x)\in[0.6040,0.7960]$ ；但更重要的是，这次概率保证同时覆盖所有其他阈值。看过数据后选一个感兴趣的阈值，并不会额外花掉一份错误概率，因为它已经在上确界事件里。

要让这条 $95\%$ 同时带的半宽不超过 $0.02$ ，充分样本量为

n\ge\frac{\log40}{2(0.02)^2},

即至少 $4612$ 个独立同分布观测。半宽缩小一半，需要的样本量约增为四倍。

离散总体仍有界，相关样本却不能直接套

即使 $X$ 只取零和一，定理仍成立；经验 CDF 的有效阈值更少，只可能让通用界保守。

若所有观测都复制同一个 Bernoulli 变量，虽然每个边缘相同，样本却不独立。取 $F(0)=1/2$ ，则 $|F_n(0)-F(0)|=1/2$ 对所有 $n$ 成立，不会随样本量缩小。把重复读数误当独立样本，会与 DKW 的指数衰减结论直接冲突。

推论与应用

第一步：化为均匀样本

取独立 $U_i\sim\operatorname{Unif}(0,1)$ ，用广义逆构造 $X_i=F^{\leftarrow}(U_i)$ 。若 $G_n$ 是均匀样本的经验 CDF，则同时对全部 $x$ 有 $F_n(x)=G_n(F(x))$ ，所以

\sup_x|F_n(x)-F(x)|\le\sup_{0\le t\le1}|G_n(t)-t|.

连续 $F$ 给出同分布的等号版本；有跳跃时只需要这条不等式。因此以下证明可集中在均匀样本上。

第二步：把全部上越界放进一条反向鞅

只须考虑 $0<\varepsilon<1$ 。令 $i_* =\lfloor n\varepsilon\rfloor+1$ 、 $u_i=i/n-\varepsilon$ ，并设

N_i=\sum_{j=1}^n\mathbf1_{\{U_j<u_i\}},\qquad i_*\le i\le n.

经验阶梯的上越界发生当且仅当某个 $U_{(i)}<i/n-\varepsilon$ ，也就是某个 $N_i\ge i$ 。固定 $\lambda>0$ ，定义

M_i=\frac{(1+\lambda/u_i)^{N_i}}{(1+\lambda)^n}.

$EM_i=1$ 。给定较大阈值 $u_{i+1}$ 下的点数，更小阈值下的点数服从参数 $u_i/u_{i+1}$ 的二项稀疏化，因此

E(M_i\mid N_{i+1},\ldots,N_n)=M_{i+1}.

按 $i$ 递减读取，这就是非负鞅。由Doob 最大不等式，可一次界住任意位置的 $M_i$ 越界概率。

具体地，记

g(x,\lambda)=n\log(1+\lambda) -x\log\left(1+\frac\lambda{x/n-\varepsilon}\right), \qquad i_*\le x\le n.

在事件 $N_i\ge i$ 上， $M_i\ge e^{-g(i,\lambda)}$ 。若 $Q=P(\sup_t[G_n(t)-t]>\varepsilon)$ ，最大不等式与放宽整数位置给

\log Q\le\inf_{\lambda>0}\max_{x\in[i_*,n]}g(x,\lambda).

这一步没有对 $n$ 个位置求概率和，所以没有额外的 $n$ 因子。

第三步：同一个指数参数如何照顾最坏阈值

这里用 Sion 极小极大定理的一维形式：若 $x$ 遍历紧区间， $\lambda$ 遍历凸区间，连续函数对 $x$ 准凹、对 $\lambda$ 准凸，则可交换 $\inf_\lambda\max_x$ 与 $\max_x\inf_\lambda$ 。在一维，“准凹”可理解为上水平集是区间，“准凸”则是下水平集是区间。

对当前 $g$ ， $\partial_\lambda g$ 的符号等于 $(n-x)\lambda-n\varepsilon$ 的符号，因此关于 $\lambda$ 先降后升（ $x=n$ 时一直下降），确实准凸。

准凹性也可直接核验。设 $e=n\varepsilon,\ell=n\lambda,y=x-e>0$ ，则除去与 $x$ 无关的项，

h(y)=(y+e)\log\frac y{y+\ell},\qquad h''(y)=-\frac{\ell[(2e-\ell)y+e\ell]}{y^2(y+\ell)^2}.

若 $\ell\le2e$ ， $h''\le0$ ，函数凹。若 $\ell>2e$ ， $h''$ 先负后正， $h'$ 从正无穷下降，再从负值上升趋零，因此 $h$ 先升后降，上水平集仍是区间。极小极大交换的条件成立。

对固定 $x<n$ ，最小值在 $\lambda=n\varepsilon/(n-x)$ 取得； $x=n$ 时令 $\lambda\to\infty$ 。代回得到

\inf_{\lambda>0}g(x,\lambda) =-n\,d(x/n\|x/n-\varepsilon),

其中 $d(a\|b)=a\log(a/b)+(1-a)\log[(1-a)/(1-b)]$ 是两个 Bernoulli 分布之间以自然对数计算的KL 散度，本段的 $\log$ 均为自然对数。固定 $b$ ，该函数在 $a=b$ 处值与一阶导数都为零，二阶导数 $1/[a(1-a)]\ge4$ ，所以 $d(a\|b)\ge2(a-b)^2$ 。于是 $\log Q\le-2n\varepsilon^2$ 。

对均匀样本作反射 $U_i\mapsto1-U_i$ ，下越界具有相同的概率界。最后只对“上越界”与“下越界”这两个事件取并集界，就得到前因子二。

一次反演得到多处分位保证

在共同带事件上，对 $0<p-\varepsilon<p+\varepsilon<1$ ，有

F_n^{\leftarrow}(p-\varepsilon) \le F^{\leftarrow}(p) \le F_n^{\leftarrow}(p+\varepsilon).

若概率索引越过零或一，分别使用 $-\infty$ 、 $+\infty$ 作为外端点。 $n=200$ 的上述带对中位数给出 $[X_{(81)},X_{(120)}]$ ；同一事件还同时约束其他分位数。若只关心一个预先指定的分位，精确二项秩区间通常能更有针对性地使用错误概率。

参考资料

Henry W. J. Reeve, 《A short proof of the Dvoretzky–Kiefer–Wolfowitz–Massart inequality》，§1 的反向鞅与一侧统一界，Corollaries 1–2。
Jean-Yves Le Boudec, 《An Elementary Proof of the Dvoretzky–Kiefer–Wolfowitz–Massart Inequality》，§§2.1–2.4，有限阈值反向鞅、极小极大与二项相对熵证明路线。

形式陈述 ​

二百个样本的一条共同带 ​

离散总体仍有界，相关样本却不能直接套 ​

第一步：化为均匀样本 ​

第二步：把全部上越界放进一条反向鞅 ​

第三步：同一个指数参数如何照顾最坏阈值 ​

一次反演得到多处分位保证 ​