On weighted means, geometric and arithmetic

On weighted means, geometric and arithmetic.

Notation and nomenclature

Function application is denoted by an infix dot ".", function composition by an infix ringlet "。" [i.e., $g\left( {h.x}\right) = \left( {g \circ h}\right) \cdot x\rbrack$ .

Dummy variable i ranges over some finite, non-empty domain D.

Function $p$ is of type $D \rightarrow R$ and satisfies

$\left\langle {\forall i : 0 \leq p,i}\right\rangle \land \left\langle {\sum i : p,i}\right\rangle = 1$

For any function $q$ of type $D \rightarrow R$ ,the weighted average w.q. is defined by

(1) $w \cdot q = \left\langle {\sum i : p \cdot i * q \cdot i}\right\rangle$

Finally, function $a$ of type $\mathcal{D}\to \mathbb{R}$ satisfies $\langle \forall i:0 < a.i\rangle$

The theorem

The well-known fact that the geometric mean is at most the arithmetic mean, i.e., with $N$ equal to the number of elements in $D$ .

(2) $\sqrt[N]{\left\langle \pi i : a.i \right\rangle} \leqslant \left\langle \sum i : a.i \right\rangle / N$ ,

is a special case of

(3) $\left\langle {\pi i : a.i}^{p,i}\right\rangle \leq \left\langle {\sum i : p.i * a.i}\right\rangle$

[Take $p.i = 1/N$ , and (3) reduces to (2).] Our target is to prove (3). Taking logarithms of both sides we are led to the relation (4) $w \cdot \left( {{\log }^{a}a}\right) \leq {\log }^{a}\left( {w.a}\right)$

Because of the monotonicity of the exponent, (4) implies (3); our target is now to prove (4).

The proof

Our proof uses two facts:

(i) When weights p.i are placed at points belonging to a convex region, their centre of gravity belongs to that region as well. [Note that this is a possible definition of convexity.]

(ii) In the Cartesian plane, the points on or below the curve $y = \log x$ [i.e., the points $(x,y)$ such that $0 < x \land y \leq \log x$ ] form a convex region. [This is a direct consequence of the fact that the 2nd derivative of the logarithm is negative.]

Let the weights $p.i$ be placed at (a.i, $\log .\left( {a.i}\right) )$ -i.e.,all the weights are on the curve $y = \log x -$ . Then their centre of gravity $C$ is at

(5) $\left( {w.a,w.\left( {{\log }^{a}a}\right) }\right)$

Because of facts (i) and (ii), $C$ lies on or below the curve $y = \log .x$ , i.e. is a point $(x,y)$ such that $y \leq \log .x$ ; in terms of (5) this means $w.(10^{\circ}a) \leq 10^{\circ}a$ .

which is what had to be proved.

In retrospect

In my initial endeavours to prove (3), I tried mathematical induction over the size of $D$ . I noticed (i) that I got formulae that reminded me of the centre of gravity and (ii) that the exponentiation in particular gave rise to ugly formulae. The step from the centre of gravity to convexity

is very small. [I felt that I was benefiting from my past as a physicist.] To get rid of the exponentiation, I decided to take logs. rithms, feeling free to do so because (3) and (4) are as a matter of (simple) fact equivalent. But (4) is so much more beautiful than (3) that I suddenly knew that I was on a very promising track. Please note that we can even write (4) as

[\left( {4!}\right) \;w.\left( {{\log }^{a}a}\right) \leq \left( {{\log }^{a}w}\right) \cdot a]

in which both sides contain the same col- lection of symbols. [During this play with symbols I felt I was profiting from my familiarity with functional programming.]

Connecting convexity with the logarithm was the last, in fact simple and obvious step. In order to appreciate how well we disentangled the argument, the reader is invited to prove (under the same conditions)

$$ \langle \sum i: p. i * a. i \rangle \leq \sqrt [ 2 ]{\langle \sum i : p . i * (a . i) ^ {2} \rangle} $$

Acknowledgement

I would like to express my gratitude to

the members of the Austin Tuesday Afternoon Club who joined me in the first exploration of the theorem and whose comments on my draft helped me with the proof's presentation. Finally I would like to express my gratitude to Dr. Martin Peters and Ruth Allewelt of Springer-Verlag for making a present to me of [0], where I found the theorem. [Needless to say, I prefer my proof.]

[0] Aigner, Martin & Ziegler, Gunther M., "Proofs from THE BOOK", Springer-Verlag Berlin, Heidelberg, New York, 1998 [ISBN 3-540-63698-6]

Austin, 9 February 2000

pror. dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 USA