Processing math: 100%

Inequalities

Jensen's Inequality

For any r.v. X with finite expectation and any convex function φ(),

Eφ(X)φ(EX)

Note:

  1. Equality holds iff φ() agrees with a linear funtion on the support of X.
  2. If φ() is strictly convex, the inequality is strict.

Corollary 1: Arithmetic-geometric Mean Inequality

If p1,,pn0 and p1++pn=1, then

ni=1piaini=1apii

A special case of arithmetic-geometric mean inequality is Young's inequality:

x,y0,p,q>0,1p+1q=1xyxpp+yqq

Corollary 2: Likelihood Inequality

If Xp(x) and q(x) is another density function, then

Elogp(X)Elogq(X))

Equality holds iff p(x)=q(x).

Covariance Inequality

For all X,g(),h() s.t. Eg(X),Eh(X),Eg(X)h(X) exist:

  1. If g() is nondecreasing and h() is nonincreasing, then Cov[g(X),h(X)]0
  2. If g() and h() are both nondecreasing/nonincreasing, then Cov[g(X),h(X)]0

Holder's Inequality

If p,q>0,1p+1q=1, then for all r.v. X and Y, given the expectations exist,

|EXY|(E|X|p)1p(E|Y|q)1q

Derivation: Using Young's inequality, |X|(E|X|p)1p|Y|(E|Y|q)1q|X|ppE|X|p+|Y|qqE|Y|q. Holder's inequality can be derived by taking expectation on both sides.

Corollary: Cauchy-Schwarz Inequality

For all r.v. X and Y, given the expectations exist,

|EXY|(E|X|2)12(E|Y|2)12

Chebyshev's Inequality

For any positive r.v. X and r>0,

P(Xr)EXr

Corollary:

  1. For all positive, increasing function g(), in addition, P(Xr)Eg(X)g(r).
  2. In particular, for any r.v. X and p>0, P(|X|r)E|X|prp.
  3. A commonly cited version is that no more than 1/k2 of a distribution's values can be more than k standard deviations away from the mean: P(|Xμ|r)σ2r2.

Bernstein inequality (exponential version for bounded r.v.'s): Suppose that |X|M almost surely, then for all ϵ>0

P(|ˉXμ|ϵ)2exp(nϵ2/2σ2+Mϵ/3)

Concentration inequalities:

  • Markov's inequality;
  • Chebyshev's inequality;
  • Chernoff bounds;
  • Bounds on sums of independent variables: Hoeffding, Azuma, McDiarmid, Bennett, and Bernstein inequalities;
  • Efron–Stein inequality;
  • Dvoretzky–Kiefer–Wolfowitz inequality.

Identities

Some properties of Gamma, Chi-squared, Poisson and negative binomial distribution.


🏷 Category=Probability