How would one formally prove that the OOB error in random forest is unbiased? I have read this statement many times but have never come across a proof. I would like to try to produce one myself but I'm not even sure on what notation to use. Can anyone help me with this?
 A: I do not know if this is the final answer, but those things can't fit a comment. 
The statement that OOB errors are unbiased is often used, but I never saw a demonstration. After many searchings, I finally gave after reading carefully the well-known page of Breiman for RF Section: The out-of-bag (oob) error estimate. In case you did not noticed (as I missed for some time), the last proposition is the important one: This has proven to be unbiased in many tests. So, no sign of formal derivation.
More than that, it seems to be proved that for the case when you have more variables than instances this estimator is biased. See here. 
For in-the-bag error there is a formal derivation. The in-the-bag error is the bootstrap error and there is plenty of literature starting with "An Introduction to the Bootsrap, by Efron and Tibshirani". However the cleanest demonstration I saw is here.
If you want to start to find a proof, I think a good starting point is the comparison of this estimate with N-fold cross validation. In ESTL is stated that there is an identity in the limit, as the number of samples goes to infinity. 
A: Why do you expect the oob error to be unbiased? 


*

*There's (at least) 1 training case less available for the trees used in the surrogate forest compared to the "original" forest. I'd expect this to lead to a small pessimistic bias roughly comparable to leave-one-out cross-validation. 

*There are roughly $\frac{1}{e} \approx \frac{1}{3}$ of the number of trees of the "original" forest in the surrogate forest that is actually evaluated with the left-out case. Thus, I'd expect higher variance in the prediction, which will cause further pessimistic bias. 
Both thoughts are closely related to the learning curve of the classifier and application/data in question: the first to the average performance as function of training sample size and the second to the variance around this average curve. 
All in all, I'd expect you'll at most be able to show formally that oob is an unbiased estimator of the performance of random forests containing $\frac{1}{e} \approx \frac{1}{3}$ of the number of trees of the "original" forest, and being trained on $n - 1$ cases of the original training data. 
Note also that Breiman uses "unbiased" for out-of-bootstrap the same way as he uses it for cross validation, where we also have a (small) pessimistic bias. 
Coming from an experimental field, I'm OK with saying that both are practically unbiased as the bias is usually much less of a problem than the variance (you're probably not using random forests if you have the luxury of having plenty of cases).
