Prev: an irreducible cubic?
Next: PROOF OF A WEIGHTED MINUS 1 IN PURE MATHEMATICS-- ERROR OF SQRT 3
From: Golabi Doon on 31 Jul 2010 09:31
Hello,

Consider a set of pairs (r_k,x_k) for k=1...n. Assume that r_k>=0 and
1>=x_k>=0. Let s be any number such that s>=sum_k r_k.

Does the following always hold? If yes, how you prove it?

sum_k ((r_k /s)*(x_k^2)) >= (sum_k (r_k/s)*x_k)^2

Thanks

Golabi
From: Ilmari Karonen on 31 Jul 2010 12:41
On 2010-07-31, Golabi Doon <golabidoon(a)gmail.com> wrote:
>
> Consider a set of pairs (r_k,x_k) for k=1...n. Assume that r_k>=0 and
> 1>=x_k>=0. Let s be any number such that s>=sum_k r_k.
>
> Does the following always hold? If yes, how you prove it?
>
> sum_k ((r_k /s)*(x_k^2)) >= (sum_k (r_k/s)*x_k)^2

It should follow from the convexity of the function x -> x^2.

In particular, it should suffice to consider the case s = sum r_k.
(We can reduce the more general case to this by appending a suitable
r_(n+1) to our sum, with x_(n+1) set to 0. Or we can just observe
that increasing s will always reduce the right hand side faster than
the left.)

Then your equation may be stated verbally as "the weighted mean of the
squares is never less than the square of the weighted mean".

Geometrically, this is equivalent to observing that the convex hull of
the points (x_k, x_k^2) in R^2 lies entirely on or above the curve (z,
z^2) for z in R. To see this, let m_1 = sum (r_k x_k) / sum r_k be
the weighted mean of the points x_k, and let m_2 = sum (r_k x_k^2) /
sum r_k be the weighted mean of their squares.

Then the point (m_1, m_2) will always lie in the convex hull of (x_k,
x_k^2), while (m_1, m_1^2) lies on the curve (z, z^2) (as do the
corners of the convex hull). The fact that the lower boundary of the
convex hull consists of line segments, each of which lies above the
curve (except for their endpoints, which are _on_ the curve) then
completes the proof.

Algebraically, we can show the same by using the definitions of m_1
and m_2 from above and, by completing the square and moving constant
factors inside the sum, showing that:

m_2 - m_1^2
= m_2 - 2 m_1^2 + m_1^2
= m_2 - 2 m_1 sum (r_k x_k) / sum r_k + m_1^2
= m_2 - 2 m_1 sum (r_k x_k) / sum r_k + m_1^2 sum r_k / sum r_k
= m_2 - sum (2 m_1 r_k x_k) / sum r_k + sum m_1^2 r_k / sum r_k
= sum (r_k ( x_k^2 - 2 m_1 x_k + m_1^2 )) / sum r_k
= sum (r_k ( x_k - m_1 )^2) / sum r_k

Given that this is the ratio of two sums of non-negative terms, it
cannot be negative, which shows that m_2 >= m_1^2 (QED).

Incidentally, I didn't just come up with all of that off the top of my
head; I just noticed that that the verbal formulation I gave above
sounded familiar, and realized that m_2 - m_1^2 is simply the formula
for the weighted sample variance of x_k wieghted by r_k, which I could
then look up.

BTW, note that your restriction that x_k belong to [0,1] is not
necessary: the same results hold for arbitrary real or even complex
x_k, or even for vectors with x_k^2 defined as x_k . x_k and for all
sorts of other things for which we can meaningfully define squaring
and multiplication by a real number.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
From: Golabi Doon on 2 Aug 2010 05:51
Thank you a lot Ilmari. I am amazed with your answer, not only due to
the time you spent for such a thorough response, but also making
connections between geoemtric and algebraic interpretation and showing
that the assumption on x_k in [0,1] is not necessary.

Regards

Golabi

On Jul 31, 11:41 am, Ilmari Karonen <usen...(a)vyznev.invalid> wrote:
> On 2010-07-31, Golabi Doon <golabid...(a)gmail.com> wrote:
>
>
>
> > Consider a set of pairs (r_k,x_k) for k=1...n. Assume that r_k>=0 and
> > 1>=x_k>=0. Let s be any number such that s>=sum_k r_k.
>
> > Does the following always hold? If yes, how you prove it?
>
> > sum_k ((r_k /s)*(x_k^2)) >= (sum_k (r_k/s)*x_k)^2
>
> It should follow from the convexity of the function x -> x^2.
>
> In particular, it should suffice to consider the case s = sum r_k.
> (We can reduce the more general case to this by appending a suitable
> r_(n+1) to our sum, with x_(n+1) set to 0.  Or we can just observe
> that increasing s will always reduce the right hand side faster than
> the left.)
>
> Then your equation may be stated verbally as "the weighted mean of the
> squares is never less than the square of the weighted mean".
>
> Geometrically, this is equivalent to observing that the convex hull of
> the points (x_k, x_k^2) in R^2 lies entirely on or above the curve (z,
> z^2) for z in R.  To see this, let m_1 = sum (r_k x_k) / sum r_k be
> the weighted mean of the points x_k, and let m_2 = sum (r_k x_k^2) /
> sum r_k be the weighted mean of their squares.
>
> Then the point (m_1, m_2) will always lie in the convex hull of (x_k,
> x_k^2), while (m_1, m_1^2) lies on the curve (z, z^2) (as do the
> corners of the convex hull).  The fact that the lower boundary of the
> convex hull consists of line segments, each of which lies above the
> curve (except for their endpoints, which are _on_ the curve) then
> completes the proof.
>
> Algebraically, we can show the same by using the definitions of m_1
> and m_2 from above and, by completing the square and moving constant
> factors inside the sum, showing that:
>
>     m_2 - m_1^2
>   = m_2 - 2 m_1^2 + m_1^2
>   = m_2 - 2 m_1 sum (r_k x_k) / sum r_k + m_1^2
>   = m_2 - 2 m_1 sum (r_k x_k) / sum r_k + m_1^2 sum r_k / sum r_k
>   = m_2 - sum (2 m_1 r_k x_k) / sum r_k + sum m_1^2 r_k / sum r_k
>   = sum (r_k ( x_k^2 - 2 m_1 x_k + m_1^2 )) / sum r_k
>   = sum (r_k ( x_k - m_1 )^2) / sum r_k
>
> Given that this is the ratio of two sums of non-negative terms, it
> cannot be negative, which shows that m_2 >= m_1^2 (QED).
>
> Incidentally, I didn't just come up with all of that off the top of my
> head; I just noticed that that the verbal formulation I gave above
> sounded familiar, and realized that m_2 - m_1^2 is simply the formula
> for the weighted sample variance of x_k wieghted by r_k, which I could
> then look up.
>
> BTW, note that your restriction that x_k belong to [0,1] is not
> necessary: the same results hold for arbitrary real or even complex
> x_k, or even for vectors with x_k^2 defined as x_k . x_k and for all
> sorts of other things for which we can meaningfully define squaring
> and multiplication by a real number.
>
> --
> Ilmari Karonen
> To reply by e-mail, please replace ".invalid" with ".net" in address.

 | 
Pages: 1
Prev: an irreducible cubic?
Next: PROOF OF A WEIGHTED MINUS 1 IN PURE MATHEMATICS-- ERROR OF SQRT 3