Powered by Blogger.

AM-GM Inequality (Part 1)

Intro to the geometric mean: portfolio returns

Everyone and their mother knows how to take the average, or arithmetic mean, of $n$ numbers $x_1, x_2, \dotsc , x_n$: $$
\text{AM}(x_1, x_2, \dotsc , x_n) = \dfrac{x_1 + x_2 + \dotsb + x_n}{n}
$$ Less well known is the geometric mean, calculated as the $n$-th root of the product of the numbers: $$
\text{GM}(x_1, x_2, \dotsc , x_n) = \sqrt[n]{x_1 x_2 \dotsm x_n} = (x_1 x_2 \dotsm x_n)^{\frac{1}{n}}
$$ Now, why would someone use such a thing? One application is analyzing returns on an investment portfolio. Let's look at an example (show-out to Max S-G for this one): say we start with a portfolio of 100 million dollars, which gains 20% in the first year, loses 20% in the second year, and gains 5% in the third year. Below is the table of portfolio sizes and returns for the 3 years:

We can see a few things here. First off, we got an error when attempting to calculate the GM of the returns directly. If we go back and look at the formula for GM above, we see that there is a root, and thus a negative input will return an error. To solve this problem, we need to use the multiple- calculated as 1 plus the return for that year- to avoid negative inputs. Then we subtract 1 at the end to get back to a return number- below is the same spreadsheet with the proper formula added:

The geometric mean is apparently the compound annual growth rate (CAGR) of the portfolio for the 3 years (note that the numbers are shown rounded, so if you do this calculation, it will be a bit off): $$
\$ 100 \times (1 + 0.3 \% )^{3} = \$ 100.8
$$ The geometric mean is the more appropriate measure of return due to the fact that returns are compounded. In other words, in year 2, we are not investing 100 million again, but rather the new portfolio value of 120 million, and the year 2 return of -20% applies to that amount. The arithmetic mean of the returns is misleading- the final portfolio value after year 3 is NOT $$
\$ 105.1 = \$ 100 \times (1 + 1.7 \% )^{3}
$$ Finally- and this is the topic of this post- the geometric mean return is less than the arithmetic mean return. It turns out this is always the case.

Inequality of the arithmetic and geometric mean

AM-GM Inequality: For $x_1, x_2, \dotsc , x_n \geq 0$, $$
\dfrac{x_1 + x_2 + \dotsb + x_n}{n} \geq \sqrt[n]{x_1 x_2 \dotsm x_n}
$$ with equality if and only if $x_1 = x_2 = \dotsb = x_n$.

I'll show the proof in part 2 of this post, but for now, let's look at the geometric interpretation and a few applications. It is easiest to start with the case where $n=2$. A point $(x,y)$, where $x$ and $y$ are both positive (there's nothing interesting about the case where one of them is zero, since then the geometric mean is zero), determines a rectangle as in the following diagram:
Here, I'm using an example point of $(3,5)$, and the rectangle is in red. The rectangle's area is $3 \times 5 = 15$, and in blue is a square of the same area. Thus the square has side length $\sqrt{15} \approx 3.87$. Notice that the square's side length is the geometric mean of the rectangle side lengths, while the arithmetic mean of the same numbers is 4, which, unsurprisingly, is greater than 3.87. Choosing a more "extreme" rectangle of the same area, say using $(x,y) = (1,15)$, would yield an even larger arithmetic mean of 8. In fact, we could choose a rectangle of area 15 with arbitrarily large arithmetic mean side lengths like $(x,y) = \left( 1{,}000{,}000 \ , \frac{15}{1{,}000{,}000} \right)$.

The AM-GM inequality tells us that any red rectangle we choose will have a larger average (i.e. arithmetic mean) side length than the side length of the blue square of the same area. Equivalently, the square has the minimum perimeter among all rectangles of equal area. An analogous statement applies to the $n=3$ case, with "square" replaced by "cube" and "area" replaced by "volume," and of course there are also analogs in higher dimensions with hypercubes and hypervolumes.

Application to minimization problems

Given the interpretation of the AM-GM inequality as a statement about the square/cube minimizing the perimeter given a constraint on the value of the area/volume, it shouldn't come as much of a surprise that we can use it to find the minimum value of certain functions that can be made to look like an arithmetic mean subject to a volume-like constraint. Let's look at a few examples- first a simple one, and then two minimization problems.

Example 1: Prove that $n! < \left( \frac{n+1}{2} \right)^{n}$ for $n=2,3,4, \dotsc$.

This is the AM-GM inequality applied to $(x_1, x_2, \dotsc , x_n) = (1,2, \dotsc, n)$: $$
\sqrt[n]{1 \cdot 2 \cdot \dotsm \cdot n} < \dfrac{1+2+ \dotsb + n}{n} = \dfrac{\frac{n(n+1)}{2}}{n} = \dfrac{n+1}{2}
$$ Raising both sides to the $n$-th power proves the original statement.

Example 2: Find the minimum value of the function $f(x_1, x_2, \dotsc , x_n) = x_1 + x_2 + \dotsb + x_n$, where $x_1, x_2, \dotsc , x_n$ are positive real numbers with $x_1 x_2 \dotsm x_n = 1 \ ( \star )$. $$
\dfrac{f(x_1, x_2, \dotsc , x_n)}{n} &= \dfrac{x_1 + x_2 + \dotsb + x_n}{n} \\[2mm]
&\geq \sqrt[n]{x_1 x_2 \dotsm x_n} \tag{AM-GM} \\[2mm]
&= 1 \tag{$\star$}
$$ which implies that $f(x_1, x_2, \dotsc , x_n) \geq n$. Furthermore, since $f(1, 1, \dotsc , 1) = n$, $n$ is indeed the minimum value of $f$.

Example 3: Let $x,y,z \geq 0$ with $xyz = 1$. Find the minimum value of $$
S(x,y,z) = \dfrac{x^2}{y+z} + \dfrac{y^2}{z+x} + \dfrac{z^2}{x+y}
$$ Clearly, $S(1,1,1) = \frac{3}{2}$. We will show that this is the minimum value of $S$ by showing that $S \geq \frac{3}{2}$.

For this one, we'll need the Cauchy-Schwarz inequality, which states that for a positive integer $n$ and real numbers $a_1, a_2, \dotsc , a_n , b_1, b_2, \dotsc, b_n$, $$
\left( \sum_{i=1}^{n}{a_{i}^{2}} \right) \left( \sum_{i=1}^{n}{b_{i}^{2}} \right)
\geq \left( \sum_{i=1}^{n}{a_{i} b_{i}} \right)^{2}
$$ Click here for the proof.

Now, note that $$
S = \left( \dfrac{x}{\sqrt{y+z}} \right)^{2}
+ \left( \dfrac{y}{\sqrt{z+x}} \right)^{2}
+ \left( \dfrac{z}{\sqrt{x+y}} \right)^{2}
$$ Using Cauchy-Schwarz with $n=3$, for any numbers $b_1, b_2, b_3$, we obtain: $$
S \cdot (b_{1}^{2} + b_{2}^{2} + b_{3}^{2})
+ \dfrac{yb_2}{\sqrt{z+x}}
+ \dfrac{zb_3}{\sqrt{x+y}}
\right) ^{2} \tag{$\spadesuit$}
$$ This works for any values of $(b_1, b_2, b_3)$, so we can choose $(\sqrt{y+z}, \sqrt{z+x}, \sqrt{x+y})$, which makes $( \spadesuit )$ simplify to: $$\begin{align}
S &\geq \dfrac{1}{2}(x+y+z) \tag{from the above equation} \\[3mm]
&\geq \dfrac{1}{2} \cdot 3 \sqrt[3]{xyz} \tag{AM-GM} \\[3mm]
&= \dfrac{3}{2} \tag{since $xyz=1$}
$$ $\square$

