= 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_{\rm rf}=B^{-1}\sum_b\widehat 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 EG\geq t)\leq\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. Therefore
$$
G\leq\mathbb EG+M\sqrt{2\log(1/δ)/B}
$$
with probability at least $1-δ$.
Back to article page
