数学-重要不等式

Mar 21, 2020 · 数学  ·
分享到:

重要不等式

数学分析

伯努利不等式

对任意整数\(n\geq 0\)，和任意实数\(x\geq -1\)， \[ (1+x)^{n}\geq 1+nx \] 如果\({\displaystyle n\geq 0}\)且是偶数，则不等式对任意实数\(x\)成立。

证明：伯努利不等式可以用数学归纳法证明。

切比雪夫总和不等式

数学上的切比雪夫总和不等式以切比雪夫命名，可用以比较两组数积的和及两组数的线性和的积的大小： \[ 若a_{1}\geq a_{2}\geq \cdots \geq a_{n}且b_{1}\geq b_{2}\geq \cdots \geq b_{n}，则：\\ n\sum _{k=1}^{n}a_{k}b_{k}\geq \left(\sum_{k=1}^{n}a_{k}\right)\left(\sum_{k=1}^{n}b_{k}\right)\geq n\sum_{k=1}^{n}a_{k}b_{n+1-k} \] 上式同时除以\(n^2\)也可以写作 \[ {\frac {1}{n}}\sum _{k=1}^{n}a_{k}b_{k}\geq \left({\frac {1}{n}}\sum_{k=1}^{n}a_{k}\right)\left({\frac{1}{n}}\sum_{k=1}^{n}b_{k}\right)\geq {\frac {1}{n}}\sum_{k=1}^{n}a_{k}b_{n+1-k} \] 它是由排序不等式而来。

证明：设\(a_{1}\geq a_{2}\geq \cdots \geq a_{n}\)且\(b_{1}\geq b_{2}\geq \cdots \geq b_{n}\)，由排序不等式可知，最大的和为顺序和： \[ {\displaystyle a_{1}b_{1}+\cdots +a_{n}b_{n}} \] 于是： \[ {\displaystyle a_{1}b_{1}+\cdots +a_{n}b_{n}=a_{1}b_{1}+a_{2}b_{2}+\cdots +a_{n}b_{n}}\\ {\displaystyle a_{1}b_{1}+\cdots +a_{n}b_{n}\geq a_{1}b_{2}+a_{2}b_{3}+\cdots +a_{n}b_{1}}\\ {\displaystyle a_{1}b_{1}+\cdots +a_{n}b_{n}\geq a_{1}b_{3}+a_{2}b_{4}+\cdots +a_{n}b_{2}}\\ \vdots\\ {\displaystyle a_{1}b_{1}+\cdots +a_{n}b_{n}\geq a_{1}b_{n}+a_{2}b_{1}+\cdots +a_{n}b_{n-1}} \] 将这\(n\)个不等式分边相加，同时对右边进行因式分解，便得到： \[ {\displaystyle n(a_{1}b_{1}+\cdots +a_{n}b_{n})\geq (a_{1}+\cdots +a_{n})(b_{1}+\cdots +b_{n})} \] 两边都除以\(n^{2}\)，就得到切比雪夫综合不等式的第一个不等号： \[ {\displaystyle {\frac {(a_{1}b_{1}+\cdots +a_{n}b_{n})}{n}}\geq {\frac {(a_{1}+\cdots +a_{n})}{n}}\cdot {\frac {(b_{1}+\cdots +b_{n})}{n}}} \] 同理，右边的不等号可由最小的和为逆序和推得。

切比雪夫不等式总和的积分形式

若\(f\)和\(g\)是区间\([0,1]\)上的可积的实函数，并且两者都是递增或两者都是递减的，则： \[ {\displaystyle \int fg\geq \int f\int g} \] 上式可推广到任意区间。

闵可夫斯基不等式(\(L^{p}(S)\)中的三角不等式K)

闵可夫斯基不等式（Minkowski inequality）表明\(L^p\)空间是一个赋范向量空间。设\(S\)是一个度量空间，\(1\leq p\leq \infty ,f,g\in L^{p}(S)\)，那么\(f+g\in L^{p}(S)\)，我们有： \[ \|f+g\|_{p}\leq \|f\|_{p}+\|g\|_{p} \] 如果\(1<p<\infty\)，等号成立当且仅当\(\exists k\geq 0,f=kg\)，或者\(g=kf\).闵可夫斯基不等式是\(L^{p}(S)\)中的三角不等式。它可以用赫尔德不等式来证明。

代数

排序不等式

排序不等式是数学上的一条基础不等式。它可以推导出很多有名的不等式，其内容如下:

