Self-study question

Given $(y_i, x_i)$, $i = 1, . . . , n$, where $y_i \in \mathbb{R}$ and $x_i ∈ R ⊂ \mathbb{R}^p$.

Show that $\displaystyle \sum_{i:x_i \in R_1}(y_i − \hat{y}_{R_{1}})^2 +\sum _{i:x_i \in R_2}(y_i − \hat{y}_{R_{2}})^2 \leq \sum_{i:x_{i} \in R}(y_i − \hat{y}_{R})^2$

where $\hat{y}_{R_{j}}$ is the mean response for the training observations within the $j$th region, and $R = R_1 \cup R_2, R_{1} \cap R_{2} = \{ \}$. Also,

$$\hat y_{R_1}=\frac{1}{n_1}\sum_{i:x_i\in R_1} y_i,$$ $$\hat y_{R_2}=\frac{1}{n_2}\sum_{i: x_i\in R_2} y_i,$$

where $n_{1}$ and $n_{2}$ are number of observations in $R_{1}$, and $R_{2}$, respectively.

My approach:

So, I solved it in a very long way, but I was hopping that someone will propose a much simpler solution (Note: I skipped several steps between the first and the second line)

\begin{align*} \sum_{i=1}^n (y_i - \bar{y})^2 &= \sum_{i=1}^n y_i^2 - n \, \bar{y}^2 \\ &= \sum_{i=1}^{n_{1}} (y_i -\bar{y}_{1})^{2}+\sum_{i=n_{1}+1}^{n} (y_{i} - \bar{y}_{2})^{2}+ \frac{n_{1} \, n_{2}}{n} \, (\bar{y}_{1}-\bar{y}_{2})^{2}\\ & \geq \sum_{i=1}^{n_{1}}(y_i -\bar{y}_{1})^{2}+\sum_{i=n_{1}+1}^{n} (y_{i} - \bar{y}_{2})^{2} \end{align*}


1 Answer 1


Your first step was unhelpful, I think. I would keep the residuals inside the square. First add and subtract the region mean

$$\sum_{i=1}^n (y_i-\bar y)^2=\sum_{i=1}^{n_1} (y_i-\bar y+\bar y_1-\bar y_1)^2+\sum_{i=n_1+1}^{n} (y_i-\bar y+\bar y_2-\bar y_2)^2$$

Now, rearrange

$$\sum_{i=1}^{n_1} (y_i-\bar y+\bar y_1-\bar y_1)^2=\sum_{i=1}^{n_1} (y_i-\bar y_1)^2+\sum_{i=1}^{n_1} (\bar y_1-\bar y)^2$$ and the same for the second region, to get

$$\sum_{i=1}^n (y_i-\bar y)^2=\sum_{i=1}^{n_1} (y_i-\bar y_1)^2+\sum_{i=1}^{n_1} (\bar y_1-\bar y)^2+\sum_{i=n_1+1}^{n} (y_i-\bar y_2)^2+\sum_{i=n_1+1}^{n} (\bar y_2-\bar y)^2$$ which is the thing you want plus two non-negative things.

If you don't think it's clear that $y_i-\bar y_1$ and $y_1-\bar y$ are uncorrelated (so that my second equality doesn't need a crossproduct term) there will be an additional step in the middle to show that


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.