Decision Tree Learning Deviation - Russell and Norvig
TL;DR: They are basically doing a chi-squared test to compare the distributions.

In more detail: Let's break this down into two parts, $\Delta = \Delta_1 + \Delta_2$ where

$$\begin{align*}
\Delta_1 &amp;= \sum_{k=1}^d \frac{(p_k-\hat{p}_k)^2}{\hat{p}_k}\\
\Delta_2 &amp;= \sum_{k=1}^d \frac{(n_k-\hat{n}_k)^2}{\hat{n}_k}.
\end{align*}$$

Then $\Delta_1$ is the test statistic for a chi-squared test of the goodness of fit between the two distributions $p_k$ and $\hat{p}^k$.  Similarly, $\Delta_2$ is the test statistic for the goodness of fit between $n_k$ and $\hat{n}_k$.

If the distribution $p_k$ is similar to $\hat{p}_k$, and $n_k$ is similar to $\hat{n}_k$, then $\Delta$ will be small (the former means that $\Delta_1$ will be small, and the latter means that $\Delta_2$ will be small).  Conversely, if $p_k$ is not similar to $\hat{p}_k$, or $n_k$ is not similar to $\hat{n}_k$, then $\Delta$ will be large (in the former case, $\Delta_1$ will be large; in the latter case,  $\Delta_2$ will be large).

So this is a convenient measure of the total deviation between these distributions: a convenient way to get a single number to help us measure the extent to which both $p_k$ is similar to $\hat{p}_k$  and $n_k$ is similar to $\hat{n}_k$.

The chi-squared test is a standard test for goodness of fit, so its test statistic is a reasonable choice here.  As for why the chi-squared test  is a good test for measuring goodness of fit, you can read the standard literature on the chi-squared test.