Variance of Leafwise Sample Means

Why Leaf Counts Matter

For a fixed partition, a piecewise-constant regression estimate uses the observations in each cell to estimate a cell-specific mean. Under random design, the number of observations falling in a cell is itself random. A leaf with many observations has a stable average; a leaf with few observations has a noisier one. A leaf with no observations has no sample average at all, so the rule used for empty leaves also affects the estimator's variability and bias.

This tutorial isolates that variance contribution. The partition is fixed independently of the training sample, and the observations are independent and identically distributed. These assumptions let us identify the cell count distribution and the conditional distribution of observations within a cell.

Setup and Definitions

Let \((X_i,Y_i)\), \(i=1,\ldots,n\), be independent and identically distributed observations, with regression function \(m(x)=E[Y\mid X=x]\). Let \(A\) be one cell of a fixed partition, and write \(p=P(X\in A)\). We consider a cell with \(p>0\), so its conditional mean \(\mu=E[Y\mid X\in A]\) is defined. The number of observations in the cell is \(N=\sum_{i=1}^n \mathbf{1}\{X_i\in A\}\), and hence \(N\sim\operatorname{Binomial}(n,p)\).

Assume the response has the regression representation \(Y=m(X)+\varepsilon\), where \(E[\varepsilon\mid X]=0\) and \(\operatorname{Var}(\varepsilon\mid X)\leq \sigma^2\) almost surely. This is the bounded conditional noise assumption. Define \(s_A^2=\operatorname{Var}(Y\mid X\in A)\). When \(m(X)\) has finite variance in the cell, the conditional variance decomposition gives \(s_A^2=\operatorname{Var}(m(X)\mid X\in A)+E[\operatorname{Var}(\varepsilon\mid X)\mid X\in A]\). Thus \(s_A^2\leq \operatorname{Var}(m(X)\mid X\in A)+\sigma^2\). Bounded noise alone does not bound variation in \(m(X)\) within the cell; the two sources should not be conflated.

Variance and Mean Squared Error with Random Counts

Conditional on \(N=k>0\), the \(k\) responses in the cell have the distribution of independent draws from \(Y\mid X\in A\). Their average has mean \(\mu\) and variance \(s_A^2/k\). When \(N=0\), the estimate is the fixed number \(a\). Applying the law of total variance separates the sampling variation among nonempty leaves from the variation in conditional means between empty and nonempty cases.

Proof. For each \(k>0\), conditional on \(N=k\), the estimator is an average of \(k\) independent draws from the cell-conditional response distribution. Thus \(E[\hat{\mu}_A\mid N=k]=\mu\) and \(\operatorname{Var}(\hat{\mu}_A\mid N=k)=s_A^2/k\). At \(N=0\), the estimator equals \(a\) deterministically. Averaging the conditional means over \(N\) gives \(E[\hat{\mu}_A]=(1-q_0)\mu+q_0a\).

For the variance, the law of total variance gives \(\operatorname{Var}(\hat{\mu}_A)=E[\operatorname{Var}(\hat{\mu}_A\mid N)]+\operatorname{Var}(E[\hat{\mu}_A\mid N])\). The first term is \(s_A^2 E[\mathbf{1}\{N>0\}/N]\). The conditional expectation equals \(\mu\) with probability \(1-q_0\) and \(a\) with probability \(q_0\). A variable taking these two values has variance \(q_0(1-q_0)(a-\mu)^2\), proving the variance formula.

For the mean squared error, condition directly on \(N\). When \(N>0\), the conditional squared error has expectation \(s_A^2/N\), because the conditional estimator is unbiased for \(\mu\). When \(N=0\), the squared error is \((a-\mu)^2\). Taking expectations over \(N\) proves the final identity. \(\square\)

The reciprocal-count factor is not \(1/(np)\): the count is random, and the reciprocal is evaluated only when the count is positive. Its exact value is

This sum is the relevant finite-sample multiplier of the within-cell response variance. In particular, the empty-cell probability and reciprocal-count factor are both governed by the cell probability \(p\).

A Useful Finite-Sample Bound

An exact reciprocal-count sum is easy to state but not always convenient in a bound. The next inequality gives a simple upper bound, including the probability of an empty leaf.

Proof. For each integer \(k\geq1\), \(1/k\leq 2/(k+1)\), since \(k+1\leq2k\). Therefore \[ E\!\left[\frac{\mathbf{1}\{N>0\}}{N}\right] \leq 2E\!\left[\frac{1}{N+1}\right]. \] For \(N\sim\operatorname{Binomial}(n,p)\), expand the expectation and use \({n\choose k}/(k+1)={n+1\choose k+1}/(n+1)\): \[ E\!\left[\frac{1}{N+1}\right] =\sum_{k=0}^n \frac{1}{k+1}{n\choose k}p^k(1-p)^{n-k} =\frac{1-(1-p)^{n+1}}{(n+1)p}. \] The last equality follows by setting \(r=k+1\) and summing the binomial expansion over \(r=1,\ldots,n+1\). Since \(1-(1-p)^{n+1}\leq1\), the claimed upper bound follows. Finally, conditional on the covariates in a nonempty leaf, independent errors with conditional variances at most \(\sigma^2\) contribute at most \(\sigma^2/N\) to the variance of the average. Taking expectations and applying the bound proves the noise-only statement. \(\square\)

Interpretation and a Common Pitfall

For a cell of probability \(p\), the expected count is \(np\), but the variance multiplier is an expectation of a reciprocal count with the empty case handled separately. As \(np\) becomes small, empty leaves become more likely and the nonempty counts tend to be small. Both effects matter. With the zero convention, the empty-leaf term in the mean squared error is \(q_0\mu^2\); it is bias-related error, not sampling variance among nonempty averages.

A common mistake is to replace the random count by its expectation and write the variance as \(s_A^2/(np)\), then treat that as an exact unconditional formula. The actual term is \(s_A^2 E[\mathbf{1}\{N>0\}/N]\), and the estimator may also vary because it takes a separate value when \(N=0\). The approximation \(s_A^2/(np)\) can be useful when counts are reliably large, but it does not account exactly for random counts or empty leaves.

Another important distinction is between estimator variance and prediction error at a particular point \(x\) in the cell. The theorem targets \(\mu\); comparing the estimate to \(m(x)\) also involves the difference \(\mu-m(x)\). If the empty convention creates bias, the full squared-error calculation must retain that bias rather than adding a squared approximation term to variance as though the estimate were unbiased.