下面\(P,Q\)表示概率测度，\(p=\mathrm{d}P/\mathrm{d}x,q=\mathrm{d}Q/\mathrm{d}x\) 表示概率密度函数

记 \(p\wedge q=\min(p,q),\ p\vee q=\max(p,q),a_-=\max\{0,-a\}, a_+=\max\{a,0\}\)

几个常用的距离

Hellinger distance

\[\mathcal{H}^2(P,Q)=\int(\sqrt{p}-\sqrt{q})^2\,\mathrm{d}x=2-2\int\sqrt{pq}\,\mathrm{d}x\]

可以证明其满足距离的定义，且 \(0\leq \mathcal{H}^2(P,Q)\leq 2\)

如果 \(P=\bigotimes_{i=1}^{n} P_i,Q=\bigotimes_{i=1}^{n} Q_i\)

则 \[\mathcal{H}^2(P,Q)=2-2\prod\limits_{i=1}^{n}(1-\frac{1}{2}\cdot \mathcal{H}^2(P_j,Q_j))\]

Total variation distance

\[\mathrm{TV}(P,Q)=\sup_{A}\lvert P(A)-Q(A)\rvert=\sup\limits_{A}\big\lvert \int_A(p-q)\,\mathrm{d}x \big\rvert\]

可以证明其满足距离的定义，且 \(0\leq \mathrm{TV}(P,Q)\leq 1\)，这可以由下式得到

\[\mathrm{TV}(P,Q)=\frac{1}{2}\int\lvert p-q\rvert\,\mathrm{d}x=1-\int p\wedge q\,\mathrm{d}x\]

Kullback divergence

\[KL(P,Q)=\int p\log \frac{p}{q}\,\mathrm{d}x\] , 如果 \(P\ll Q\)

可以利用 Jensen inequality 证明其非负

\[\int p\log \frac{p}{q}\,\mathrm{d}x=-\int p\log \frac{q}{p}\,\mathrm{d}x\ge-\log\int q\,\mathrm{d}x\ge 0\]

但是不满足对称性(所以不叫 distance)，可以构造 \(KL(P,Q)+KL(Q,P)\) 来满足对称性

如果 \(P=\bigotimes_{i=1}^{n} P_i,Q=\bigotimes_{i=1}^{n} Q_i\)

\[KL(P\mid\mid Q)=\sum_{j=1}^{n}KL(P_j,Q_j)\]

另一个十分有用的性质时对于正态分布来说

现考察其 KL 散度，记 \(\varphi(x)=\frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\},\varphi(x+t)=\frac{1}{\sqrt{2\pi}}\exp\{-(x+t)^2/2\}\)，则其KL 散度为

\[\begin{align}KL(\varphi(x),\varphi(x+t)&=\int_{-\infty}^{+\infty} \frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\}\left(\frac{(x+t)^2-x^2}{2}\right)\,\mathrm{d}x\\&=\int_{-\infty}^{+\infty} \frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\}\frac{t^2}{2}\,\mathrm{d}x+\int_{-\infty}^{+\infty} \frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\}\left(-tx\right)\,\mathrm{d}x\\&=\frac{t^2}{2}+0=\frac{t^2}{2}\end{align}\]

\(\chi^2\) divergence

\[\chi^2(P,Q)=\int q\cdot \left(\frac{p}{q}-1\right)^2\,\mathrm{d}x\]

同样其也不满足对称性。可以证明其有性质

\(\chi^2(P,Q)=\int \frac{p^2}{q}\,\mathrm{d}x-1\)

如果 \(P=\bigotimes_{i=1}^{n} P_i,Q=\bigotimes_{i=1}^{n} Q_i\)

\[\chi^2(P,Q)=\prod\limits_{i=1}^{n}(1+\chi^2(P_i,Q_i))-1\]

Csizsar f-divergence

上述四个都是 Csizsar f-divergence 的特殊情况，其定义为 \[D(P,Q)=\int q\cdot f(p/q) \mathrm{d}x\]，其中要求 \(f\) 是在 \(\mathbb{R}^+\) 上的凸函数。之前四个距离分别是 \(f(x)=\lvert x-1\rvert/2\), \(f(x)=(\sqrt{x}-1)^2\) ， \(f(x)=x\log x\) 和 \(f(x)=(x-1)^2\)

距离相关的不等式

Le Cam's Inequallities

为方便，分别记 Hellinger、Total variation 和 KL 散度为 \(H,V,K\)

式一

\[\int p\wedge q\,\mathrm{d}x\ge\frac{1}{2}(\int\sqrt{pq}\,\mathrm{d}x)^2=\frac{1}{2}(1-H^2/2)^2\]

证明：只需注意到 \(\int p\wedge q\,\mathrm{d}x+\int p\vee q\,\mathrm{d}x=2\)

则有

\[\begin{align}(\int\sqrt{pq}\,\mathrm{d}x)^2&=(\int\sqrt{p\wedge q\ \cdot\ p\vee q}\,\mathrm{d}x)^2\\&\leq\int p\wedge q\,\mathrm{d}x\ \cdot\ \int p\vee q\,\mathrm{d}x\\&=\int p\wedge q\,\mathrm{d}x\ \cdot\ \left(2-\int p\wedge q\,\mathrm{d}x\right)\\&\leq 2\int p\wedge q\,\mathrm{d}x\end{align}\]

式二

\[H^2/2\leq V\leq H\sqrt{1-H^2/4}\leq H\]

证明：

左边： \(V=1-\int p\wedge q\,\mathrm{d}x\ge 1-\int pq\,\mathrm{d}x=H^2/2\)

