摘要: 概率方法的应用,Cr不等式
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
概率方法是证明不等式的一个有力方法,此前我们介绍过很多相关的例子。可以参考下面这些文章:
- Weierstrass不等式,概率方法的威力
- Schweitzer不等式,概率方法的威力
- 一个微分不等式,概率方法的威力
- 概率方法的威力:由数学期望的性质推导出不等式
- 概率方法证明不等式:构造随机变量,将不等式中的项解释为事件的概率
概率方法中的一种思考路径是,构造随机变量,使得原不等式的项可以凑成期望、方差、协方差等数字特征,然后用期望、方差、协方差的性质得到原不等式成立。
本文我们看一个在概率论中很有用的不等式,即 Cr 不等式,该不等式与随机变量的 r 阶绝对矩 E|ξ|r 有关。
对于随机变量序列 ξn,我们可以定义它的各种收敛,比如“几乎处处收敛”,“依概率收敛”,“依分布收敛”等。有时我们想考察随机变量序列 ξn 与一个特定随机变量 ξ 的偏差 |ξn−ξ| 的收敛性质。r 阶绝对矩 E|ξn−ξ|r 可以作为衡量这种收敛性的一个参考指标,称为 r 次平均收敛。
r 次平均收敛的讨论范围自然是 ξn−ξ 的 r 阶绝对矩 E|ξn−ξ|r 有限的随机变量,所有这些随机变量构成了一个函数类,在这个函数类中按照一定方式定义距离,可以作成一个度量空间,记为 Lr。随机变量序列 ξn 的 r 次平均收敛等价于 Lr 空间中的函数列按距离的收敛。
本文我们不展开这样深刻的结论,只讨论 Cr 不等式以及应用概率方法的证明过程,后续我们可以介绍一下这样的度量空间如何构造。
前面我们提到了,概率方法的一种流程是构造随机变量后将不等式的项凑成期望、方差等数字特征的性质,这里我们会凑出一个期望的 Holder 不等式,因此我们先回顾一下数学期望的 Holder 不等式。
期望的 Holder 不等式
若 r>1,1r+1s=1,则对任意的随机变量 ξ,η 都有:
E|ξη|≤(E|ξ|r)1r(E|η|s)1s仅当存在两个不全为 0 的常数 a,b 使得 P(a|ξ|r+b|η|s=0)=1 时。
以上就是期望的 Holder 不等式,在文章 一个微分不等式,概率方法的威力 中我们使用过该不等式,并且介绍了该不等式的证明。
Cr 不等式
Cr 不等式最简单的情况是数列只有两个项的时候。
定理(Cr不等式)
若 a,b∈R,r>0,则 (|a|+|b|)r≤Cr(|a|r+|b|r),其中:
Cr={10<r≤12r−1r>1该不等式可以通过构造函数,研究其单调性、凸性来得到。当 0<r≤1 时,考察 f(t)=(1+t)r−tr−1 的单调性,然后再令 t=ba,(a≠0) 即可。当 r>1 时,考察 g(x)=|x|r 的凸性,即可得 (|a|+|b|2)r<12(|a|r+|b|r)。
下面我看 n 个项的数列的 Cr 不等式。
定理(Cr不等式)
若 ak∈R,r>0,则 (n∑k=1|ak|)r≤Crn∑k=1|ak|r,其中:
Cr={10<r≤1nr−1r>1取等条件:当 r>1 时为 |a1|=|a2|=⋯=|an|;r=1 时为 a1,⋯,an 同号;0<r<1 时为 a1,⋯,an 中至多一个不为 0。
证明(概率方法)
首先看 r>1 的情况。
设 ξ 为以概率 1n 取 a1,⋯,an 的随机变量,则:
E|ξ|=1n(|a1|+⋯+|an|)E|ξ|r=1n(|a1|r+⋯+|an|r)由 Holder 不等式 E|ξη|≤(E|ξ|r)1r(E|η|s)1s,取 η=1,有:
E|ξ|=E|ξη|≤(E|ξ|r)1r(E|η|s)1s=(E|ξ|r)1r代入后就得到:
1n(|a1|+⋯+|an|)≤(1n(|a1|r+⋯+|an|r))1r也就是:
(|a1|+⋯+|an|)r≤nr−1(|a1|r+⋯+|an|r)由 Holder 不等式的取等条件:存在两个不全为 0 的常数 a,b 使得 P(a|ξ|r+b|η|s=0)=1。也就是 ξ 与 η 几乎处处成比例。而 η=1,因此 ξ 需要几乎处处都是相同的值,也就是 |a1|=|a2|=⋯=|an|。
对于 r≤1 的情况,只需要考虑 a1,⋯,an 不全为 0 的情形,由于 r≤1,对于 k=1,2,⋯,n 均有以下不等式:
|ak||a1|+⋯+|an|≤|ak|r(|a1|+⋯+|an|)r将以上不等式相加,即得:
(|a1|+⋯+|an|)r≤(|a1|r+⋯+|an|r)最后考虑取等条件,由绝对值的性质得,当 r=1 时,等号成立的条件是 a1,⋯,an 同号。当 r<1 时,等号成立的条件为 a1,⋯,an 至多一个不为零。
◻
期望的 Cr 不等式
类似于数学期望的 Holder 不等式,Cr 不等式也有数学期望的形式。设 ξ1,⋯,ξn 为随机变量,则:
E|ξ1+⋯+ξn|r≤Cr(E|ξ1|r+⋯+E|ξn|r)其中 Cr 与数列形式的 Cr 不等式一样:
Cr={10<r≤1nr−1r>1取等条件也可以从数列形式的 Cr 不等式得到。
总结
Holder 不等式给出了两个随机变量乘积的期望的上界,当两个随机变量几乎处处成比例时,乘积的期望达到最大,这在优化和统计推断中会用到。
Cr 不等式说明了如果 ξ1,⋯,ξn 的 r 阶绝对矩有限,则它们的和 ξ1+⋯+ξn 的 r 阶绝对矩也有限。