使用指示函数进行表示

$L^p$ 空间的几个不等式

Cauchy-Schwarz 不等式

若随机变量 $X$ 和 $Y$ 的二阶矩 $E[X^2]$ 和 $E[Y^2]$ 存在，那么

$$|E[XY]{|}^2\le E[X^2]E[Y^2]$$

去中心化之后就是

$$|\mathrm{Cov}(X,Y)|\le \sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)},$$

从而相关系数满足 $|{\rho }_{XY}|\le 1$

方法1: 和所有类型的 Cauchy-Schwarz 不等式证明方法一样，利用判别式 $\Delta <0$ 去导出这个不等式:
考虑 $t\in \mathbb{R}$，然后利用 $E[(tX+Y{)}^2]\ge 0$，即

$$t^{2}E[X^2]+2tE[XY]+E[Y^2]\ge 0$$

利用 $\Delta <0$，即可得到

$$|E[XY]{|}^2\le E[X^2]E[Y^2]$$

方法2:
由5. 条件数学期望与投影，我们将概率空间看作内积空间，此时由内积空间的 Cauchy-Schwarz 不等式，就是 $|E[XY]{|}^2\le E[X^2]E[Y^2]$，此外，还有

$$\cos \theta =\frac{Cov(X,Y)}{\sqrt{Var(X)Var(Y)}}={\rho }_{XY}$$

因此

$$|\mathrm{Cov}(X,Y)|\le \sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)},$$

并且 $|{\rho }_{XY}|\le 1$

Hölder 不等式

若 $p,q>1$，且 $\frac{1}{p}+\frac{1}{q}=1$，则

$$E|XY|\le (E|X{|}^p{)}^{1/p}(E|Y{|}^q{)}^{1/q}.$$

当 $p=q=2$ 时，就是 Cauchy–Schwarz 不等式

Minkowski 不等式

若 $p\ge 1$，则

$$(E|X+Y{|}^p{)}^{1/p}\le (E|X{|}^p{)}^{1/p}+(E|Y{|}^p{)}^{1/p}.$$

由5. 条件数学期望与投影中往 $L^p$ 空间的推广 ，这两个不等式分布对应 $L^p$ 空间的两个不等式

$$|⟨a,b⟩|\le \Vert a\Vert {}_p\Vert b\Vert {}_q,\Vert a+b\Vert {}_p\le \Vert a\Vert {}_p+\Vert b\Vert {}_p$$

因此上面的两个不等式自然成立

Lyapunov 不等式

若 $0<r<s$，且相应矩存在，则

$$(E|X{|}^r{)}^{1/r}\le (E|X{|}^s{)}^{1/s}.$$

即高阶矩存在通常可以推出低阶矩存在

我们使用 Hölder 不等式证明: 在上面的 Hölder 不等式中，$p=\frac{s}{r}>1$，令 $Y=1$，得到

$$E[|X|{}^r\cdot 1]\le {\left(E[(|X|{}^r{)}^{\frac{s}{r}}]\right)}^{\frac{r}{s}}\cdot {\left(E[1^q]\right)}^{\frac{1}{q}}$$

两边同时取 $\frac{1}{r}$ 次方，立刻得到：

$$(E|X|{}^r{)}^{\frac{1}{r}}\le (E|X|{}^s{)}^{\frac{1}{s}}$$

---

尾部不等式

Markov 不等式

随机变量 $X\ge 0$，常数 $a>0$，则

$$P(X\ge a)\le \frac{E[X]}{a}$$

证明: 记 $A=\{X\ge a\}$，用 $1_A$ 表示事件 $A$ 的示性函数。因为 $X\ge 0$，所以对每个样本点都有 $X\ge a{1}_A$，两边取期望，由使用指示函数进行表示中指示函数的性质，有

$$E[X]\ge E[a{1}_A]=aE[1_A]=aP(A)=aP(X\ge a).$$

即

$$P(X\ge a)\le \frac{E[X]}{a}.$$

Chebyshev 不等式

若 $E(X)=\mu$，$\mathrm{Var}(X)={\sigma }^2<\infty$，则对任意 $\epsilon >0$

