6
$\begingroup$

Say I have two vectors [1,2,1,2,2] and [1,2,1,1,1]. The number at each dimension is the frequency of one element. How do I measure whether these two vectors are close to the uniform distribution? I know if this is continuous values, I can calculate the entropy of the two vectors. The one with higher entropy is closer to a uniform distribution. But now I am solving a discrete optimization problem so I can only use integer values.

Currently, I am thinking calculating the value max([1,2,1,2,2]) - min([1,2,1,2,2]). The vector with the lower score is closer to the uniform distribution. Is there a better method?

$\endgroup$
9
  • 3
    $\begingroup$ What's "better" depends on what you want it to be good at. A more "typical" measure might be a chi-square statistic, or perhaps some concentration/diversity index (whether you choose one or the other, or something else might in part depend on what these counts represent/what you're using it to do). The range of counts - as you suggest - might make sense in some situations, but it's hard to say much about what's better if it's not clear what the aim of this is. $\endgroup$
    – Glen_b
    Aug 24, 2020 at 10:53
  • 1
    $\begingroup$ Please check that my edits preserve your meaning. $\endgroup$
    – Nick Cox
    Aug 24, 2020 at 11:01
  • $\begingroup$ Yeah. I want to assign an objective function for the solver. So what you suggest is actually the objective function depends on my own heuristics strategies. $\endgroup$
    – hidemyname
    Aug 24, 2020 at 11:06
  • 2
    $\begingroup$ I agree with @Glen_b: it depends. I note that entropy is perfectly well defined for probabilities $p$ of discrete categories as $\sum p \log(1/p)$ where the logarithm is to whatever base (2, $e$, 10) you find congenial. I also flag that many people prefer to write $-\sum p \log p$, which in my view makes the meaning a little less transparent. For your examples and using natural logarithms entropy for both is almost identical at around 1.56. Further note that if you look at (1) SD of frequencies (2) SD of probabilities you get different answers! $\endgroup$
    – Nick Cox
    Aug 24, 2020 at 11:06
  • $\begingroup$ Thank you. The problem is that a discrete optimization solver would only accept integer values. $\endgroup$
    – hidemyname
    Aug 24, 2020 at 11:11

2 Answers 2

5
$\begingroup$

Your suggestion should work.

I'm going to make another suggestion, which also yields an integer value for the discrepancy from uniformity. As indicated in comments, we don't really have enough information to say whether it's better for your application.

The usual chi-squared goodness of fit statistic is $\sum_i (O_i-E_i)^2/E_i$ (where $O_i$ is the observed count in category $i$ and $E_i$ is the expected count). When used for deviation from perfect uniformity, $E_i=N/k$, where $N=\sum_i O_i$ is the total count and $k$ is the number of categories.

This chi-squared statistic from uniformity is also related to the simple variance of the counts.

Note that this statistic simplifies in the uniformity case, as follows:

\begin{eqnarray} \sum_i (O_i-E_i)^2/E_i &=& \sum_i (O_i-N/k)^2/(N/k)\\ &=& \frac{k}{N} \sum_i (O_i-N/k)^2\\ &=& \frac{k}{N} \sum_i [O_i^2-2N/k\cdot O_i+(N/k)^2]\\ &=& \frac{k}{N} [\sum_i O_i^2-2N/k \sum_i O_i+\sum_i (N/k)^2)]\\ &=& \frac{k}{N} [\sum_i O_i^2-2N/k\cdot N+ k\cdot(N/k)^2)]\\ &=& (\frac{k}{N} \sum_i O_i^2)-2N+ N\\ &=& (\frac{k}{N} \sum_i O_i^2)-N \end{eqnarray}

A simple linear rescaling of the chi-squared statistic is then $\sum_i O_i^2$, which will be integer-valued.

With $r={N\mod k}$, you could compute the smallest possible such value by putting $\lfloor N/k\rfloor$ (the average count rounded down) into $k-r$ bins and $\lceil N/k \rceil$ (the same, rounded up) into $r$ bins. It would be reasonable - but not necessary - to subtract the sum of squared counts for this arrangement from the above sum of squared counts. This would give an arrangement like $[1,2,1,2,2]$ get the value $0$, since it cannot be made smaller. If you'd like such an arrangement to get a non-zero value, the value of $\sum O_i^2$ under exactly equal allocation is $N^2/k$, but this won't be an integer in such cases, so you'd need to round that down before subtracting from $\sum O_i^2$ (rounding down would mean the difference $(\sum O_i^2)-\lfloor N^2/k\rfloor$ would only be exactly zero when the spread was perfectly uniform).

$\endgroup$
3
  • $\begingroup$ Thank you!!! I think this might be a good solution. Can you elaborate more on this? Maybe use one example to explain this? I am a little confused with notations here. $\endgroup$
    – hidemyname
    Aug 24, 2020 at 12:11
  • $\begingroup$ With your first set of values, $[1,2,1,2,2]$, $O_1=1, O_2=2, O_3=1, O_4=2, O_5=2$. Also $k=5$, $N=1+2+1+2+2=8$, $\sum O_i^2= 1+4+1+4+4 = 14$, and the minimum possible value is also $14$, so if you subtracted the minimum possible sum of squares you'd get $0$. $\endgroup$
    – Glen_b
    Aug 24, 2020 at 12:15
  • $\begingroup$ Alternatively if you subtracted $\lfloor N^2/k\rfloor$ (=$12$ here), you'd be left with the value $2$. $\endgroup$
    – Glen_b
    Aug 24, 2020 at 22:49
3
$\begingroup$

You can just as well use entropy in the discrete case as in the continuous case. The discrete uniform distribution on, say, $\{ 1,2,\dotsc,n \}$ also maximizes entropy among all distributions on that same support. Note that it does not matter if that support set is integers on just indices into some discrete set $\{ x_1, x_2, \dotsc, x_n \}$ since the entropy $$ H=-\sum_i p_i \log p_i $$ does not involve at all the actual values in the support set. That is an important difference from the continuous entropy $-\int f(x)\log f(x)\; dx$ which actually uses the values in the support via the differential $d x$.

So just use entropy, but there are also other possibilities.

$\endgroup$
2
  • $\begingroup$ I still don't get it. But log(p) should be non-integer, right? $\endgroup$
    – hidemyname
    Aug 25, 2020 at 14:02
  • $\begingroup$ why is that a problem? Even if you are solving a discrete maximization problem, the criterion function does not need to be integer-valued? Why? Maybe you should ask a question directly about that max problem, see en.wikipedia.org/wiki/XY_problem $\endgroup$ Aug 25, 2020 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.