# What is the limit of the random forest (or bagging) estimator?

I am looking for a proof or intuition as to why the absolute limit of a random forest estimator is the expectancy of a single tree (see citation below), i.e:

$$\hat{f}_{rf}(x) = \lim_{B \to \infty}[\hat{f}^B_{rf}(x)] = \lim_{B \to \infty}[\frac{1}{B}\sum_{b=1}^BT(x;\Theta_b)]=E_{\Theta|Z}[T(x;\Theta(Z))] \tag{1}\\$$

where $$Z$$ = current sample (not bootstrap); $$T(x;\Theta_b)$$ = prediction for the tree grown on the $$b^{th}$$ bootstrapped sample with parameters $$\Theta_b$$ (split variables, split points, leaf values).

Since random forest / bagging is an average and a tree is a random variable, how can the limit converge absolutely? I thought a LLN or CLT could be applicable, but those are based on convergence in probability ($$plim = \overset{p}{\to}$$) or in distribution ($$dlim = \overset{d}{\to}$$). Since the trees are not independent (only $$id$$ identically distributed, not $$iid$$), not even a basic WLLN is applicable because the variance never fully vanishes (see convergence in mean-square).

Source: (1) is cited from

2008. Elements of Statistical Learning 2nd Ed, Equation 15.3. Hastie, Tibshirani, Friedman

2008. Elements of Statistical Learning 2nd Ed, Equation 15.4. Hastie, Tibshirani, Friedman

Resources: I could not find the answer (so far) in the following papers:

Stefan Wager. Asymptotic Theory For Random Forest (https://arxiv.org/pdf/1405.0352.pdf)

Jason M. Klusowski. Sharp analysis of a simple model for random forests (https://arxiv.org/pdf/1805.02587.pdf)

Gilles Louppe. UNDERSTANDING RANDOM FORESTS From Theory To Practice (https://arxiv.org/pdf/1407.7502.pdf)

• What makes random forest id, instead of iid? Which "i" do you think not hold? – Kota Mori Oct 30 '20 at 13:36
• Trees in a random forest / bagging are not independent since they are all generated from the same sample through bootstrapping. They are only identically distributed. I am assuming because they are generated by the same algorithm (see EoSL link). I edited the question for clarity. – PaulG Oct 30 '20 at 15:22

$$\hat{f}_{rf}(x) = \mathrm{E}_\Theta T(x; \Theta) = \lim_{B\to\infty} \hat{f}^{B}_{rf}(x)$$ ... The distribution of $$\Theta$$ is conditional on the training data.
• That part I am not sure. Given that a random forest prediction $\hat{f}^{B}_{rf}$ for a given $B$ is random, I suppose this should be "plim" or "a.s. lim". But I'm not sure if this is just lazy notation or the authors actually mean "deterministic" convergence rather than "probabilistic" for some reason. I hope some other folks kindly clarify this. – Kota Mori Oct 30 '20 at 19:16