Proof that Gini Impurity in a Decision Tree is Monotone Decreasing?

Question

I asked this in a reply to an answer to another of my questions; but I think this merits its own question since I couldn't find an answer, and it's a pretty interesting question on its own.

Suppose we construct a decision tree for classification based on the Gini impurity function. Can we prove that the weighted average of the Gini impurities of children nodes is always <= the Gini impurity of the parent node?

More precisely:

Let G(S)=sum_i p_i(1-p_i), where S is a finite nonempty set of points with known classification, p_i is the proportion of points in S with classification i, and the sum is taken over all classes. In the special case of binary classification, this simplifies to G(S)=2p(1-p), where p is the proportion of one of the classes.

Assume that every point x has a feature f. Denote the value of this feature by x(f). A splitting of S is defined as a partition of S into {S_left, S_right}, where S_left = {x in S: x(f) <= c} and S_right = {x in S: x(f) > c}. We require both of these sets to be nonempty.

A splitting is called good if

|S_left|/|S| G(S_left) + |S_right|/|S| G(S_right) <= G(S)

1. Must there always exist at least one good splitting?
2. Must all splittings be good?

Answer 1

I think I've got a proof. Any node can be identified with the vector (p_1,...,p_k) that gives the proportion of points with each classification. The Gini impurity function can then be viewed as a function from R^k to R. The weighted average of the proportions of points in S_left and S_right belonging to a certain class is equal to the proportion of points in S belonging to that class. Thus the inequality is just stating that the Gini impurity function is concave. But that is true; its matrix of second derivatives is just a diagonal matrix whose diagonal entries are all -1.