proving the approach correct

In the fine tradition of "digging deeper," I wanted to understand the solution to this problem more completely. I mean, when I read the problem statement, it did not jump out at me instantly that the value of x that minimizes

f(x) = k/n * ((x-a1)^2 + (x-a2)^2 + ... + (x-an)^2) is the artihmetic mean of a1...an

If you look at the example, you may think "Aha! The output is the average of the input!" But the solver must beware, test writers just love to mislead by simple example cases that do not reveal the entire subtlety of the problem. They'll get you with one of those WA#12s if you're not careful.

So I dusted off my calculus and recalled that to calculate the min/max of a function, find the derivative of f(x) and set it to zero, and then solve for x. So here we go...

f(x) = k * (x^2 -2(a1)x + (a1)^2 + x^2 -2(a2)x + (a2)^2 + ... + x^2 -2(an)x + (an)^2) / n

= k (x^2 - (2/n)(a1 + a2 + ... + an)x + ((a1)^2 + (a2)^2 + ... + (an)^2)/n

so we have

f'(x) = k(2x - (2/n)(a1 + a2 + ... + an))

setting to zero and solving for x gives

x = (a1 + a2 + ... + an) / n

Voila! Not a guess, but good solid derivation. Oh, and we can be sure that this is minimum rather than a maximum because the function is an upward opening parabola (since we assume that k is positive).

*Edited by author 04.10.2012 01:16*

Re: proving the approach correct

Posted by

BillSu 26 Apr 2014 18:21

Thanks.

Best Explanation.

Re: proving the approach correct

You may also see it in this way: the variance of samples x1..xn is the one that minimizes the sum of (xi-a)^2.

Re: proving the approach correct

I guess it's extremum, isn't it? We haven't learnt that makes it a little difficult(

*Edited by author 16.04.2016 23:55*

Re: proving the approach correct

I didn't know any extremums and others but now I know a little with this site: mathprofi.ru

Re: proving the approach correct

Posted by

AB&B 14 Mar 2021 17:50

You are great, thank you!

Re: proving the approach correct

I haven't studied calculus yet, so i came up with the quadratic equation and it turns out to be correct, yet I don't even know how to prove it.