如果 \[ \begin{aligned} &{\displaystyle x_{1}\leq x_{2}\leq \cdots \leq x_{n}}和{\displaystyle y_{1}\leq y_{2}\leq \cdots \leq y_{n}}是两组实数。而\\ &{\displaystyle x_{\sigma (1)},\ldots ,x_{\sigma (n)}}是{\displaystyle x_{1},\ldots ,x_{n}}的任意一个排列。 \end{aligned} \] 排序不等式指出: \[ {\displaystyle x_{1}y_{1}+\cdots +x_{n}y_{n}\geq x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}\geq x_{n}y_{1}+\cdots +x_{1}y_{n}}。 \] 以文字可以说成是顺序和不小于乱序和，乱序和不小于逆序和。这个不等式有一点强大在于，完全和符号无关。

排序不等式可以用数学归纳法证明。关键在于下列结果：

若\(x_{i}\leq x_{j},\,y_{i}\leq y_{j}\)，则有 \[ {\displaystyle (x_{j}-x_{i})(y_{j}-y_{i})\geq 0} \] 移项得出 \[ {\displaystyle x_{i}y_{i}+x_{j}y_{j}\geq x_{j}y_{i}+x_{i}y_{j}}。 \] 重复以上步骤便可得出排序不等式。

杨氏不等式

杨氏不等式，指出：假设\(a, b, p 和q\)是正实数 ，且有\(\frac{1}{p}+\frac{1}{q} = 1\)，那么： \[ {\displaystyle ab\leq {\frac {a^{p}}{p}}+{\frac {b^{q}}{q}}.} \] 等号成立当且仅当\({\displaystyle a^{p}=b^{q}}\)，因为这时 \[{\displaystyle ab=a(b^{q})^{1 \over q}=aa^{p \over q}=a^{p}={a^{p} \over p}+{b^{q} \over q}}\] 杨氏不等式是加权算术－几何平均值不等式的特例，杨氏不等式是证明赫尔德不等式的一个快捷方法。该不等式以威廉·亨利·杨命名。

证明：我们知道函数\({\displaystyle f(x)=e^{x}}\)是一个凸函数， 因为它的二阶导数恒为正。 从而我们有： \[{\displaystyle ab=e^{\ln(a)}e^{\ln(b)}=e^{{1 \over p}\ln(a^{p})+{1 \over q}\ln(b^{q})}\leq {1 \over p}e^{\ln(a^{p})}+{1 \over q}e^{\ln(b^{q})}={a^{p} \over p}+{b^{q} \over q}}\] 这里我们使用了凸函数的一个性质：对任意\(t\)，若\(0 < t <1\)，则有： \[{\displaystyle f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)}\]

柯西不等式

柯西-施瓦茨不等式，又称施瓦茨不等式或柯西-布尼亚科夫斯基-施瓦茨不等式，是一条很多场合都用得上的不等式；例如线性代数的矢量，数学分析的无穷级数和乘积的积分，和概率论的方差和协方差。它被认为是最重要的数学不等式之一。它有一些推广，如赫尔德不等式。

柯西-施瓦茨不等式叙述，对于一个内积空间所有向量\(x\)和\(y\)， \[ \big| \langle x,y\rangle \big|^2 \leq \langle x,x\rangle \cdot \langle y,y\rangle\] 其中\(\langle\cdot,\cdot\rangle\)表示内积，也叫点积。等价地，将两边开方，引用向量的范数，不等式可写为 \[ |\langle x,y\rangle| \leq \|x\| \cdot \|y\|.\,\] 另外，等式成立当且仅当\(x\)和\(y\)线性相关。

柯西不等式有大量的特例形式与推广，这里不一一列举。

内斯比特不等式

内斯比特不等式是数学的一条不等式，它说对任何正实数\(a,b,c\)，都有： \[ {\displaystyle {\frac {a}{b+c}}+{\frac {b}{a+c}}+{\frac {c}{a+b}}\geq {\frac {3}{2}}.} \]

平均数不等式

平均数不等式，或称平均值不等式、均值不等式，是数学上的一组不等式，也是基本不等式的推广。它是说：

如果\(x_{1},x_{2},\ldots ,x_{n}\)是正数，则 \[ H_n \le G_n \le A_n \le Q_n \] 当且仅当\(x_{1}=x_{2}=\cdots =x_{n}\)，等号成立。

用文字描述即对这些正数：调和平均数 ≤ 几何平均数 ≤ 算术平均数 ≤ 平方平均数（方均根）

马勒不等式

