I recently came across the following summation in the definition of the Gini impurity in a machine learning lecture on decision trees:

$$\sum_{i \ne j}{P(\omega_i)P(\omega_j)} \space\space\space i,j \in c$$

Based on the formulas used in the lecture, the above summation involves only combinations. In other words, if $(i,j)=(1,2)$ is included then $(2,1)$ is not. This is intuitively how I would interpret the notation, and how my professor did as well.

However, based on the formulas in Wikipedia, the above summation should be over all permutations. Indeed, if I were to write it more explicitly as shown below, then this way makes sense too:

$$\sum_i\sum_j{P(\omega_i)P(\omega_j)} \space\mid\space i \ne j$$

So is either of these correct or accepted? And regardless, how would one explicitly write the double summation over all combinations as I did for permutations?

  • $\begingroup$ Just a hint $\sum_{i} \sum_{j} P(\omega_{i})P(\omega_{j})=\sum_{i} P(\omega_{i}) ( \sum_{j} P(\omega_{j}))$ you can do the same with the first sum. $\endgroup$ – rtybase Nov 10 '15 at 22:48

I have seen, and used, the notation $$\sum_{i \ne j}{P(\omega_i)P(\omega_j)}$$ many times before, and it never once occurred to me that somehow if $i = 2$ and $j = 1$ is included, then you should exclude $i = 1$ and $j = 2$. If you want to do that, then you should use a notation that explicitly says so, such as $$\sum_{i > j}{P(\omega_i)P(\omega_j)}.$$

Just because this particular sum treats $i$ and $j$ symmetrically does not mean all such sums do. If you are summing some $F(i, j)$ where in general $F(i, j) \ne F(j, i)$, then how would you decide which of $(1,2)$ and $(2,1)$ to include in the sum?.

It is possible that the lecture made some use of the fact that $$\sum_{i \ne j}{P(\omega_i)P(\omega_j)} = 2\sum_{i > j}{P(\omega_i)P(\omega_j)},$$ instead of interpreting it in in what I have to call an inappropriate fashion.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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