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 les than or equal to the Gini impurity of the parent node?

More precisely:

Let $G(S)=\displaystyle\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) \leq 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

$$\frac{|S_{left}|}{|S|} G(S_{left}) + \frac{|S_{right}|}{|S|} G(S_{right}) \leq 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.