马勒不等式陈述说由两个无穷正项序列的对应项的和构成序列的几何均值大于或等于这两个无穷序列几何均值的和: \[ {\displaystyle \prod _{k=1}^{n}(x_{k}+y_{k})^{1/n}\geq \prod_{k=1}^{n}x_{k}^{1/n}+\prod_{k=1}^{n}y_{k}^{1/n}} \] 其中, 对任何的\(k, x_k, y_k > 0\).

证明：由均值不等式, 有: \[ {\displaystyle \prod _{k=1}^{n}\left({x_{k} \over x_{k}+y_{k}}\right)^{1/n}\leq {1 \over n}\sum _{k=1}^{n}{x_{k} \over x_{k}+y_{k}},} \] 和 \[ {\displaystyle \prod _{k=1}^{n}\left({y_{k} \over x_{k}+y_{k}}\right)^{1/n}\leq {1 \over n}\sum _{k=1}^{n}{y_{k} \over x_{k}+y_{k}}.}\] 因此, \[ {\displaystyle \prod _{k=1}^{n}\left({x_{k} \over x_{k}+y_{k}}\right)^{1/n}+\prod _{k=1}^{n}\left({y_{k} \over x_{k}+y_{k}}\right)^{1/n}\leq {1 \over n}n=1.} \] 两边同乘以分母项后即得结论.

线性矩阵不等式

线性矩阵不等式是凸优化中，具有形式： \[ {\displaystyle \operatorname {LMI} (y):=A_{0}+y_{1}A_{1}+y_{2}A_{2}+\cdots +y_{m}A_{m}\geq 0\,} \] 的表达式, 其中,

  • \({\displaystyle y=[y_{i}\,,~i\!=\!1,\dots ,m]}\)是一个实向量
  • \({\displaystyle A_{0},A_{1},A_{2},\dots ,A_{m}}\)是 \(n\times n\)的实对称矩阵\({\mathbb {S}}^{n}\)
  • \(B\geq 0\)是广义的不等式，意思是在\(\mathbb S^{n}\)的半正定子空间\(\mathbb {S}_{+}\)内，\(B\)是半正定矩阵。

线性矩阵不等式表示\(y\)的凸集限制条件。

几何

三角不等式

三角不等式是数学上的一个不等式，表示从A到B再到C的距离永不少于从A到C的距离；亦可以说是两项独立物件的量之和不少于其和的量。

  • 在三角形ABC中，这个式子用标量可以写作\({\displaystyle {\overline {AB}}+{\overline {BC}}\geq {\overline {AC}}}\)。用向量的写法，这个不等式可以写成：\({\displaystyle \left|{\overrightarrow {AC}}\right|\leq \left|{\overrightarrow {AB}}\right|+\left|{\overrightarrow {BC}}\right|}\)
  • 在实数中，此式依然成立：\(\left|a+b\right|\leq \left|a\right|+\left|b\right|\)。
  • 在\({\displaystyle L^{p}(S)}\)中是闵科夫斯基不等式。

外森比克不等式

外森比克不等式（Weitzenböck's inequality）是有关三角形边长和面积的一个不等式。设三角形的边长为\(a,b,c\)，面积为\(A\)，则外森比克不等式声称 \[a^2+b^2+c^2 \ge 4 \sqrt{3} A\] 成立。当且仅当三角形为等边三角形，等号成立。佩多不等式是外森比克不等式的推广。

阿达马不等式

数学中的阿达马不等式从上限制了n维欧几里得空间中，由\(n\)支向量\({\mathbf {v}}_{1}, {\mathbf {v}}_{2}, \ldots \mathbf {v} _{n}\)标出的体积。

这不等式的几何意义是当向量为正交集时体积最大。

概率与统计

集中不等式

集中不等式是数学中的一类不等式，描述了一个随机变量是否集中在某个取值附近。例如大数定律说明了一系列独立同分布随机变量的平均值在概率上趋近于它们的数学期望，这表示随着变量数目增大，平均值会集中在数学期望附近。

马尔可夫不等式

在概率论中，马尔可夫不等式给出了随机变量的函数大于等于某正数的概率的上界。马尔可夫不等式把概率关联到数学期望，给出了随机变量的累积分布函数一个宽泛但仍有用的界，例如不超过1/5的人口会有超过5倍于人均收入的收入。

