大家好,又见面了,我是你们的朋友全栈君。
欢迎前往我的个人博客阅读原文。
解决不能准确计算出概率和期望的问题的有效策略有三种:模拟、约束和近似。模拟,就是使用 Monte Carlo 法模拟,但是模拟结果很容易遭到质疑,而且即使在速度很快的计算机上,模拟也可能需要长时间运行。对概率的约束可以证明概率在一定范围内,界限可能无法给出一个很好的近似,至少可以保证真实值一定是此区间的一个值。极限理论近似法即使用大数定律和中心极限定理处理数据量比较大的情形。
下面给出概率论中的一些不等式约束:
Cauchy-Schwarz 不等式:对联合期望的边际约束
Cauchy-Schwarz 不等式是所有数学公式中最著名的不等式之一。
Cauchy-Schwarz 不等式 对任意的随机变量 X X X 和 Y Y Y , X X X 和 Y Y Y 的方差有限,都有
∣ E ( X Y ) ∣ ≤ E ( X 2 ) E ( Y 2 ) . |E(XY)|\le\sqrt{E(X^2)E(Y^2)}. ∣E(XY)∣≤E(X2)E(Y2).
Proof. 对于任意的 t t t,有
0 ≤ E ( Y − t X ) 2 = E ( Y 2 ) − 2 t E ( X Y ) + t 2 E ( X 2 ) 0\le E(Y-tX)^2=E(Y^2)-2tE(XY)+t^2E(X^2) 0≤E(Y−tX)2=E(Y2)−2tE(XY)+t2E(X2)
下面寻找使不等式最优的 t t t 值,是不等式右边最小:
f ( t ) = t 2 E ( X 2 ) − 2 t E ( X Y ) + E ( Y 2 ) f ′ ( t ) = 2 t E ( X 2 ) − 2 E ( X Y ) = 0 f(t)=t^2E(X^2)-2tE(XY)+E(Y^2)\\f'(t)=2tE(X^2)-2E(XY)=0 f(t)=t2E(X2)−2tE(XY)+E(Y2)f′(t)=2tE(X2)−2E(XY)=0
解得 t = E ( X Y ) E ( X 2 ) t=\cfrac{E(XY)}{E(X^2)} t=E(X2)E(XY)。代入 t t t 的值得,
∣ E ( X Y ) ∣ ≤ E ( X 2 ) E ( Y 2 ) . |E(XY)|\le\sqrt{E(X^2)E(Y^2)}. ∣E(XY)∣≤E(X2)E(Y2).
- 如果 X X X 和 Y Y Y 不相关,那么 E ( X Y ) = E ( X ) E ( Y ) E(XY)=E(X)E(Y) E(XY)=E(X)E(Y), E ( X Y ) E(XY) E(XY) 只取决于边际期望 E ( X ) E(X) E(X) 和 E ( Y ) E(Y) E(Y)。
- 如果 X X X 和 Y Y Y 的均值是 0,即当 E ( X ) = E ( Y ) = 0 E(X)=E(Y)=0 E(X)=E(Y)=0 时, E ( X Y ) = C o v ( X , Y ) E(XY)=Cov(X,Y) E(XY)=Cov(X,Y), E ( X 2 ) = V a r ( X ) E(X^2)=Var(X) E(X2)=Var(X), E ( Y 2 ) = V a r ( Y ) E(Y^2)=Var(Y) E(Y2)=Var(Y),所以化简 Cauchy-Schwarz 不等式,可得 ∣ ρ X Y ∣ ≤ 1 |\rho_{XY}|\le1 ∣ρXY∣≤1。那么 Cauchy-Schwarz 不等式的统计解释为: X X X 和 Y Y Y 的相关系数介于 − 1 -1 −1 和 1 1 1 之间。
- 将 X X X 写作 X = X ⋅ 1 X=X\cdot1 X=X⋅1,则由 Cauchy-Schwarz 不等式,可得 ∣ E ( X ⋅ 1 ) ∣ ≤ E ( X 2 ) E ( Y 2 ) |E(X\cdot1)|\le\sqrt{E(X^2)E(Y^2)} ∣E(X⋅1)∣≤E(X2)E(Y2),化简得 E ( X 2 ) ≥ ( E X ) 2 E(X^2)\ge(EX)^2 E(X2)≥(EX)2,这便为方差非负提供了一种快速证明的方法。
- 二阶矩法: P ( X > 0 ) ≥ ( E X ) 2 E ( X 2 ) P(X>0)\ge\cfrac{(EX)^2}{E(X^2)} P(X>0)≥E(X2)(EX)2 或 P ( X = 0 ) ≤ V a r ( X ) E ( X 2 ) P(X=0)\le\cfrac{Var(X)}{E(X^2)} P(X=0)≤E(X2)Var(X)。
- Cauchy-Schwarz 不等式允许由边际矩母函数的存在推断出联合矩母函数的存在。
关于凸性的 Jensen 不等式
对于非线性函数 g g g, E g ( X ) Eg(X) Eg(X) 可能不同于 g ( E X ) g(EX) g(EX)。如果 g g g 是一个凸函数或凹函数,那么 Jensen 函数将告诉我们 E g ( X ) Eg(X) Eg(X) 和 g ( E X ) g(EX) g(EX) 哪个更大。
Jensen 不等式 设 X X X 是一个随机变量。如果 g g g 是一个凸函数,那么 E g ( X ) ≥ g ( E X ) Eg(X)\ge g(EX) Eg(X)≥g(EX)。如果 g g g 是一个凹函数,那么 E g ( X ) ≤ g ( E X ) Eg(X)\le g(EX) Eg(X)≤g(EX)。在这两种情况下,等号成立的唯一条件是,存在常数 a a a 和 b b b,使 g ( X ) = a + b X g(X)=a+bX g(X)=a+bX 的概率是 1。
Proof. 如果 g g g 是凸函数,那么所有与 g g g 相切的直线都在 g g g 的下方。特别地,令 μ = E ( X ) \mu=E(X) μ=E(X),并考虑点 ( μ , g ( μ ) ) (\mu,g(\mu)) (μ,g(μ)) 处 的切线。用 a + b x a+bx a+bx 表示这条切线,则 g ( x ) ≥ a + b x g(x)\ge a+bx g(x)≥a+bx,对定义域内的所有 x x x 都成立。
对两边同时取数学期望,有
E g ( X ) ≥ E ( a + b X ) = a + b E ( X ) = a + b μ = g ( μ ) = g ( E X ) Eg(X)\ge E(a+bX)=a+bE(X)=a+b\mu=g(\mu)=g(EX) Eg(X)≥E(a+bX)=a+bE(X)=a+bμ=g(μ)=g(EX)
如果 g g g 是凹函数,那么 h = − g h=-g h=−g 是凸函数,所以可以应用上述对 h h h 的证明,看到关于凹函数 g g g 的不等式的
不等号方向与凹函数情况中的相反。
最后,假设等号对凸函数成立。令 Y = g ( X ) − a − b X Y=g(X)-a-bX Y=g(X)−a−bX。 Y Y Y 是一个非负的随机变量,且 E ( Y ) = 0 E(Y)=0 E(Y)=0,所
以 P ( Y = 0 ) = 1 P(Y=0)=1 P(Y=0)=1。所以,当且仅当 P ( g ( X ) = a + b X ) = 1 P(g(X)=a+bX)=1 P(g(X)=a+bX)=1 时等号成立。
对于凹函数的情况,可以令 Y = a + b X − g ( X ) Y=a+bX-g(X) Y=a+bX−g(X),然后用相同的方法证得。
- 由 Jensen 不等式容易得到
- E ∣ X ∣ ≥ ∣ E X ∣ E|X|\ge|EX| E∣X∣≥∣EX∣;
- E ( 1 X ) ≥ 1 E X E\left(\cfrac{1}{X}\right)\ge\cfrac{1}{EX} E(X1)≥EX1,对于正的随机变量 X X X;
- E ( ln X ) ≤ ln ( E X ) E(\ln X)\le\ln(EX) E(lnX)≤ln(EX),对于正的随机变量 X X X;
- 如果用数据集的样本标准差估计未知的标准差,那么可以用 Jensen 不等式来观察偏差的正负;
- 在信息理论,Jensen 不等式的一个重要应用是关于如何量化信息的研究。
Markov 不等式,Chebyshev 不等式,Chernoff 不等式:尾概率的界限
Markov 不等式 对任意随机变量 X X X 和常数 a > 0 a>0 a>0,有 P ( ∣ X ∣ ≥ a ) ≤ E ( X ) a P(|X|\ge a)\le\cfrac{E(X)}{a} P(∣X∣≥a)≤aE(X)。
Proof. 令 Y = ∣ X ∣ a Y=\cfrac{|X|}{a} Y=a∣X∣,则需要证明 P ( Y ≥ 1 ) ≤ E ( Y ) P(Y\ge1)\le E(Y) P(Y≥1)≤E(Y)。
注意到 I ( Y ≥ 1 ) ≤ Y I(Y\ge1)\le Y I(Y≥1)≤Y,因为如果 I ( Y ≥ 1 ) = 0 I(Y\ge1)=0 I(Y≥1)=0,那么 Y ≥ 0 Y\ge0 Y≥0;如果 I ( Y ≥ 1 ) = 1 I(Y\ge1)=1 I(Y≥1)=1,那么 Y ≥ 1 Y\ge1 Y≥1。
在不等式两边同时取期望,得 Markov 不等式。
- Markov 不等式是一个非常粗糙的约束,因为它不需要对 X X X 作出假定。不等式的右边可能大于 1 1 1,甚至可能无穷大。
Chebyshev 不等式 令 X X X 的均值为 μ \mu μ,方差为 σ 2 \sigma^2 σ2,那么对任何一个 a > 0 a>0 a>0,有 P ( ∣ X − μ ∣ ≥ a ) ≤ σ 2 a 2 P(|X-\mu|\ge a)\le\cfrac{\sigma^2}{a^2} P(∣X−μ∣≥a)≤a2σ2。
Proof. 根据 Markov 不等式,可得
P ( ∣ X − μ ∣ ≥ a ) = P ( ( X − μ ) 2 ≥ a 2 ) ≤ E ( X − μ ) 2 a 2 = σ 2 a 2 . P(|X-\mu|\ge a)=P((X-\mu)^2\ge a^2)\le\frac{E(X-\mu)^2}{a^2}=\frac{\sigma^2}{a^2}. P(∣X−μ∣≥a)=P((X−μ)2≥a2)≤a2E(X−μ)2=a2σ2.
- 用 c σ c\sigma cσ 代替 a a a,由于 c > 0 c>0 c>0,则有以下 Chebyshev 不等式等价形式
P ( ∣ X − μ ∣ ≥ c σ ) ≤ 1 c 2 . P(|X-\mu|\ge c\sigma)\le\frac{1}{c^2}. P(∣X−μ∣≥cσ)≤c21.
这给出了随机变量偏离其均值 c c c 倍标准差的概率的上限。
Chernoff 不等式 对任意随机变量 X X X、常数 a > 0 a>0 a>0 和 t > 0 t>0 t>0,有
P ( X ≥ a ) ≤ E ( e t X ) e t a . P(X\ge a)\le\frac{E(e^{tX})}{e^{ta}}. P(X≥a)≤etaE(etX).
Proof. 变换 g ( x ) = e t x g(x)=e^{tx} g(x)=etx 是可逆且严格递增的函数,因此,由 Markov 不等式,可得
P ( X ≥ a ) = P ( e t X ≥ e t a ) ≤ E ( e t X ) e t a . P(X\ge a)=P(e^{tX}\ge e^{ta})\le\frac{E(e^{tX})}{e^{ta}}. P(X≥a)=P(etX≥eta)≤etaE(etX).
- Chernoff 不等式有两个非常好的性质:
- 不等号右边可以关于 t t t 进行优化,并给出严格的上界,如 Cauchy-Schwarz 不等式的证明;
- 如果 X X X 的矩母函数存在,那么分子的界限就是矩母函数,且可以利用矩母函数的一些有用性质。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/145087.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...