新浪博客

Jensen 不等式的证明

2014-01-03 23:39阅读：

http://blog.sina.cn/dpool/blog/u/1581965157

Jensen 不等式：f( E[x]) <= E[ f(x) ]，定理详细内容请参考维基。

在证明 Jensen 不等式之前，先介绍两点，一个是 仿射组合， 一个是关于证明的一个引理。


1. 仿射组合

Jensen <wbr>不等式的证明

目前比较常用用来表示线段的方式是 y = ax + b , x ∈ (x0, x1) 这种形式，在这里，介绍另一种表示线段的形式，也就是《
算法导论》里说的仿射组合。

设线段的两个端点分别为 p 、q ， 那么可以用
ap + bq , (a+b=1, a、b >= 0)
来表示一条两个端点分别为 p、q 的线段。特别的，当 a、b ∈ R 时，表示一条穿过点 p、q 的直线。

2. 证明用到的一个引理

引理所说的是这样一个不等式：
假设 f(x) 是一个关于 x 的凸函数，x = {x1, x2, ... , xn}, a = {a1, a2 , ..., an }， an >= 0, n ∈ N, 且 a1 + a2 + ... + an = 1，那么
Jensen <wbr>不等式的证明

关于凸函数有一条重要的性质：
假设 f(x) 是一个关于 x 的凸函数， x1, x2 在 f(x) 的定义域内， a、b >= 0，且 a+b=1，那么
f( ax1 + bx2 ) <= af(x1) + bf(x2)
Jensen <wbr>不等式的证明



现在用归纳法来证明这个引理：

Jensen <wbr>不等式的证明因此，引理得证。

3. 证明Jensen 不等式：f( E[X] ) <= E[ f(x) ]

因为 Jensen 不等式的右边 E[ f(x) ] 是 f(x) 等于某个特定值的概率，而不是 x 等于某个特定值的概率， 所以
Jensen <wbr>不等式的证明
而 ∑(x:f(x)=y, ) Pr{X=x} 就是f(x) 等于某个特定值的概率（Pr{ f(x)=y }）, 根据引理，得出 f( E[X] ) <= E[ f(x) ]。


此文参考自MIT《算法导论》第九课。原视频链接：http://v.163.com/movie/2010/12/6/U/M6UTT5U0I_M6V2TGB6U.html


我的更多文章

下载客户端阅读体验更佳

APP专享