Sheng Li (gmachine1729) wrote,
Sheng Li
gmachine1729

How I used Holder’s inequality to prove Minkowski’s inequality for subadditivity of L^p

Originally published at 狗和留美者不得入内. You can comment here or there.

I’ve pretty much always sucked at inequalities. Hopefully, now that I am older and more mature, I can develop some deeper intuition for them. I feel like the biggest difference between the me after age 25 and the me before then is that the former, older version of me is much better at thinking deeply and learning and understanding pretty much everything systematically, which is of course closely connected with self-discipline and self-control. The younger me, when faced with something that did not come extremely naturally to me, would often be totally at a loss on where to start. The older me is also much better at problem decomposition as well as working on problems of a more ambiguous nature. I am leagues better at learning from experience. In contrast, in undergrad, not only was I often not able to solve problems, I could not even understand their solutions deeply enough to pretty much never forget it. The older me is also much more creative and independent-thinking. As for this “creativity” matter, I will acknowledge however that I have never composed by own math or programming contest problems despite having solved a good number. I may well succeed if I try now, though I certainly wouldn’t have succeeded in that before age 25, when I struggled too much even to solve them.

As for inequalities, I was too dumb in high school to solve any actual olympiad problem in that category, though I was aware of AM-GM (arithmetic geometric mean) and to a lesser extent Cauchy’s inequality (which comes up more in real math). Later, I learned of the rearrangement inequality, for which it is immediate to me now that the proof of which, I’ve never done completely myself, involved a swap argument. There is also Jensen’s inequality, which is trivial in some sense, though I also feel like I’ve never really ever thought of it independently, until perhaps now.

Definition 1: A function [公式] is convex if for any [公式] , for any [公式] , given the function defining the line joining [公式] [公式] , we have [公式] . To picture this, one can draw a line between two points on the plane and then draw a curve underneath it with non-negative first derivative. If instead, [公式] , we say that [公式] is concave. [公式]

Theorem 2 (Jensen’s inequality): If [公式] is convex, then for any [公式] ,

[公式]

Proof: This follows directly from the definition of convexity in that [公式] represents any arbitrary point on the line segment joining the two points [公式] . [公式]

Theorem 3 (Jensen’s inequality for finite set): Suppose [公式] is convex. Take any [公式] and any probability distribution on it with [公式] as the corresponding probabilities. Then,

[公式]

Proof: We prove this by induction. We note how[公式]

gives rise to a binary distribution. As our inductive hypothesis, we can assume that

[公式]

This in combination with Jensen’s inequality on two variables completes our inductive proof. [公式]

Theorem 4 (Jensen’s inequality for continuous probability distribution): Given a probability density function [公式] characterizing a random variable [公式] and a convex function [公式] on the reals,

[公式]

Proof: If we are using the Riemann integral, we simply apply Theorem 3 to partitions and take the limit. If we are using the Lebesgue integral, we can do analogous for simple functions. [公式]

Theorem 5 (Young’s inequality): Given non-negative [公式] and [公式] such that [公式] ,

[公式]

Proof: One who is familiar with Jensen’s inequality should upon seeing the RHS of it, notice that one can use Jensen’s to derive a special case of it. The logarithm is a concave function, in which case the inequality in Jensen’s is reversed.

[公式]

Monotonicity of the logarithm yields our desired result. [公式]

Theorem 6 (Holder’s inequality): Given positive [公式] such that [公式] and [公式] , we have

[公式] or equivalently,

[公式]

Proof: Since the norm operator [公式] on [公式] for any [公式] is absolutely homogenous, we can assume WLOG that [公式] . With monotonicity of the integration operator, we have by Young’s inequality,

[公式]

[公式]

Theorem 7 (Minkowski’s inequality): For [公式] ,

[公式]

Proof: We have

[公式]

This gives us

[公式] wherein we used [公式] , which completes our proof. [公式]

I’ll be honest and say that after trying for an hour and failing, I looked up the proof for Holder’s inequality. From it, I learned of Young’s inequality. Due to never having internalized Jensen’s inequality, I couldn’t easily prove Young’s inequality myself, and even went astray, along the futile AM-GM direction. However, after reading the proof of Young’s inequality and also that one can assume WLOG that [公式] , Holder’s inequality became more or less trivial. I’m now aware that after first realizing to simplify by assuming unit norms WLOG, one then ought to realizes that one is free to take any power of the norms on the RHS without altering its value. Using that [公式] in combination with expressions that are powers of that unit norm as a medium of comparison then becomes the natural next step. With monotonicity of the integral operation in mind on the partial order of non-negative functions in mind, one then finds the symmetric expression [公式] on which Jensen’s inequality can be applied.

Too bad, I was too dumb to figure this out myself. My lack of any non-trivial understanding of inequalities in the past, of course, also had much to do with it. On the plus side, I did within an hour figure out Minkowski’s inequality on my own, which may be the first non-trivial and important inequality I proved myself without ever having looked up the proof. I might have seen the proof before of course, but only in a very cursory and superficial way, such that I did not remember anything about it.

Tags: uncategorized
Subscribe

  • Disqus comment search service released!

    Originally published at 狗和留美者不得入内. You can comment here or there. THIS HAS BEEN UPDATED. SEE…

  • Ron Maimon on Disqus

    Originally published at 狗和留美者不得入内. You can comment here or there. I used my Disqus comment search to get all of Ron Maimon’s comments on…

  • Found my Disqus search on Google

    Originally published at 狗和留美者不得入内. You can comment here or there. On the third or second or seventh page. I think I was a bit harsh on them lol.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 0 comments