Leaf Size, Tree Depth, and Empty-Cell Control

Why Leaf Occupancy Matters

A tree can divide the covariate space into many regions, but each terminal region must contain enough observations to support the estimate assigned to it. A leaf with very few observations produces an unstable estimate; a leaf with none cannot support a sample mean at all. Tree complexity therefore has a practical constraint: a partition must be rich enough to capture structure, yet its leaves must remain estimable.

Two controls are often used. A minimum leaf sample size restricts how many observations a terminal node may contain in the sample used to construct the tree. A maximum depth limits the number of splits along any root-to-leaf path. These controls constrain the tree, but they are not interchangeable. In particular, a depth limit controls the number of leaves, not the probability mass or estimation-sample occupancy of any particular leaf.

Definitions and Deterministic Constraints

If the tree has \(K\) leaves, two immediate constraints are \(K\leq 2^D\) and \(Km\leq n\). The first follows from binary branching: at depth \(d\), there can be at most \(2^d\) nodes. The second follows because the \(K\) terminal nodes are disjoint and each must contain at least \(m\) observations. Thus

These are upper bounds on the number of leaves, not guarantees that a tree with that many leaves is feasible. The observed covariates and permitted split rules may prevent some splits, and a particular tree may use fewer leaves. Nor does a large minimum leaf size imply that leaf occupancies are equal: the condition is a lower bound on each occupancy.

Proof. At depth zero there is one node. Each node can have at most two children, so induction gives at most \(2^d\) nodes at depth \(d\). Every leaf is at some depth no greater than \(D\); equivalently, a binary tree of depth at most \(D\) has at most \(2^D\) leaves. One way to see the latter directly is to extend any shallower leaf to depth \(D\) by adding hypothetical descendants: this cannot decrease the number of terminal positions at depth \(D\), and there are at most \(2^D\) such positions. Separately, the leaves partition the construction observations among disjoint cells. If each of \(K\) cells contains at least \(m\) observations, then \(n\geq Km\), hence \(K\leq\lfloor n/m\rfloor\). Combining the bounds proves the claim. \(\square\)

Independent Estimation Samples and Empty Cells

The construction-sample guarantee applies to the sample used to enforce the minimum-size rule. It need not carry over to a separate estimation sample. For example, a partition can be chosen using one sample and then its leaf estimates computed using another. Conditional on the chosen partition, the second sample falls into each cell according to that cell's probability mass.

The probability of an empty cell is exactly \((1-p_j)^{n_e}\), and it is at most \(\exp(-n_ep_j)\), since \(1-u\leq e^{-u}\) for \(u\geq0\). If every leaf has mass at least \(p_{\min}>0\), the union bound gives

This is a useful guarantee only when the leaves have a known positive mass lower bound. A maximum depth by itself gives no such bound: a single split may isolate a region with arbitrarily small probability. Even a finite number of leaves can therefore include a rare cell that is likely to receive no estimation observations.

Proof. Fix a leaf \(j\), and write \(\mu_j=n_ep_j\). For \(N_j\sim\operatorname{Binomial}(n_e,p_j)\), Markov's inequality applied to \(e^{-tN_j}\), with \(t=\log 2\), yields

Since \(1+v\leq e^v\), the last factor is at most \(\exp\{\mu_j(e^{-t}-1)\}\). Substituting \(t=\log 2\) gives an upper bound \(\exp\{-\mu_j(1-\log 2)/2\}\). Because \((1-\log 2)/2>1/8\), this is at most \(\exp(-\mu_j/8)\). The event \(N_j<\mu_j/2\) is contained in \(N_j\leq\mu_j/2\), so it has the same upper bound. Finally, apply the union bound over leaves and use \(\mu_j\geq n_ep_{\min}\). \(\square\)

The theorem controls occupancy relative to its expectation, not relative to a chosen integer minimum. To guarantee at least \(r\) observations with high probability, one can use the event \(N_j\geq\mu_j/2\): if \(n_ep_{\min}\geq2r\), this event implies \(N_j\geq r\) for every leaf. Its failure probability is at most \(K\exp(-n_ep_{\min}/8)\).

Occupancy and the Variance of Leafwise Estimates

Occupancy affects both whether an estimate can be computed and how variable it is. To make the variance statement precise, suppose that conditional on the estimation covariates, responses in a leaf have independent errors with mean zero and variance \(\sigma^2\). For a leaf \(A_j\) with \(N_j>0\), estimate its constant signal by averaging its responses after removing any fixed cellwise signal component. Conditional on the covariates, the variance of that average is \(\sigma^2/N_j\). Thus more observations reduce the noise variance, while an empty leaf makes the sample average undefined.

More generally, feasibility depends on the number of parameters being estimated within each leaf. A cellwise constant mean requires at least one observation to form a sample mean. A model with several leaf-specific coefficients needs enough observations and a design matrix of adequate rank; a raw count alone cannot guarantee that rank. Minimum leaf size can rule out obviously inadequate counts, but it cannot by itself ensure that every more complex leafwise fit is identifiable.

Common Mistake: Treating Depth as an Occupancy Guarantee

A tempting argument is: “The depth is bounded, so there cannot be many leaves; therefore every leaf must contain many observations.” The first part is correct, but the conclusion does not follow unless a sample size and a positive lower bound on cell probability are also considered. A small number of leaves can still include a very rare region.

For instance, suppose one leaf has probability \(p=0.005\), and the independent estimation sample has \(n_e=200\). Its expected count is only \(n_ep=1\), and its exact empty probability is

So this leaf is empty with probability about 0.367, despite the partition having a finite number of leaves. A depth cap can limit the total number of opportunities for empty cells, but it cannot remove the risk from a rare cell. The correction is to separate three questions: how many leaves can the tree have, how much probability mass each leaf carries, and how many independent observations are available to estimate it.

Using the Constraints Together

A practical analysis checks both deterministic and probabilistic constraints. The minimum construction-sample size and maximum depth cap the tree's complexity through the leaf-count bound. If a separate estimation sample is used, cell-probability assumptions and its sample size determine whether each leaf is likely to be occupied. When an occupancy lower bound \(r\) holds, it also bounds the conditional noise variance by \(\sigma^2/r\).

These controls express a bias–variance tension rather than a universal recipe. Fewer, larger leaves tend to have more observations and more stable estimates, but can represent the regression function less finely. More leaves can improve local representation while increasing estimation variance and the chance of empty or underfilled cells. The appropriate constraints depend on the available sample size, the distribution of covariates, and the complexity of the leafwise estimate.