Out-of-bag counts

Topic: Ensembles, random forests, and boosting · more questions on this topic
‹ Variance of an average One round of AdaBoost ›

Each observation is excluded from a given bootstrap sample with probability (1-1/n)^n. For n=200 and T=500 trees, how many trees are out-of-bag for an observation on average, and what is the probability that an observation is in every bootstrap sample?

Worked answer (click to show)

\Bigl(1-\frac{1}{200}\Bigr)^{200}=0.3669,

so an observation is out-of-bag for about 0.3669\times 500\approx 184 of the 500 trees. The probability that it is in every bootstrap sample is

(1-0.3669)^{500}=0.6331^{500} =\exp(500\log 0.6331) =\exp(-228.6) \approx 10^{-99}.

A zero out-of-bag count is extraordinarily unlikely under independent bootstrap draws. The count is still random, with expectation about 184.