右边：注意到式一推导过程中可以推导出

\[(1-H^2/2)^2=(\int\sqrt{pq}\,\mathrm{d}x)^2\leq (1-V)(1+V)=1-V^2\]

由此导出 \(V^2 \leq H^2(1-H^2/4)\)

式三

\[H^2\leq K\]

证明：由于 \(-\log(x+1)\ge -x,\ (x>-1)\)，代入 KL 散度计算中有

\[\begin{align}K&=-\int p\log(q/p)\,\mathrm{d}x\\&=-2\int p\log(\sqrt{q/p})\,\mathrm{d}x\\&=-2\int p\log(\sqrt{q/p}-1+1)\,\mathrm{d}x\\&\ge -2\int p(\sqrt{q/p}-1)\,\mathrm{d}x\\&=2-2\int(\sqrt{pq})\,\mathrm{d}x=H^2\end{align}\]

综合之前我们可以得到 \(V\leq H\leq\sqrt{K}\)，但这并不是最优的，因为我们可以证明下式

Pinsker's Inequalities

\[V\leq\sqrt{K/2}\]

令 \(\psi(x)=x\log x-x+1,x\ge 0\)，并定义 \(0\log 0=0\)

注意到 \(\psi(0)=1,\psi(1)=0,\psi'(1)=0,\psi''(x)=1/x\ge 0,\psi(x)\ge 0\)

可以精巧地构造出下列不等式，使用高中的导数知识求导即可证明

\[(x-1)^2\leq (4/3+2x/3)\psi(x)\]

于是

\[\begin{align}V&=\frac12\int\lvert p-q\rvert \,\mathrm{d}x\\&=\frac12\int\lvert p/q-1\rvert q\,\mathrm{d}x\\&\leq\frac12\int\sqrt{4/3+2p/3q}\cdot\sqrt{\psi(p/q)}\cdot q\,\mathrm{d}x\\&\leq \frac{1}{2}\sqrt{\int (4q/3+2p/3)\,\mathrm{d} x}\sqrt{\int q\cdot\psi(p/q)\,\mathrm{d} x}\\&=\frac{1}{2}\sqrt{2}\sqrt{K}=\sqrt{K/2}\end{align}\]

刻画 \(K\) 和 \(V\) 的另一个不等式

\(V\leq 1-\frac{1}{2}\exp\{-K\}\)

证明：使用 Jensen 不等式有

\[\begin{align}(\int\sqrt{pq}\,\mathrm{d}x)^2&=\exp\{2\log\int\sqrt{pq}\,\mathrm{d}x\}\\&=\exp\{2\log\int p\sqrt{\frac{q}{p}}\,\mathrm{d}x\}\\&\ge\exp\{2\int p\log\sqrt{\frac{q}{p}}\,\mathrm{d}x\}\\&=\exp\{-K\}\end{align}\]

所以有 \(\int p\wedge q\,\mathrm{d}x\ge \frac{1}{2}\exp\{-K\}\)

即 \(V=1-\int p\wedge q\,\mathrm{d}x\leq 1-\frac{1}{2}\exp\{-K\}\)

刻画 K 和 \(\chi^2\) 不等式

\(K\leq\log(1+\chi^2)\leq \chi^2\)

证明: 使用 Jensen 不等式有

\[\log(1+\chi^2)=\log\int \frac{p^2}{q}\,\mathrm{d}x\ge\int p\log\frac{p}{q}\,\mathrm{d}x=K \]

所以我们通过给出 \(\chi^2\) 的上界可以同样控制住 \(K\)。

刻画误差下界

本文是为非参数统计中刻画误差下界服务的。其关心的值为

\[p_{err,1}=\int\limits_\psi\max\limits_{j=0,1}\mathbb{P}_j[\psi\neq j]\ge \frac{1}{2}\inf\limits_\psi\{\mathbb{P}_0[\psi\neq 0]+\mathbb{P}_1[\psi\neq 1]\}=\frac{1}{2}(\mathbb{P}_0[\psi^\ast\neq 0]+\mathbb{P}_1[\psi^\ast\neq 1])\]

其中 \(\psi^\ast\) 为极大似然估计，为 \(\psi^\ast=\boldsymbol{1}[P_0<P_1]\) 其中 \(P_0,P_1\) 是 \(\mathbb{P}_0,\mathbb{P}_1\) 对应的概率密度函数。

注意到 \(\frac{1}{2}(\mathbb{P}_0(\psi^\ast\neq 0))+\mathbb{P}_1(\psi^\ast\neq 1))=\frac{1}{2}\int P_0\wedge P_1=(1-V)/2\)

由此我们得

  • 如果 \(V \leq\alpha <1\), 则 \(p_{err,1}\ge\frac{1-\alpha}{2}\) （立得）
  • 如果 \(H\leq\alpha <2\), 则 \(p_{err,1}\ge\frac{1-\sqrt{\alpha(1-\alpha/4)}}{2}\) （使用 \(V\leq H\sqrt{1-H^2/4}\)）
  • 如果 \(\mathrm{K}(\mathbb{P}_1,\mathbb{P}_0)\leq\alpha <\infty\) (或 \(\chi^2(\mathbb{P}_0,\mathbb{P}_1)\leq\alpha<\infty\), 则 \(p_{err,1}\ge\max\{\frac{1}{4}e^{-\alpha},\frac{1-\sqrt{\alpha/2}}{2}\}\) （使用 \(V\leq\sqrt{K/2}\) 和 \(V\leq 1-\frac{1}{2}\exp\{-K\}\)）