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 1 We 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.
for all .
For sufficiently nice functions, one can easily determine convexity by looking at its second derivative.
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.
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 .