= Solution
Let $m_i=\mathbb E(Y_i\mid X_i)$. Conditional on $X_{1:n}$,
$$
\gamma_j=\frac1{N_j+1}\sum_i
m_i\mathbf1_{\widehat R_j}(X_i).
$$
The responses are conditionally independent, so cross-covariances vanish and
$$
\boxed{
\mathbb E[(\widetilde\gamma_j-\gamma_j)^2\mid X_{1:n}]
=\frac1{(N_j+1)^2}\sum_i
\operatorname{Var}(Y_i\mid X_i)
\mathbf1_{\widehat R_j}(X_i)}.
$$
Because the regions partition predictor space,
$$
\widetilde T(X)-\mathbb E(\widetilde T(X)\mid X,X_{1:n})
=\sum_j\mathbf1_{\widehat R_j}(X)
(\widetilde\gamma_j-\gamma_j).
$$
Only one summand is nonzero. Put
$q_j=\mathbb P(X\in\widehat R_j)$; the partition is deterministic because $D'$ is fixed, and $N_j\sim\operatorname{Bin}(n,q_j)$. The variance bound and
$N_j/(N_j+1)^2\leq1/(N_j+1)$ give
$$
\begin{aligned}
\mathbb E[\{\widetilde T(X)-\mathbb E(\widetilde T(X)\mid X,X_{1:n})\}^2]
&\leq\sigma^2\sum_jq_j\,
\mathbb E\frac1{N_j+1}\\
&\leq\sigma^2\sum_{j:q_j>0}\frac1n
\leq\boxed{\frac{\sigma^2J}{n}}.
\end{aligned}
$$
This is the <conditional variance of a fixed regression-tree partition> bound.
Back to article page
