InequalitiesSummary

Basic Inequalities in Probability 1 Standard Notations: µ X = E X (expected value), σ 2 X = E ( X - µ X ) 2 (variance). Fundamental inequalities. (1) Re-arrangement : for every ream numbers a 1 ≤ a 2 ≤ · · · ≤ a n and b 1 ≤ b 2 ≤ · · · ≤ b n , and every permutation τ of the set { 1 , 2 , . . . , n } , a 1 b n + a 2 b n − 1 + . . . + a n b 1 ≤ a 1 b τ (1) + a 2 b τ (2) + . . . + a n b τ ( n ) ≤ a 1 b 1 + a 2 b 2 + . . . + a n b n . Proof: induction can work. Example: if x, y, z > 0, then x y + z + y x + z + z x + y ≥ 3 2 . Indeed, with no loss of generality, assume that x ≤ y ≤ z , so that y + z ≥ x + z ≥ x + y and 1 / ( y + z ) ≤ 1 / ( x + z ) ≤ 1 / ( x + y ). Now take a 1 = 1 / ( y + z ) , a 2 = 1 / ( x + z ) , a 3 = 1 / ( x + y ), b 1 = x, b 2 = y, b 3 = z, and note that 3 = a 1 ( b 2 + b 3 ) + a 2 ( b 1 + b 3 ) + a 3 ( b 1 + b 2 ) ≤ 2( a 1 b 1 + a 2 b 2 + a 3 b 3 ). (2) Power mean : If a 1 > 0 , a 2 > 0 , . . . , a n > 0, and M p =          ( 1 n ∑ n k =1 a p k ) 1 /p , p 6 = 0 , ±∞ , M 0 = ( a 1 a 2 · · · a n ) 1 /n , p = 0 , M + ∞ = max( a 1 , . . . , a n ) , p = + ∞ , M −∞ = min( a 1 , . . . , a n ) , p = -∞ , then lim p → 0 M p = M 0 , lim p →−∞ M p = M −∞ , lim p → + ∞ M p = M + ∞ , and the function p → M p is strictly increasing unless a 1 = a 2 = . . . = a n . Proof: induction can work. Special names: M 1 is arithmetic mean (AG), M 0 is geometric mean (GM), M − 1 is harmonic mean (HM). The (famous) AG/GM/HM inequality, M 1 ≥ M 0 ≥ M − 1 , is a particular case of the power mean inequality. Concentration inequalities . (1) Markov [1880] : if Y > 0, then P ( Y ≥ a ) ≤ E Y a . Proof. E Y ≥ E Y I Y ≥ a ≥ a E I Y ≥ 0 = a P ( Y ≥ a ). (2) Chebyshev [1865] : with µ X = E X, σ 2 X = E ( X - µ X ) 2 , P ( | X - µ X | ≥ a ) ≤ σ 2 X a 2 . Proof. Apply Markov with Y = ( X - µ X ) 2 . Variations. • Standartized : P ( | X - µ X | ≥ kσ X ) ≤ 1 k 2 . • Cantelli [1928] : P ( X - µ X ≥ a ) ≤ σ 2 X σ 2 X + a 2 . Proof. For t > 0 , by Markov, P ( X - µ X + t > a + t ) = P ( ( X - µ X + t ) 2 > ( a + t ) 2 ) ≤ ( σ 2 X + t 2 ) / ( a + t ) 2 . Direct computations show that the right hand side is minimized by taking t = σ 2 X /a . • Vysochanskij-Petunin [1980] : if X is unimodal , then P ( | X - µ X | > kσ X ) ≤ 4 9 k 2 . 1 Sergey Lototsky, USC 1

