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:
- Variance
- 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?
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$.