2
$\begingroup$

This question is basically a part of an algorithmic problem about dynamic programming I was trying to solve.

You need to consider two things that I'm about to compare below:

  1. Variance
  2. Unfairness Sum - defined and explained below

Unfairness Sum-

Let's say we have a list of positive integers denoted as myList. The Unfairness Sum of myList is defined as the sum of the absolute differences of all the pairs (explained below) in myList.

To Explain
For example, if

myList = $\{1, 2, 5, 5, 6\}$

Then the Unfairness Sum will be (note that numbers are considered unique based on their index-or position- in list, not their values)

$$\text{Unfairness Sum}= |1-2| + |1-5| + |1-5| + |1-6| + |2-5| + |2-5| + |2-6| + |5-5| + |5-6| + |5-6|$$

What I want to know

Can I say that variance & Unfairness Sum are perfectly related (I know they are strongly related because this approach of variance has worked for half of my test cases - having up to a max of 9000 integers`)?

In other words,
Can I say that among a lots of lists of positive integers, a list with minimum variance will always be the list with Minimum unfairness sum?

$\endgroup$
3
  • 1
    $\begingroup$ The way you have defined it, every list has a minimum unfairness sum. So I think your question is about minimum variance versus minimum minimum unfairness sum. $\endgroup$ Sep 7, 2020 at 13:14
  • $\begingroup$ @Gerry I realized it now. I have edited the question to make it more clear. $\endgroup$ Sep 7, 2020 at 13:29
  • $\begingroup$ Also thank you @integrand for helping me out by editing the question according to math formatting styles :) $\endgroup$ Sep 7, 2020 at 13:32

1 Answer 1

2
$\begingroup$

The list that minimizes the absolute sum does not always minimize the variance sum. Consider two lists: $\{1, 1, x\}$ and $\{1, 2, 3\}$ where $x$ is a real number that satisfies $x \geq 1$.

We get \begin{align} a(1,2,3) &= |1-2| + |1-3| + |2-3| = 4\\ v(1,2,3) &= (1-2)^2 + (2-2)^2 + (3-2)^2 = 2 \end{align} and \begin{align} a(1,1,x) &= |1-1| + |1-x| + |1-x| = 2(x-1)\\ v(1,1,x) &= (1 - \frac{(2+x)}{3})^2 + (1 - \frac{(2+x)}{3})^2 + (x - \frac{(2+x)}{3})^2 \end{align} where we have used $x\geq 1$ to claim $|1-x|=x-1$. We want to find $x\geq 1$ that satisfies: \begin{align} &a(1,2,3) > a(1,1,x)\\ &v(1,2,3)<v(1,1,x) \end{align}


To find such a value $x\geq 1$, we have $$a(1,2,3)>a(1,1,x) \iff 4 > 2(x-1) \iff x<3$$ However \begin{align} &v(1,2,3)<v(1,1,x) \\ &\iff 2<(1 - \frac{(2+x)}{3})^2 + (1 - \frac{(2+x)}{3})^2 + (x - \frac{(2+x)}{3})^2 \end{align} There are values $x \geq 1$ that satisfy both inequalities, for example $x=2.8$.

$\endgroup$
7
  • $\begingroup$ Interesting... However x has to be a positive integer not a floating point (decimal value) number, does that make a difference? $\endgroup$ Sep 7, 2020 at 17:16
  • 1
    $\begingroup$ It does not make a difference. Just multiply everything by a factor of 10. Note that $a(10(b_1, ..., b_n)) = 10a(b_1, ..., b_n)$ and $v(10(b_1,...,b_n)) = 100v(b_1, ..., b_n)$. $\endgroup$
    – Michael
    Sep 7, 2020 at 17:18
  • $\begingroup$ That does it for me, thank you for your help :) $\endgroup$ Sep 7, 2020 at 17:21
  • $\begingroup$ I will consider what happened with me in regards of my test cases, was a coincidence (or a strong relation) $\endgroup$ Sep 7, 2020 at 17:23
  • 1
    $\begingroup$ You can check the same example for standard deviation, the resulting inequality needed is $\sqrt{v(1,2,3)}<\sqrt{v(1,1,x)}$ which is different but is satisfied when $x>(3+\sqrt{3})/3$, for which $x=2.8$ also works: wolframalpha.com/input/… The quadratic penalty associated with outliers is indeed the intuition that I used to construct this example. But in general nonlinear operations can be unusual and it is no surprise that different nonlinear operations result in different orderings. $\endgroup$
    – Michael
    Sep 8, 2020 at 7:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .