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

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?