2 (3) Chernoff [1955]: If M X ( t ) = E e tX exists for all t > 0, and a > 0, then P ( X ≥ a ) ≤ e ln M X ( t ) − at , with subsequent minimization of the right-hand side with respect to t > 0. Proof. Use Markov with Y = e tX . Example. If X is standard normal, then M X ( t ) = e t 2 / 2 , so that ( t 2 / 2) - at ≥ - a 2 / 2, with the lower bound achieved for t = a/ 2, and therefore P ( X ≥ a ) ≤ e − a 2 / 2 . (4) Paley-Zygmund [1932]: if Y > 0 and 0 < θ < 1, then P ( Y > θµ Y ) ≥ (1 - θ ) 2 µ 2 Y σ 2 Y + µ 2 Y . Proof. Keeping in mind that E Y 2 = σ 2 Y + µ 2 Y , µ Y = E Y I Y ≤ θµ Y + E Y I Y >θµ Y . Then E Y I Y <θµ Y ≤ θµ Y (obviously), and E Y I Y >θµ Y ≤ √ E Y 2 √ P ( Y > θµ Y ) (Cauchy-Schwarz; see below). Moment inequalities. (1) Jensen [1905] : If g = g ( x ) , x ∈ R , is convex , then E g ( X ) ≥ g ( E X ) (e . g . E e X ≥ e µ X . ) If f = f ( x ) is concave , then E f ( X ) ≤ f ( E X ) (e . g . X > 0 ⇒ E ln X ≤ ln µ X . ) Proof: g convex ⇔ for every x 0 ∈ R there is a number C ∈ R such that g ( x ) ≥ g ( x 0 ) + C ( x - x 0 ); if g ′ exists, then C = g ′ ( x 0 ) [the graph of g is above the tangent line at x 0 ]. Now put x = X, x 0 = µ X , and take expected value on both sides. (2) Lyapunov [1900] : if 0 < p < r , then ( E | X | p ) 1 /p ≤ ( E | X | r ) 1 /r . Proof: Use Jensen with g ( x ) = | x | r/p and | X | p instead of X . (3) H¨older [1885] : if p > 1 , q > 1 , and (1 /p ) + (1 /q ) = 1, then E | XY | ≤ ( E | X | p ) 1 /p ( E | Y | q ) 1 /q . The inequality is strict unless X = cY for some non-random number c . Proof. Using concavity of the log function, argue that ab ≤ ( a p /p ) + ( b q /q ) , a, b > 0. Then set a = | X | / ( E | X | p ) 1 /p , b = | Y | / ( E | Y | q ) 1 /q , and take expectation on both sides. Note that the H¨older inequality is trivial if E | X | p = 0 and/or E | Y | q = 0. (4) Cauchy-Bunyakovsky-Schwarz [1820 → 1855 → 1885] : E | XY | ≤ √ E X 2 √ E Y 2 . Proof: take p = q = 2. (5) Minkowski [1900] : if p ≥ 1, then ( E | X + Y | p ) 1 /p ≤ ( E | X | p ) 1 /p + ( E | Y | p ) 1 /p (that is, the functional X 7→ ( E | X | p ) 1 /p satisfies the triangle inequality and thus defines a norm on the space of random variables with finite p -th moment.) Proof. p = 1 is obvious. For p > 1, take q = p/ ( p - 1) [so that (1 /p ) + (1 /q ) = 1], note that | X + Y | p = | X + Y | · | X + Y | p − 1 ≤ | X | · | X + Y | p − 1 + | Y | · | X + Y | p − 1 , and then, by H¨older, E ( | X | · | X + Y | p − 1 ) ≤ ( E | X | p ) 1 /p ( E | X + Y | p ) 1 /q , E ( | Y | · | X + Y | p − 1 ) ≤ ( E | Y | p ) 1 /p ( E | X + Y | p ) 1 /q . It remains to combine the inequalities: E | X + Y | p ≤ ( ( E | X | p ) 1 /p + ( E | Y | p ) 1 /p ) ( E | X + Y | p ) 1 /q and then simplify, keeping in mind that 1 - (1 /q ) = 1 /p .