Proof that Gini Impurity in a Decision Tree is Monotone Decreasing?
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.