In the analysis of randomized algorithms, we frequently use various inequalities to simplify expressions or make them easier to work with. These inequalities are usually obvious by plotting them, and proving them just uses basic calculus.

**1. Facts from Convex Analysis **

Let be a function defined on an interval .

Definition 1We say that is convex on if

for all and all .

Geometrically, this say that the chord connecting the points and lies above the function . The following example illustrates that is convex.

An equivalent statement of this definition is as follows.

Fact 1Suppose is convex. Then, for any points with , we have

for all .

For sufficiently nice functions, one can easily determine convexity by looking at its second derivative.

Fact 2Suppose is twice differentiable and that the second derivative is non-negative on all of . Then is convex.

In our example above we used . Its second derivative is , which is non-negative, so is convex.

The next fact says that, for convex functions, the linear approximation at any point lies beneath the function.

Fact 3 (Subgradient Inequality)Suppose is convex, and is differentiable at a point . Then

for any point .

The following example illustrates this for at the point .

**2. The Inequalities **

**Inequality 1.**.Convexity of follows from Fact 2 since its second derivative is . The inequality follows by applying Fact 3 at the point .**Inequality 2.**for all .Convexity of on the set follows from Fact 2 since its second derivative is . The inequality follows by applying Fact 1 at the points and .**Inequality 3.**.As above, convexity of follows from Fact 2. The inequality follows by applying Fact 1 at the points and .

Pingback: Lecture 2: Markov Inequality, Amplification by Independent Trials, Chernoff Bounds | UBC CPSC 536N

Pingback: Lecture 3: Balls and Bins, Congestion Minimization, Quicksort | UBC CPSC 536N

Pingback: Lecture 6: Dimensionality Reduction by the Johnson-Lindenstrauss Lemma | UBC CPSC 536N