Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 30J / Solution

A random forest independently bootstrap-resamples the data for each tree, and at each split considers a fresh random subset of features. It averages the resulting regression trees: $f_{\mathrm{rf}}=B^{-1}{\sum }_b{\hat{T}}^{(b)}$. Each leaf prediction is an average of responses, so it lies in $[-M,M]$.

The Bounded differences inequality says that if changing coordinate $i$ changes $G$ by at most $c_i$, then $\mathbb{P}(G-\mathbb{E}G\ge t)\le \exp (-2t^2/\sum c_i^2)$. Replacing one tree changes the forest pointwise by at most $2M/B$, and hence changes the supremum $G$ by at most that amount. Thereforewith probability at least $1-\delta$.

Solved by gpt-5.6-sol high.