Useful Inequalities Cauchy-Schwarz
Minkowski
H¨ older
n P
n P
i=1
n P
i=1
Bernoulli
xi y i
i=1
2
≤
|xi + yi |p
|xi yi | ≤
n P
i=1
1
p
n P
i=1
x2i
n P
≤
|xi |p
(1 + x)r ≥ 1 + rx
{x2 > 0}
i=1
i=1
1/p
(1 +
x)r
(1 +
nx)n+1
≤
≤1+
1
p
n P
i=1
+
|yi |q
n P
i=1
|yi |p
1/q
1
p
for p ≥ 1.
for p, q > 1,
1 p
1 q
+
≥ (1 + (n +
for x ∈ [−1,
1 ), r−1
for x ∈ R, n ∈ N.
ex
≥
xe
1 2−x
1+ xn n!
for x ∈ R, and
ex ≥ 1 + x + e−x
≥ 1 + x,
≤1−
x2 2
x 2
− 1) ≤
x2 n
≥ ex 1 −
+1≤
ex
≤ 1+
for x ≥ 0, reverse for x ≤ 0.
for x ∈ [0, ∼ 1.59] and
< xx < x2 − x + 1
x1/r (x
x n n
rx(x1/r
2−x
for n > 1, |x| ≤ n.
x n+x/2 n
≤1−
x 2
for x ∈ [0, 1].
− 1)
for x, y > 0.
2 − y − e−x−y ≤ 1 + x ≤ y + ex−y , and ex ≤ x + ex
logarithm
x−1 x 2x 2+x
≤ ln(x) ≤
x2 −1 2x
1 n
ln(n + 1) < ln(n) + ln(1 + x) ≥
x 2
ln(1 + x) ≥ x − x3 2
x−
hyperbolic
x cos x ≤ 2 x π
−
2
for x, y ∈ R.
1 i=1 i
x3 2
Stirling
e
means
min xi ≤
Lehmer
n n e
≤ 2n .
P
P
√
Heinz
√
Newton
≤
√
2πn
n P −1 xi
√1 x
<
√
x+1−
n n 1/(12n+1) e e ≤(
Q
xi )1/n ≤
√
√ √ x−1 < 2 x−2 x−1
≤ n! ≤ 1 n
P
√
n n 1/12n e e
2πn q
xi ≤
1 n
P
for x ≥ 1.
≤ en
P 2 x P i xi
xi 2 ≤
n n e
≤ max xi
P P p 1/p , w ≥ 0, Mp ≤ Mq for p ≤ q, where Mp = i i wi |xi | i wi = 1. Q In the limit M0 = i |xi |wi , M−∞ = mini {xi }, M∞ = maxi {xi }.
log mean
i
i
wi |xi |p
wi |xi |p−1
xy ≤ xy ≤
√
x+ 2
P wi |xi |q ≤ P i q−1 i wi |xi |
√
y
1
(xy) 4 ≤
x1−α y α +xα y 1−α 2
Sk 2 ≥ Sk−1 Sk+1 P 1 Sk = n k
Jensen
≤
1≤i1 0, α ∈ [0, 1].
Sk ≥
p
(k+1)
ai 1 ai 2 · · · aik ,
Sk+1
and
for 1 ≤ k < n,
ai ≥ 0.
≤ ln(n) + 1
Chebyshev
x √ 3
x3 3
≤ tan x
≤ sin x,
x2 , sinh x
all for x ∈ 0,
for x ∈ R, α ∈ [−1, 1].
i
P pi xi ≤ i pi ϕ (xi )
n P
f (ai )g(bi )pi ≥
n P
ai b i ≥
i=1
≤ x cos2 (x/2) ≤ sin x ≤ (x cos x + 2x)/3 ≤
≤ sin x ≤ x cos(x/2) ≤ x ≤ x +
P
where pi ≥ 0,
P
pi = 1, and ϕ convex.
π 2
.
n P
f (ai )pi
i=1
n P
i=1
n P g(bi )pi ≥ f (ai )g(bn−i+1 )pi i=1
for a1 ≤ · · · ≤ an , b1 ≤ · · · ≤ bn and f, g nondecreasing, pi ≥ 0, Alternatively: E f (X)g(X) ≥ E f (X) E g(X) .
for x ∈ [0, ∼ 0.43], reverse elsewhere. √ ≤ x 3 cos x ≤ x − x3 /6 ≤ x cos
ϕ
Alternatively: ϕ (E [X]) ≤ E [ϕ(X)]. For concave ϕ the reverse holds.
for x ∈ [0, ∼ 0.45], reverse elsewhere.
ex(α+x/2)
nn kk (n−k)n−k
1
ln(x) ≤ n(x n − 1) for x, n > 0.
Pn
x cos x 1−x2 /3
cosh(x) + α sinh(x) ≤
√ √ 2 x+1−2 x <
for x ≥ 0, reverse for x ∈ (−1, 0].
x3 4
+
x2 2
≤ x cos x ≤ x3 sinh2 x
≤
square root
Maclaurin-
for x ∈ [0, ∼ 2.51], reverse elsewhere.
x2 2
ln(1 − x) ≥ −x − trigonometric
≤ x − 1,
√x x+1
≤ ln(1 + x) ≤
for x, n > 0.
for x ∈ (0, 1).
for x, r ≥ 1. xy y xy + y x > 1 and ex > 1 + x > e x+y y
≤
Pd n n for n ≥ d ≥ 0. ≤ nd + 1 and i=0 i ≤ 2 Pd d n en for n ≥ d ≥ 1. i=0 i ≤ d Pd n n d for n ≥ d ≥ 0. i=0 i ≤ d 1 + n−2d+1 2 P n n αn n 1−α ≤ i=0 i ≤ 1−2α αn for α ∈ (0, 21 ). αn
power means
(iv) q < 0 < p , −q > x > 0, (v) q < 0 < p , −p < x < 0. x n n
n k
and
n i=0 i
r > 1.
(ii) − p < −q < x < 0, (iii) − q > −p > x > 0. Reverse for:
ex ≥ 1 +
(en)k kk
≤
Pd
= 1.
(a + b)n ≤ an + nb(a + b)n−1 for a, b ≥ 0, n ∈ N. p q ≥ 1 + xq for (i) x > 0, p > q > 0, 1+ x p
exponential
nk k!
≤
2πnα(1−α)
for x ∈ [−1, 0], n ∈ N. 1)x)n
n k
≤
n n √ 1 1 for n ≥ k ≥ 0 and √4πn (1 − 8n ≤ √4πn (1 − 9n ≤ n ) ≤ 2n ). k n n1 +n2 n1 n2 for n1 ≥ k1 ≥ 0, n2 ≥ k2 ≥ 0. ≤ k +k k1 k2 1 2 √ nH(α) π n , H(x) = − log2 (xx (1−x)1−x ). G ≤ αn ≤ G for G = √ 2 2
for x ∈ [0, 1], r ∈ R \ (0, 1).
rx 1−(r−1)x
(n−k+1)k } k!
k
max { n , kk nk 4k!
for x ≥ −1, r ∈ R \ (0, 1). Reverse for r ∈ [0, 1].
1 1−nx
(1 +
yi2
|xi |p
(1 + x)r ≤ 1 + (2r − 1)x x)n
n P
binomial
v0.28 · January 13, 2016
rearrangement
i=1
n P
i=1
ai bπ(i) ≥
n P
ai bn−i+1
i=1
for a1 ≤ · · · ≤ an ,
b1 ≤ · · · ≤ bn and π a permutation of [n]. More generally: n n n P P P fi (bi ) ≥ fi (bπ(i) ) ≥ fi (bn−i+1 ) i=1
i=1
i=1
with fi+1 (x) − fi (x) nondecreasing for all 1 ≤ i < n.
P
pi = 1.
Weierstrass
Q
1 − xi
i
wi
P
≥1−
i
w i xi
where xi ≤ 1, and
Carleman
either wi ≥ 1 (for all i) or wi ≤ 0 (for all i). P If wi ∈ [0, 1], wi ≤ 1 and xi ≤ 1, the reverse holds. Young
Kantorovich
( px1p
+
P
xi 2
i
1 −1 ) qxq
xi yi
0 0.
Hadamard
(det A)2
Schur
Pn
i=1
≤
A2ij
i=1 j=1
λ2i ≤
Pn
Hilbert
i,j=1
A2ij
and
i=1
di ≤
Pk
i=1
λi
Acz´ el
Qn Pn a P x i a i xi Qn i=1 i a ≤ Pn i=1 for xi ∈ [0, 12 ], ai ∈ [0, 1], ai = 1. i i=1 (1 − xi ) i=1 ai (1 − xi ) a1 b 1 −
given that Mahler
n Q
Pn a21
xi + yi
i=1
Abel Milne
b1 min k
Pn
ai b i Pn
i=2
k P
i=1
i=1 (ai
>
+ bi )
≥ a21 −
2 i=2 ai
1/n
ai ≤
2
≥ n P
i=1
n Q
i=1
or
1/n xi
b21
+
Pn >
2 b2 1 i=2 ai Pn 2 i=2 bi .
n Q
i=1
ai bi ≤ b1 max
P
k
ai bi n i=1 ai +bi
1/n yi
−
Pn
2 i=2 bi
i=1
ϕ(ai ) ≥
1 n!
P
π
P∞
m=1
≤
Pn
i=1
Pn
i=1 bi
m P n Q
j=1 i=1
aiπ(j)
for a1 ≥ a2 ≥ · · · ≥ an and b1 ≥ · · · ≥ bn , Pt Pt i=1 ai ≥ i=1 bi for all 1 ≤ t ≤ n,
1 n!
P
n 1 · · · xbπ(n) xbπ(1)
π
1 c2 +1/2
<
Copson
∞ P P
n=1
n=1
Kraft LYM
P
k≥n
4
≤ π2
m=1
P
P∞
n=1
a2n
P∞
2n n=1 (n2 +c2 )2
ak k
p
2−c(i) ≤ 1
X∈A
Sauer-Shelah
P∞
≤π
a2m
1 P∞ 2
n −1 |X|
≤ pp
∞ P
P∞
n=1
1 c2
<
an p
n=1
n2 a2n
1
2 2 n=1 bn
for am , bn ∈ R.
for an ≥ 0, p > 1, reverse if p ∈ (0, 1).
for c(i) depth of leaf i of binary tree, sum over all leaves. ≤ 1, A ⊂ 2[n] , no set in A is subset of another set in A.
|A| ≤ |str(A)| ≤
Pr Pr
vc(A) P i=0
n i
for A ⊆ 2[n] , and vc(A) = max{|X| : X ∈ str(A)}.
n W
k P Ai ≤ (−1)j−1 Sj
for 1 ≤ k ≤ n, k odd,
n W
k P Ai ≥ (−1)j−1 Sj
for 2 ≤ k ≤ n, k even.
i=1
Sk =
for an ∈ R.
for c 6= 0.
str(A) = {X ⊆ [n] : X shattered by A},
for b1 ≥ · · · ≥ bn ≥ 0. ai
am bn n=1 m+n
Mathieu
Bonferroni
ai
j=1 i=1
aij ≤
With max{m, n} instead of m + n, we have 4 instead of π. P∞ a1 +a2 +···+an p p p P∞ p ≤ p−1 for an ≥ 0, p > 1. n=1 an n=1 n
where xi , yi > 0.
i=1
m P n Q
and
ϕ(bi )
i=1
P∞
i=1
k P
Pn
n 1 ≥ · · · xa xa π(n) π(1)
an
λ1 ≥ · · · ≥ λn the eigenvalues, d1 ≥ · · · ≥ dn the diagonal elements. Ky Fan
Pn
P∞
for 1 ≤ k ≤ n.
A is an n × n matrix. For the second inequality A is symmetric.
aiπ(j)
j=1 i=1
|ak |
k=1
where 0 ≤ ai1 ≤ · · · ≤ aim for i = 1, . . . , n and π is a permutation of [n]. Q n Pn Qn for |ai |, |bi | ≤ 1. i=1 ai − i=1 bi ≤ i=1 |ai − bi | Qn Q n n i=1 (α + ai ) ≥ (1 + α) , where i=1 ai ≥ 1, ai > 0, α > 0. P P P P 1+y 1−y 1−y 1+y 1+x 1−x 1−x 1+x bi bi ≥ bi bi i ai i ai i ai i ai
Carlson
where A is an n × n matrix. Pk
Pn
xi ≥ 0 and the sums extend over all permutations π of [n].
where xi > 0, (xn+1 , xn+2 ) := (x1 , x2 ),
where x, y, z ≥ 0, t > 0
n m Q P
≤e
where a1 ≥ a2 ≥ · · · ≥ an and b1 ≥ b2 ≥ · · · ≥ bn and {ak } {bk },
i=1
xt (x − y)(x − z) + y t (y − z)(y − x) + z t (z − x)(z − y) ≥ 0
1/k
with equality for t = n and ϕ is convex (for concave ϕ the reverse holds).
Hardy
n P n Q
aij ≥
|ai |
and {ai } {bi } (majorization), i.e.
and n ≤ 12 if even, n ≤ 23 if odd. Schur
m Q n P
k i=1
for 1 ≥ x ≥ y ≥ 0, and i = 1, . . . , n.
for ϕ convex.
for ai , bi ≥ 0, or more generally: P P for ϕ concave, and a = ai , b = bi .
n 2
Callebaut f (x) dx
k=1
j=1 i=1
where a < b, and ϕ convex.
ϕ(x) dx ≤
≥ a log
bi
for x, y ≥ 0, p, q > 0,
R U +1
f (i) ≤
and
xi xi+1 +xi+2
i=1
i=L
≥n
aπ(i)
n P
PU
1 b−a
≤
+
1 p
for xi , yi > 0, √ A = (m + M )/2, G = mM .
≤ M < ∞,
f (b)−f (a) b−a
yq q
2 A 2 P yi 2 ≤ G i xi yi
i
f (x) dx ≤
a+b 2
i=1
P
P
≤ xy ≤
xp p
sum & product
Q
Pn
j=1
j=1
P
1≤i1 0.
nσ 2 Mε ≤ exp − 2 θ where Xi i.r.v., 2 M nσ i=1 P 1 Var[Xi ], |Xi | ≤ M (w. prob. 1), ε ≥ 0, E[Xi ] = 0, σ 2 = n Pr
n P
Xi ≥ ε
θ(u) = (1 + u) log(1 + u) − u. n P −ε2 Pr Xi ≥ ε ≤ exp 2 2(nσ + M ε/3) i=1
for Xi i.r.v.,
1 P E[Xi ] = 0, |Xi | < M (w. prob. 1) for all i, σ 2 = n Var[Xi ], ε ≥ 0. −δ 2 P Pr Xn − X0 ≥ δ ≤ 2 exp for martingale (Xk ) s.t. 2 2 n i=1 ci Xi − Xi−1 < ci (w. prob. 1), for i = 1, . . . , n, δ ≥ 0.
Var[Z] ≤
1 2
E
n P
i=1
Z − Z (i)
2
for Xi , Xi ′ ∈ X i.r.v.,
f : X n → R, Z = f (X1 , . . . , Xn ), Z (i) = f (X1 , . . . , Xi ′ , . . . , Xn ). −2δ 2 Pr Z − E[Z] ≥ δ ≤ 2 exp Pn for Xi , Xi ′ ∈ X i.r.v., 2 i=1 ci Z, Z (i) as before, s.t. Z − Z (i) ≤ ci for all i, and δ ≥ 0.
V B i ≤ M exp M ≤ Pr Q M = (1 − Pr[Bi ]), ∆ =
∆ 2 − 2ε P
i6=j,Bi ∼Bj
Pr
V
Q B i ≥ (1 − xi ) > 0
where Pr[Bi ] ≤ ε for all i,
Pr[Bi ∧ Bj ].
where Pr[Bi ] ≤ xi ·
Q
(i,j)∈D
(1 − xj ),
for xi ∈ [0, 1) for all i = 1, . . . , n and D the dependency graph.
If each Bi mutually indep. of the set of all other events, exc. at most d, V B i > 0. Pr[Bi ] ≤ p for all i = 1, . . . , n , then if ep(d + 1) ≤ 1 then Pr
i
where X1 , . . . , Xn are i.r.v., E[Xi ] = 0, P Var[Xi ] < ∞ for all i, Sk = ki=1 Xi and ε > 0.
3
Pr max1≤k≤n |Xk | ≥ ε ≤ E |Xn | /ε
Azuma
A related lemma, assuming E[X] = 0, X ∈ [a, b] (w. prob. 1) and λ ∈ R: 2 λ (b − a)2 E eλX ≤ exp 8 P Pr max |Sk | ≥ ε ≤ ε12 Var[Sn ] = ε12 Var[Xi ]
q 8 if λ ≥ Pr X − E[X] ≥ λσ ≤ 9λ4 2 , 3 2 2τ 4τ if ε ≥ √ , Pr X − m ≥ ε ≤ 9ε2 3 ε 2τ Pr X − m ≥ ε ≤ 1 − √ if ε ≤ √ . 3τ
for Xi ∈ [0, 1] k-wise i.r.v.,
ˆ = ⌈µδ/(1 − p)⌉, E[Xi ] = pi , X = P Xi , µ = E[X], p = k≥k
for X ≥ 0,
Where X is a unimodal r.v. with mode m,
Doob
Pr[X ≥ t] ≤ F (a)/at for X r.v., Pr[X = k] = pk , P F (z) = k pk z k probability gen. func., and a ≥ 1. µ eδ −µδ 2 Pr X ≥ (1 + δ)µ ≤ ≤ exp 3 (1 + δ)(1+δ) P for Xi i.r.v. from [0,1], X = Xi , µ = E[X], δ ≥ 0 resp. δ ∈ [0, 1). µ e−δ −µδ 2 Pr X ≤ (1 − δ)µ ≤ for δ ∈ [0, 1). ≤ exp 2 (1 − δ)(1−δ) Further from the mean: Pr X ≥ R ≤ 2−R for R ≥ 2eµ (≈ 5.44µ).
Petunin-Gauss
Etemadi
E (X − µ)k and Pr X − µ ≥ t ≤ tk k/2 nk for Xi ∈ [0, 1] k-wise indep. r.v., Pr X − µ ≥ t ≤ Ck t2 √ P X= Xi , i = 1, . . . , n, µ = E[X], Ck = 2 πke1/6k ≤ 1.0004, k even.
Pr X ≥ t ≤
Kolmogorov
Vysochanskij-
Pr X − E[X] ≥ t ≤ Var[X]/t2 where t > 0. Pr X − E[X] ≥ t ≤ Var[X]/(Var[X] + t2 ) where t > 0. Pr X > 0 ≥ (E[X])2 /(E[X 2 ]) where E[X] ≥ 0. Pr X = 0 ≤ Var[X]/(E[X 2 ]) where E[X 2 ] 6= 0.
Var[X] (1 − µ)2 (E[X])2 + Var[X]
Pr X ≥ µ E[X] ≥ 1 −
Var[X] < ∞, and µ ∈ (0, 1).
Pr |X| ≥ a ≤ E |X| /a where X is a random variable (r.v.), a > 0. Pr X ≤ c ≤ (1 − E[X])/(1 − c) for X ∈ [0, 1] and c ∈ 0, E[X] . Pr X ∈ S] ≤ E[f (X)]/s for f ≥ 0, and f (x) ≥ s > 0 for all x ∈ S.
Hoeffding
Paley-Zygmund
✁✂
L´ aszl´ o Kozma · latest version: http://www.Lkozma.net/inequalities_cheat_sheet