That will do it for this post. In part 2, I will show the proof of the AM-GM inequality, along with a few more examples of its use in miscellaneous problems.

Thanks for reading, and post any questions in the comments section.

Proof of Cauchy-Schwarz in R^n

If ${\bf x} = (x_1, x_2, \dotsc , x_n), {\bf y} = (y_1, y_2, \dotsc, y_n) \in \Bbb{R}^{n}$, i.e. the $x_{i}$'s and $y_{i}$'s are all real numbers, then the Cauchy-Schwarz inequality states that: $$
\left( \sum_{i=1}^{n}{x_{i} y_{i}} \right)^{2} \leq \left( \sum_{i=1}^{n}{x_{i}^{2}} \right) \left( \sum_{i=1}^{n}{y_{i}^{2}} \right)
$$ This is actually a special case of the more general Cauchy-Schwarz inequality, but this post is just to show a neat proof (straight from Wikipedia) of this special case, which will be used in a few other posts. You'll need to recall quadratics and discriminants from algebra for this proof.

Proof of Cauchy-Schwarz for $\Bbb{R}^{n}$: If all the $x_i$'s or all the $y_i$'s are zero, then both sides of the inequality are zero, and the inequality is trivially true. So assume that at least one of the $x_i$'s and at least one of the $y_i$'s are non-zero. Regard the $x_{i}$'s and $y_{i}$'s as fixed for a moment, and consider the following quadratic polynomial in the variable $z$ : $$
p(z) &= (x_1 z + y_1)^{2} + (x_2 z + y_2)^{2} + \dotsb + (x_n z + y_n)^{2} \\[3mm]
&= \underbrace{\left( \sum_{i=1}^{n}{x_{i}^{2}} \right)}_{a} z^2
+ \underbrace{\left( 2 \sum_{i=1}^{n}{x_{i} y_{i}} \right) }_{b} z
+ \underbrace{\left( \sum_{i=1}^{n}{y_{i}^{2}} \right) }_{c}
$$ From the first formula, $p(z)$ is the sum of squares, so we know that $p(z) \geq 0$ for any value of $z$. Furthermore, since $a$ is the sum of squares, we also have $a > 0$ (strictly greater, since at least one of the $x_i$'s is non-zero), which means the graph of $p(z)$ is an upward-opening (i.e. "holds water") parabola.

These two facts combined mean that $p(z)$ has at most one real root, and so the discriminant $b^2 - 4ac \leq 0$. Thus $$
\left( 2 \sum_{i=1}^{n}{x_{i} y_{i}} \right)^2 - 4 \left(  \sum_{i=1}^{n}{x_{i}^{2}} \right) \left( \sum_{i=1}^{n}{y_{i}^{2}} \right) \leq 0 \\[3mm]
\Downarrow \\[3mm]
\left( \sum_{i=1}^{n}{x_{i} y_{i}} \right)^2 \leq \left(  \sum_{i=1}^{n}{x_{i}^{2}} \right)
\left( \sum_{i=1}^{n}{y_{i}^{2}} \right)
$$ $\square$