设\(X\)是一个非负随机变量，\(\varepsilon>0\)为正实数，则有 \[ P(X>\varepsilon) \leq \frac{E(X)}{\varepsilon} \] 证明： \[{\begin{aligned} {\textrm {E}}(X)&=\int_{-\infty }^{\infty }xf(x)dx\\ &=\int_{0}^{\infty }xf(x)dx\\ &\geq \int_{\varepsilon}^{\infty }xf(x)dx\\ &\because x > \varepsilon, \forall x \in (\varepsilon,\infty)\\ &\geq \int_{\varepsilon}^{\infty }\varepsilon f(x)dx\\ &=\varepsilon\int _{\varepsilon}^{\infty }f(x)dx\\ &=\varepsilon{\textrm {P}}(X\geq \varepsilon). \end{aligned}}\] 离散情形下证明类似。

对于单调增加函数的扩展版本:

若\(φ\)是定义在非负实数上的单调增加函数，且其值非负，\(X\)是一个随机变量，\(\varepsilon ≥ 0，且φ(\varepsilon) > 0\)，则 \[ {\displaystyle \mathbb {P} (|X|\geq \varepsilon)\leq {\frac {\mathbb {E} (\varphi (|X|))}{\varphi (\varepsilon)}}} \]

切比雪夫不等式

切比雪夫不等式（英语：Chebyshev's Inequality）显示了随机变量的“几乎所有”值都会“接近”平均。

切比雪夫不等式对任何分布形状的数据都适用，但是需要随机变量的期望、方差都存在。可表示为：对于任意\(b>0\)，有： \[ {\displaystyle P(|X-E(X)|\geq \varepsilon)\leq {\frac {Var(X)}{\varepsilon^{2}}}} \] 反过来写就是 \[ {\displaystyle P(|X-E(X)|\leq \varepsilon)\geq 1-{\frac {Var(X)}{\varepsilon^{2}}}} \]

在概率论中，还有一种等价表述：

设\(X\)为随机变量，期望值为\(\mu\)，标准差为\(\sigma\)。对于任何实数\(k>0\)， \[ P(\left|X-\mu \right|\geq k\sigma )\leq {\frac {1}{k^{2}}}. \]

证明：可从马尔可夫不等式直接证明：马氏不等式说明对任意随机变量\(Y\)和正数\(a\)有\(\Pr(|Y|>a)\leq \operatorname {E}(|Y|)/a\)。取\(Y=(X-\mu )^{2}\)及\(a=(k\sigma )^{2}\)可证。

霍夫丁不等式

霍夫丁不等式适用于有界的随机变量。设有两两独立的一系列随机变量\(X_{1},\dots ,X_{n}\)。假设对所有的\(1 \leq i\leq n\)，\(X_{i}\)都是几乎有界的变量，即满足： \[ {\displaystyle \mathbb {P} (X_{i}\in [a_{i},b_{i}])=1.} \] 那么这\(n\)个随机变量的经验期望： \[ {\overline {X}}={\frac {X_{1}+\cdots +X_{n}}{n}} \] 满足以下的不等式: \[ {\displaystyle \mathbb {P} ({\overline {X}}-\mathbb {E} [{\overline {X}}]\geq t)\leq \exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),} \] \[ {绝对值：\displaystyle \mathbb {P} (|{\overline {X}}-\mathbb {E} [{\overline {X}}]|\geq t)\leq 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),} \]

Efron–Stein不等式