$$P(|X-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{{\epsilon }^2}.$$

由前面的 Markov 不等式，就有

$$\begin{array}{rl}P(|X-\mu |\ge \epsilon )& =P((X-\mu {)}^2\ge {\epsilon }^2)\\ & \le \frac{E[(X-\mu {)}^2]}{{\epsilon }^2}=\frac{\mathrm{Var}(X)}{{\epsilon }^2}=\frac{{\sigma }^2}{{\epsilon }^2}.\end{array}$$

Cantelli 不等式(单边 Chebyshev 不等式)

设 $E[X]=\mu$，$\mathrm{Var}(X)={\sigma }^2<\infty$。那么对任意 $t>0$，有

$$P(X-\mu \ge t)\le \frac{{\sigma }^2}{{\sigma }^2+t^2}.$$

这比上面的双边 Chebyshev 不等式得到的结果更强

方法1: 引入参数进行估计
令 $Y=X-\mu$，则 $E[Y]=0$，$E[Y^2]={\sigma }^2$，任取常数 $c>0$，当 $Y\ge t$ 时，有 $Y+c\ge t+c>0$，因此

$$\{Y\ge t\}\subseteq \{(Y+c{)}^2\ge (t+c{)}^2\}.$$

现在由 Markov 不等式

$$\begin{array}{rl}P(Y\ge t)& \le P((Y+c{)}^2\ge (t+c{)}^2)\\ & \le \frac{E[(Y+c{)}^2]}{(t+c{)}^2}.\end{array}$$

而

$$E[(Y+c{)}^2]=E[Y^2]+2cE[Y]+c^2={\sigma }^2+c^2.$$

此时

$$P(Y\ge t)\le \frac{{\sigma }^2+c^2}{(t+c{)}^2}.$$

对于上式右边的函数，求导得到其最小值点为 $c=\frac{{\sigma }^2}{t}$，代入即得

$$\begin{array}{rl}P(Y\ge t)& \le \frac{{\sigma }^2+\frac{{\sigma }^4}{t^2}}{{\left(t+\frac{{\sigma }^2}{t}\right)}^2}\\ & =\frac{{\sigma }^2}{{\sigma }^2+t^2}.\end{array}$$

方法2: 分段估计，然后利用 Cauchy-Schwarz 不等式
同样令 $Y=X-\mu$，现在我们用指数函数进行表示，考虑随机变量 $t-Y$，现在我们来进行分段估计

$$t-Y=(t-Y)1_{\{Y<t\}}+(t-Y)1_{\{Y\ge t\}}$$

两边取期望，得到

$$t=E[(t-Y)1_{\{Y<t\}}]+E[(t-Y)1_{\{Y\ge t\}}]$$

右边第二项显然小于等于0，因此

$$t\le E[(t-Y)1_{\{Y<t\}}]$$

现在利用我们之前证明的 Cauchy-Schwarz 不等式，令 $X=t-Y$ 以及 $Y=1_{\{Y<t\}}$，就有

$$t^2\le {\left(E[(t-Y)1_{\{Y<t\}}]\right)}^2\le E[(t-Y{)}^2]\cdot E[1_{\{Y<t\}}^2]$$

其中 $E[(t-Y{)}^2]=E[t^2-2tY+Y^2]=t^2-0+{\sigma }^2=t^2+{\sigma }^2$，$E[1_{\{Y<t\}}^2]=E[1_{\{Y<t\}}]=P(Y<t)$
因此代入就有 $P(Y<t)\ge \frac{t^2}{t^2+{\sigma }^2}$，即

$$P(Y\ge t)\le 1-\frac{t^2}{t^2+{\sigma }^2}=\frac{{\sigma }^2}{{\sigma }^2+t^2}$$

---

Hoeffding 不等式

设 $X_1,\dots ,X_n$ 相互独立，且 $a_i\le X_i\le b_i$，$S_n={\sum }_{i=1}^n{X}_i$，则

$$P(|S_n-E[S_n]|\ge t)\le 2\exp \left(-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right).$$

这种和的分布以及指数形式让我们立刻想到矩母函数
令 $Y_i=X_i-E[X_i]$，因为 $a_i\le X_i\le b_i$，所以 $Y_i$ 的取值区间长度依然是 $b_i-a_i$，现在我们证明

$$P\left(\sum _{i=1}^n{Y}_i\ge t\right)\le \exp \left(-\frac{2t^2}{\sum (b_i-a_i{)}^2}\right)$$

对于任意参数 $s>0$，由指数函数的单调性以及 Markov 不等式

$$P\left(\sum _{i=1}^n{Y}_i\ge t\right)=P\left(e^{s\sum Y_i}\ge e^{st}\right)\le \frac{E\left[e^{s\sum Y_i}\right]}{e^{st}}=e^{-st}E\left[\exp \left(s\sum _{i=1}^n{Y}_i\right)\right]$$

我们发现最后一项 $E\left[\exp \left(s{\sum }_{i=1}^n{Y}_i\right)\right]$ 就是 ${\sum }_{i=1}^n{Y}_i$ 的矩母函数
因为 $X_i$ 是相互独立的，所以 $Y_i$ 也相互独立。由矩母函数的性质: 如果 $X$ 和 $Y$ 是两个相互独立的随机变量，那么 $M_{X+Y}(t)=M_X(t)\cdot M_Y(t)$，因此

$$E\left[\exp \left(s\sum _{i=1}^n{Y}_i\right)\right]=\prod _{i=1}^{n}E[e^{s{Y}_i}]$$

现在由矩母函数 > 矩母函数的估计中的 Hoeffding 引理

$$E[e^{s{Y}_i}]\le \exp \left(\frac{s^2(b-a{)}^2}{8}\right)$$

代入就有

$$\begin{array}{rl}P\left(\sum _{i=1}^n{Y}_i\ge t\right)& \le e^{-st}\prod _{i=1}^n\exp \left(\frac{s^2(b_i-a_i{)}^2}{8}\right)\\ & =\exp \left(-st+\frac{s^2}{8}\sum _{i=1}^n(b_i-a_i{)}^2\right)\end{array}$$

现在我们将括号里的函数看作 $s$ 的函数，其最小值点为 $s=\frac{4t}{\sum (b_i-a_i{)}^2}$，代入即可得到

$$P\left(\sum _{i=1}^n{Y}_i\ge t\right)\le \exp \left(-\frac{2t^2}{\sum (b_i-a_i{)}^2}\right)$$

即

$$P(S_n-E[S_n]\ge t)\le \exp \left(-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right).$$

上面证明的是 $S_n-E[S_n]\ge t$ 的概率，现在考虑另一边的不等式

$$P(S_n-E[S_n]\le -t)=P(-(S_n-E[S_n])\ge t)$$

这只要在之前的过程中，令 ${\sum }_{i=1}^n{Y}_i\to -{\sum }_{i=1}^n{Y}_i$，取值区间长度依然是 $b_i-a_i$，而之前的推导都和 $Y_i$ 无关，因此

$$P(S_n-E[S_n]\le -t)\le \exp \left(-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right).$$

综上

$$P(|S_n-E[S_n]|\ge t)\le 2\exp \left(-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right).$$

---

其他不等式

例

证明

$$|P(AB)-P(A)P(B)|\le \frac{1}{4}$$

令 $X=1_A,Y=1_B$，于是由使用指示函数进行表示的性质
$E(XY)=P(AB)$、$E(X^2)=E(X)=P(A)$、$E(Y^2)=E(Y)=P(B)$， 所以

$$P(AB)-P(A)P(B)=\mathrm{Cov}(X,Y).$$

由前面得到的 Cauchy-Schwarz 不等式

$$|\mathrm{Cov}(X,Y)|\le \sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}=\sqrt{P(A)(1-P(A))P(B)(1-P(B))}.$$

再利用 $x(1-x)\le \frac{1}{4}$，就得到最终的 $\frac{1}{4}$ 上界，并且当 $A=B$ 且 $P(A)=\frac{1}{2}$ 时，左边恰好等于 $\frac{1}{4}$，因此 $\frac{1}{4}$ 为最优系数