Introductory probability textbooks emphasize the ubiquity of Cauchy-Schwarz inequality in proving other inequalities. Some related inequalities include Holder’s inequality, Young’s inequality, geometric mean arithmetic mean inequality, which ultimately all boil down to Jensen’s inequality. These inequalities form the foundation of analysis. On the other hand, concentration type of inequality tends to exploit the opposite directions. I am not an expert in the latter, despite my paper with W. Xu on a small application thereof. Instead I will expound on a recent problem-solving adventure that illustrates techniques for proving the opposite inequalities. The problem is communicated to me by Xin Zhou.
The inequality in question is . One is tempted to try convexity type of argument initially, but is bound to fail. Instead we want to exploit the extreme points in the space of random variables, i.e., find the worst case that still satisfies the inequality. First we perform some simplifying reduction: X can be assumed nonnegative, since if we replace X by , then left hand side is unchanged whereas the right hand side is non-increasing. Next due to the same scaling properties of both hand sides, we can assume . Therefore we need to prove , for and $X = |X |$. Clearly the scaling reduction simplifies things a lot.
Now we write , where . Thus if we condition on , the right hand side is completely deterministic. Now let and , so that . Now we want to show that the worst case scenario satisfies . That is, is either or bigger than or equal to . We show this by showing that any nonnegative variable can be reduced to such a form, preserving first and second moments, and in such a way that is non-decreasing. The obvious thing to try is first to multiply by the indicator . Then we need to compensate for the shrinkage of first and second moments by modifying the part of that’s . If we attempt a naive constant value , then we run out of degrees of freedom when trying to match both first and second moments, since the probability is pre-fixed. Therefore we need to augment the probability space if necessary and make the part of that’s two-piece constant, that is, with probabilities respectively, where , and . This is guaranteed to work, since by Jensen. The augmentation of probability space to accommodate the two-piece function might seem like ugly hack, but I don’t see another easy way around as of today.
Lastly why does this make non-decreasing? Essentially we are looking at given and . Clearly by “pushing” the part of between and to , and add the scrapped mass to the part above or equal , we preserve 2nd moment and increase . And the augmentation hack from previous paragraph essentially says by adding the mass tactfully, we can preserve first moment also. Having established a canonically worst case form random variable, it’s easy to check that they satisfy our objective inequality. Hence we are done.