Efron–Stein不等式给出了随机变量方差的一个上限估计。设有两两独立的随机变量\(X_{1}\dots X_{n}\)和\(X_{1}'\dots X_{n}'\)，并且对所有的\(i\)，\(X_{i}'\)与\(X_{i}\)有着相同的分布。那么令 \[{\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n})}\] 则有 \[\mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum_{i=1}^{n}E[(f(X)-f(X^{(i)}))^{2}]. \]

布尔不等式

布尔不等式（Boole's inequality），由乔治·布尔提出，指对于全部事件的概率不大于单个事件的概率总和。这是一个很平凡的不等式，但是很长时间内没有给出严格证明。

对于事件\(A_1、A_2、A_3、......\)： \[P(\bigcup_{{i}}A_{i})\leq \sum_{i}P(A_{i})\] 在测度论上，布尔不等式满足\(σ\)次可加性。

琴生(Jensen)不等式(凸函数相关)

琴生不等式（Jensen's inequality）给出积分的凸函数值和凸函数的积分值间的关系。琴生不等式有以下推论：过一个凸函数上任意两点所作割线一定在这两点间的函数图象的上方，即： \[tf(x_{1})+(1-t)f(x_{2})\geq f\left(tx_{1}+(1-t)x_{2}\right),0\leq t\leq 1.\]

琴生不等式可以用测度论或概率论的语言给出。这两种方式都表明同一个很一般的结果。

测度论的版本

假设\(\mu\)是集合\(\Omega\)的正测度，使得\(\mu (\Omega )=1\)。若\(g\)是勒贝格可积的实值函数，而\(\varphi\)是在\(g\)的值域上定义的凸函数，则 \[ \varphi \left(\int_{{\Omega}}g\,d\mu \right)\leq \int_{\Omega }\varphi \circ g\,d\mu \]

概率论的版本

以概率论的名词，\(\mu\)是个概率测度。函数\(g\)换作实值随机变数\(X\)（就纯数学而言，两者没有分别）。在\(\Omega\)空间上，任何函数相对于概率测度\(\mu\)的积分就成了期望值。这不等式就说，若\(\varphi\)是任一凸函数，则 \[ \varphi \left(E(X)\right)\leq E(\varphi (X)) \]

赫尔德(holder)不等式

赫尔德不等式是数学分析的一条不等式，取名自奥托·赫尔德(Otto Hölder)。这是一条揭示\(L^p\)空间的相互关系的基本不等式：

设\(S\)为测度空间，\(1\leq p,q\leq \infty\)，及\({1 \over p}+{1 \over q}=1\)，设\(f\)在\(L^{p}(S)\)内，\(g\)在\(L^{q}(S)\)内。则\(f g\)在\(L^{1}(S)\)内，且有 \[ \|fg\|_{1}\leq \|f\|_{p}\|g\|_{q}。 \] 若\(S\)取作\(\{1,...,n\}\)附计数测度，便得赫尔德不等式的特殊情形：对所有实数（或复数）\(x_{1},...,x_{n};y_{1},...,y_{n}\)，有 \[ \sum_{{k=1}}^{n}|x_{k}y_{k}|\leq \left(\sum_{{k=1}}^{n}|x_{k}|^{p}\right)^{{1/p}}\left(\sum_{{k=1}}^{n}|y_{k}|^{q}\right)^{{1/q}}。 \] 我们称p和q互为赫尔德共轭。(感觉会用于范数的证明)。

当\(p = q = 2\)，便得到柯西-施瓦茨不等式。赫尔德不等式可以证明\(L^p\)空间上一般化的三角不等式，闵可夫斯基不等式。

证明：一般通过杨氏不等式证明。

信息论

吉布斯不等式(相对熵)

若\(\sum _{i=1}^{n}p_{i}=\sum _{i=1}^{n}q_{i}=1\)，且\(p_{i},q_{i}\in (0,1]\)，则有： \[ -\sum _{i=1}^{n}p_{i}\log p_{i}\leq -\sum_{i=1}^{n}p_{i}\log q_{i} \] 等号成立当且仅当\(\forall i, p_{i}=q_{i}\)。

吉布斯不等式等价于： \[ 0\leq -\sum_{i=1}^{n}p_{i}\log q_{i}-(-\sum_{i=1}^{n}p_{i}\log p_{i})=\sum _{i=1}^{n}p_{i}\log(p_{i}/q_{i})=D_{\mathrm {KL} }(P\|Q) \] 文字解释就是：\(0 \leq 交叉熵-熵 = 相对熵\)。

克拉夫特不等式

在编码理论，克拉夫特不等式给出了一个码字长度集合存在唯一可解编码/单义可译码（uniquely decodable code）的必要条件。因为这个不等式在前缀码和树上面应用很多，所以在计算机科学和信息学中很常用。

克拉夫特不等式对码字限制长度以保证前缀编码的可能性。这个不等式说明码字长度指数的倒数的分布和概率质量函数很相似。

  • 如果克拉夫特不等式中严格成立，相应的编码有冗余（redundancy）。
  • 如果克拉夫特不等式中等式成立，相应的编码被称作complete code。
  • 如果克拉夫特不等式不成立，相应的编码不是唯一可解编码（uniquely decipherable）。

设符号表中的原始符号为\(S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}\) 在大小为\(r\)的字符集上编码为唯一可解编码的码字长度为 \[\ell_{1},\ell_{2},\ldots ,\ell_{n}.\] 则 \[ {\displaystyle \sum _{i=1}^{n}r^{-\ell_{i}}\leqslant 1.} \] 反之, 给定一个满足上述不等式的自然数集合\(\ell_{1},\ell_{2},\ldots ,\ell_{n}\), 则在大小为\(r\)字符集上，存在一组唯一可解编码符合相应的码字长度。