# 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 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?