Jensen's inequality Lemma. Let f be a convex function, and let X be a random variable.Then,f(E[Ⅺ)≤Ef(X) 700 f(E[X)=f∑k,P{X=k} k=-∞0 ≤∑f(k),P({X=k k =ELf(X).□ Tricky step, but true-think about it c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.15© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.15 Jensen’s inequality [ ( )] ( ) Pr{ } ( [ ]) Pr{ } E f X f k X k f E X f k X k k k = ≤ ⋅ =   = ⋅ = ∑ ∑ ∞ =−∞ ∞ =−∞ . Proof. Tricky step, but true—think about it. Lemma. Let f be a convex function, and let X be a random variable. Then, f(E[X]) ≤ E[f(X)]