Random forest - Out-of-bag estimates

Question

I am reading the chapter on random forests by Leo Breiman (found here: https://www.stat.berkeley.edu/~breiman/randomforest2001.pdf).

In section 3.1 Using out-of-bag estimates to monitor error, strength, and correlation (page 11), it says:

In each bootstrap training set, about one-third of the instances are left out. Therefore, the out-of-bag estimates are based on combining only about one-third as many classifiers as in the ongoing main combination.

I am not sure I understand how the first sentence (that about one-third of cases are left out of each bootstrap sample) implies the second (that each case is OOB in about one-third of the trees)?

Answer 1

In a bootstrap sample we replace. The probability of a subject $x$ being sampled with replacement is at about $\frac{2}{3}$. If we build for example $1000$ trees with different bootstrap samples, we expect that $x$ will be in $\frac{2}{3} * 1000$ of these samples. We expect that one third of the trees were therefore not build with subject $x$. The OOB only calculates the error for the trees that have not been build with $x$, which is $\frac{1}{3} * 1000$ in that case.