online advertising

Friday, November 11, 2016

Minimizing sum of distances

Problem:

Find $ m $ such that $ \sum_{i = 1}^{n}{\left|x_i - n\right|} $ is minimized.

Solution:

The reaction is that the mean is going to minimize it, but it isn't true. The median will.

Consider a random $ m $, suppose there are $ a $ numbers in $ x_i $ are less than $ m $ and $ b $ numbers of $ x_i $ are larger than $ m $.

If we decrease $ m $ by 1, we change the sum by $ b - a $.
If we increase $ m $ by 1, we change the sum by $ a - b $.

Therefore, as long as $ a \ne b $, we can always reduce the sum, therefore, the only reasonable answer is the median.

This is for the case of odd number of elements, in case we have even number of element, any number between the two center elements would give the same minimal distance sum.

Thanks Sven for generalizing the problem, and Noah for the idea about median.

No comments:

Post a Comment